Two Random Choices Beat One Careful One: The Load Balancer Mental Model Nobody Teaches

The problem

Picture a fleet of 100 identical workers behind a load balancer. You send requests uniformly at random — each request goes to a random worker, independent of the others. It sounds fair. It isn't.

If you send 100 requests to 100 workers this way, the most loaded worker doesn't get 1 request. On average, it gets around log(100) / log(log(100)) — roughly 4 to 5 requests — while plenty of workers sit idle. Send 10,000 requests to 10,000 workers and the busiest one gets over 9, not ~1. This isn't a bug in your random number generator. It's math, and it's called the "balls into bins" problem.

Most engineers have felt the symptom — a "perfectly balanced" random or round-robin-ish LB that still produces one hot node, one node pegged at 90% CPU while its siblings idle at 20% — without ever learning the mechanism. So they reach for the wrong fix: bigger instances, more replicas, a mysterious "just restart it" ritual. None of that touches the actual cause.

Why it happens

Uniform random assignment doesn't spread load evenly — it clusters, the same way random points in a room form clumps and empty patches instead of a neat grid. The formal result: if you throw n balls into n bins independently and uniformly at random, the maximum bin load is, with high probability, Θ(log n / log log n).

That's not linear in n, but it's not constant either — it grows, slowly but unboundedly, as your fleet scales. The more workers you add expecting things to smooth out, the more that log(n) term keeps producing a stubborn outlier. This is exactly why "just add more instances" often makes the imbalance more visible in absolute terms even as it helps in relative terms — the tail keeps growing with the fleet.

What to do about it

The fix has a name — the power of two choices (Azar, Broder, Karlin, Upfal, 1994; popularized for systems by Michael Mitzenmacher) — and it's absurdly cheap for how much it buys you.

Instead of picking one random worker, pick two random workers and send the request to whichever currently has less load. That's the entire algorithm. The result: the maximum load drops from Θ(log n / log log n) to Θ(log log n / log log log n) — an exponential improvement in the exponent. At n = 10,000, that's the difference between a worst node carrying ~9x the average and one carrying ~2-3x.

You've probably already used this without naming it:

• Envoy's P2C (power-of-two-choices) load balancer is a built-in policy, not something you write yourself.
• HAProxy's leastconn and AWS ALB's least-outstanding-requests algorithm are cousins of the same idea — they just skip the "pick two" sampling step and check global state directly, which works at small scale but gets expensive to coordinate globally at large scale (hence P2C's popularity: it needs no central coordinator).
• Consistent hashing ring hot spots — the classic complaint that one shard runs hot even with a "good" hash function — are the same balls-into-bins effect. The standard mitigation, virtual nodes (100-200 vnodes per physical node), works by turning one ball into many smaller, independently-placed balls, which flattens the same log(n) tail.

The one gotcha that bites people who implement this from scratch: power of two choices needs reasonably fresh load signal. If your "current load" metric is stale — cached for 30 seconds, propagated through a slow gossip protocol — every requester samples the same stale "least loaded" node and stampedes it. You've now built a synchronized herd instead of a load balancer. The fix is either querying live local queue depth at decision time (what Envoy does) or adding jitter/randomization to which two nodes get sampled, so staleness doesn't correlate across requesters.

Key takeaways

• Uniform random load balancing is not fair load balancing — balls-into-bins guarantees a growing max-load outlier as your fleet scales, Θ(log n / log log n).
• Sampling two random candidates and picking the lesser-loaded one collapses that outlier to Θ(log log n / log log log n) — two lookups instead of one, no central coordinator required.
• This is already built into Envoy, and it's the theoretical justification behind leastconn-style balancers you've probably deployed without reading the paper behind them.
• The failure mode of power-of-two-choices itself is stale load data causing correlated stampedes — check freshness before you trust the "least loaded" signal.