Is it worth moving this logic into it's own function to keep this lambda easier to read?

thought about but then decided against since it isn't that big.. I am happy either way, your call.

Is it worth validating that the hosts were actually removed?

you mean from the intermediate sets? or that added/removed were > 0 (i think they can be 0)?

ah, now i know what you meant

hmm, might be a bit messy

hmm, these should probably be ordered so that the merged update sees hosts in the same order it would have seen them if they were delivered immediately?

cc: @zuercher @mattklein123

maybe not that important and not worth the cost...

It's probably easier to debug I think if there is some determinism here. There is no major performance advantage of unordered here most likely.

to keep it ordered we'd have to keep two sets (added/removed) to check uniqueness (e.g.: that a host isn't added/removed twice) and we'd also have to keep two vectors (added/removed) to preserve the order..... or am I missing an ordered set data structure hidding somewhere? :-)

... "by default this is not configured and updates apply immediately.".

Won't this delay the first update after a long period of silence? Should we instead apply immediately in this case? I think we can then just keep track of the last time we applied and only add to a pending queue if < window length.

addressed in the latest commit

Nit: these intermediate vars can be const.

FWIW, I was arguing for just a deterministic ordering, e.g. using set vs. unordered_set in my earlier comment, rather than arrival ordering. But, I don't mind if we stick with this.

Nit: const auto& host here and below.

Where does added_seen and removed_seen get inserted into?

oops, good catch

What about sequences of ops in which a host is added, removed and added back again? I'm not sure if we have correctness here.

hmm, becomes trickier with ordering so we should probably avoid that. if we just kept the sets, we can handle cancellations (added/removed). we'd have to decide if want drop cancelled out ops (i say yes).

I see, you nuke it here. I'd suggest keeping the timer alive and just doing disable/enable, it probably doesn't matter, but one less wasted allocation/free.

it would be nice to avoid the allocation/free pair, but then we'd have to check if the timer is enabled or not by looking at the last update timestamp... at which point things become a bit more involved. Preferences?

On a related note, the logic to apply an update immediately if the last update happened within a merge window should probably also check if a timer exists (e.g. timer != nullptr). Otherwise, updates could lose their order.

I guess we can add a bool to track the timer's state

Should we also count non-coalesced updates? Or can we just infer this from total?

Not needed?

Nit: prefer using here.

I think a test that has add, remove, add for the same host would be interesting.

This hashes on the pointer value I think. Do we have a guarantee that two identical hosts will have the same pointer value from the caller of scheduleUpdate()?

yeah good point, we should track the host's address instead.

Do we want to take the latest value for host, since it might have a new health status etc? As this works today, if we do add(unhealthy), add(healthy), only the unhealthy status for the host is set, since insert just returns false the second time.

Again, as with add, remove, add, I think we would benefit from some more tests here.

yes, we want the latest value. and yep, will follow-up with comprehensive testing.

@htuch note that a health change does not get treated as an add/remove:

https://github.com/envoyproxy/envoy/blob/master/source/common/upstream/upstream_impl.cc#L902

That is, if (only) a host's health flipped you'd get called with no new added/removed hosts in which case we'd still do the right thing. Which is, calling postThreadLocalClusterUpdate() with empty vectors for hosts_added and hosts_removed.

Anyway, I'll back all of these claims with tests.

Sorry what does this comment mean? Is this just tracking the race condition? Is it worth the extra code for this? I think this should be incredibly rare but I agree it can happen.

It's for tracking two things:

a) did we not merge this update because we are out of a merge window? i found this stat useful while testing this out, because it tells you how often merging is not needed
b) did we had merged updates pending that we are cancelling (and delivering immediately)? also useful to know how often a merge window is cancelled before expiring.

I'd like to keep these, I think they are useful. Happy to clarify comments/names. Ideas?

OK makes sense. I would probably go with the stat name @htuch suggested and put the entirety of what you jus wrote in a comment here? I think that would make it clear.

Done.

Nit: s/cluser/cluster/

Nit: s/healthcheck/health check/

Kind of prefer out_of_merge_window for the stats names/vars to be clearer what's happening here. With recent stats optimizations happening, we can use longer names without any memory penalty.