Queueing and Latency §

Little’s law in practice: if a server handles 1000 requests/second with an average response time of 10 ms, the average number of in-flight requests is $L = 1000 \times 0.01 = 10$: the server only needs 10 concurrent request slots, no matter how fast individual requests are. Little’s law is remarkably general — it holds for any stable queue, regardless of the arrival or service distributions, which is why it is the first tool to reach for when sizing connection pools, thread pools, or worker counts.

Why you must scale before saturation: as $\rho \to 1$, $W \to \infty$. This is the mathematical reason you must add capacity before utilization reaches a critical threshold, typically 70–80%. At $\rho = 0.8$, $W = 5 / \mu$ (5× the service time); at $\rho = 0.95$, $W = 20 / \mu$ (20× the service time). The growth is non-linear — the curve below shows $W$ (in units of service time) against $\rho$:

Waiting until 95% utilization already means users experience 20× the baseline latency. When this happens, the fix is to add capacity — vertically, horizontally, or automatically. The concrete techniques (bottleneck analysis, vertical vs horizontal scaling, load balancers, caching, sharding, cost models, and autoscaling) are covered in Scaling Strategies.

Where latency comes from: the end-to-end response time a user sees is the sum of network transit time (propagation, transmission, and congestion delays in Networks), queueing delay at each hop ($W_q$ above), and service time ($S$). Queueing theory only models the last two; a 200 ms round trip across an ocean cannot be improved by adding servers, only by moving content closer (CDNs) or reducing round trips.

When M/M/1 is a good model — and when it breaks: M/M/1 assumes Poisson arrivals and exponential service times. It is a good first-order model for stateless request handling with roughly uniform service times, and it correctly captures the qualitative non-linear blow-up near saturation. It breaks down when arrivals are bursty (diurnal patterns, flash crowds — bursts see much worse latency than the average $\lambda$ suggests) or when service times are heavy-tailed (database queries, GC pauses — the mean $1/\mu$ then understates the tail). In those cases use M/G/1 (arbitrary service distribution, where the Pollaczek–Khinchine formula adds a variance term to $W_q$), or measure and simulate, as the simulation below does.

Mini-example: a disk serves 80 I/O operations/second with a mean service time of 10 ms ($\mu = 100$/s), and requests arrive at $\lambda = 75$/s. Then $\rho = 0.75$ and $W = 1/(100 - 75) = 40$ ms: each operation spends on average 30 ms waiting and 10 ms being served. If the disk is upgraded to $\mu = 125$/s, $W = 1/50 = 20$ ms — doubling the speed halved the latency, because $\rho$ dropped to 0.6.

Why averages hide the tail: the mean is dominated by the bulk of requests. A single slow request (a GC pause, a disk seek, a network retransmission) inflates the p99 without visibly moving the mean. SLOs are therefore stated in percentiles — “99% of requests complete in under 200 ms” — because the mean says nothing about the worst user experience, and in a service with millions of users even the p99.999 describes thousands of real requests per day.

The union-bound argument: let $X_1, \ldots, X_n$ be the sub-call latencies. For any $\varepsilon > 0$, by the union bound:

where $x_i$ is the $(1 - \varepsilon/n)$-quantile of $X_i$. Hence $\sum_i x_i$ is an upper bound on the $(1 - \varepsilon)$-quantile of the sum. The converse trap: summing per-call p99s (each with $P(X_i > x_i) = 0.01$) gives only $P(\text{total} > \sum x_i) \le 0.01n$ — for $n = 10$ that bounds the p90 of the total, not the p99. Each extra “nine” of end-to-end guarantee pushes the required per-call quantile further out, which is why tail SLOs get expensive fast as fan-out grows.

Tail latency and saturation: tail latency is the primary reason to scale before the mean suggests trouble. In an M/M/1 queue the total time in system $W$ is exponentially distributed with rate $\mu(1 - \rho)$, so $P(W > t) = e^{-\mu(1-\rho)t}$ and the p99 of the response time is:

At $\rho = 0.95$, $W_{99} \approx 92/\mu$: the p99 response time is about 92× the service time, while the mean is only 20×. The tail degrades roughly five times faster than the mean as the server saturates — percentiles are the sensitive overload detector.

Mitigations: hedging (send a duplicate request if the first is slower than the p95, and keep the faster reply — cheap when the tail is rare), prioritized scheduling of short requests, and per-request deadlines with early abandonment. These are described in “The Tail at Scale” (authoritative source above).

Mini-example: an API gateway calls 3 services in parallel and returns when all respond. Each service has p99 = 30 ms and p999 = 80 ms. The response time is the max of the three. By the union bound, $P(\max_i X_i > 80) \le 3 \times 0.001 = 0.003$: the p99.7 of the gateway response is at most 80 ms. To guarantee a p99.9, each service would need p99.967 ≈ p99.97.

Token bucket: a bucket holds at most $b$ tokens; tokens are added at a constant rate $r$ (e.g. 100 tokens/second). Each request consumes one token; a request that finds the bucket empty is rejected or queued. This allows short bursts of up to $b$ requests while enforcing the long-term rate $r$ — exactly the knob you need to keep $\lambda$ below the $\mu$ that queueing theory says you must not exceed.

Leaky bucket: requests enter a fixed-size buffer that drains at a constant rate; a request that arrives when the buffer is full is dropped. Unlike the token bucket, the output rate is constant regardless of the input pattern — useful when the downstream (a database, a third-party API) can only absorb a fixed rate. The cost is added latency: requests wait in the buffer, so the leaky bucket is itself a queue with $W_q > 0$.

Load shedding: when the system is at capacity, it deliberately rejects low-priority work to protect high-priority work: drop analytics events before transactions, serve stale cached responses instead of hitting the database, or return HTTP 429 (Too Many Requests) with a Retry-After header. Well-behaved clients back off exponentially with jitter, avoiding the thundering-herd retry storm that would otherwise re-create the burst.

Interaction with queueing: backpressure is the practical implementation of the queueing-theory insight that $W \to \infty$ as $\rho \to 1$. Rather than letting the queue grow without bound (degrading latency for everyone, including the requests you could have served), the system rejects the excess, keeping $\rho$ below the saturation threshold and latency low for accepted requests. A bounded queue plus rejection is strictly better than an unbounded queue under overload.

Where it applies: at the edge (reverse proxy, API gateway), between tiers (a fixed-size database connection pool is a leaky bucket), and inside a service (bounded worker-pool queues). At the network level, TCP congestion control is backpressure in its purest form — the receiver’s window and dropped packets tell the sender to slow down (see Networks).

Bounding the p99: to bound the p99 of the total ($\varepsilon = 0.01$), each sub-call must be taken at its $(1 - \varepsilon/n)$-quantile with $n = 5$, i.e. the $(1 - 0.002)$-quantile = p99.8. If each call has p99.8 = 25 ms, the p99 of the total is at most $5 \times 25 = 125$ ms.

If you only know the per-call p99s (20 ms each), their sum bounds the $(1 - 0.01 \times 5)$-quantile = p95 of the total — not the p99, which could be significantly higher.

Bounding the p99.9: now $\varepsilon = 0.001$, so each sub-call must be taken at its $(1 - 0.001/5)$-quantile = p99.98. If each call has p99.98 = 40 ms, the p99.9 of the total is at most $5 \times 40 = 200$ ms.

Key insight: the tighter the end-to-end SLO (lower $\varepsilon$), the further into each dependency’s tail you must look. A composite service needs each dependency to meet a stricter per-call SLO than the overall target — and if a dependency cannot meet it, the remedies are architectural: reduce the fan-out, parallelize the calls (sum becomes max), add hedging, or put the dependency behind a cache so most requests never pay its tail at all.