Variance and the Effective Capacity of a Replica Pool

A pool of interchangeable replicas is the standard unit of horizontal capacity, and the standard assumption is that its capacity is the sum of the replicas’. The assumption holds exactly when work arrives smoothly and each replica takes the same time for every request. Both conditions fail: request service times span orders of magnitude, arrivals cluster, and the balancer’s knowledge of replica state is stale by the time it acts. The gap between summed capacity and sustainable capacity is variance, and it is large enough to change a replica count by a third or more.

Two kinds of variance, two different losses

Service-time variance and arrival variance are usually discussed together, but they cost capacity through different paths and respond to different remedies.

Service-time variance wastes capacity within a replica. A server with variable service times is idle while it waits for a long request to finish, even when other requests are queued, and if the pool does not allow that work to move to a less busy replica, the idle time is unrecoverable. The two-moment approximation for a single server’s mean waiting time is

$$W_q \approx \frac{\rho}{1-\rho}\cdot\frac{C_a^2+C_s^2}{2}\cdot S$$

so a coefficient of variation $C_s$ of three on service time contributes a factor of five to the variability term relative to deterministic service. For a latency objective, that factor has to be bought back either by running at lower utilization or by splitting the long requests out of the pool.

Arrival variance wastes capacity across replicas. Independent Poisson arrivals to a large pool even out at the pool level by the law of large numbers, so a thousand-replica pool sees arrival variance that is negligible. The interesting case is correlated arrivals: a batch job, a synchronization barrier in a client, a cron-driven traffic spike, or a retry storm all make many replicas busy or idle together. Correlation at the pool level is what makes a pool behave like a single server sized at the pool’s total, complete with the nonlinear latency curve.

The distinction has a practical consequence for measurement. Service-time variance is visible in a single replica’s latency histogram and can be attacked by workload shaping. Arrival correlation is invisible in per-replica metrics and requires looking at the cross-correlation of load across replicas, or simply at the variance of the pool-level utilization over short windows.

The price of a stale routing decision

A balancer that assigns requests round-robin without knowing queue occupancy effectively randomizes. With $m$ replicas and $n$ requests in flight, the maximum queue depth under random assignment grows like $O(\sqrt{n \log m / m})$ and, more importantly, the probability that some replica holds far more than its share is not small. The tail of the queue-length distribution is what drives the tail of latency, so random assignment at high utilization produces a long tail even when the mean is fine.

Choosing the least loaded of two randomly selected replicas changes the exponent. Under the power-of-two-choices result, the maximum load in a pool of $m$ bins drops from order $\log m / \log\log m$ for random assignment to order $\log\log m$, which for any pool size within reason is a handful of requests. The mechanism is that a request only needs one comparison to avoid the worst bin, and two comparisons suffice to keep every bin near the average.

Least-connections balancing performs the same trick with live state, but the state is stale by one round trip: the balancer’s count does not include requests that a replica received after the last information it has. At moderate load the staleness is irrelevant; at high load, the number of in-flight requests is large enough that a decision made on a count from a few milliseconds ago can be badly wrong, which is one way a pool that scales well at 50 percent utilization stops scaling at 80.

Balanced policies also fail in the presence of request classes with wildly different service times, because connection counts are a poor proxy for work. A replica handling one slow request looks idle to a least-connections balancer and is then sent more work. Queued-work-aware routing, where the balancer knows the expected work rather than the count of connections, is the fix; the constraint it imposes is that the balancer must know each request’s class before routing, which is not always possible when the class is a property of the payload.

When one slow replica takes the tail

The tail at scale is dominated by the slowest of the replicas that participate in a request, and a fan-out request that must wait for all of responses inherits the maximum of their latencies. With fifteen parallel calls and a p99 of 100 ms on each, the probability that at least one call exceeds 100 ms is roughly $1-(1-0.01)^{15}$, about 14 percent, so the caller’s own p99 is far above its dependencies’ p99. This is the mechanism behind tail amplification, and its capacity consequence is that effective capacity of a fan-out tier is set by the tail of its dependencies rather than by its own mean service rate.

The remedy that costs the least capacity is to remove the shared queue between the caller and the dependency, so that a slow dependency response does not block a replica that could be serving other work. The remedy that costs the most capacity is to over-provision the dependency until its tail is small enough, which buys tail latency with hardware and is sometimes the only option.

Hedging and deadline propagation change the budget rather than the capacity: a hedged request issued to a second replica after a threshold spends extra capacity to shorten the tail, and the capacity cost of hedging is proportional to the fraction of requests that trigger a second attempt. Whether that is worth it depends on the ratio of the latency budget to the capacity cost, and on whether the second replica is likely to be faster, which it is if the first was slow for an idiosyncratic reason and not if the slowdown is systemic.

Effective capacity as a function of the target

The practical way to express all of this is a single curve per pool: sustainable throughput at the given latency objective, as a function of replica count. The curve is not linear in replica count near the objective, because the tail objective is met by the pool’s slowest members. For a pool of $m$ replicas each with utilization $\rho$ and a p99 residence time $W_{99}$, the fraction of requests that hit a replica above the objective is approximately $m$ times the per-replica exceedance probability if the replicas are independent and identically loaded. Holding the objective fixed, the per-replica exceedance probability must shrink as $m$ grows, which forces lower utilization per replica. Running a larger pool at the same target therefore costs more capacity per replica than a smaller one, unless the balancer is good enough to keep the load distribution tight.

def sustainable_throughput(replicas, service_time, target_wait, variability, z=2.326):
    # Bisection on per-replica utilization so that the pool's p99 fits the target.
    # Mean wait uses the Kingman form; the tail adds z standard deviations of wait.
    def tail_ok(rho):
        mean_w = rho / (1 - rho) * variability * service_time
        # Exponential-ish wait distribution: sd ~= mean for the M/M/1 case.
        return mean_w + z * mean_w <= target_wait
    lo, hi = 0.0, 0.99
    for _ in range(40):
        mid = (lo + hi) / 2
        if tail_ok(mid):
            lo = mid
        else:
            hi = mid
    return replicas * lo / service_time

Two features of that sketch are the point. The tail test is stricter than the mean test by a factor that depends on the assumed wait distribution, so the answer depends on the shape of waiting times and not only on their mean. And the throughput is proportional to replicas times per-replica utilization, so the nonlinearity enters entirely through the utilization that passes the test, which falls as the objective tightens.

What pooling actually buys

Pooling identical replicas is worth more than the sum of their capacities because of statistical multiplexing: a request that would have queued behind a busy server can use an idle one. The gain is largest for small pools with high variance and diminishes as the pool grows, which is the opposite of the intuition that bigger pools are always more efficient. The reason is that a large pool is already well mixed, so the marginal replica adds only its own service capacity, while in a small pool the marginal replica can absorb a queue that would otherwise dominate the tail.

This is why sharding for capacity and pooling for latency are different operations. Sharding reduces contention on a shared resource and increases total capacity at the cost of making each fixed work unit go to a specific shard, which concentrates variance. Pooling over the shards removes the concentration but reintroduces the contention. The design that gets both is hierarchical: a few shards, each with a pool of replicas large enough for the mixing to work, with the shard count chosen from the measured serialization, as described in Amdahl and Gustafson Bounds in Capacity Models.

The relationship between load, concurrency, and pool size is where variance meets arithmetic. The identity in Little’s Law as a Consistency Check on Load Measurements gives the mean concurrency a pool must support for a rate and latency, and the variance argument says the pool must exceed that mean by an amount set by the tail. Sizing at the mean concurrency is exact for a deterministic system and a guaranteed tail violation for a real one.

The measurement that makes variance visible

The metric that captures all of this in one number is the ratio of p99 to p50 of residence time, computed per replica and at the pool level. A ratio near one indicates a system whose capacity is predictable by the mean. A ratio in the tens indicates that the mean is not descriptive, and that any capacity plan derived from mean latency is optimistic by an amount that scales with the ratio. The ratio is cheap to compute from histograms already collected, and unlike absolute latency it is comparable across traffic levels, which makes it useful for tracking whether a release made the variance worse. The treatment that follows from the ratio is a check on aggregation: a quantile computed by averaging per-replica quantiles is not the pool’s quantile, and the error grows with the spread between replicas, which is the same spread the ratio measures.