Least Outstanding Requests

Round robin distributes requests evenly. It does not distribute load evenly, because requests are not equal and neither are backends. On a fleet of 60 mixed-generation instances where request cost varies twentyfold, an instance handed an expensive request is still given its next request on schedule, so work accumulates behind it while a neighbour sits idle. The resulting p99 is made almost entirely of requests queued behind something expensive.

Least outstanding requests measures the one quantity that reflects both effects at once: in-flight count is a live signal of how busy a backend actually is, with no configuration describing instance speed or request cost.

Why it matters

The improvement at the tail is larger than intuition suggests, and queueing theory says why. Routing to the shortest queue approximates a single shared queue, and one queue has dramatically better tail latency than N independent queues at the same utilisation, because no server idles while work waits elsewhere. The effect grows with request-cost variance, which is exactly the regime where tails are a problem.

It is also self-correcting during faults. A backend that becomes slow holds its requests longer, so its in-flight count rises and it is given less work - a damping loop that needs no health check and no ejection decision.

Implementation patterns

• Use the power-of-two-choices form. Envoy's LEAST_REQUEST policy samples two hosts at random and picks the one with fewer active requests, which captures most of the benefit of a full scan at constant cost and avoids the herding that an exact global minimum can cause.
• Pair it with slow start. A newly added host has zero in-flight requests and will be handed a burst while its caches and pools are cold. Envoy's slow-start mode ramps its weight over a configured window; enabling least-request without it is a common way to make a deployment worse.
• Count the right unit. For long-lived streams and WebSockets, in-flight connections are the load; for request-response traffic, in-flight requests.
• Keep it client-side where you can. A balancer in each caller (a sidecar or a smart client) sees its own in-flight counts and avoids a central component in the path, at the cost of each caller seeing only its own view.
• Bound per-backend concurrency as well. Shortest-queue routing distributes load; it does not cap it, and a saturated fleet still needs admission control.

Industry example

The algorithm's modern popularity comes from service meshes. Envoy, open-sourced by Lyft in 2016, ships LEAST_REQUEST as a first-class policy with the two-choices sampling and slow-start support, and gRPC's own load-balancing documentation describes equivalent pick-first and weighted strategies for client-side balancing. The underlying result is older: the power-of-two-choices analysis from the mid-1990s showed that sampling two queues and choosing the shorter gives an exponential improvement over random choice, while sampling all of them adds little, which is why real implementations sample two.

Failure scenarios

• Cold-start overload. A new or restarted host absorbs a burst, becomes slow, and then correctly stops receiving traffic - after serving a wave of slow requests.
• Hung requests poison the signal. A backend whose requests never complete shows a permanently high in-flight count and is quietly removed from rotation, or the reverse: a backend that fails instantly shows zero and attracts everything.
• Fast-failure attraction. An instance returning errors in microseconds has the lowest in-flight count on the fleet, so it receives the most traffic. Error-rate-based ejection is the necessary companion.
• Multiplexed connections at L4, where in-flight requests are invisible and the algorithm cannot be applied at all.
• Heterogeneous fleets by design - a canary, a shadow deployment, hosts holding different shards - where the algorithm finds and acts on a difference you created deliberately.

Trade-offs

Least-request needs per-request visibility, which rules out plain L4 balancing, and it needs state per backend in every balancer. It is marginally more expensive than round robin and considerably more responsive. What it gives up is predictability: traffic distribution becomes a function of live behaviour, so a capacity plan cannot assume an even split, and debugging "why did this host get three times the traffic" requires the in-flight series rather than a configuration file. Round robin's compensating virtue is that it is trivially explicable.

When not to use it

For identical backends serving uniform requests, round robin is cheaper, more predictable and equally good - the extra signal has nothing to find. Prefer consistent hashing instead when per-key cache locality dominates performance, since hit rate beats queue fairness, with bounded load to stop a hot key overwhelming one host. And avoid it without a slow-start ramp on any fleet that deploys frequently, because the cold-start burst is a reliable way to turn a routine rollout into a latency incident.

Interview question

Q: You switch a 40-host fleet from round robin to least-outstanding-requests and p99 improves, but every deployment now produces a two-minute spike of slow requests. What is happening and how do you fix it without going back?

What a strong answer covers: identifying the cold-start burst - a fresh host has zero in-flight requests so it attracts traffic while its caches, JIT and connection pools are cold; the fix as a slow-start ramp weighting the host up over a window, plus readiness checks that gate on warmed state rather than process liveness; the related failure of fast-failing hosts attracting traffic and the need for error-based ejection; and the general point that in-flight count is a load proxy that breaks when requests do not complete normally.

Quick check

Quiz: Why does routing to the shortest queue improve tail latency so much? It approximates one shared queue, so no backend idles while work waits elsewhere - and a single queue has far better tail behaviour than N independent ones at the same utilisation.

Flashcard: What must accompany least-request on a frequently deployed fleet? A slow-start ramp - a new host has zero in-flight requests and will otherwise absorb a burst while cold.