Percentiles, averages, and the tail

Percentiles

A percentile names a point in the distribution by the share of samples at or below it: the p99 is the value such that 99% of samples are at or below it and 1% above. The p50 is the median, the middle sample, with half on each side. The p99.9 has one sample in a thousand above it, the p99.99 one in ten thousand. The max is the largest sample of all, and sometimes written p100. Read against the table above, the p50 falls in the 200–299 bucket, near 290 ns; the p99 in 500–999, near 820 ns; the p99.9 in 1,000–1,999, near 1.9 µs; the p99.99 in 2,000–9,999, near 8 µs; and the max above 100 µs. The p50 describes the common case, the p99 and p99.9 the tail, and the max the worst thing that happened.

The max is an event, not noise. Some update in the run took 120 µs because something happened to it: the page under its slot faulted, an interrupt landed on the core, the thread was moved, the line it needed had been evicted by another process. The same thing will happen to some update in production, and its cause can be found, which is why a later section keeps the identity of the slowest samples. Discarding the max as an outlier deletes the most informative sample in the run. It does vary more from run to run than any percentile, because one event sets it; that is a reason to report it with the sample that set it, not a reason to drop it.

A percentile needs samples above it to mean anything. The p99 of 100 samples is decided by the largest one or two of them, whichever convention is used, so it is one event wearing a statistic’s name. The p99.9 of 1,000 samples is one of the two largest; with 10,000 it rests on ten. The p99.99 needs 100,000 samples to rest on ten and several hundred thousand to stay put from run to run. So every percentile in this chapter is given with the count of samples it came from, and none is quoted with fewer than ten samples above it.

The average is a number no event had

The mean, or average, is the sum of the samples divided by their count. For the distribution above it is about 320 ns, a value near which plenty of samples lie but which describes neither the common case, 290 ns at the median, nor the tail. Its real fault is what it does with a rare, large sample. Replace one of the million with a stall of 10 ms: the sum grows from 320 ms to 330 ms, so the mean moves from 320 ns to 330 ns, 3%, a change that run-to-run variation would hide. The max moves from 120 µs to 10 ms, 83 times. In this example the displayed p50, p99 and p99.9 remain unchanged at the reported precision. A single replacement can shift a percentile by a rank and can change its reported value when that rank crosses a gap in the distribution.

The standard deviation, the mean’s usual companion, fares worse. With the stall it becomes about 10 µs, thirty times the mean, and a bell 10 µs wide centred on 330 ns, with nearly half its area below zero, describes nothing that happened. Nor can percentiles themselves be averaged: the p99 of two runs together is not the average of their p99s, because the slow samples of one run are not spread over the other’s. The way to combine runs, by adding their counts, comes with the histogram.

Why the tail is the product

A tail sample is rare as a fraction and common as a count. At 100,000 updates a second, the p99.9 is passed a hundred times a second, and the slow updates are not spread at random through the day. They cluster where queues are long, in bursts, and bursts are when the market moves: many orders arrive at once because something changed, and the update that waits longest is often the one that moved the best price. In the book chapter’s terms, a quote left resting at a price the market has moved through is filled by the trader who knew, and the update that should have moved the quote is the slow one. The cost of the tail is measured in fills, and the median says nothing about it.

The same holds wherever one answer waits for many. A web page that needs a hundred calls to a hundred servers is as slow as the slowest of them. Dean and Barroso give the arithmetic: if each server answers in 10 ms but takes a second once in a hundred times, its p99, then a page that waits for all hundred meets at least one slow server in 1 − 0.99¹⁰⁰ = 63% of loads. The slowest page is the one a user remembers, and the p99 of a single server becomes the median of the product.

What it costs

Keeping a distribution costs more than keeping a number, and the difference decides how a program records its samples. A running sum and count is 16 bytes and about 1 ns per sample, and yields only the mean. Every sample kept in a preallocated array is exact and costs 8 bytes and about 1 ns each: 8 MB per million samples, 80 MB for ten million, and for an eight-hour session at 100,000 updates a second, 2.88 billion samples, 23 GB. Sorting ten million of them to read percentiles takes 0.3–1 s. A histogram, the structure taken apart later in the chapter, keeps every percentile to two or three significant figures in 25–170 KB of fixed memory, at 10–30 ns per sample.

What it costs not to keep the tail is easiest to see as events per second. At 100,000 updates a second the p99 is exceeded 1,000 times a second, the p99.9 100 times, the p99.99 10 times, and the p99.9999 once every ten seconds, 2,880 times in that eight-hour session. A “one in a million” event is an ordinary part of every trading day.