Power of Two Choices and the Cost of a Random Probe

A load balancer has three obvious strategies and each has a defect. Send every request to a fixed backend by hashing: the assignment is stateless and cheap, but a hot key or a skewed key distribution overloads some backends while others idle. Send every request to the least loaded backend: the choice is optimal at the moment it is made, but computing it requires global state, which means either a central coordinator or a shared view that every balancer must keep coherent. Send every request to a random backend: no state at all, and in expectation the load is even, but the maximum load across n backends grows like log n / log log n, so a small fraction of backends run well above the mean.

The fourth strategy — sample two backends at random, send the request to whichever reports less load — gets almost all of the balance with almost none of the state. Its maximum load grows like log log n rather than log n / log log n, which for a few hundred backends is a difference between a maximum several times the mean and a maximum close to it. The result is one of the few places in systems design where a constant amount of extra work produces an asymptotic improvement rather than a constant-factor one.

The urn argument

The classical analysis is a balls-into-bins process. Throw m balls into n bins uniformly at random and the maximum bin load is, with high probability, about (m/n) + Θ(sqrt((m/n) log n)): the mean plus a term that grows with the logarithm of the bin count. At m = n, the mean is one ball per bin and the maximum is roughly log n / log log n, so with a hundred bins the busiest bin holds several balls while most hold one.

Now change the rule: each ball samples two bins and goes to the emptier. The maximum load becomes log log n / log 2 plus a constant, so at a hundred bins the maximum is around three, and the distribution of loads is far tighter. The improvement is not a constant factor applied to the same growth curve; it changes the curve’s shape, from a function that is nearly linear in log n to one that is nearly constant.

The reason is that the two-choice rule creates a negative feedback. A bin that has grown to load k is sampled by a ball with probability proportional to its share, and when it is sampled against a bin of load less than k, the ball goes elsewhere. The only way a bin reaches load k+1 is for both sampled bins to already be at load k, which requires the existence of another full bin. That mutual requirement is what caps the maximum: high loads cannot form without company, and the company is unlikely.

import random

def assign(bins, probes=2):
    """Return the index of the least loaded of `probes` random bins."""
    best = random.randrange(len(bins))
    for _ in range(probes - 1):
        cand = random.randrange(len(bins))
        if bins[cand] < bins[best]:
            best = cand
    return best

# one ball: with probes=1 this is uniform placement,
# with probes=2 the maximum load after n balls falls from ~log n to ~log log n

The snippet makes the cost explicit: two random numbers and one comparison, with no coordination between balancers. Two balancers that sample independently produce the same guarantee, because the analysis never assumed a shared view. That property is what makes the technique usable in a stateless proxy fleet, where no component knows the global load.

The load signal is the hard part

The analysis assumes the sampled bins report their current load exactly. Real backends report something else: a queue depth measured at the moment of the probe, an in-flight request count from a recent interval, a CPU utilization averaged over a scrape interval, or a latency estimate. Each of these is a proxy for load, and each is stale or noisy in a different way.

A queue depth read at probe time is the most faithful signal when the queue is the thing being balanced, because it directly measures the wait a new request would experience. Its problem is sampling cost: reading the depth requires a request to the backend, which adds a round trip to every dispatch decision. The common compromise is to piggyback the depth on responses — each backend reports its depth in the headers of the response it returns — so the balancer’s view is updated by the traffic it is already sending, at the cost of being one response stale.

An in-flight count maintained by the balancer itself is free but wrong in two directions. It counts requests the balancer sent, not requests the backend is actually processing, so a backend that is slowly draining a backlog from another source looks idle. And it does not distinguish a request that will take a microsecond from one that will take a second, so a backend holding one long request looks as loaded as a backend holding one short one.

CPU utilization is the signal that most often misleads. A backend at high CPU may be doing useful work or may be spinning on a lock; a backend at low CPU may be waiting on a downstream call that will never return quickly. Utilization measures occupancy of one resource, not the capacity to accept more work, and the two diverge exactly when the backend is in trouble — the situation in which the balancer’s decision matters most.

When two choices are worse than one

The technique has failure modes that the asymptotic analysis does not cover.

The first is herd behaviour under a shared bottleneck. If all backends call the same database, then the least loaded backend is the one whose requests have not yet reached the database, and sending more traffic to it moves the queue rather than removing it. The balancer balances the visible signal and leaves the actual constraint untouched. Under a shared bottleneck, the useful signal is the bottleneck’s load, not the backends’, and a balancer that cannot see it will happily distribute load evenly onto a saturated dependency.

The second is that the sampled signal can be gamed by the request itself. A backend that reports its in-flight count at the start of a request looks lightly loaded until the request completes; a backend that reports at the end looks heavily loaded for the whole duration. The measurement point determines whether the signal leads or lags the work, and a lagging signal causes the balancer to send a second request to a backend that is still busy with the first.

The third is that two choices do not help when the number of backends is small. With two backends, sampling both and picking the emptier is exactly the least-loaded policy, and its benefit over random is small. With three, the benefit is real but modest. The asymptotic result is about large n, and a deployment with a handful of backends is not in that regime.

The fourth is that the rule is memoryless with respect to affinity. If a backend holds a cache entry for a key, sending the next request for that key elsewhere costs a cache miss. Two-choice balancing treats all backends as interchangeable, so it scatters requests for the same key and destroys locality. The fix is a hybrid: hash on the key to a small set of candidate backends, then apply two-choice within that set. The set’s size trades locality against balance: a larger set improves the balance and scatters requests for the same key across more caches.

Choosing the probe count

Three probes instead of two reduces the maximum load further, and the improvement from two to three is smaller than from one to two. The general result for d choices is a maximum load of log log n / log d, so the marginal gain per probe falls as 1/log d. Two is the usual choice because it captures most of the benefit at the smallest sampling cost, and because the sampling cost is not only the random number: each probe that requires a network read costs a round trip, and doubling that cost is a real budget item.

The probe count also interacts with the load signal’s noise. With a noisy signal, more probes help less than the clean-signal analysis predicts, because the extra probes are comparing noisy estimates rather than true loads. Under high noise, a single probe plus a queue-depth threshold can outperform two probes, since the threshold makes a decision on absolute rather than relative grounds. This is one of the few places where the theoretically weaker policy wins in practice, and the reason is that the theory’s assumption — exact load — is the one that fails.

A useful compromise for large fleets is to probe two backends and apply a tie-breaking rule based on the request’s key, so that requests for the same key that find equal loads land on the same backend. The rule costs a hash of the key and preserves locality in the common case where loads are equal, which is the common case when the fleet is healthy.

Interaction with connection reuse and pool state

A load balancer that dispatches per request rather than per connection has a second decision: which existing connection to use. Backends are usually reached over pooled connections, and a backend with a warm pool accepts a request without the establishment cost that a cold one pays, as the checkout path in connection pool checkout and the exhaustion cliff describes. Two-choice balancing based on load alone will send traffic to a backend whose pool is cold if its load signal is slightly lower, and the request then pays establishment time that the load signal did not account for.

The signal can be corrected by including pool occupancy in the load estimate, which makes the estimate a combination of queue depth and pool state. The combination’s weights are a tuning problem, and the tuning is easier if the two components are measured separately and reported together. A backend that is idle with a full pool and a backend that is idle with an empty pool are not equivalent, and a balancer that treats them as equivalent will oscillate between them as their signals diverge.

The interaction with retries is the more dangerous one. A retry that goes through the same balancer samples the same backends and may land on the same one, especially if the fleet is small. Two-choice balancing without retry-awareness can therefore retry a failed request onto the backend that caused the failure, which is why retry logic usually excludes the failed backend explicitly rather than relying on the load signal to avoid it.

What the guarantee does and does not promise

The power-of-two result is a statement about the maximum load in a static assignment of m balls to n bins. It does not promise that no request waits, because a bin at the maximum load still has a queue. It does not promise that the maximum is small in absolute terms, only that it is close to the mean. And it says nothing about the latency distribution, which depends on the service-time distribution at each backend as much as on the assignment.

What it does promise is that the maximum load is close enough to the mean that a fleet sized for the mean can serve the peak without a large fraction of backends being overloaded. That is the property that matters for capacity planning: without the two-choice rule, the fleet must be sized for a maximum that is several times the mean, and the extra capacity sits idle most of the time. With the rule, the fleet is sized for a maximum close to the mean, and the capacity is used.

The technique is therefore best understood as a capacity-efficiency mechanism rather than a latency mechanism. It makes a fleet’s worst backend behave like its average backend, which raises the load the fleet can carry at a given latency target. The latency of an individual request still depends on the backend it lands on, and that backend is still a queue with its own utilization curve, described in queueing delay and the cost of service-time variance.