Telling Saturation Apart From Contention

A p99 that triples is compatible with at least two different faults that require different fixes. In the first, the resource has more work arriving than it can complete, and requests wait in a queue behind other requests. In the second, the resource completes its own work but spends part of each interval waiting for something else: a lock held by another thread, a cache line owned by another core, a page fault serviced by the kernel, a hypervisor that has scheduled another virtual machine. The first is saturation and is relieved by more capacity or less work. The second is contention and is relieved by reducing the sharing. Adding capacity to the second makes the contention worse.

The arithmetic of a queue near capacity

For a single server with Poisson arrivals and exponential service, the mean waiting time in the queue relative to the mean service time is $\rho / (1 - \rho)$, where $\rho$ is utilisation. The shape of that function is the whole story. At half utilisation, the average request waits about one service time. At 90 percent, it waits about nine. At 99 percent, about ninety-nine. The relationship is not linear and has no knee in the mathematical sense; it climbs smoothly and then very steeply, and the steepness near the top means small changes in offered load produce large changes in waiting time.

Little’s law connects the three quantities that are usually measured separately: the average number of items in a system $L$ equals the arrival rate $\lambda$ multiplied by the average time each item spends in it $W$. That identity holds for any stable system and gives a cross-check that is worth performing on every capacity investigation, because it catches the common error of attributing to the server time that was actually spent in a queue outside it. If a service reports a mean concurrent-request count of 40 and an arrival rate of 400 per second, each request is in the system for about 100 milliseconds on average, whatever the application’s own timing says. A discrepancy between that figure and the application’s internal measurement is a finding, and it localises the missing time to a queue the application can see but does not measure.

Mean values conceal the phenomenon under investigation. Queueing theory’s own result is that waiting time varies most in the tail, and the tail is where the incident lives. A server at 70 percent mean utilisation has intervals where instantaneous utilisation is well above 90 percent because arrival processes are bursty, and the waits that occur in those intervals dominate the p99. This is the reason utilisation alone is a weak predictor of latency and why queue length, a direct measure of the state that causes waiting, is a better one when it is available.

What run-queue and off-CPU measurements reveal

The evidence that separates saturation from contention is the distribution of time, not the total. On Linux, the time a thread is runnable but not running is run-queue delay, and the time it is blocked on something is off-CPU time. A saturated CPU shows run-queue delay, with the scheduler’s own accounting of the waiting interval growing with load and with the load average measured over one, five, and fifteen minutes diverging in the way that indicates a sustained rather than transient overshoot.

A contended resource shows off-CPU time concentrated in one place. For a lock, the blocked interval is attributable to a specific lock acquisition, and if a sampling profiler records both the stack of the running thread and the stack of blocked threads, the contended code path appears as a small number of blocked samples pointing at one acquisition site. For a mutex implemented with a system call, the blocked time may be visible in the kernel as a futex wait.

Off-CPU time has no single portable unit of measurement, which is why it is usually reconstructed from two sources: sampling of thread states and tracing of the blocking operations themselves. The reconstruction matters because the naive measurement, wall-clock duration of a function, sums on-CPU and off-CPU time and therefore cannot distinguish a slow computation from a fast computation behind a lock. Self time in a profile — the time attributed to a frame with callee time removed — is an approximation of the on-CPU component and is the quantity that should be compared between two versions of the same system.

The third form of evidence is per-core. Aggregate utilisation across many cores hides a single hot core, and a single saturated core is enough to make a lock-protected structure the bottleneck. A service reporting 900 percent of 1600 percent across sixteen cores may have one core at 100 percent and a lock queue attached to it, and the aggregate reports headroom that does not exist for the code path that matters.

Contention that does not appear in the application’s own timers

Some contention is below the level at which the application instruments itself, and it shows up only as throughput that fails to scale with added parallelism.

Cache coherence is the standard example. A counter incremented by many cores, or a false-shared pair of variables in the same cache line, forces ownership transfer of a 64-byte line between cores for every update. The cost of that transfer is on the order of the memory hierarchy’s latency rather than the arithmetic, which makes the operation hundreds of times more expensive than its instruction sequence suggests. The fix is structural: per-core counters summed at read time, padding to separate the lines, or an algorithm that avoids a shared mutable word in the hot loop.

Allocator contention is a second form. A single global free list serialises allocation across threads, and the symptom is an application whose scaling curve flattens as threads are added even though each thread’s own work is unchanged. Thread-local caches in the allocator exist precisely to remove the shared word from the common path, and their presence is why the same workload behaves differently between runs, which is also why a reproduction that does not fix the thread count can appear to confirm or refute contention at random.

Kernel contention is a third. Page faults on a shared mapping, interrupts delivered to a single CPU, and the scheduler’s own run-queue locks all serialise work outside the application’s visibility. Time stolen by a hypervisor appears in /proc/stat as a separate field rather than as user or system time, which is why a virtual machine can report low utilisation and high latency simultaneously: the virtual CPU was runnable, and the physical CPU was busy with someone else’s work.

Why more capacity can make contention worse

Parallelism is the natural response to saturation and the wrong response to contention. Adding threads to a lock-protected critical section increases the number of waiters without increasing the work completed, and the resulting convoy makes the probability of a thread finding the lock free lower, so the effective serialised fraction grows. Amdahl’s law describes the ceiling this produces for a fixed serial fraction; the operational observation is that throughput can fall as threads increase past a threshold, not merely plateau.

The same inversion appears in distributed systems. A saturated downstream service triggers timeouts in callers, and callers that retry without jitter or a budget add load to a service that was already past capacity. The retries are work, so the arrival rate rises; the arrival rate is what determines waiting time, so the waiting time rises; the higher waiting time causes more timeouts. The loop has no internal stabiliser, which is why retry budgets exist and why they are usually expressed as a fraction of requests rather than as a fixed count.

A cache that is being thrashed by concurrent misses has the same shape: the work of filling an entry is duplicated across requests that arrive close together, so the effective capacity drops as concurrency rises, and a stampede guard that lets one requester do the fill converts the duplicated work into waiting, which is cheaper. Identifying which of these mechanisms is active is a question of mechanism, and the shape of the population affected is the fastest route to it.

Evidence that settles the question

Three measurements, in order of cost, distinguish the two regimes.

Throughput against concurrency settles it when the data already exists. If adding concurrency increased throughput proportionally before the incident and now increases it not at all, the resource is saturated. If adding concurrency reduced throughput, contention is active, and the reduction is direct evidence that the uniform-resource model does not apply.

On-CPU fraction settles it when a profiler is available. If the request thread is on CPU for most of its duration and the code doing the work is the code that was expected, the latency is real work, and saturation is the likely explanation. If the thread is blocked for a large fraction of the duration, the question becomes what it is blocked on, and that is a question about a specific wait, which is answerable with a stack sample.

Queue length settles it when the resource exposes one, and it is the only one of the three that gives a continuous signal suitable for alerting. A disk queue outside the drive’s own parallelism, a run queue longer than the number of cores, a thread pool with zero idle workers, a connection pool with all connections checked out: each of these is a leading indicator that moves before latency does, and each names a specific queue rather than a general impression of busyness.

Where none of the three is available, the fallback is a controlled change. Reducing offered load by a known fraction and observing whether latency falls proportionally is a saturation test; if latency falls more than proportionally, the system was in the steep part of the queueing curve, and if it barely moves, something else is bounding the latency. That experiment perturbs production, which puts it late in the sequence, and its result has to be read against the possibility that the load reduction also removed the contention by removing the concurrent arrivals that caused it.