Queueing and tail latency

A server takes 100 ms to handle a request and is busy 90% of the time. It still has 10% to spare, so requests should take about 100 ms, maybe a little more. In fact they take about a second on average, and the unluckiest 1 in 100 more than four and a half seconds.

The reason is that requests don't arrive politely one after another. They arrive at random, so sometimes several land at once and have to wait in line, and a busy server has little slack to work the line down. This lesson shows how a line forms, why it explodes as the load nears 100%, why the slowest requests matter more than the average, and how a rate limiter keeps a service out of that danger zone. It is the first tool of capacity planning, and of system design.

arrival rate λ

How many requests arrive per second, on average. They come at random moments (a Poisson process), so they bunch up.

service rate μ

How many requests one server finishes per second, on average. Its mean service time is 1/μ: μ = 10 means 100 ms.

load ρ

The share of the servers' capacity the arrivals use: ρ = λ / (c·μ) for c servers. At 1 or more the line grows forever.

latency

Waiting in line plus being served. It is what a user feels.

p50 and p99

Percentiles of latency: half the requests are faster than p50, and 1 in 100 is slower than p99, the "tail".

token bucket

A rate limiter: a bucket of tokens that refills at a steady rate. Each request spends one, and an empty bucket turns requests away.

One server, 100 ms per request on average, 8 requests a second: a load of 80%. Step through and watch the line in the top row. Each bar below is one request: the lower part is time spent waiting, the upper part time being served.

A handy check on any of these numbers is Little's law: the average number of requests in the system equals the arrival rate times the average latency, $L = \lambda W$. At 8 requests a second and 500 ms each, 4 requests are inside on average. It holds for any queue, random or not.

The player stops before some arrivals and asks whether the request will have to wait, then asks what more traffic would do to the slowest requests. Look at the top row: is every server busy?

Try the light load and the nearly full one, and compare p99 with the mean in the summary. Then try two servers sharing one line at the same 80% load: with a shared line, a server never sits idle while someone waits, so the mean drops from 500 ms (two separate lines) to about 280 ms, and p99 roughly halves.

A service can only stay out of the danger zone if traffic can't push it there. A token bucket in front of it holds up to a fixed number of tokens and refills at a steady rate. Each request spends a token; a request that finds the bucket empty is turned away straight away instead of joining a line that would take seconds. The capacity decides how big a burst gets through at once, and the refill rate caps the long run: in any $t$ seconds, at most capacity $+$ rate $\times t$ requests.

• Load is $\rho = \lambda / (c\mu)$. Random arrivals bunch up, so a line forms well before $\rho = 1$.
• For one server, mean latency is $1/(\mu - \lambda)$: the service time divided by the spare capacity. It explodes near 100%.
• Latency has a long tail. Set targets on p99, not the mean, especially when one page waits for many calls.
• Little's law, $L = \lambda W$, links the number inside, the arrival rate and the latency, for any queue.
• One shared line beats a line per server.
• A token bucket caps the long-run rate at its refill rate and lets bursts of up to its capacity through: keep the rate well under what the service can sustain.