Queueing Delay and the Cost of Service-Time Variance

Two services can run at the same average utilization, serve the same average number of requests per second, and have wildly different waiting times. The difference is the distribution of service times, not their mean. A server whose work is always close to its average queues far less than one whose work is sometimes trivial and sometimes enormous, even when both spend the same fraction of time busy. The queueing formulas make this precise, and the coefficient that expresses it — the ratio of variance to the square of the mean — appears in every one of them.

For a single server with random arrivals and exponentially distributed service times, the mean waiting time in the queue is:

$$W_q = \frac{\rho}{1-\rho},\bar{S}$$

where ρ is utilization and S̄ is the mean service time. The term ρ/(1−ρ) is the utilization penalty: at ρ = 0.5 it is 1, at ρ = 0.8 it is 4, at ρ = 0.9 it is 9, at ρ = 0.95 it is 19. The mean service time is multiplied by that penalty, so a system at 90 percent utilization makes every request wait nine mean service times on average before service even begins.

That formula is the exponential-service case. The general single-server result for arbitrary service time distributions, with arrivals that are Poisson, is the Pollaczek–Khinchine formula:

$$W_q = \frac{\rho}{1-\rho}\cdot\frac{\bar{S}}{2}\left(1 + C^2\right)$$

where C² is the squared coefficient of variation of the service time, the variance divided by the square of the mean. Exponential service has C² = 1, which recovers the first formula. Deterministic service has C² = 0, which halves the wait. A heavy-tailed service distribution with C² of 4 or more multiplies the wait several times over. The utilization penalty is unchanged; the variance factor is a separate multiplier, and it is often the larger of the two.

Why the variance enters at all

The intuition is about residual time. A request arriving at a busy server must wait for the request currently in service to finish, and the expected remaining time of that request is not half its mean service time — it is longer, because the arrival is more likely to land during a long request than during a short one. That sampling bias is the inspection paradox: a random arrival samples the service interval in proportion to its length, so long intervals are over-represented.

For a service time distribution with mean S̄ and second moment E[S²], the expected residual time is E[S²]/(2S̄). The second moment is where variance lives: E[S²] = Var(S) + S̄², so the residual time grows with the variance even when the mean is fixed. The Pollaczek–Khinchine formula is essentially the utilization penalty applied to that residual time, and the factor (1 + C²)/2 is the residual time expressed relative to the mean.

This is why a service whose latency is mostly uniform queues well even at high utilization, and why a service with a small fraction of very slow requests queues badly even at moderate utilization. A distribution with a mean of 10 milliseconds and a standard deviation of 10 has C² = 1; the same mean with a standard deviation of 30 has C² = 9, which multiplies the mean wait by 5. The tail’s existence costs queueing delay for every request, not just for the requests in the tail.

The multi-server correction

A pool of N workers is not N independent single-server queues if the queue is shared; it is one queue with N servers. The waiting time for that arrangement is not N times smaller than the single-server case, because a request waits only when all N servers are busy. The exact expression for the M/M/N case involves the Erlang C formula, and its practical content is that the utilization penalty softens as N grows: at the same per-server utilization, a pool of thirty-two queues far less than a pool of one.

The practical implication is that consolidating many small pools into one large pool improves utilization without the wait penalty that the same utilization would impose on a small pool. Two pools of eight, each at 70 percent utilization, have a combined wait that is worse than one pool of sixteen at 70 percent, because the combined pool can absorb a burst on one side with idle capacity on the other. The cost of consolidation is the head-of-line blocking between classes described in head-of-line blocking in a shared worker pool, which is the reason consolidation is not unconditional.

The Erlang C behaviour also explains a familiar operational fact: a service with many workers can run at high utilization without visible queueing, while a service with a handful of workers shows queueing at the same utilization. The number of servers is a parameter of the wait, not just of the capacity.

def mean_wait(rate, mean_service, c_squared=1.0):
    """Pollaczek-Khinchine mean queue wait for Poisson arrivals, one server."""
    rho = rate * mean_service
    if rho >= 1.0:
        return float('inf')          # unstable: queue grows without bound
    return rho / (1.0 - rho) * mean_service / 2.0 * (1.0 + c_squared)

mean_wait(90, 0.010, 1.0)   # 0.9 utilization, exponential: ~0.090 s
mean_wait(90, 0.010, 4.0)   # same load, C^2 = 4: ~0.225 s

The second call is the same system with a heavier-tailed service time and no other change. The mean wait more than doubles. Nothing about the arrival rate, the mean service time, or the worker count changed; only the shape of the distribution did.

Where the variance comes from

Service-time variance has several distinct sources, and each responds to a different remedy.

Queueing inside the service is the first. A handler that waits on a lock, a downstream call, or a connection checkout inherits the variance of whatever it waits on. Composition amplifies: a handler that makes three serial calls has service time equal to the sum of three random variables, and its variance is the sum of theirs plus their covariances. Parallel calls take the maximum instead, whose variance is smaller than the sum’s but still larger than any single component’s.

Garbage collection and other stop-the-world pauses are the second. A pause is a service-time outlier that affects every request in flight at that moment, so it produces correlated outliers rather than independent ones. The correlation matters because the queueing formulas assume independent service times; correlated outliers make the wait worse than the formula predicts, and they make the tail spike in a way that averages hide.

Cache misses, cold starts, and lazy initialization are the third. A request that hits a warm cache is fast; the first request after a deploy or after an eviction is slow. The mixture of fast and slow requests has high variance by construction, and the fraction of slow ones depends on the cache’s size relative to the working set. Reducing the working set or warming the cache shifts the mixture’s weight rather than its shape.

Contention is the fourth, and it is self-reinforcing. When a shared resource is contended, service times lengthen for everyone holding it, which raises variance, which raises the queue, which raises the number of requests in flight, which raises contention. The system moves along the utilization curve without any change in offered load, which is the dynamic described in contention ceilings and the limits of parallelism.

What reducing variance actually buys

The Pollaczek–Khinchine formula says the wait scales with (1 + C²)/2. Halving C² from 4 to 2 cuts the variance-dependent part of the wait by 40 percent; driving C² toward zero approaches a 50 percent reduction relative to exponential. The gain is bounded, and it is a multiplier on the utilization penalty rather than a substitute for it. A system at 95 percent utilization with deterministic service still waits 19 half-service-times, which is nine and a half mean service times — better than the 19 of the exponential case, but still a large multiple.

The practical consequence is that variance reduction and utilization reduction are both levers, and they compose. Running at lower utilization is usually the cheaper lever, because it requires only capacity; variance reduction requires changing the service. But variance reduction is the lever that improves the tail disproportionately, since the tail is generated by the outliers, while utilization reduction improves the mean and the tail together.

Two variance-reduction techniques are worth naming because they change the distribution rather than just its mean. Caching converts a slow path into a fast one for the fraction of requests that hit, which moves probability mass from the slow mode to the fast mode and can increase C² if the hit rate is partial — the mixture becomes more bimodal. Batching converts many small service times into one larger one, which lowers the variance per unit of work but raises the mean latency of the batched items, a trade examined in batching and the amortization of per-request cost.

Utilization targets that account for variance

A utilization target chosen without reference to variance is a target chosen for a distribution that may not exist. The usual 70 to 80 percent guidance assumes a service time distribution with C² near 1; for a heavy-tailed service the same target produces waits several times larger, and for a nearly deterministic one it leaves capacity unused.

The defensible procedure is to measure C² from the service-time histogram, then choose the utilization that meets the wait objective under that C², then verify by measurement. Because the formula assumes Poisson arrivals, and real arrivals are burstier than Poisson, the measured wait will usually exceed the prediction; the prediction is a lower bound, useful for direction and for comparing configurations rather than for promising a number.

A second consideration is that C² is not stationary. It rises during incidents, when a downstream dependency slows and a subset of requests becomes very slow, and it falls when the system is healthy. A configuration tuned for the healthy C² will be far past its target during an incident, which is why the utilization target has to be chosen for the degraded case as well. This is the argument for leaving headroom proportional to the expected degradation rather than to the mean load.

The tail of the wait distribution is not given by these formulas at all; they describe means. Tail wait depends on the arrival process’s burstiness and on the service distribution’s shape in its far tail, and it is best measured rather than predicted. What the formulas supply is the correct qualitative dependence: wait grows with utilization hyperbolically and with variance linearly, and neither can be traded for the other without bound.