Load Balancing and the Power of Two Choices

Why sampling two servers and taking the shorter queue is exponentially better than sampling one, and why least-outstanding-requests beats round robin for variable work.

AI SystemsAdvanced⏱ 1 hour7 min readload balancingballs into binspower of two choicesround robinleast loaded

1 problem →

AssumesQueueing and the Utilisation Wall · Concentration Inequalities

One choice

TheoremMaximum load under uniform random assignment

Throw $n$ balls independently and uniformly into $n$ bins. Then with probability tending to $1$ , the maximum load is

\bigl(1+o(1)\bigr)\,\frac{\ln n}{\ln \ln n} .

Assumptions

The matching lower bound is a second-moment argument that we do not reproduce; it is the harder half and is given in the cited literature. The upper bound is proved below, which is the direction a system designer needs — it says the imbalance is no worse than this.

PropositionA log n / log log n upper bound for one choice

With $n$ balls in $n$ bins, for $k \ge 1$ ,

\Pr[\text{some bin has} \ge k \text{ balls}] \;\le\; \frac{n}{k!} .

Consequently, taking $k = \lceil e\ln n/\ln\ln n\rceil$ makes this $o(1)$ , so the maximum load is $O(\ln n/\ln\ln n)$ with high probability.

Two choices

TheoremThe power of two choices

Throw $n$ balls into $n$ bins, each ball choosing $d \ge 2$ bins uniformly at random and going into the least loaded of them (ties broken arbitrarily). Then with probability tending to $1$ the maximum load is

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

Assumptions

Stated without proof; the argument is a layered-induction bound on the number of bins with load at least $k$ , given in full in the cited paper. What matters here is the shape: $\ln\ln n$ rather than $\ln n/\ln\ln n$ , and a further improvement only in the constant $1/\ln d$ as $d$ grows beyond two.

Simulating $n$ balls into $n$ bins, averaged over five runs:

$n$	$d=1$ max load	$\ln n/\ln\ln n$	$d=2$ max load	$\ln\ln n/\ln 2$
$10^3$	5.8	3.57	3.0	2.79
$10^4$	6.6	4.15	3.0	3.20
$10^5$	7.8	4.71	3.2	3.53

Key idea

The gain from $d=1$ to $d=2$ is exponential; the gain from $d=2$ to $d=3$ is a factor $\ln 3/\ln 2 \approx 1.58$ in the leading term, and from $d=3$ onward it is diminishing. Two probes is the whole trick. This is why production balancers sample a small constant number of backends rather than maintaining a global ordering — the global information is worth almost nothing beyond what two random samples already provide, and it costs a coherency term of the kind Scaling Limits — Amdahl, Gustafson and the Coherency Penalty warns about.

What to measure when you probe

PropositionRound robin ignores the information that matters

Let servers be identical and let request $i$ have service time $S_i$ . Round robin equalises the count of requests routed to each server. Least-outstanding-requests equalises the number currently in service. These coincide only if the $S_i$ are equal; in general, by Little's law applied per server, the occupancy of server $j$ satisfies

L_j \;=\; X_j\,\E[W_j],

so equalising $L_j$ equalises the product of throughput and latency — the actual load — whereas equalising the routed count equalises $X_j$ alone.

Key idea

For LLM serving the service-time coefficient of variation is large — generations differ in length by orders of magnitude — so round robin and occupancy-based balancing are not close. By the Pollaczek–Khinchine formula in Queueing and the Utilisation Wall, queueing delay scales with $1+c_s^2$ ; routing on counts lets that variance land unevenly, while routing on occupancy absorbs it.

What this does not say

The theorems here are about static balls into bins, where balls never leave. The queueing version — the supermarket model, where jobs arrive and depart — is analysed in the second reference and has the same qualitative conclusion, with the maximum queue length under $d = 2$ decaying doubly exponentially in the load rather than singly. The static statement is quoted because it is the one with a clean, checkable form; the dynamic statement is the one that actually applies to a serving system.

References

PaperY. Azar, A. Z. Broder, A. R. Karlin, E. Upfal (1999). Balanced AllocationsThe theorem that two choices give log log n maximum load.
PaperM. Mitzenmacher (1996). The Power of Two Choices in Randomized Load BalancingDevelops the fluid-limit analysis and the supermarket model for queues rather than static balls.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremMaximum load under uniform random assignmentThrowing n balls into n bins uniformly leaves a fullest bin with about log n / log log n balls with high probability.
TheoremThe power of two choicesSampling d bins and using the least loaded reduces the maximum load to log log n / log d plus a constant — an exponential improvement in d = 2 already.
PropositionA log n / log log n upper bound for one choiceproof includedA first-moment argument shows uniform assignment leaves no bin with materially more than log n / log log n balls.
PropositionRound robin ignores the information that mattersproof includedRound robin equalises request counts, which equalises load only when service times are identical; least-outstanding-requests equalises occupancy, which by Little's law tracks load.

Problems (1)

All problems

Balls into bins, with one choice and with twoCodingIntermediate⏱ 1 hour