Section 10: The Slowest Request Is the Customer You Keep - Deep Dive: Engineering the 99.9th Percentile

Executive Summary: Section 2 promised a cart that answers within 300 ms for 99.9% of requests at peak, with a mean around 10 ms. The gap between them is where the engineering lives. Quorums already absorb the slowest replica, since the coordinator waits for the fastest 2 of 3. Four mechanisms remove the remaining tail sources. Buffered writes take the disk off the write path (about 5× better p99.9 at peak, per the 2007 paper), and we name the durability window they open. Client-driven coordination removes the load-balancer hop (at least ~30 ms off p99.9 and 3–4 ms off the mean, per the paper). Admission control keeps background repair out of foreground time. Strategy 3's balance and the fastest-replier coordinator keep any one node from always being late. A cache is proposed and declined.

Interviewer: "Your mean is 10 ms. Why should I care about the other end of the curve?"

You: "Because one request in a thousand isn't a rounding error at 25,000 requests per second. It's a steady stream of customers, and Section 2 argued they're disproportionately the best ones: customers with the longest histories need the most processing. So I'll design for p99.9 and let the mean take care of itself. First I'll find where the slow requests come from, then I'll remove each source by name."

Where the Tail Comes From

A request touching three replicas in three data centers has many chances to be unlucky: a disk seek behind a flush, a replica mid-way through a Merkle exchange, a detour through a load balancer, a coordinator that is the busiest node in the ring. None is common. At 75,600 replica operations per second, all of them are certain.

The quorum is the first defense, and it's free. With (N, R, W) = (3, 2, 2), the coordinator sends to all three replicas but returns after the second answer. For Dana's partition 517, if K in DC3 is mid-checkpoint or busy with a Merkle exchange, B and F answer and K's slowness never reaches the customer. That is exactly why we rejected W = 3: any one slow replica would set the latency of every write. W = 1 would be faster still, but one disk away from loss. Two of three is the point where one slow replica is free to be slow.

The quorum handles one slow replica. It can't help when the slowness is everywhere at once, for example every replica paying a synchronous disk write, or when it sits in front of the replicas, like a hop or a hot coordinator. The four mechanisms below cover those cases.