Utilization and the Nonlinear Growth of Waiting Time

A server at half load does not respond in half the time of an idle one. The relationship between how busy a resource is and how long a request waits for it is convex, and it bends sharply near the top. This curvature is the single most consequential fact in latency analysis, because it means that the difference between 70 percent and 90 percent utilization is not a 29 percent increase in delay but frequently a factor of three or more, and the difference between 90 and 95 percent is larger still.

The shape is not a property of the workload’s arrival pattern. It follows from the service-time distribution, and specifically from its variability, which is why two systems with identical utilization can have wildly different latency.

Where the curve comes from

Consider one resource with arrivals at rate $\lambda$ and a mean service time of $1/\mu$ seconds. Utilization is $\rho = \lambda/\mu$, the fraction of time the resource is occupied. For the simplest model, Poisson arrivals and exponentially distributed service, the mean number in system is $\rho/(1-\rho)$ and the mean time in system is

$$ W = \frac{1}{\mu - \lambda} = \frac{1}{\mu}\cdot\frac{1}{1-\rho} $$

The first factor is the service time; the second is the stretch factor, which is 1 at zero load, 2 at 50 percent, 10 at 90 percent, and 20 at 95 percent. The resource is not “90 percent as fast” at 90 percent utilization. Each request waits an average of nine service times before it is served.

The derivation is worth internalizing because it shows why the denominator is $1-\rho$ rather than something with a gentler shape. The probability that the server is busy when a request arrives is $\rho$, and a request that arrives to a busy server must wait for the residual service of the one in progress plus, recursively, whatever is queued ahead of it. That recursion sums to a geometric series whose ratio is $\rho$. The series converges only while $\rho < 1$, and its sum is $1/(1-\rho)$. Every queueing result that produces a hyperbolic latency curve has this geometric-series structure underneath, which is why the blow-up is generic and not an artifact of the exponential assumption.

Variance, not the arrival process, sets the multiplier

The exponential case is a special case of a more general result for a single server with general service times and Poisson arrivals: the mean waiting time in the queue is

$$ W_q = \frac{\rho}{1-\rho}\cdot\frac{1}{2}\left(\frac{1}{\mu}\right)\left(1 + C_s^2\right) $$

where $C_s^2 = \sigma^2\mu^2$ is the squared coefficient of variation of service time. The first factor is the utilization term; the second is half the mean service time; the third is the variability term, which equals 2 for exponential service (where $C_s^2 = 1$), 1 for deterministic service (where $C_s^2 = 0$), and larger than 2 for anything more variable than exponential.

Two consequences follow directly. First, halving the variance of service time halves the queueing delay at every utilization level, while leaving the utilization itself unchanged. A system that makes its slow path less slow, even without making its fast path faster, buys latency across the whole load range. Second, heavy-tailed service distributions, where $C_s^2$ is large or undefined, produce delays that the formula understates because the moments it uses do not exist. Empirical traffic often shows this: file sizes and request durations on the web are well described by heavy-tailed distributions, and the second moment of such a distribution can be dominated by a rare extreme.

The corollary is that “the server is only at 60 percent CPU” is not evidence that it has headroom. If the service-time distribution has a long tail, the 40 percent of idle time is fragmented into gaps too short to be useful, and the queue that forms during the busy periods is longer than the mean utilization suggests. The right question is not the mean utilization but the fraction of time the resource has more than $k$ items waiting.

Measuring the curve instead of assuming it

The theoretical curve is a model; the operational version is measured. A load test that steps through arrival rates and records latency at each step traces the actual curve, and the trace is more useful than any closed-form formula because it captures the real service-time distribution, the real scheduling, and the real contention.

Two features of the trace matter. The knee is the utilization at which latency starts to rise faster than load. Below it, adding load costs little; above it, each increment of load costs more than the last. The knee’s location is a property of the system, not a universal constant, and it moves when the service-time distribution changes. The asymptote is where latency diverges, and it is approached but never reached in a real system because something else fails first: a queue bound is exceeded, connections time out, or the load generator’s own concurrency limit caps the offered rate.

A trace taken with a closed-loop generator flattens the curve artificially, because a saturated server slows the generator and thereby reduces the offered load. The measurement then shows a plateau rather than a wall, and the plateau is an artifact of the measurement apparatus rather than a property of the server. This is the same mechanism that produces coordinated omission in latency samples, described in Coordinated Omission and the Samples a Closed Loop Never Takes, and it is the reason a capacity conclusion drawn from a closed-loop test has to be treated as a lower bound on the achievable rate.

The utilization target is a risk statement

Sizing a fleet to run at 50 percent utilization rather than 80 percent is often described as waste. The framing misses what the extra capacity buys: it moves the operating point down the steep part of the curve, and it does so for the tail rather than the mean.

At $\rho = 0.5$, the queueing multiplier is 1; at 0.8 it is 4; at 0.9 it is 9. If a service has a target of 200 milliseconds at the 99th percentile, the multiplier applies to the whole distribution, not just the median. The 99th percentile of a queueing delay in a simple single-server model grows with the same $1/(1-\rho)$ factor as the mean, so a fleet running at 0.9 rather than 0.5 has roughly nine times the queueing contribution at every percentile. Whether that is affordable depends on how much of the total latency is queueing rather than service, which is a measurable split.

There is a second, stronger argument that does not depend on the model. Capacity has to absorb variance in demand, and demand variance is not the only source: instance loss, deployment, and slow nodes all reduce effective capacity by a step. A fleet at 80 percent utilization has 20 percent headroom for a step change; one at 95 percent has 5 percent, and a single instance failing in a fleet of twenty removes exactly 5 percent. The operating point therefore sets the size of the failure the fleet can absorb without entering the steep region, and that is a design decision with a stated cost in hardware.

The counter-argument is real and should be stated: idle capacity costs money, and the curve’s steepness is a property of the queueing model rather than of every real system. Systems with admission control, priority classes, or preemption can keep the latency of a protected class flat while a background class runs near saturation. That works because the protected class sees a resource whose effective utilization is low, having been reserved. The reservation is the same thing as running at lower utilization, expressed differently.

Where the model stops applying

The single-server formula assumes one queue and one server. Real services have neither. Requests are dispatched across many workers, each with its own short queue, and the dispatch policy determines whether the aggregate behaves like one big server or like many small ones. A single shared queue feeding all workers behaves like one server of aggregate capacity and achieves the lowest mean delay. Per-worker queues with random assignment behave like many independent servers and lose efficiency whenever one worker is idle while another has a backlog, which is exactly the load-imbalance penalty described in Work Distribution, Join Barriers, and Idle Time at the End of a Stage.

The model also assumes that service time does not depend on queue length. In real systems it does, in both directions. A deep queue can improve throughput through batching, which shortens service time; and it can degrade throughput through cache pressure and context switching, which lengthens it. When service time is a function of load, the curve is no longer the hyperbolic one the formula predicts, and only measurement settles its shape.

Finally, the formula describes steady state. A system that is only briefly near saturation does not reach the equilibrium queue, because the queue takes time to build and drain. Short bursts at high utilization cost less than the steady-state curve implies, and the relevant analysis becomes transient rather than stationary. Bursty arrivals at constant mean rate therefore produce a different curve from smooth ones, which is why the arrival process matters for the shape even though it does not appear in the $C_s^2$ term of the single-server result.