A service is balanced across 60 backend instances of mixed generations. Request cost varies by a factor of 20 and the slowest instances are roughly 2x slower than the fastest. Round robin gives a p99 of 1.8 s against a p50 of 90 ms. Which algorithm should the balancer use?
Show the full answer Hide the answer
The deciding property
Requests differ in cost and instances differ in speed, so equal request counts produce unequal queues. Round robin equalises the thing that does not matter. An instance that receives a 20x-cost request is still handed its next request on schedule, so work piles up behind it while a neighbour sits idle, and the tail is made of requests queued behind an expensive one.
Least outstanding requests measures the only quantity that reflects both effects at once. In-flight count is a live measure of how busy an instance actually is, so a slow instance or one with an expensive request in progress stops receiving new work until it catches up. No configuration describes instance speed or request cost; the signal is observed.
Why it wins here, mechanically
Queueing theory gives the reason this matters so much at the tail. Routing to the shortest queue converts many short independent queues into something close to one shared queue, and a single queue has dramatically better tail latency than N independent queues at the same utilisation, because no server idles while work waits elsewhere. In practice Envoy's LEAST_REQUEST policy samples two hosts at random and picks the one with fewer active requests - the power-of-two-choices result, which captures most of the benefit of a full scan at constant cost.
Why the other options fail
- "Round robin with health checks." Health checks remove dead instances, not slow ones. This is the configuration in the question: healthy, slow and still receiving its full share.
- "Consistent hashing on the request key." The right answer to a different problem - cache locality, session affinity, hot-key isolation. Here it makes the tail worse, because an expensive key is pinned to one instance and every request for it queues behind the last one.
- "Weighted round robin with weights from instance size." It handles the hardware half and not the request half, and the weights are a static guess that must be maintained as instance types change. A static weight cannot know that an instance is currently busy.
What would flip the decision
| If this changes | Choose | Because |
|---|---|---|
| requests are uniform and instances identical | round robin | nothing for the extra signal to find; simpler is better |
| responses are long-lived streams or WebSockets | least outstanding requests, measured on connections | connection count is the load, and round robin pins imbalance for the connection's lifetime |
| a per-key cache dominates performance | consistent hashing, with bounded load | hit rate beats queue fairness, and the bound stops hot keys overwhelming one host |
| the balancer is L4 and cannot see requests | round robin plus outlier ejection | in-flight request count is not observable at L4 |
When this is the wrong answer
Least outstanding requests needs the balancer to see request boundaries, which rules it out for plain L4 balancing of multiplexed connections. It also behaves badly with a slow-start problem: a freshly added instance has zero outstanding requests, so it receives a burst of traffic while its caches and connection pools are cold, and it promptly becomes the slow instance. Envoy's slow-start mode and similar ramping features exist for that reason, and enabling the algorithm without one is a common way to make a deploy worse. For a fleet of identical instances serving uniform requests, round robin is cheaper, more predictable and perfectly adequate.