01Why random dispatch fails quietly
You have sixty-four replicas of a model behind a load balancer. The simplest correct thing to do with an incoming request is to send it to one of them at random. It needs no coordination, no health state, no shared counter, and it is perfectly fair in expectation: over a long run every replica gets the same number of requests.
Fair in expectation is not the same as fair at any moment, and the gap between those two is where your p99 lives. Randomness clumps. Some replicas draw more than their share, and nothing in the scheme ever notices or corrects it — the next request is dispatched with no memory of the last. The imbalance is not a transient that settles; it is the steady state.
The useful way to measure this is not the busiest replica's absolute queue, which obviously grows with traffic, but how far ahead of the average it runs. If that excess were a constant, you could provision for it once. It is not.
02The measurement
Hand m requests to n replicas, one at a time, each going to a uniformly random replica. Then ask how much work the busiest replica is holding, relative to
| Requests per replica | Look at 1 | Look at 2 | Look at 4 |
|---|---|---|---|
| 1 | +3.12 | +1.63 | +1.00 |
| 10 | +8.61 | +1.93 | +1.00 |
| 100 | +25.89 | +1.94 | +1.01 |
| 500 | +57.16 | +1.87 | +1.00 |
| 2,000 | +112.45 | +1.93 | +1.00 |
Excess work at the busiest replica, over the fleet average. Lower is better.
Read the two bold numbers against each other. Under random dispatch the busiest replica ends up 112 requests ahead of average. Change one thing — look at two replicas and take the shorter queue — and it ends up 1.93 ahead. Same traffic, same fleet, same randomness.
The column shapes matter more than any single cell. The first column climbs and keeps climbing. The second is flat: 1.63, 1.93, 1.94, 1.87, 1.93, across traffic spanning three orders of magnitude. That is the whole result.
Why one extra look changes the shape
With one choice, a replica gets unlucky when it is picked more often than average, and nothing resists that. With two, a replica only grows if it is picked and is the shorter of the two — so the taller it gets, the harder it is to grow further. The scheme acquires negative feedback it did not have before. That is why the change is not “better constants”: it moves the imbalance from something that accumulates to something that is actively pushed back down.
03What it does to latency
Queue length is a proxy. What a user feels is waiting. The lab runs the fleet as an actual queueing system: requests arrive at some offered load, each replica works through its own backlog, and service times are lognormal — because real generations are, a median request and a long one differing by a lot.
Start on look at 1 at 95% load. The skyline is jagged: a few replicas are buried while others idle, and the 1% of requests unlucky enough to land on a buried one wait a long time. Now press look at 2. The skyline flattens, and the tail does something more dramatic than the median:
| Offered load | Look at 1 | Look at 2 | Look at 4 | 1→2 | 2→4 |
|---|---|---|---|---|---|
| 50% | 15.8 | 3.2 | 0.9 | 5.0× | 3.4× |
| 70% | 29.0 | 4.5 | 1.5 | 6.5× | 2.9× |
| 85% | 48.7 | 5.8 | 2.2 | 8.3× | 2.7× |
| 95% | 153.9 | 8.3 | 3.7 | 18.4× | 2.3× |
p99 queue wait, in units of a median request's service time. 64 replicas.
Two things to take from that table. The benefit grows with load — exactly when you need it, at 95% utilisation, random dispatch is at its worst and two choices is at its most valuable. And the returns die immediately after the first extra probe: 18.4× for the first, 2.3× for the second. Looking at all sixty-four replicas would be an exact least-loaded policy, and it would barely beat looking at two, while requiring you to know the state of the entire fleet on every single request.
That last point is the engineering one
“Least loaded” sounds obviously better than “two at random”, and it is — by a margin so small it rarely justifies what it costs. Exact least-loaded needs global state: a consistent view of every replica's depth at dispatch time, which means either a central bottleneck or a shared store you now have to keep fresh and correct. Two choices needs two numbers, fetched from two machines, with no coordination between them and no consequence if one is slightly stale. You pay almost nothing and capture almost all of it.
Does this survive real complications?
Stale load information. Mild staleness is tolerable; severe staleness inverts the scheme, because everyone discovers the same idle replica at the same moment and stampedes it. If your signal is seconds old, add jitter or use in-flight counts the dispatcher owns locally rather than numbers the replicas report.
Multiple dispatchers. Independent load balancers each probing two replicas behave roughly like one that probes two, as long as they probe independently. Shared caches of “who looked idle recently” are what break it.
Heterogeneous replicas. If machines differ in speed, compare estimated completion time rather than queue depth, or the fast replicas will be systematically underused.
Cache affinity. This is the real tension for model serving. Routing by prefix-cache locality and routing by load pull in opposite directions, and the right answer is usually to probe a small set of cache-eligible replicas and take the least loaded among those — two choices applied inside the affinity constraint rather than instead of it.
04Recap
- Random dispatch is fair in expectation and badly unfair at any instant, and nothing in it corrects the difference.
- Its imbalance grows with traffic — the busiest of 100 replicas ran 112 requests ahead of average in the heaviest case measured.
- Probing two and taking the shorter queue pins that excess near 1.9, flat across three orders of magnitude of traffic.
- At p99 and 95% load that is 18×, and the benefit grows with load rather than shrinking.
- The second extra probe buys 2.3×; exact least-loaded buys little more than two, at the cost of global state.
- So probe two. It is the rare change that is nearly free, nearly optimal, and needs no coordination at all.
Most tail-latency work is a search for the one slow component. This is the other kind: no component is slow, and the latency is manufactured by the dispatch rule itself. The fix is not a faster machine or another replica — adding replicas does not help, because the skew scales with the fleet. It is one extra question, asked before you commit.
Sources, and what is mine
The result is the “power of two choices”, from the balanced-allocations line of work (Azar, Broder, Karlin & Upfal; and Mitzenmacher's thesis on randomized load balancing) · The Memory Wall and The Speculation Ceiling, on what each replica is doing while it waits
What I could and could not verify. Journals and arXiv were unreachable from where this was written, so the attribution above is from memory and is a pointer to read rather than a claim about what those papers state. I have not checked my framing or terminology against them, and I quote no figure from them. The asymptotic forms usually given — roughly log n / log log n for one choice against log log n / log d for d choices — are stated nowhere in the post above for that reason.
Every number here is from the simulation on this page. The static table is 100 replicas averaged over 200 runs at a fixed seed; the latency table is a discrete-event queueing simulation of 64 replicas with Poisson arrivals and lognormal service times, discarding the first 20% as warm-up. The lab re-runs that simulation in your browser, so the figures in the prose are the figures the page produces. I checked the simulator against the one case with an obvious right answer first: at an offered load above capacity the queues must diverge, and an early version of this post nearly shipped with a table showing two choices barely helping, because I had scaled arrivals by the lognormal's median instead of its mean and was quietly running every scenario at 105% load.
And it is a model. One dispatcher, instant and accurate load readings, identical replicas, no cache affinity, no retries, no request cancellation. Each of those matters in a real fleet and the deeper note in §03 says which way. The claim being made is about the shape of the two policies — one imbalance that accumulates, one that does not — and that shape is what survives the complications.