Data engineering
Part 3 of 6 · Approximate AggregationsT-Digest — Centroid Compression, Tail Accuracy & Heuristic Limits
T-Digest stores mergeable centroids with a compression parameter that spends accuracy on the tails. Interviewers want how centroids work, why p99 looks good, and where the heuristic breaks versus KLL’s theorems.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How you spend accuracy
Prefer
Scale function + high enough compression
Centroids near q=0 and q=1 stay small. The middle absorbs weight. Query interpolates along cumulative weight. Validate p99.9 on sampled exact days.
- Popular in ELK / APM stacks for a reason.
- Merge is concat + recompress — associative enough for trees.
- Same API: per-event update or map-file then reduce.
Alternative
Low compression, or treat it like a theorem
Over-merge fattens tails — a silent SLO lie. There is no KLL rank-ε proof to hide behind. Mixed units in one digest make centroids meaningless.
- KLL if you must cite ε.
- HDR / Prom hist if the range is known and buckets are the SLI.
- Exact offline for audits.
Overview
T-Digest (Ted Dunning et al.) is the sketch many latency pipelines actually ship: mergeable centroids with a compression parameter that spends accuracy on the tails. Interviewers probe how centroids work, why tails look good, and where the heuristic breaks versus KLL’s theorems.
A T-Digest stores a list of centroids (mean, weight). New points merge into nearby centroids under a size limit that depends on quantile index — centroids near 0 and 1 stay small (precise); middle centroids absorb more weight (compressed). Compression parameter δ (often just “compression”) caps how aggressive merging is.
You should be able to:
- Draw absorb → recompress → interpolate.
- Say “heuristic, empirically strong tails” without claiming a rank-ε proof.
- Name over-merge as the silent p99 lie.
Centroid compression
- Each centroid: (mean μ, weight w).
- Scale function limits max weight at quantile q: heavier allowance near q = 0.5.
- Higher compression → more centroids → better accuracy, more memory.
- Query: interpolate between centroids by cumulative weight for quantile φ.
The sandbox below greedily merges closest means until a centroid budget — a toy. Production t-digest uses the scale function properly.
Tail accuracy (why people like it)
Empirically strong on p99 / p999 for unimodal latency-like data because the scale function protects extremes. That is heuristic: no KLL-style rank ε proof. Always back-test against exact percentiles on sampled days.
If the interviewer wants a theorem, say KLL. If they want APM p99.9 that “looks right,” say T-Digest plus dual-read calibration — ops.
Heuristic limits
- Multimodal / mixed units in one digest → misleading centroids (seconds plus milliseconds is the classic).
- Negative / unbounded values still work as floats — interpret carefully.
- Over-merge (too low compression) fattens tails — silent SLO lie.
- Not a drop-in for cardinality or distinct counts (HLL is hub-only on the map).
Merge semantics
Merges concatenate centroids then recompress. Associative enough for tree aggregation; floating-point and recompress order can yield tiny differences. Recommend the same compression across siblings.
Cost is O(centroids). After concat you are over budget until recompress runs.
T-Digest vs KLL vs HDR
| Structure | Tails | Error story | Merge |
|---|---|---|---|
| T-Digest | Empirically strong | Heuristic | Concat + recompress |
| KLL | Good general quantiles | Provable rank ε | Level-wise, same family |
| HDRHistogram | As good as the bucket grid | Quantization of a known range | Add bucket counts |
HDR / Prom hist for known latency ranges and SLI-friendly cuts: histogram SLIs. Decision matrix: when to choose.
Streaming vs batch
Update per event on agents; periodically flush serialized digests to a merger. Or map each file → digest → reduce merge — same API.
Architecture (centroids + query)
Flow
- 1
1 Value x
- next2 Find nearest centroid
- 2
2 Find nearest centroid
- next3 Absorb weight if under scale
- 3
3 Absorb weight if under scale
- next4 Recompress if over budget
- relatedFail: compression too low fattens p99
- 4
4 Recompress if over budget
- next5 Serialize to peer digests
- 5
5 Serialize to peer digests
- next6 Merge plus interpolate quantile
- 6
6 Merge plus interpolate quantile
- 7
Fail: compression too low fattens p99
Lesson map
T-Digest — Centroid Compression, Tail Accuracy & Heuristic Limits
T-Digest stores mergeable centroids with a compression parameter that spends accuracy on the tails. Interviewers want how centroids work, why p99 looks good, and where the heuristic breaks versus KLL’s theorems.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB v["1 Value x"] c["2 Find nearest centroid"] m["3 Absorb weight if under scale"] r["4 Recompress if over budget"] v -->|1 Value x to 2 Find nearest centroid| c c -->|2 Find nearest centroid| m m -->|3 Absorb weight if under scale| r
Sandbox: conceptual T-Digest (Python)
Educational — use tdunning/t-digest or DataSketches in production. Toy recompress merges closest centroids until a budget.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Same 10k unimodal samples. Sketch A compression 20, sketch B compression 200. Which p99 do you trust more, and why? If traffic is bimodal (cache hits + cold misses), what goes wrong with a single digest?
Interview Q&A
What is a centroid?
Answer
A weighted mean representing many samples collapsed under a size bound. Pair (μ, w). Query walks cumulative weight.
Why better tails?
Answer
The scale function keeps extreme centroids small so p99 / p999 resolve finer than the middle of the distribution.
What does the compression knob do?
Answer
Higher compression → more centroids → accuracy up, memory up. Too low → over-merge → fat tails.
Is there a theorem like KLL?
Answer
No comparable rank-ε guarantee. Empirical results plus the papers. If the interviewer wants ε, use KLL.
Merge cost?
Answer
O(centroids). Concatenate, then recompress. Floating-point and order can yield tiny differences.
When do you avoid T-Digest?
Answer
Need provable ε, multimodal mixture, mixed units, exact compliance, or distinct counts.
Relation to histogram SLIs?
Answer
Digests can back “approx p99” panels. Bucket histograms remain clearer for Prom-style threshold SLIs. Cross-link; do not redo SLO math.
Streaming vs batch?
Answer
Per-event update on agents with periodic flush, or one digest per file then reduce. Same merge API.
Production libraries?
Answer
tdunning/t-digest, DataSketches TDigest, Elasticsearch percentiles aggregation. Cite compression in the runbook.
Same compression across regions?
Answer
Recommended. Mixed compression is a parameter-drift incident waiting for ops.