One stall in a million updates

Worked example: a million updates with one stall

At 14:30:00.000 a replay begins feeding a million updates for instrument 42 to the strategy thread on core 3, one every 10 µs, ten seconds of market. Each update’s latency is taken from its arrival to its decision, and 999,999 of them fall as in the table drawn earlier. At 14:30:04.210 the thread stops for 10 ms, as it would if the scheduler had given its core to something else, and the update it was handling finishes 10 ms late. The run is reported twice, once without the stall and once with it:

Of eight lines only three move, and the mean, the one most often reported, moves least. The max says exactly what happened: one event, 10 ms. The percentiles say, correctly, that the stall touched one update in a million.

That last statement holds only for this harness, and it is the first sign of how a number lies. In those 10 ms about 1,000 further updates were due, and in a real feed each would have arrived on time and waited behind the stall; counted that way, the stall is 1,000 samples spread from 0 to 10 ms, and the p99.99 is about 9 ms where the table shows 8 µs. Which of the two a harness reports is taken apart with the other ways a number lies.

Seeing it

The plainest way to see a distribution is to keep every sample, sort them, and index. A replay that reads the clock around each event pushes each difference into a Vec allocated before the run, and afterwards:

/// The sample with at least num/den of all samples at or below it.
/// `sorted` is ascending; the index rounds up, so at small counts the larger
/// neighbour is chosen.
fn at(sorted: &[u64], num: usize, den: usize) -> u64 {
    sorted[(sorted.len() * num / den).min(sorted.len() - 1)]
}

fn report(mut ns: Vec<u64>) {
    ns.sort_unstable();
    let mean = ns.iter().sum::<u64>() as f64 / ns.len() as f64;
    println!("n {} p50 {} p99 {} p99.9 {} max {} mean {:.0} ns",
             ns.len(), at(&ns, 50, 100), at(&ns, 99, 100), at(&ns, 999, 1000),
             ns[ns.len() - 1], mean);
}

For a million samples, at(&ns, 99, 100) reads index 990,000, the 990,001st smallest. The HdrHistogram library, taken apart later in the chapter, takes the smallest value with at least 99% of samples at or below it, the 990,000th; the two differ by one rank. That difference matters most at small counts, but can also change the value at a sharp percentile boundary in a large run; print the count and name the convention. Then break it on purpose: make one event in the million spin for 10 ms, and predict first which of the six figures moves and by how much. The mean should move by about 10 ns and the max should rise to about 10 ms. A substantial p99 change is a reason to inspect the ranked samples and any queued arrivals; it does not by itself prove that there was more than one stall.

Read more: Gil Tene, “How NOT to Measure Latency”, a conference talk he has given many times, with several recordings online, is the standard account of why latency is a distribution, why the max is information and why averages and standard deviations mislead. Jeffrey Dean and Luiz André Barroso, “The Tail at Scale” (Communications of the ACM, February 2013), works through the arithmetic of fan-out and the techniques large services use to live with a tail they cannot remove.