Improve LB rebuild behavior when health status changes occur

[htuch]

Today, when health checks transition host status or new health status arrives in EDS (#2726), we do expensive (at least O(n^2)) rebuilds in various places of the host lists, healthy host lists, locality lists, subsets, WRR, etc.

This isn't great when we scale the number of endpoints per cluster, if we have short health check intervals or if we have short EDS intervals. This issue will track work on optimizing this behavior.

[htuch]

@alyssawilk @zuercher FYI, tracking issue.

[brian-pane]

We're seeing this update code using 80+% of the total CPU capacity on 32-core hosts with ~2000 upstream endpoints in a cluster. Are the O(n^2)-time operations happening just in one thread (and pushed out as thread-local copies to all the workers), or are they happening in all the workers? From the CPU metrics, I suspect it's the latter (all the workers).

[brian-pane]

For what it's worth, we're also using the subset load balancer with three keys, each with two possible values. Based on CPU profiles, Envoy::Config::Metadata::metadataValue is a large contributor to the total run time of the rebuild.

[mattklein123]

@brian-pane please discuss in #3790. Right now it's happening on every thread. There are various ways we can improve this situation, but I don't think reverting this change is in the cards. If this is causing major issues as I already said in the other issue, we can add an option to disable weighting support entirely.

[brian-pane]

@mattklein123 you lost me on the part about "reverting this change." Unless I'm missing something, #2874 isn't proposing to revert anything, but rather to improve the algorithmic efficiency of the current implementation.

[mattklein123]

Sorry, I was just saying that I don't want to revert this change, and would like to figure out solutions to roll forward.

[brian-pane]

Got it, thanks. I'm on the same page: fixing forward rather than rolling back.