Smooth call pattern for weighted least_request load balancing

[zackhsi]

Provide a mechanism to distribute load in a non-bursty way across weighted hosts.

Description:

We use least_request load balancing to distribute load evenly across hosts. This is our preferred load balancing algorithm, and it works well when all the weights are set to 1. However, we "redline" our hosts to measure the peak throughput of a single machine by steadily increasing its load balancing weight until latencies rise to an unacceptable level.

When we adjust the weight of a host, envoy distributes requests by:

If any host in the cluster has a load balancing weight greater than 1, the load balancer shifts into a mode where it randomly picks a host and then uses that host <weight> times.

This leads to bursty requests which unrealistically stress the weighted host.

So the question is, how can we simultaneously enjoy:

• least_request load balancing
• unevenly weighted hosts
• smooth, non-bursty, traffic

Relevant Links:

https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/load_balancing#weighted-least-request

[mattklein123]

Duplicate of #3284. Let's track there.

[zackhsi]

Thanks!