The Tail at Scale

A search can wait on hundreds of machines even when each machine is fast almost every time. The 2013 paper asks how to make the whole service predictably responsive when its parts are not. Its answer is to reduce avoidable variation, then design around the slow response that remains.

The Search That Waits for One Hundred Leaves

Picture one search sent to one hundred leaf servers. In the paper's example, each leaf typically replies in 10 milliseconds, but one request in a hundred is slow and takes a full second. Assume those slow events are independent and the search needs every leaf's answer. The probability that all one hundred reply within a second is 0.99^100, about 37%. About 63% of searches wait more than a second. The one-in-a-hundred event at a leaf becomes the common user experience.

This calculation has conditions. If the search can answer without every leaf, or the delays on different leaves are correlated, 1 - 0.99^n does not describe its latency exactly. It isolates the fan-out effect the paper wants us to see. Even a rarer hiccup can matter: the paper's figure shows that a one-in-10,000 slow event at each server makes almost one in five requests slow when a service waits on 2,000 servers.

The paper also measures a real Google service. Its Table 1 compares waiting for one random leaf, 95% of leaves, and all leaves:

Waiting for the last 5% doubles p99 from 70 to 140 milliseconds. That gives a design target: the few stragglers near the end matter more than another small improvement to the average leaf.