8 — Queueing, tail latency and scalability limits

Systems don’t slow down gradually as load rises. They look fine, and then suddenly they don’t. Queueing theory explains why, and a small amount of it goes a long way.

Little’s law

Little’s law links three quantities in any stable system:

$L = \lambda W$

• $L$ is the average number of items in the system.
• $\lambda$ is the arrival rate.
• $W$ is the average time each item spends in the system.

At 1,000 requests a second and 50 ms each, 50 requests are in flight on average. It holds whatever the distribution of arrivals, and it’s useful for sizing.

Sizing a thread pool. At 200 requests a second and 100 ms per request, the system needs 20 in flight, so a pool smaller than that can’t keep up.

Spotting trouble. If the rate stays flat and in-flight requests double, then latency has doubled, even before anyone’s latency graph shows it.

Why latency explodes

A simple model is one server with random arrivals, known as an M/M/1 queue. Its mean time in the system is:

$W = \frac{S}{1-\rho}$

$S$ is the service time and $\rho$ is utilization, the fraction of time the server is busy. A simulation with 200,000 requests and a service time of 1:

The server isn’t any slower at 90%. The time is all spent waiting. From 50% to 90%, the mean grows fivefold. From 90% to 99%, it grows another tenfold or more. The 99% row is above theory because queues that close to saturation take a very long time to settle, so a run of this length doesn’t reach the long-term average.

Real systems differ from this model, but the shape holds. It explains a few things:

• Why a small traffic rise can cause a sudden outage.
• Why servers are run well below full utilization.
• Why variance matters. Occasional slow requests hold up everything queued behind them.

The last point is sometimes called the supermarket effect: one person with a very full cart delays everyone behind them. Reducing variability in service time can help as much as reducing the average.

Tail latency amplification

The chapter so far covered one server. Fan-out makes the slow end much more important.

If a request calls many servers and waits for all of them, then it’s as slow as the slowest. The chance of hitting at least one server’s p99 response is $1 - 0.99^n$:

So in a large fan-out, a backend’s p99 becomes the typical experience. Search engines and social feeds work this way, and The Tail at Scale describes the problem and its fixes.

Causes of tail latency include garbage collection pauses, background compaction, shared hardware, queues and cold caches. Many aren’t bugs, and they can’t all be removed. So large systems learn to tolerate them.

Hedged requests

A hedged request sends a second copy to another replica if the first hasn’t answered within a short delay, and uses whichever answers first.

A simulation where 1% of requests stall for 1,000 ms, others take 5 to 15 ms, and a hedge fires at 20 ms:

That’s a dramatic improvement for only 1.0% extra requests. The delay is the key: waiting until around the p95 or p99 means few requests are duplicated. This assumes that slowness is random and that replicas are independent. If the backend is slow because it’s overloaded, hedging adds load at the worst time, so it needs a budget.

Hedging is only safe for operations that can be repeated, such as reads.

Tied requests go further. A request is sent to two servers, each knowing about the other, and whichever starts it first cancels the other copy.

Other defences

• Replicas and quorums. Waiting for any two of three masks one slow node.
• Partial results. A search can return without its slowest shard.
• Keeping fan-out small. Fewer dependencies mean a smaller chance of a slow one.

Coordinated omission

Latency measurements often have a subtle flaw. A load generator that waits for each response before sending the next one stops sending during a stall. So a one-second freeze produces just one slow sample, when real users arriving during that second would all have been affected. The tool has coordinated with the system, and the tail looks much better than it is. Tools that send at a fixed rate avoid this.

Limits to scaling

Adding machines doesn’t scale forever.

Amdahl’s law says that the serial part of a job limits speedup. If 5% of the work can’t be parallelized, the maximum speedup is 20 times, however many machines are used.

The Universal Scalability Law, from Neil Gunther, adds a second effect:

$C(N) = \frac{N}{1 + \alpha(N-1) + \beta N(N-1)}$

• $\alpha$ is contention: waiting for shared resources, such as locks.
• $\beta$ is coherency: the cost of keeping nodes in agreement.

The coherency term grows with the square of $N$, because every node may need to talk to every other. So throughput doesn’t just flatten, it can peak and then fall as more nodes are added.

This is why adding servers sometimes makes things worse, and why designs try to avoid coordination. A system with no shared state, called shared nothing, has the best scaling properties.

Queues in the wrong place

Queues form at the slowest point. Speeding up anything else doesn’t help, because the bottleneck sets the throughput. This is the theory of constraints. It also means that fixing one bottleneck reveals the next.

Bufferbloat is a related problem. Large buffers feel safe, but they turn overload into latency. Google’s SRE guidance and most overload designs prefer short queues that reject work early, over long ones that serve it late.

A clever trick for overloaded queues is adaptive LIFO. Under normal load, requests are served oldest first. Under overload, the newest are served first, because they’re the ones whose users are still waiting.

The takeaway

Latency depends on utilization, not just on code speed, and it rises very sharply near full load. In a fan-out, a backend’s rare slow requests become common. Design for headroom, watch the tail, and remember that more machines bring more coordination.