Symptom

You have 100 backends and a load balancer hashing request IDs to pick one. Expected load per backend is exactly 1%, and you have checked the hash is good.

Then the dashboard shows one backend at three times the mean. You check for a hot key: none. You check the hash: uniform. You add more backends and the imbalance persists. Somebody suggests the hash function is bad after all, and a week goes into replacing it, and the imbalance does not change.

The hash function was never the problem. Uniform random assignment produces imbalance as a matter of course, and the size of that imbalance is a theorem. Linearity of expectation (T007) tells you the mean load per bin and says nothing about the maximum, which is the number that determines whether a backend falls over, what your p99 looks like, and how much headroom you must provision.

The good news is the second half of this post, and it is one of the highest return-on-complexity results in systems engineering: a change that costs one extra probe per request turns an exponential-ish gap into a doubly logarithmic one.

Statement

Single choice. Throw $n$ balls independently and uniformly at random into $n$ bins. With high probability, the maximum load is

$$\Theta\!\left(\frac{\log n}{\log \log n}\right).$$

Two choices (Azar, Broder, Karlin, Upfal). Throw $n$ balls into $n$ bins, but for each ball sample $d \ge 2$ bins uniformly and place it in the least loaded of the $d$. With high probability, the maximum load is

$$\frac{\ln \ln n}{\ln d} + \Theta(1).$$

Read those two together, because the contrast is the entire point:

  • Going from one choice to two takes you from $\log n/\log\log n$ to $\log\log n$ — an exponential improvement.
  • Going from two choices to three takes you from $\log_2 \ln n$ to $\log_3 \ln n$ — a constant factor.

The first extra probe buys almost everything; the rest buy almost nothing. That asymmetry is why “the power of two choices” is the name.

Concretely, at $n = 10^6$: one choice gives a max load around 10; two choices gives $\ln\ln(10^6)/\ln 2 \approx 3.8$, so about 4. Take $n$ up to $10^9$ and the one-choice figure keeps climbing while the two-choice figure moves to 4.4. Doubly logarithmic growth is, for practical purposes, constant.

Argument

Why one choice is unbalanced. The load of a particular bin is $\mathrm{Binomial}(n, 1/n)$, mean 1. The probability it has at least $k$ balls is at most $\binom{n}{k}(1/n)^k \le 1/k!$. Setting this to $1/n$ and using Stirling, $k! \approx (k/e)^k$, gives $k \log(k/e) \approx \log n$, so $k = \Theta(\log n/\log\log n)$. Now union bound (T008’s standard partner) over all $n$ bins: with probability $1 - o(1)$ no bin exceeds this, and a matching argument shows some bin reaches it.

So the max is not $O(1)$, and no amount of hash quality changes that. The imbalance is a property of randomness, not of your hash.

Why two choices is doubly logarithmic — the layered induction. This is the argument worth carrying around. Let $\beta_k$ be the fraction of bins with load at least $k$. A ball lands in a bin of load $\ge k$ only if both its sampled bins already have load $\ge k$, which happens with probability $\beta_k^2$. Roughly, then,

$$\beta_{k+1} \lesssim \beta_k^2.$$

Start from $\beta_2 \le 1/2$ or so and iterate: the exponent squares each time, so $\beta_{k} \approx 2^{-2^{k}}$. The height at which $\beta_k$ drops below $1/n$ — meaning no bin at all is that tall — is $k \approx \log_2\log_2 n$. The squaring is the whole mechanism, and $d$ choices give $\beta_{k+1} \approx \beta_k^d$, which changes the base of the outer logarithm and nothing else. That is exactly why the third choice is nearly worthless.

Why this is more than a curiosity. The single-choice result is what makes hash tables have $\Theta(\log n/\log\log n)$ worst-case chains despite $O(1)$ expected chains — the fact quoted in T007 as the reason expectation does not determine your p99. The two-choice result then repairs it: cuckoo hashing gives each key two candidate positions, evicting and relocating on collision, and achieves worst-case $O(1)$ lookup with high space efficiency. Same theorem, used as a data-structure design.

Where it lands in real systems. NGINX, HAProxy, and Envoy all implement “power of two random choices” load balancing (Envoy calls it LEAST_REQUEST with a default choice count of 2); it is the default in several service meshes. The reason it beats exact least-loaded in distributed settings is the topic of the next section.

Forbids

Perfect balance from uniform random assignment. Expect $\Theta(\log n/\log\log n)$ imbalance and provision for it. A backend at 3x the mean with 100 backends is unremarkable, and chasing it as a bug wastes weeks.

Fixing single-choice imbalance by improving the hash. A perfectly uniform hash is the model. If the hash is uniform and you still see imbalance, the theorem says you will, and only changing the assignment algorithm helps.

Meaningful gains past a few choices. $d = 2$ to $d = 3$ is a constant factor in the logarithm; going to $d = 10$ costs 10 probes for essentially nothing. If someone proposes probing more backends, the theorem prices it.

Provisioning from the mean. With $m$ tasks over $n$ machines you must size for the max, not the mean. Sizing from the mean is how capacity plans fail while being arithmetically correct.

Does not forbid

It does not say randomization is required, and this is worth saying because deterministic schemes are often better. Round-robin achieves perfect balance for identical requests with no probing at all. Consistent hashing keeps a key on the same backend, which is what makes caches work — and bounded-load consistent hashing (Mirrokni, Thorup, Zadimoghaddam, used by Vimeo) adds a load cap to consistent hashing and gets both properties. Randomization is the answer when you have no coordination, not always.

It does not say two choices beats exact least-loaded. Exact least-loaded is better in the model. The reason nobody uses it in a distributed load balancer is the herd effect: with many independent balancers, all of them see the same “least loaded” backend from stale state and stampede it, which is worse than either. Two random choices is robust precisely because it is not coordinated, and this is a case where a theoretically weaker algorithm wins on a property the theorem does not model.

It does not hold when the balls are not exchangeable. Requests have wildly different costs; a single expensive query outweighs a thousand cheap ones. The theorem counts balls. If your load is heavy-tailed in cost, balancing counts balances the wrong thing, and least-outstanding-request or a cost-weighted scheme is what you want. This is the same limitation as T008’s on heavy tails.

It does not survive stale information gracefully. The analysis assumes the loads you sample are current. With delayed load reports, two choices degrades, and Mitzenmacher’s later work on “the power of two choices with stale information” shows the improvement can disappear entirely. Sampling at the moment of the decision matters.

It does not apply when $m \gg n$. With $m$ balls into $n$ bins for large $m$, single choice gives $m/n + \Theta(\sqrt{(m\log n)/n})$ — the deviation becomes small relative to the mean, so imbalance stops mattering. Two choices gives $m/n + \ln\ln n$, where the gap above the mean is independent of $m$. That is the sharper statement for a long-running system, and it is the one to quote for a load balancer that runs for months.

Boundary

  • The dynamic setting. Real systems have arrivals and departures, not a fixed throw. Mitzenmacher’s fluid-limit analysis shows the queue-length distribution decays doubly exponentially with two choices and only exponentially with one, which is the same contrast in the steady state.
  • Memory helps too. Remembering the least loaded bin from the previous round (“one choice plus memory”) achieves similar gains to two choices, which suggests the real resource is information rather than probes.
  • The $(1+\beta)$-choice variant. Using two choices only a $\beta$ fraction of the time still gets you most of the benefit, which matters when probing is expensive.
  • Cuckoo hashing and beyond. Two hash functions with relocation give worst-case $O(1)$ lookups; the load threshold where insertion starts failing (0.5 for two functions, about 0.91 for three) is itself a sharp phase transition, and a nice example of a threshold phenomenon in a data structure.
  • Connection to consistent hashing. T072’s rebalancing behaviour depends on load distribution, and this is the result underneath it: how much a node can exceed its share is what determines whether removing a node cascades.
  • Why virtual nodes exist. Consistent hashing with one point per node gives a node’s share of the ring as a spacing between uniform points, whose variance is large — the same single-choice imbalance, in a different coordinate. Giving each node a hundred or more virtual points averages a hundred independent spacings and shrinks the deviation by $\sqrt{100}$. Dynamo, Cassandra, and Riak all do this, and the number of virtual nodes is a variance knob rather than an implementation detail.
  • The lower bound is what makes the result interesting. $\Omega(\log\log n)$ holds for any $d$-choice scheme, so two choices is not merely good, it is within a constant of optimal for this class. Knowing that stops the search for a cleverer probing rule.