p99 latency vs p95: why tail latency decides fan-out designs

p99 latency is the time the slowest one in a hundred requests takes, and p95 is the time the slowest one in twenty takes. The gap between them matters most when a request fans out, meaning one request turning into many calls, because the request waits for the slowest call. Say a search asks 100 shards, slices of the index that each live on their own machine, and each shard has a p99 of 10 ms. The typical request then takes about 11 ms, and the request p99 is about 26 ms.

0.5×1×2×ResetHedge off

Scroll →

Request p50

11 ms

Request p99

26 ms

Hit a slow call

63%

Extra calls

+0%

Fan-out (calls per request)100shards

With 100 calls per request, 63% of requests include at least one call slower than the shard p99 of 10 ms. The typical request is now 11 ms and the p99 is 26 ms. Turn on Hedge to cut the tail.

The figure runs that search. Each shard answers in about 2 ms most of the time, 6 ms at p95 and 10 ms at p99. Drag the fan-out from 100 down to 1 and watch the histogram move left. Then set it back to 100 and turn on Hedge, which sends the same request to a second copy when the first is slow.

What p99 and p95 measure#

Take the last 1,000 requests to one endpoint and sort their times, fastest first. The 500th is the p50, the median: half of all requests were faster. The 950th is the p95 and the 990th is the p99. Ten requests out of the thousand were slower than the p99, and those ten are the tail, the slowest few requests.

An average hides that tail. Say 99% of requests take 20 ms and 1% take 5 seconds. The average is about 70 ms, which looks healthy on a dashboard. The p99 is 5 seconds, which is what the people complaining are seeing.

Why not the maximum? The slowest single request out of a million is usually noise: a garbage collection pause, a host that was being rebooted, one client on a bad connection. The maximum changes every minute and nobody can design to it. The p99 is stable enough to put a number on and to alert on.

Why one slow request in a hundred reaches most users#

A p99 of 10 ms sounds like 1% of users see 10 ms. It isn't, because users make more than one request. A page that loads 30 resources, or a session of 100 API calls, meets the slowest hundredth over and over.

The chance that one call avoids the tail is 0.99. The chance that 100 calls all avoid it is 0.99 to the 100th power, about 37%. So a user who makes 100 calls in a session has a 63% chance of hitting at least one p99-sized delay. The p99 is what a typical active user experiences, and the p95 is something they meet several times a session.

That is why p99 sits in most latency targets. A target on the p95 leaves one request in twenty out of the promise, and an active user meets that request within a minute.

Fan-out turns the shard p99 into the request's median#

Now put the same arithmetic inside one request. The search API in the figure asks 100 shards at once and merges the answers when the last one arrives. Its latency is the slowest of the 100 calls, every time.

Each call is slower than 10 ms one time in a hundred. The chance that none of the 100 is slow is 0.99 to the 100th power, about 37% again. So 63% of requests include at least one call that ran past the shard's p99. A delay that was rare for one call is the normal case for the request.

The sizes follow. With one call, the request has the shard's own numbers: 2 ms typically, 10 ms at p99. With 100 calls, the typical request takes about 11 ms, which is slower than a single shard's p99. The request p99 is about 26 ms. No shard got slower. The request samples the tail 100 times and keeps the worst.

The table is the figure's own output. The first column is a design decision. Everything else follows from it.

Four ways to cut the tail#

Step through the figure. It is the six-shard search from the sharding module's drill, with the drill's numbers.

0.5×1×2×▶ Play all

Scroll →

Search p99

230 ms

Extra calls

0.0%

Shards answered

100.0%

01 Normal02 Sick E03 Hedge04 Partial

01

Six shards, and the search waits for the slowest. Shard B's p99 of 206 ms plus 22 ms of merging puts the search p99 near 230 ms. Shard E is at 71.

Hedged requests are the first fix. When a call has waited past the shard's p95, send the same request to a second copy of that shard and take whichever answer comes back first. Only one call in twenty waits that long, so the extra load is about 5%. In Fig 01 at fan-out 100, hedging brings the request p99 from 26 ms to about 13 ms and the median from 11 ms to 9 ms. Hedge reads. A write sent twice may run twice.

Timeouts that get shorter with depth are the second. If the gateway gives up after 1 second, the service it calls has to give up sooner, and the shard call sooner still. Otherwise a slow shard keeps a worker busy producing an answer nobody is waiting for, and under load those abandoned requests crowd out the live ones. One budget: 1 second at the gateway, 800 ms for the search API, 500 ms per shard call.

Partial results are the third. The coordinator stops waiting at a deadline and ranks what it has. A search that covered 99 of 100 shards is usually fine. A bank balance from 99 of 100 shards is wrong. Say which one you are building before you offer this.

Less fan-out is the fourth, and the one people forget. The number of calls per request is a design choice. Fewer, larger shards, or routing a query only to the shards that can hold its answer, cuts N. Going from 100 calls to 10 moves the share of requests that meet a slow call from 63% to 10%. The request p99 goes from 26 ms to 16 ms, and no shard was touched.

Whichever fix you pick, look for the cause too. A fan-out with a bad tail is usually one bad shard, like Shard E in Fig 02, with a garbage collector pausing or a cold cache. Fix that one shard and the search p99 drops with it.

What to say in an interview#

When you draw a fan-out, say the tail arithmetic before the interviewer asks for it.

1. Name the measure. "Each shard has a p99 of 10 ms, the slowest one in a hundred calls."
2. Do the arithmetic out loud. "100 calls, so 0.99 to the 100th, about 37%, avoid every slow call. Two thirds of requests wait on a slow one, and the request p99 is around 25 ms."
3. Pick a fix and price it. "Hedge after the p95 for about 5% extra calls, with a 500 ms per-call timeout under the gateway's 1 second."
4. Say what you would watch. "Per-shard p99, so one sick shard shows up as one line, and the request p99 as the number users feel."

If the interviewer asks what you would do about the average, say you would take it off the dashboard.