A load balancer would love to know everything.

It would like the exact queue length on every server, the service time of every request already running, the cache state behind every connection, the next failure, and the shape of the next burst.

It does not get that.

So a practical load balancer lives between two compromises:

pick one server blindly
or
maintain a global picture that may already be old

The power-of-two-choices trick lives in the middle. Pick two servers at random. Send the request to the less-loaded of the two.

That is it. One extra random probe. One comparison.

The surprise is not that two choices are better than one. The surprise is how much better.

The Tail Squares Itself

Start with the cleanest model: throw \(m\) unit balls into \(n\) bins.

If every ball picks one bin uniformly at random, the average load is \(m/n\), but the fullest bin is not close to the average. In the classical case \(m=n\), the maximum load is about

\[\frac{\log n}{\log \log n}\]

with high probability.

Now let each ball sample \(d\) bins and choose the least loaded among them. Azar, Broder, Karlin, and Upfal’s balanced-allocation theorem shows the dramatic change: for \(m=n\) and fixed \(d \ge 2\), the maximum load becomes

\[\frac{\log \log n}{\log d} + O(1)\]

with high probability.1

That is not a small constant-factor cleanup. It changes the scale from log n / log log n to log log n.

The hand-wavy proof sketch is worth keeping in your head. To make a bin reach height \(k+1\) under two choices, a ball must see two candidate bins that are already at height at least \(k\). If the fraction of bins at height \(k\) is \(x_k\), the next layer is roughly proportional to \(x_k^2\). The tail keeps squaring itself. With \(d\) choices it gets raised to the \(d\)th power.

This is why the second choice matters so much, and the fifth choice often matters much less. The first comparison changes the tail’s arithmetic.

A Small Dispatch Desk

The lab below allocates unit jobs to servers. It compares:

  1. one random server;
  2. two random servers, choose the shorter visible queue;
  3. configurable \(d\) random servers;
  4. a least-loaded snapshot over the whole fleet.

The Report interval knob is the systems caveat. With interval 1, every decision sees fresh loads. With larger intervals, the dispatcher compares stale snapshots. This is not meant to be a production load-balancer model. It is a microscope for the allocation tail.

The audit is generated by the same JavaScript as the lab. It checks parameter sanitation, job conservation, histogram accounting, percentile ordering, determinism, one-choice equivalence, default two-choice improvement, fresh least-loaded behavior, stale-snapshot validity, high-d behavior, asymptotic yardstick positivity, and a 192-case grid over server counts, load levels, choice counts, report intervals, and seeds.

Deterministic allocation model. Jobs are unit work, servers are identical, and queues do not drain during the allocation window. The point is the placement tail, not service-time realism.

At the default setting, 512 jobs are placed on 256 servers. One random choice hits a maximum load of 8 and a p99 load of 6. Two choices hit a maximum load of 4 and a p99 load of 3. The coefficient of variation falls from about 0.677 to 0.388.

The fresh least-loaded snapshot reaches maximum load 2, which is what you would hope for in a perfectly informed centralized allocator at exactly two jobs per server. But now raise Report interval. A stale global minimum can become a trap: many jobs chase the same old “empty” server before the snapshot updates. That is why the practical lesson is not “always find the global minimum.” It is:

fresh local comparisons beat stale global certainty

Queueing Makes It Less Toy, Not Less True

The balls-into-bins theorem has no service times. Real servers drain queues, requests have different costs, and arrivals are not a polite fixed batch.

Mitzenmacher studied the dynamic version: jobs arrive as a Poisson stream, servers process work, and each arrival samples a small number of queues. The same qualitative message survives: a small number of random choices gives large improvements in delay and queue length compared with one random choice.2

This is often called the supermarket model. Vvedenskaya, Dobrushin, and Karpelevich analyzed the mean-field behavior of the join-the-shortest-of-two queues process, where the queue-length tail decays extremely quickly in the limit.3 Mitzenmacher, Richa, and Sitaraman’s survey puts the static and dynamic stories under the same umbrella: balanced allocations are a broad family of “sample a little, compare a little” algorithms.4

That is the clean theory.

The messy systems version adds:

  • delayed health and queue reports;
  • heterogeneous machines;
  • connection stickiness;
  • cache warmth;
  • request sizes you do not know yet;
  • retries and hedges that are already extra traffic;
  • a control plane that cannot afford to update every edge on every request.

So the theorem is not a production proof. It is a warning against a common mistake: treating load balancing as if the choices were “blind randomness” or “perfect global state.” There is a third option. Sample a tiny random subset and compare inside it.

Incomplete Views Can Be Better Views

NGINX’s discussion of power-of-two choices frames this as a way to work with an incomplete and delayed view of upstream load: checking two random servers avoids the need to constantly maintain a precise global ordering.5 HAProxy has also exposed random load-balancing strategies that sample a small number of servers and select by a load metric, precisely because global least-connection views can be more expensive and more synchronization-sensitive than they look.6

The lab’s stale-snapshot knob shows the small version of the problem. If a central allocator sees a snapshot that is refreshed every 64 jobs, the server that was least-loaded at the beginning of the window may receive a pile of work before anyone admits the old fact is old. A randomized local comparison spreads the error around. It does not make stale information correct; it limits how many decisions can be poisoned by the same stale winner.

This is the quiet systems intuition behind the theorem:

randomness is not only for fairness
it is also for decorrelation

When every client follows the same stale global signal, they herd. When each client samples a small independent pair, the system gets many small mistakes instead of one synchronized mistake.

Why Two Is Usually the Interesting Number

The theorem says more choices help:

\[\frac{\log \log n}{\log d}.\]

Going from one to two changes the scale. Going from two to four divides the constant by another factor of two in the clean asymptotic expression. That can matter, but it also costs more probes, more load reads, more branch decisions, and more sensitivity to stale load metrics. Beyond a point, the extra choice is trying to buy perfection from a measurement system that may not be perfect.

This is why “power of two” became the slogan. The second probe is the nonlinear one.

I like the rule in this form:

one random choice ignores evidence
all choices overpays for evidence
two choices buys the part of evidence with the steepest return

That sentence is not a replacement for benchmarking your load balancer. It is a good default suspicion. If one random pick is leaving hot spots, ask whether you need a global scheduler, or whether you just need one more random door.

  1. Yossi Azar, Andrei Broder, Anna Karlin, and Eli Upfal, “Balanced Allocations”, SIAM Journal on Computing 29(1), 1999. SIAM record: https://epubs.siam.org/doi/10.1137/S0097539795288490. The classic result is the drop from about \(\log n/\log\log n\) to \(\log\log n/\log d + O(1)\) maximum load for \(d \ge 2\) choices. ↩

  2. Michael Mitzenmacher, “The Power of Two Choices in Randomized Load Balancing”, IEEE Transactions on Parallel and Distributed Systems 12(10), 2001. ↩

  3. Nikita D. Vvedenskaya, Roland L. Dobrushin, and Fridrikh I. Karpelevich, “Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach,” Problems of Information Transmission 32(1), 1996. ↩

  4. Michael Mitzenmacher, Andrea W. Richa, and Ramesh Sitaraman, “The Power of Two Random Choices: A Survey of Techniques and Results”, in Handbook of Randomized Computing, 2001. ↩

  5. F5 NGINX, “NGINX and the Power of Two Choices Load-Balancing Algorithm”, 2018. ↩

  6. HAProxy Technologies, “Power of Two Random Choices”, 2019. ↩