Tail latency amplification

Large systems answer one user request by calling many backends at once. A search query might hit 100 index shards, and a feed might fetch from dozens of services. The response can't be returned until the slowest backend answers. That turns rare slowness on one server into common slowness for users. This effect is called tail latency amplification.

The big idea

Think of a group project where the whole group presents when the last member finishes. If one member is slow once in a hundred times, the group is slow often. With more members, the group is slow more often. Each member's p99 starts to look like the group's median.

The analogy holds, but the real version is worse. Backend responses don't wait for each other in a neat queue. Any one of the parallel calls can hold up the whole reply.

Walking through it

If each backend is slow, above its p99, with probability 0.01, the chance that at least one of N backends is slow is:

P(at least one slow) = 1 − 0.99^N

N = 1     → 1%
N = 10    → 9.6%
N = 100   → 63.4%
N = 1000  → 99.996%

With a fan-out of 100, 63% of user requests are as slow as a single server's p99. The backend's p99 has become the user's median.

This is the central point of Jeff Dean and Luiz André Barroso's 2013 paper, "The Tail at Scale." In a Google service they measured, one random leaf request had a p99 of 10 ms. Waiting for all the leaves of a fan-out request pushed the p99 to 140 ms. The last 5% of the leaves accounted for half of that delay.

Work backwards to set a target. To keep the overall p99 at a target, each leaf must hit that target at roughly the 1 − 0.01/N percentile. For N = 100, that is the leaf's p99.99.

Individual servers have tails even when they run identical code. Common causes include garbage-collection pauses, background jobs such as compaction and backups, noisy neighbors on the same host, and cold caches after a restart. You can reduce these, but you can't remove them.

Common mistakes

• Ignoring a 1% problem. It's rare for one call and common for a fan-out of a hundred.
• Setting a wide fan-out with no latency budget. Every extra parallel call adds to the odds of a slow reply. Check the budget as the fan-out grows.
• Fixing only the average backend. The tail on one slow host can dominate the user's response.

Check yourself

1. Ten backends, each with a 1% chance of being slow. What is the chance a request sees at least one slow one? About 9.6%.
2. For a fan-out of 100 to meet a 99th-percentile target, what leaf percentile do you need? About the leaf's p99.99.

Key takeaways

• The response waits for the slowest parallel call, so fan-out amplifies the tail.
• At a fan-out of 100, a backend's p99 becomes about the user's median.
• Work backwards from the target to find the leaf percentile you need.
• Tame the tail with timeouts, hedging and partial results.

Further learning

The Tail at Scale (Dean and Barroso) is the original paper, and it's short.

Next, read about taming the tail, which covers the techniques for handling slow calls.