"How slow are Tiffin's slowest checkouts?" is a percentile question. The p99 latency is the time that 99% of requests beat, so it tells you what the unluckiest 1 in 100 customers waits. To compute it exactly you sort every request's latency and pick the value 1% from the top. With a billion requests a day across 40 servers, that means shipping and sorting a billion numbers just to draw one line on a dashboard.
Quantile sketches answer the same question from a few kilobytes per server, and, more importantly, they can be merged, so 40 servers' sketches combine into one fleet-wide answer. This lesson covers the three you'll meet (HDR histograms, DDSketch and t-digest) and reservoir sampling, the other way to keep "a representative few" of a huge stream.
Why you can't average percentiles
The obvious shortcut is to have each server compute its own p99 every minute and average them. It's wrong, and not by a little.
Say that in one minute, server A handles 9,900 checkouts, nearly all around 50 ms, with a p99 of 60 ms. Server B is having a bad minute: it handles only 200 checkouts, all around 3 seconds.
| Method | Fleet p99 |
|---|---|
| Average of the two p99s | (60 + 3,000) / 2 = 1,530 ms |
| Average weighted by requests | about 118 ms |
| The real p99 of all 10,100 requests | about 3,000 ms |
The slowest 1% of 10,100 requests is the slowest 101, and all 200 of B's requests are slower than everything on A. So the real p99 is around 3 seconds. The plain average is off by half, and the weighted average, which feels more careful, says everything is fine.
The lesson generalises: percentiles don't add, average or roll up. The p99 of 60 one-minute p99s isn't the p99 of the hour either. To combine percentiles you need the distribution underneath, kept in a form you can merge. That form is a sketch.