Percentiles and t-digest

The problem: "average latency: 22 ms"

Snip's dashboard says redirects average 22 ms. Yet a big customer says links "sometimes take ages". Both are true: most redirects are fast and a few are very slow, and the average hides the few. Snip's requirement is about the slow ones: p99 under 50 ms at the server. To check it, Snip needs percentiles, from 40 app servers, per minute, per region.

Percentiles can't be averaged

Each of Snip's servers can compute its own p99. The tempting dashboard averages them. Tested with simulated latencies from four servers, one of them slower:

The average is wrong, and not in a predictable direction: it depends on how the servers' distributions differ. The true p99 needs information about the whole distribution from each server, not one number. Prometheus's documentation says it plainly: you cannot aggregate quantiles, and averaging them yields statistically nonsensical values.

Option 1: keep every value

Exact, and expensive: 100,000 redirects a second is 8.6 billion latencies a day, and every percentile query sorts them. Fine for offline analysis of raw events (11.06 Raw events vs derived data), not for a live dashboard.

Option 2: histograms

Count values into fixed buckets: under 5 ms, 5–10, 10–25, 25–50, 50–100, and so on. Each server sends its bucket counts; counts from many servers simply add up, so they merge perfectly. A percentile is found by walking the buckets until the running count passes 99%.

The catch: the answer is only as precise as the buckets. If p99 falls in the 50–100 ms bucket, you know it's between 50 and 100. Prometheus notes the error is limited by the width of the bucket the quantile lands in, so buckets have to be chosen around the thresholds you care about (Snip puts a boundary exactly at 50 ms).

Option 3: sketches with guaranteed accuracy

Sketches choose their buckets automatically to keep the error small:

• Logarithmic buckets (DDSketch's approach): each bucket is about 2% wider than the last, so any value is known within about 1% relative error, whether it's 3 ms or 3 seconds. Buckets add up across servers, like histograms.
• t-digest keeps clusters of nearby values (centroids) and deliberately keeps them small near the extremes, so p99 and p99.9 are accurate even though the middle is summarised coarsely. Digests from different servers can be combined.

export class LogHistogram {
  private buckets = new Map<number, number>();
  private n = 0;
  private readonly gamma: number;

  constructor(readonly relativeError = 0.01) {
    this.gamma = (1 + relativeError) / (1 - relativeError);
  }

  add(ms: number) {
    const i = Math.ceil(Math.log(ms) / Math.log(this.gamma)); // bucket covers (gamma^(i-1), gamma^i]
    this.buckets.set(i, (this.buckets.get(i) ?? 0) + 1);
    this.n++;
  }

  merge(other: LogHistogram) {
    for (const [i, c] of other.buckets) this.buckets.set(i, (this.buckets.get(i) ?? 0) + c);
    this.n += other.n;
  }

  quantile(q: number) {
    const rank = q * (this.n - 1);
    let seen = 0;
    for (const i of [...this.buckets.keys()].sort((a, b) => a - b)) {
      seen += this.buckets.get(i)!;
      if (seen > rank) return (2 * this.gamma ** i) / (this.gamma + 1); // within relativeError of the true value
    }
    return NaN;
  }
}

Tested on the same four servers: each server's 50,000 latencies went into its own sketch, the four were merged, and the merged sketch reported a p99 of 100.5 ms against the true 100.3, a p50 of 22.4 (true 22.4) and a p99.9 of 169.0 (true 167.7), all within the promised 1%, using 257 buckets instead of 200,000 values.

Recap

Interview questions