Computing Extremely Accurate Quantiles Using t-Digests

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Search, Analytics and Geo · 9 minReservoir sampling: a fair sample of a stream you cannot storeHow to keep k uniformly random items from a stream of unknown length using only k slots of memory, why it works, and where it is used.Read hereClose

  The problem

  You want a small, unbiased sample of a stream: log lines, requests, events. You cannot store the whole stream, and you do not know how long it will be. "Keep every 1,000th item" is not random and can be biased by periodic traffic. "Pick random items" needs to know the total in advance.

  Reservoir sampling keeps exactly k items so that, at any moment, each of the n items seen so far has the same probability k / n of being in the sample.

  Algorithm R

  1. Put the first k items in the reservoir.
  2. For each later item number i (counting from 1), draw a random integer j between 1 and i.
  3. If j is at most k, replace reservoir slot j with the new item. Otherwise discard the new item.

  100%

  Figure SDA-SAG-06-1 · Algorithm R for one new item · © forcsguy.com

  function reservoir<T>(stream: Iterable<T>, k: number, rand = Math.random): T[] {
    const sample: T[] = []; let i = 0;
    for (const item of stream) {
      i++;
      if (sample.length < k) sample.push(item);
      else { const j = Math.floor(rand() * i); if (j < k) sample[j] = item; }
    }
    return sample;
  }
  

  Why it is fair

  Item i enters with probability k / i. Then it survives each later step m with probability 1 - (k / m) x (1 / k) = (m - 1) / m. Multiply them for item i after n items: (k / i) x (i / (i + 1)) x ... x ((n - 1) / n) = k / n. Every item ends with the same chance, whatever its position.

  Where it is used

  • Debug and audit samples of request logs or events, at constant memory.
  • Estimating statistics, such as the share of requests with a certain property, from the sample.
  • Training data selection from a live stream.
  • Approximate quantiles when a small error is acceptable (for tighter tail accuracy see the t-digest lesson).

  Sampling many streams

  100%

  Figure SDA-SAG-06-2 · Merging samples from several servers · © forcsguy.com

  Keep the count with every sample; without it you cannot merge correctly. A simple way is to draw each output slot by choosing a server with probability equal to its share of the total count, then taking a not-yet-used item from that server's reservoir.

  Variants and limits

  • Weighted sampling (Efraimidis and Spirakis, A-Res) lets some items be more likely, for example by traffic weight.
  • Sliding windows need extra structure: plain reservoir sampling treats the whole history equally.
  • A sample answers "what does a typical item look like?" It does not answer exact counts or rare-event questions; for those use sketches such as HyperLogLog or count-min.

  Real-world reading

  Related reading

  • Random Sampling with a ReservoirJeffrey Vitter · University of Maryland (hosted copy)Papers
  • Reservoir sampling (Wikipedia)Wikipedia contributors · WikipediaDocumentation
  • Computing Extremely Accurate Quantiles Using t-DigestsTed Dunning and Otmar Ertl · arXivPapers

  Open this lesson with its quiz and exercise

• Search, Analytics and Geo · 10 minPercentiles at scale: t-digest and mergeable summariesWhy you cannot average p99 across servers, how histograms and t-digests summarise latency, and how digests merge across hosts and time windows.Read hereClose

  The problem with averages and with averaging percentiles

  Users feel the tail: the slowest one percent of requests. So teams track p95 and p99 latency. But percentiles do not combine the way sums do.

  Imagine two hosts. Host A serves 9,000 requests a minute with p99 of 100 ms. Host B serves 1,000 requests with p99 of 900 ms. The average of the two p99s is 500 ms. The true fleet p99 is close to 100 ms or more, depending on how B's slow requests are spread: the answer depends on the whole distribution, not on the two summary numbers.

  So to get a fleet percentile you must merge distributions, then read the percentile. Shipping every raw value is too heavy at scale, so we need a compact summary that merges.

  100%

  Figure SDA-SAG-07-1 · Why percentiles must be merged as distributions · © forcsguy.com

  Options for summarising a distribution

  • Fixed-bucket histogram. Count how many values fall in each bucket (for example 0 to 5 ms, 5 to 10 ms ...). Merging is adding counts. Simple and common, but accuracy depends on well-chosen buckets, and wide tail buckets hide detail.
  • Log-scale histograms (HDR histogram, DDSketch). Buckets grow geometrically, giving a guaranteed relative error such as 1 percent across a huge range.
  • t-digest. Keeps a limited number of centroids, each a mean and a count. Cluster sizes are limited so that they are tiny near the extremes and large in the middle. The tails stay accurate while memory stays small, typically a few hundred centroids.

  100%

  Figure SDA-SAG-07-2 · How a t-digest spends its clusters · © forcsguy.com

  The compression parameter (often called delta) trades memory for accuracy. Larger values keep more centroids.

  Putting it in a metrics pipeline

  1. Each service instance records latencies into a digest per metric and time slice, such as 10 seconds.
  2. It sends the digest (a few kilobytes) instead of raw measurements.
  3. The collector merges digests across hosts for the fleet, and across slices for longer windows (a minute, an hour).
  4. The dashboard reads p50, p95 and p99 from the merged digest.

  Because merging works for any grouping, you can later ask for any slice: by endpoint, region or version, as long as you kept the digests per that label.

  Honest limits

  • Results are estimates with an error that is smallest in the tails. State the accuracy you need.
  • Merging many times can slowly increase error; keep windows sensible.
  • Do not alert on a percentile computed from too few requests; small windows are noisy for any method.
  • If you can afford an exact computation for a small dataset, do that. Digests are for volume.

  Real-world reading

  Related reading

  • Computing Extremely Accurate Quantiles Using t-DigestsTed Dunning and Otmar Ertl · arXivPapers
  • t-digest reference implementationTed Dunning · GitHubGitHub
  • The Site Reliability WorkbookGoogle SRE team · O'Reilly / GoogleBooks

  Open this lesson with its quiz and exercise