At nightfall, thirty lanterns come on down the long street — thirty noodle stalls, thirty pots, thirty lines.

The old custom on this street was easy enough: walk in, pick a stall, sit down. The noodles are much the same everywhere; no one’s broth is meaningfully better than anyone else’s.

And so the same scene played out every evening. At the east end, three pots sat idle while their owners stood with folded arms watching the crowd drift by. At the west end, one stall had eleven people waiting, and the last of them stood there long enough for the broth in the pot to be changed twice. Nobody did anything wrong — everyone simply “picked a stall.” But when thirty stalls get picked at random a few hundred times, one of them always gets unlucky and gets picked far too often. On average each stall should have two or three people waiting. But the longest line is never the average line. And the longest line is the one people complain about, and the one people turn around and walk away from.

Old Chen, who managed the street, tried a fix. He put a board up at the entrance and sent a boy to walk the whole street every so often, counting the lines and chalking the numbers up. Anyone walking in could glance at the board and head straight for the emptiest stall.

One night of that was worse. The board said “stall seven is empty,” and every single person who entered the street for the next stretch of time walked to stall seven — and by the time they got there, twenty people were waiting, while the board still read, neatly, empty. The board was out of date from the moment it was written, and stale news walked everyone into the same hole together. Chen thought about sending the boy around more often, but the street was long and the boy had only two legs.

It was the old woman boiling noodles who eventually said, off-handedly:

“When you come in off the street, don’t ask anyone, don’t look at the board. Just glance at two stalls, sit at the one with fewer people. That’s it.”

Chen thought this was hopelessly sloppy. Two stalls out of thirty, and total ignorance about the other twenty-eight — how was that any better than picking blind?

He tried it for a night anyway.

The result startled him. The longest line dropped from eleven or twelve people to three or four. Not a little better. It collapsed.

The reason isn’t hard. Under the old custom, a stall got crowded by bad luck stacking on bad luck. Now, every arriving customer forced two stalls into a head-to-head comparison, and the longer a stall’s line, the smaller its chance of winning that comparison. Long lines kept themselves out. And the bigger the street, the wider the gap: grow from thirty stalls to three hundred, and the worst line under “pick one at random” grows with it, while the worst line under “glance at two” barely moves.

Chen, greedy now, asked: what about three stalls? Five?

They tried. Three was better than two — but only slightly, nothing like the leap from one to two. And every extra glance meant a few more steps and a little more delay. By the fifth stall, the walking had eaten the entire advantage.

The old woman’s rule had one more quiet virtue: the board at the entrance could come down. No boy running errands, no stale ledger, no stampede. Each customer asked two stalls, and asked about right now.

— By this point you’ve probably recognized it: this is the power of two random choices.

What this is

Throw n balls into n bins uniformly at random, and the fullest bin ends up with roughly Θ(log n / log log n) balls — about a dozen when n is ten thousand, against an average of one. That is the fate of pure random load balancing: a beautiful mean and an ugly tail.

In 1994 Azar, Broder, Karlin and Upfal proved something counterintuitive: if each ball instead samples d bins at random and goes into the less loaded one, the fullest bin drops to ln ln n / ln d + Θ(1). Look closely at what going from d = 1 to d = 2 does — log n / log log n collapses to log log n, an exponential improvement. Going from d = 2 to d = 3 only changes ln d from ln 2 to ln 3, a constant factor. Hence the usual one-line summary: the second sample buys almost everything; the third buys almost nothing.

Why does “one more glance” carry so much weight? Because it converts independent bad luck into competition with feedback. For a backend to accumulate a long queue, it has to keep winning pairwise comparisons — and every extra request it holds makes winning the next one less likely.

In practice this is P2C (power of two choices) load balancing. Envoy’s LEAST_REQUEST policy defaults to choice_count: 2 — it does not scan every endpoint looking for the idlest one, it picks two at random and compares. NGINX’s random two least_conn and HAProxy’s balance random(2) are the same trick.

Its real rival isn’t random but the “globally optimal” join-shortest-queue: scan all n backends and take the idlest. With a single dispatcher and perfectly fresh information, JSQ genuinely wins. Reality supplies two killers — O(n) sampling cost, and a load view that is inevitably stale. Several load balancer replicas sharing a metrics snapshot from a few seconds ago will all decide the same backend is idlest, all pile onto it, flatten it, and then pile onto the next one together. Mitzenmacher’s classic result: once information is stale, JSQ performs worse than pure random, while P2C — using only two fresh samples and never chasing the optimum — is remarkably robust to staleness and jitter.

That is what makes it worth remembering: an O(1), stateless, uncoordinated local decision that buys you near-optimal tail behaviour. When you’re tuning Envoy, writing a client-side balancer, or picking a policy for a homegrown dispatcher, the default answer is usually “sample two at random, take the less loaded one.”

Metaphor mapping

• The thirty noodle stalls → n backends / endpoints
• The line in front of each stall → each backend’s queue depth (outstanding requests)
• Customers walking onto the street → arriving requests
• “Just pick a stall” → pure random load balancing, d = 1
• The longest line → max load, the source of p99 tail latency
• Two or three on average vs eleven at the worst stall → fine mean, terrible tail
• The board at the entrance → a centralized global load view (periodically reported metrics)
• “Out of date from the moment it was written” → staleness, the inherent lag in load information
• Everyone rushing stall seven at once → herd behavior caused by stale information
• The boy walking the whole street → join-shortest-queue, O(n) sampling cost
• “Glance at two, sit at the shorter one” → power of two choices, d = 2
• Longer lines being less likely to win a comparison → negative feedback, self-balancing load
• Thirty stalls to three hundred, worst line barely moving → max load grows only as log log n
• Three stalls being only slightly better → d appears only inside ln d, sharply diminishing returns
• Extra glances costing extra steps → probe cost
• The board coming down → no central state, no coordination, purely local decisions