Data engineering
Part 5 of 6 · Approximate AggregationsKLL vs T-Digest vs HDRHistogram vs Exact — When to Choose What
Senior interviews are decision matrices, not brand loyalty. Pick the structure that matches error model, merge needs, value domain, and ops cost — KLL, T-Digest, HDR/Prom hist, or exact offline.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Say the axis before the library
Prefer
Match error, merge, and domain
Need a theorem and any φ later → KLL. Need empirical p99.9 in APM → T-Digest plus calibration. Need SLI-friendly latency with a known max → HDR or Prom hist. Need legal totals → exact offline.
- DDSketch / Prom hist are bucket cousins of HDR, not quantile sketches.
- Reservoir is simpler and weaker than KLL for the same memory.
- Each series may hold a sketch — labels still kill you.
Alternative
Brand loyalty, or average the p99s
Shipping T-Digest because ELK did, or HDR because a blog did, without merge/domain, fails the follow-up. Averaging shard percentiles is still wrong.
- One Prom bucket layout for every service blinds you.
- Mixed units in one digest garbage the centroids.
- HLL is unique counts — hub-only, wrong for latency.
Overview
Senior interviews are decision matrices, not brand loyalty. Pick the structure that matches error model, merge needs, value domain, and ops cost. This page compares KLL, T-Digest, HDRHistogram (and friends), and exact methods — and points at histogram SLIs without re-teaching SLOs.
You should be able to:
- Walk the choice flow without naming a library first.
- Fill the option cards in one sentence each.
- Call out the anti-patterns in the table below.
Decision axes
| Axis | Question |
|---|---|
| Error model | Provable rank ε (KLL) vs heuristic tails (T-Digest) vs bucket quantization (HDR / Prom) |
| Mergeability | Required across shards / regions? |
| Domain knowledge | Known latency bounds (µs–minutes) vs arbitrary magnitudes |
| Memory / CPU | Budget per series |
| Query flexibility | Any φ later vs pre-declared buckets |
| Compliance | Need exact reproducible totals? |
Option cards
- KLL — best default mergeable general quantile; tune k; cite rank error. Depth: KLL.
- T-Digest — observability favorite for p99 / p999; tune compression; validate empirically. Depth: T-Digest.
- HDRHistogram — excellent for latency with configured range / sigfigs; mergeable bucket counts; great with SLI histograms.
- DDSketch / Prometheus hist — relative-error or fixed buckets; Prom hist = predefined cuts. Layout mistakes: histogram SLIs.
- Exact — sort, or a full dump; offline QA / audits.
- Reservoir sample — simple; weaker quantile guarantees than KLL for the same memory.
Rule of thumb
Need cross-shard merge + any quantile + theorem → KLL.
Need max tail fidelity in APM → T-Digest (validate).
Need SLI-friendly latency with known max → HDR or Prom hist.
Need legal / exact → exact offline; use sketches only for ops dashboards.
Anti-patterns
- Averaging shard percentiles
- One Prom histogram bucket layout for all services without review
- Mixing units (seconds + milliseconds) in one digest
- Using HLL for latency (wrong sketch family — hub only)
Memory ballpark
| Structure | Grows with |
|---|---|
| KLL | k (slowly with n) |
| T-Digest | compression (centroid count) |
| HDR | range × significant figures |
| Exact | n |
Per-series cost still multiplies by label cardinality. Sketches do not fix unbounded labels — metric cardinality.
Architecture (choice flow)
Single-column decisions. Audit-without-merge short-circuits to exact. Known range without merge prefers HDR / Prom hist.
Decisions
- ?
1 Merge across shards?
- no plus audit2 Exact offline
- yes3 Need provable rank error?
- 2
2 Exact offline
- ?
3 Need provable rank error?
- yes4 KLL
- no5 Tail p99.9 critical?
- 4
4 KLL
- ?
5 Tail p99.9 critical?
- yes6 T-Digest
- no7 Known latency range?
- 6
6 T-Digest
- ?
7 Known latency range?
- yes8 HDR or Prom hist
- no4 KLL
- 8
8 HDR or Prom hist
Lesson map
KLL vs T-Digest vs HDRHistogram vs Exact — When to Choose What
Senior interviews are decision matrices, not brand loyalty. Pick the structure that matches error model, merge needs, value domain, and ops cost — KLL, T-Digest, HDR/Prom hist, or exact offline.
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 m["1 Merge across shards?"] x["2 Exact offline"] e["3 Need provable rank error?"] k["4 KLL"] m -->|no plus audit| x m -->|yes| e e -->|yes| k
Sandbox: chooser (Python)
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
Ad-platform bid values, arbitrary magnitude, must merge across 200 shards, legal team wants a weekly exact on 1% of auctions. What is online vs offline? Now a 0–30 s HTTP latency SLI with a Prom histogram already in the mesh. Do you add KLL?
Interview Q&A
KLL or T-Digest for ad-platform bids?
Answer
Often KLL for general quantiles plus a proof story. T-Digest if tails dominate the product and you will back-test. Bids are rarely a known microsecond–minute grid, so HDR is a weaker default.
Why HDR for latency?
Answer
Fixed meaningful buckets, fast, mergeable counts. A natural partner for threshold-ratio SLIs. Depth of the SLI argument: histogram vs average.
Prometheus hist limitation?
Answer
Buckets chosen a priori. Bad layout → blind spots. That is a histogram-SLI problem, not a sketch-merge problem.
Exact in streaming?
Answer
Usually impossible at global scale. Exact on a sampled shard (or nightly 1% keys) for calibration. Legal totals stay offline.
Can HDR replace KLL?
Answer
If the domain is bounded and the buckets suffice for every query you will ever ask — yes. Otherwise you need a sketch for arbitrary φ or unbounded magnitudes.
Memory ballpark?
Answer
KLL ~ f(k); T-Digest ~ f(compression); HDR ~ f(range × sigfigs); exact ~ n. Then multiply by series count.
Cardinality?
Answer
HLL — different problem. Hub-only on the map. Not a latency sketch.
Metric cardinality interaction?
Answer
Each series may hold a sketch. Label explosion still kills you. Cross-link metric cardinality; do not re-teach user_id.
DDSketch vs HDR?
Answer
DDSketch targets relative-error buckets across magnitudes. HDR is a configured latency range and significant figures. Both merge counts; neither is KLL.
Reservoir vs KLL?
Answer
Reservoir is easy to explain and weaker for quantiles at the same memory. Prefer KLL if quantiles are the query.