Queueing Theory & Little's Law

Every service you run is a queueing system: requests arrive at some rate, wait somewhere (an accept queue, a thread pool, a connection pool, a run queue), get served, and leave. Three pieces of math — Little's law, the M/M/1 response-time curve, and Kingman's approximation — cover most day-to-day capacity reasoning, and they explain concretely why "CPU is only at 85%" and "p99 is on fire" happen at the same time.

Little's law #

For any system in steady state, the mean number of items inside it equals arrival rate times mean time spent inside:

$$L = \lambda W$$

What makes it universally applicable: it assumes nothing about arrival distributions, service time distributions, scheduling order, or how many servers there are. The only requirement is stationarity — over the measurement window, what flows in flows out. You can therefore draw the boundary anywhere — one mutex, one thread pool, one service, a whole pipeline — and the law holds for each boundary separately.

The workhorse form for sizing: concurrency = throughput × latency. A service doing 2,000 req/s at 50 ms mean has $2000 \times 0.05 = 100$ requests in flight. If its worker pool has 64 threads, 36 requests are always waiting somewhere else — and their queueing time is part of that 50 ms. The law also inverts: given a fixed concurrency limit $L$ (a pool of 100 connections) and downstream latency $W = 10$ ms, the ceiling on throughput is $L/W = 10{,}000$ req/s.

Utilization and the hockey stick #

Let $\lambda$ be the arrival rate and $\mu$ the service rate (one server completes $\mu$ requests/s, so mean service time $\tau = 1/\mu$). Utilization is $\rho = \lambda/\mu$. For the simplest model — M/M/1, Poisson arrivals and exponential service times, one server — mean response time and mean queue wait are:

$$W = \frac{1}{\mu - \lambda} = \frac{\tau}{1-\rho}, \qquad W_q = \frac{\rho}{\mu - \lambda} = \frac{\rho\,\tau}{1-\rho}$$

The denominator $\mu - \lambda$ is the spare capacity available to drain the queue. As $\rho \to 1$ it goes to zero, so response time doesn't degrade linearly — it explodes:

The same numbers as a table — bars are linear, 2 px per multiple of $\tau$:

Going from 50% to 80% utilization costs 2.5× latency. Going from 90% to 99% costs another 10×. And these are means — the tail percentiles sit further out on the same explosion (see tail latency & jitter sources).

Variability multiplies the pain: Kingman #

M/M/1 fixes both distributions. Kingman's approximation (G/G/1 — arbitrary arrivals and service times, one server) separates the wait into three independent factors:

$$W_q \;\approx\; \underbrace{\frac{\rho}{1-\rho}}_{\text{utilization}} \cdot \underbrace{\frac{c_a^2 + c_s^2}{2}}_{\text{variability}} \cdot\; \tau$$

where $c_a$ and $c_s$ are the coefficients of variation (stddev / mean) of interarrival and service times. For exponential distributions $c_a^2 = c_s^2 = 1$, the variability factor is 1, and the formula collapses to the exact M/M/1 result. For perfectly regular arrivals and constant service times it's 0 — a metronome feeding a constant-time server never queues.

Real systems sit above 1, often far above:

• Bursty arrivals ($c_a^2 > 1$): cron-aligned batch jobs, clients that retry in sync, mobile fleets waking on a push notification. Same average $\lambda$, several times the wait.
• Heavy-tailed service times ($c_s^2 > 1$): one endpoint that does 200 ms of work sharing a pool with 2 ms lookups, GC pauses, cold caches. A single slow request holds the server while the queue behind it grows.

The factors multiply. A service at $\rho = 0.8$ with $c_a^2 = c_s^2 = 4$ (entirely realistic for mixed workloads) queues $4\times$ longer than M/M/1 at the same load: $W_q = 16\tau$ instead of $4\tau$. (The table above lists response times $W = W_q + \tau$ — its $5\tau$ at $\rho = 0.8$ is that $4\tau$ queue wait plus one service time.)

Sizing rules that fall out #

Latency-sensitive services get a utilization ceiling around 0.7–0.8. At $\rho = 0.9$ mean response is already 10 service times, and both the burst sensitivity and the tail are worse than the mean. This is the whole story behind "running at 80–90% CPU destroys tail latency": the last 20% of the machine is only cheap for throughput, never for latency. Batch pipelines that care about throughput alone can run at 0.95+; anything with a p99 SLO cannot.

Multiple servers soften the knee, but don't remove it. With $k$ workers sharing one queue, a burst only queues when all $k$ are busy, so bigger pools tolerate higher $\rho$ at the same wait. The classic rule of thumb (square-root staffing, from the Erlang-C model) is to provision $k \approx R + c\sqrt{R}$ servers for offered load $R = \lambda\tau$ — headroom grows with the square root of load, so big services genuinely can run hotter than small ones.

Pools are the $L$ in Little's law. A connection pool or thread pool caps concurrency at its size; required concurrency is $\lambda W$. The failure mode: a downstream slowdown raises $W$, so at unchanged $\lambda$ the needed concurrency rises past the pool size, the pool saturates, and the queue reappears upstream of it — latency propagates backwards through the system. This is why saturated pools need explicit backpressure or load shedding rather than unbounded internal queues, and why autoscaling should trigger on utilization, which moves early and smoothly, not on latency, which moves late and vertically.

Where the models break #

Open vs closed systems. The formulas above describe open systems: arrivals don't care how the system is doing. A closed-loop load generator (k virtual users, each sending the next request after the previous response) is a different animal — when the target slows, its own arrival rate drops with it, so it can never push $\rho \to 1$. Schroeder et al. showed the two setups produce wildly different response-time curves for the same service. Production internet traffic is mostly open; if your benchmark is closed, it is structurally blind to the hockey stick.

Coordinated omission. The closed-generator problem has a measurement twin: a generator that waits for each response before sending the next one silently drops exactly the samples that would have landed during a stall, biasing percentiles down by orders of magnitude. Covered properly in latency percentiles & coordinated omission; both errors come from letting the system under test throttle the arrival process.

Retries make $\lambda$ endogenous. The models assume the arrival rate is a given. With timeouts and retries, effective $\lambda$ rises precisely when capacity falls — the mechanism behind retry storms and metastable failures. No steady-state formula applies mid-storm; the fix is architectural (retry budgets, shedding), not analytical.

Non-stationary service times. Warmup, cache eviction, GC cycles, and noisy neighbors mean $\mu$ itself drifts. The formulas still work per regime, but a single all-day average of $\tau$ predicts nothing about the worst hour.