Load Balancing Policy and Effective Capacity

A load balancer’s job sounds like an even split. Even splits are easy to compute and hard to make useful, because the quantity that should be split is not requests but work, and work is not known until a request has been classified. A policy that splits requests evenly can leave half the pool idle and the other half queued, and the cap on throughput comes not from the replicas’ capacity but from the imbalance the policy creates. Effective capacity is the throughput a pool sustains under a policy at a latency target, and it is always less than the sum of the replicas’ capacities by an amount the policy controls.

What the balancer can know, and when

A routing decision is made with a subset of the information needed to make it well. The balancer knows the request’s headers, its source, and a count of connections or requests it has itself assigned. It does not know how long the request will take, how much memory the handler will allocate, or how long the downstream dependency will be slow. Every policy is a bet about which of the available signals correlates with the missing ones.

The strongest available signal is often not per-replica state but the request’s own class, derivable from the path or a header. If requests to one endpoint cost a hundred times more than requests to another, routing by endpoint rather than by connection count is the difference between a balanced pool and one whose most expensive replica serves exactly the traffic the policy’s statistic cannot see. The measurement question is whether the classes are distinguishable before service starts, and for a large fraction of APIs they are.

The information also has a lifetime. A least-connections balancer bases its decision on a count that includes requests assigned before the current one and excludes requests that other balancers assigned. With several balancer instances in front of the same pool, each sees a partial view, and the counts diverge. Sharing state across balancers fixes the divergence at the cost of a coordination round trip per request, which reintroduces the serialization that Amdahl and Gustafson Bounds in Capacity Models warns about. Most large deployments accept the partial view and rely on statistical robustness rather than accuracy.

Why random beats round-robin at saturation

Round-robin assigns in a fixed cycle and is exactly balanced in count, which means it is exactly unbalanced in work whenever the replicas’ service times differ or the pool is not a multiple of the cycle. Constant-weight round-robin with weights is worse under heterogeneity: the weights are set from nominal capacity, which drifts as machines pick up background load.

Random assignment is worse in count but better in expectation, and the tail of the maximum load is what matters. For $n$ requests placed uniformly at random into $m$ bins, the maximum load is of order $\log m / \log \log m$ times the mean, so in a pool of a thousand replicas the worst replica holds roughly twice the average. In queueing terms, that replica is at twice the utilization of the rest, and at moderate mean utilization it is past the knee.

Two random choices with the lesser load selected reduces the maximum to order $\log \log m$, which for any realistic pool size is a small constant above the mean. The information cost is one extra comparison and the knowledge of one other bin’s occupancy, which can be read from a shared counter with no coordination. This is the strongest return on complexity in load balancing, and it is why the policy is common in practice.

The mechanism deserves stating precisely, because it is not that the second choice is better. The first choice is random: some fraction of requests land on a bin already above the mean. The second choice lets the request avoid that bin with probability proportional to the number of choices, so the bins that are above the mean receive fewer requests than those below it. The feedback is what keeps the maximum bounded, and it works on any monotone occupancy measure.

import random

def pick(replicas, load_of):
    # load_of(r) returns a monotone measure of queued work; expensive, so sample twice.
    first, second = random.sample(replicas, 2)
    if load_of(first) <= load_of(second):
        return first
    return second

The function’s cost assumption is the design constraint. If load_of is a local read, the second choice is free; if it is a network round trip to a replica, the policy halves throughput. Implementations therefore sample load from shared state updated asynchronously, accepting staleness for the sake of not paying for the read on the critical path.

Sticky routing and the capacity it costs

Session affinity and consistent hashing trade capacity for locality. Consistent hashing places both keys and replicas on a ring, so a key maps to the nearest replica clockwise, and adding or removing a replica moves only the fraction of keys adjacent to it rather than reshuffling everything. That property is what makes it usable for caches and stateful shards, and the cost is a static mapping that cannot respond to load.

The capacity consequence is a form of imbalance that no amount of routing intelligence can remove, because the keys are determined by the data. With $m$ replicas and random key hashing, the load per replica has a standard deviation proportional to $1/\sqrt{m}$, so the busiest replica carries roughly $1 + O(1/\sqrt{m})$ times the mean. In a pool of sixteen, the busiest carries materially more than a sixteenth of the work, and the pool’s effective capacity is the busiest replica’s capacity times sixteen, which is less than the sum. Virtual nodes, where each replica occupies many positions on the ring, reduce the variance by making each replica’s share an average over many small intervals, at the cost of memory per position and of a more expensive lookup.

Affinity is worse than hashing when sessions are sticky and the session’s work is heavy. A client pinned to a replica for the duration of a session sends all its work there, and if the client population’s session sizes are heavy-tailed, the pool has replicas carrying wildly different totals that are stable for the session’s duration. The balancer’s statistics are correct and useless: the mean load is right, and the maximum is what sizes the pool. Breaking affinity, or moving session state out of the replica, is the capacity fix; a smarter routing policy is not.

Policies that trade latency for throughput

Several policies improve the tail at the expense of total capacity, and the trade is worth stating in the terms a plan uses.

Work stealing or querying several replicas and cancelling the losers raises the tail at the cost of duplicated work. A hedged request issued after a delay $d$ costs the original request plus the fraction of requests whose response takes longer than $d$, and the savings in tail latency is the fraction of requests that the hedge serves faster. The capacity cost is directly proportional to the hedge rate, so a hedging policy that fires on one percent of requests costs one percent of capacity, and one that fires on twenty percent costs twenty percent. Setting $d$ from the service-time distribution is the whole of the tuning.

Shortest-queue routing of the whole request improves the mean at the cost of a global queue, which is a serialization point. In practice the queue is per balancer, and the serialization is one lock per balancer rather than one per request, which is why the policy works at all. The capacity ceiling it introduces is the balancer’s own throughput, and a fleet large enough to need more balancers has reintroduced the problem the policy solved.

Preemption or priority routing protects latency-critical traffic at the cost of the throughput of background work. The capacity accounting is straightforward if the priorities are stable: the high-priority class gets its share, and the remaining capacity serves the rest. It becomes unstable when the high-priority class grows, because the background class is starved rather than slowed, and a starved background class that is a dependency of the high-priority one turns the priority scheme into a positive feedback loop.

Measuring the policy’s capacity, not the pool’s

The number a capacity plan needs is the throughput the deployed policy achieves at the latency target, and it can be measured without distinguishing the policy’s effect from the replicas’ by comparing the distribution of load across replicas. The relevant statistic is the coefficient of variation of a per-replica load measure sampled over short windows. A policy that balances well produces a small value and a pool whose aggregate behaviour matches the single-replica curve scaled by replica count. A policy that balances poorly produces a large value and a pool whose aggregate behaviour matches a single replica at the pool’s total load.

That comparison also identifies the remedy. If the imbalance is temporal, meaning the replicas’ loads average out over the observation window but differ at any instant, the policy is too slow to react and the fix is a faster signal. If the imbalance is persistent, meaning some replicas are always busier, the routing key is correlated with the load and the fix is to change the key or remove affinity. The distinction is visible in the autocorrelation of the imbalance, and it is worth measuring before choosing between a policy change and a policy parameter change.

The broader point is that effective capacity is a property of the pair, policy and pool. Provisioning replicas without measuring the imbalance they will carry produces a count that is correct for a system that does not exist, which is the same error as sizing from mean service time when the tail is what the latency objective measures.