Queues and tails: why 19 % more load makes latency four times worse

What is actually being asked

The ladder usually runs like this:

1. "What is p99?" — the warm-up.
2. "Why can you not look at the mean?" — where the substance starts.
3. "Load grew by a fifth and latency went up fourfold. Why?" — the central question.
4. "How highly can you load a service?" — about headroom.
5. "Why is the tail longer than the middle?" — usually answered with "because of load", which is wrong.
6. "What do you do about the tail?" — about what can actually be changed.

The numbers in this lesson come from a model rather than from a run on a live service. The reason is the same as in the lesson on retries: observing how latency depends on utilisation means changing the load on a working service. The model gives the same dependency with named assumptions; in exchange the reader must remember that a real service has several workers, a bounded queue and timeouts.

Base: a queue appears when requests arrive faster than they are served

Before talking about utilisation, percentiles and models it is worth naming, in ordinary words, where a queue comes from at all.

Suppose a server can handle ten requests per second. That is its limit — it cannot do more.

• Eight arrive per second. The server keeps up. Sometimes requests arrive in a burst and somebody has to wait, but a gap follows the burst and the queue drains inside it. There is headroom, and the headroom is those gaps.
• Ten arrive per second. The server is busy the whole time. There are no gaps any more — and with no gaps there is nothing for the queue to drain into: whatever piled up during a burst stays there and keeps growing.

That is the whole reason a queue behaves so strangely near the limit: what disappears is not capacity but the gaps.

The second thing to name before anything else is what the latency a user sees is made of:

service time + waiting time = latency

Service time is how long the server spends on the request itself. Waiting time is how long the request stood in the queue while the server was busy with others. The user sees only the sum, but the two terms change differently — and that is what this lesson is about.

And here is the central question: which of the two terms grows when things "got slower"? The work has not changed: the same code, the same hardware, the same request.

The answer: the waiting grows. Service stays exactly what it was, while time in the queue keeps increasing — because the gaps that drain it keep getting rarer.

That is already enough to answer the basic interview question. Everything below is about how disproportionately the waiting grows, where the gap between the middle and the tail comes from, and why what moves that gap is not what people usually assume.

Mechanism 1: a queue gets expensive faster than load grows

TIME IN THE SYSTEM AGAINST UTILISATION
--------------------------------------
    load       mean        p50        p95        p99
    0.50      20.3       14.0       61.2       94.0 
    0.70      34.1       23.6      103.2      158.1 
    0.80      51.3       35.8      155.7      227.2 
    0.90     109.2       74.1      331.9      503.2 
    0.95     212.9      152.9      634.0      932.5 

The "load" column is the fraction from the Base: eight requests out of ten the server can take is utilisation 0.8, nine and a half is 0.95. Formally, the utilisation ρ of the model is the share of time the single server is busy.

And straight away, the boundary without which that number misleads: the ρ of the model is not the CPU utilisation on your dashboard. CPU says how hard the hardware is working; ρ says how densely occupied the one place where the queue forms is. They need not agree: the bottleneck may be a disk, a database connection, a worker pool or a lock — and then the queue grows by every rule in this table while the CPU chart stays calm. Read the table with the ρ of the resource that actually constrains you, not of the most visible one.

Read the "mean" column: 20 → 34 → 51 → 109 → 213. Load grows in ever smaller steps; time accelerates.

The reason is not that the service got tired. Service takes the same 10 ms throughout; only waiting grows. The mechanism: while the worker is busy, new requests pile up, and the higher the utilisation the rarer are the gaps in which a queue drains. At 0.5 there are many gaps, at 0.95 almost none, and each random burst takes longer and longer to clear.

Hence the rule worth answering with: the last percentage points of utilisation are the most expensive. In the "mean" column the step from 0.5 to 0.8 is 20.3 → 51.3, and the next step, from 0.8 to 0.95, is 51.3 → 212.9 — fourfold.

Mechanism 2: putting a number on the disproportion

WHAT GROWS FASTER THAN WHAT
---------------------------
  load 0.80 -> 0.95 is a rise of              1.19x
  mean time rises by                          4.15x
  p99 rises by                                4.10x
  p99 over mean at load 0.80                  4.43x
  p99 over mean at load 0.95                  4.38x

The first two lines answer the central question: load rose by 19 %, latency fourfold. That is the disproportion that makes plans of the form "we still have fifteen percent of headroom" wrong: fifteen percent of utilisation is not fifteen percent of latency.

The fourth and fifth lines are why the model is worth reading closely. The ratio of p99 to the mean did not change: 4.43 against 4.38. In M/M/1 — the model this whole table comes from — p99 and the mean scale identically: the tail grows at exactly the rate the middle does, not faster.

Why that happens is visible in the model's own construction, and it is worth naming: time in the system here is exponentially distributed, and for an exponential distribution any quantile is the mean times a constant factor. That is why the ratio of p99 to the mean cannot change — what grows is the factor in front of it, not the ratio.

Now, carefully, about what follows from that. It does not follow that the tail never grows faster than the mean. Exactly one thing follows: "the tail always grows faster than the mean simply because of the queue" is not a general law — there exists a queue where it is untrue, and it happens to be the most thoroughly studied queue in existence. The rule is written from the boundary: in M/M/1 the tail and the mean scale together; outside it, that is an open question.

And a real system leaves that boundary in many ways. A heavy-tailed service time (one class of requests that takes an order of magnitude longer than the rest), several servers instead of one, batching (requests processed in groups), priorities (some requests let through first) — in each of those the picture differs, and the tail may well part company with the middle. The first of them is measured in this lesson, and that is where we go next.

Mechanism 3: the tail is made by spread, not by load

The hypothesis: what pulls the tail away from the middle is the spread of service times, not the load. The test — the same load, the same average service time, only the spread changes: instead of "10 ms on average", "95 % of requests take 5 ms and 5 % take 105 ms". The mean of that is exactly the same: 0.95 × 5 + 0.05 × 105 = 10.

SAME MEAN SERVICE TIME, DIFFERENT SPREAD
----------------------------------------
  both runs: load 0.80, average service time 10 ms
  A: service time exponential, average 10 ms
  B: service time is 5 ms in 95% of cases and 105 ms in 5%

                           mean        p50        p99
      A, exponential      51.3       35.8      227.2
            B, mixed     139.1       92.2      713.8
  p99 of B over p99 of A                      3.14x
  p50 of B over p50 of A                      2.58x

Everything grew — the median and the tail alike — but the tail grew further: 3.1x against 2.6x. And utilisation did not move by a single percent, nor did the average work per request.

This is exactly the step outside M/M/1 mentioned above: the moment service time acquired a heavy tail, the tail of latency moved faster than the middle. Note the order of the claims — not "the tail grows faster than the mean because queues", but "the tail grows faster than the mean when the spread changes; load alone is not enough to do it".

Hence the phrasing to answer with: the tail is made by spread, not by load. Five percent of slow requests is not "five percent of users will wait"; it is a queue forming behind them, and everybody else joins it.

And the practical consequence: if the tail has parted company with the middle, look for the slow class of requests. Adding capacity at the bottleneck lowers utilisation and compresses the whole distribution — the tail together with the middle; removing spread moves the tail specifically. Which lever is stronger depends on how close the bottleneck is to saturation — that is the next section.

Mechanism 4: speeding up the bottleneck at the same arrival rate

The first table invites a wrong conclusion. At utilisation 0.95 a request spends 212.9 ms in the system on average, of which service is 10 ms — about five percent; so speeding up service is pointless? No: that reasoning holds waiting constant, and waiting itself depends on how fast service is. With the same arrival rate, a faster server is busy less often — utilisation falls together with service time, and the queue shrinks.

The check uses the same model and the same seed: the arrival rate is held at 95 requests per second, and only the server changes.

SAME ARRIVALS, MORE CAPACITY: 95 REQUESTS PER SECOND IN EVERY ROW
-----------------------------------------------------------------
  arrivals: 95 requests per second in every row, seed 20260905

                                       util     mean      p50      p99   theory
           baseline: 1 server, 10 ms  0.950    212.9    152.9    932.5    200.0
        service -20%: 1 server, 8 ms  0.760     34.1     23.8    153.1     33.3
    capacity x1.2: 1 server, 8.33 ms  0.792     41.0     28.6    181.6     40.0
            second server: 2 x 10 ms  0.475     13.0      9.5     55.4     12.9
      one server twice as fast: 5 ms  0.475      9.6      6.7     44.7      9.5

  baseline row equals block 1 at load 0.95   True

                against the baseline  mean falls  p99 falls
        service -20%: 1 server, 8 ms       6.24x      6.09x
    capacity x1.2: 1 server, 8.33 ms       5.19x      5.13x
            second server: 2 x 10 ms      16.34x     16.83x
      one server twice as fast: 5 ms      22.08x     20.85x

Service 20 % shorter (10 → 8 ms) lowers utilisation from 0.95 to 0.76, and the mean falls from 212.9 to 34.1 ms — 6.2x, p99 6.1x. If "20 % faster" means 1.2x the capacity (8.33 ms), the gain is 5.2x. The M/M/1 formula for the mean, E[T] = 1/(μ − λ), gives the same direction and the same order: 200 → 33.3 ms; right at the limit a finite simulation strays from the formula by a few percent.

A second server is a capacity gain too, only a twofold one, and its gain is correspondingly larger: 16x on the mean. Comparing it with a 20 % speedup compares different gains. At an equal gain, one server twice as fast gives an even lower mean here, 9.6 ms against 13.0: with two servers every request is still served in 10 ms. And a second server helps only if the work really splits: a shared lock or a shared database leaves the bottleneck where it was.

The opposite extreme — "speeding up the code always pays best" — is wrong too. What the same speedup buys depends on how close the bottleneck is to saturation:

THE SAME 20% SHORTER SERVICE AT DIFFERENT ARRIVAL RATES
-------------------------------------------------------
  1 server; service 10 ms -> 8 ms; arrivals fixed within each row

  arrivals/s         util  mean, 10 ms  mean, 8 ms    falls
          50   0.50->0.40         20.3        13.4    1.51x
          80   0.80->0.64         51.3        22.7    2.26x
          95   0.95->0.76        212.9        34.1    6.24x

Far from the limit (50 requests per second) the same 20 % buys one and a half times; near it, six. And it is the bottleneck that is worth speeding up: a faster step that has no queue in front of it does not lower the utilisation of the resource where the queue actually forms.

Deeper: what the model leaves out

The model behind this lesson is M/M/1, and its name is worth carrying alongside its numbers: almost every conclusion holds inside its boundaries rather than in general. Four things worth saying yourself.

There is one worker. A real service handles several requests in parallel, which changes the numbers a lot: a queue in front of several workers drains faster, and the same utilisation costs less. The direction of the dependency survives; the exact multiples do not. This is also where "p99 and the mean grow together" breaks: that equality was shown for M/M/1 and nowhere else.

The queue is unbounded. Nobody is refused and nobody leaves. A real system has an accept queue of finite length — the one described in tcp(7) and taken apart in the lesson on the accept queue — and client timeouts (the lesson on timeouts): both cut the tail off — at the price of errors instead of waiting.

There are no retries. In life there are, and they add load exactly when the system is at its limit (the lesson on retries). The real curve is steeper than the model's by that contribution.

And ρ once more. Utilisation in the model is the share of time the one place where the queue forms is busy. A dashboard usually has no such number: it has CPU utilisation, while the queue may be sitting at a connection pool, a disk or a lock. Applying this table to CPU percentages is the most common mistake made when carrying these conclusions into a live system.

How to answer in an interview

Short answer: time in the system is service plus waiting, and what grows with utilisation is the waiting, not the service. So the dependency is disproportionate: in the model, raising utilisation from 0.80 to 0.95 is plus 19 %, and time grew 4.1x with the work unchanged at 10 ms per request.

That is enough for a correct answer. What follows is what you add when the interviewer digs.

If the interviewer digs deeper

Three things separate a good answer. First, you do not pass "the tail grows faster than the mean" off as a law of queues: in the M/M/1 model the p99-to-mean ratio is constant (4.43 against 4.38), so load alone stretches the whole distribution as one. Second, you name the real cause of a long tail — the spread of service times; in the same model, at the same load and the same mean, swapping even service for "95 % at 5 ms and 5 % at 105 ms" tripled p99 and raised the median a little over twofold. Third, you draw the practical conclusion at a fixed arrival rate: if the tail has parted from the middle, you look for the slow class of requests; if the whole distribution is growing, the bottleneck needs capacity — and near the limit even a 20 % gain cuts time by a multiple (in the model at 95 requests per second, from 212.9 to 34.1 ms), while far from it the gain is much smaller.

And two things that are easy to overdo. First: "p99 and the mean grow together" is a property of M/M/1, not a law of queues. With a heavy-tailed service time, several servers, batching or priorities the tail does part company with the middle — the spread measured in this lesson is exactly such a case. Second: the ρ of the model is not the CPU utilisation on a dashboard; before applying the table to your system, work out which resource the queue is actually forming at.

Next they ask

Common misconceptions

Practice

Two exercises. Answer first, then check against the real output: in both, the correct answer comes from a run of the model rather than being written by hand.

low = simulate(0.80)
high = simulate(0.95)
mixed = simulate(0.80, service_mixed)
print(f"{high['mean'] / low['mean']:.1f}")
print(f"{high['p99'] / low['p99']:.1f}")
print(f"{mixed['p99'] / low['p99']:.1f}")

4.1
4.1
3.1

1.2
4.1
3.1

4.1
8.5
1.0

1.2
1.2
3.1

Knowledge check