Data engineering
Part 1 of 6 · Approximate AggregationsApproximate Aggregations — Sketches for Quantiles, Cardinality & Merge Pipelines
Exact p99 over billions of events does not fit in memory, and averaging shard percentiles is wrong. Interviewers expect mergeable sketches: fixed-size summaries you update online, serialize, and combine leaves to regions to global.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How you get a fleet p99
Prefer
Merge sketches, then query
Each shard holds a fixed-size KLL or T-Digest. Regions merge blobs. Global query reads one sketch. Error is bounded (or empirically validated), memory does not grow with n.
- Associative combine — no raw replay.
- Same API for streaming updates and batch partition reduce.
- Idempotent merge keys so retries do not double-count weight.
Alternative
Average the shard p99s, or sort everything
Percentile-of-averages is not a percentile. Exact sort is the gold standard offline and does not merge at billion-event scale.
- A hot shard’s tail disappears into the mean of means.
- Exact needs O(n) memory or a full dump.
- Pre-declared Prom buckets are a different tool — see histogram SLIs, not this cluster.
Why this cluster exists
Interviews start at the wrong average, not at library trivia.
- 1
Ask for fleet p99
Billions of events, many shards, many regions. Sorting the union does not fit. - 2
Average shard p99s
Looks like a number. It is not a percentile of the mixture. - 3
Emit a sketch per leaf
KLL or T-Digest on the stream or per Parquet partition. Depth: KLL, then T-Digest. - 4
Tree-merge up the topology
Leaf to region to global. Depth: merge pipelines, then production ops. - 5
Retry the same blob twice
Without a sketch_id, weight doubles and the quantile lies. Depth: production ops.
Overview
Interview prompt: how do you compute p99 across a sharded pipeline? Seniors are graded on mergeability and error models, not on naming a vendor.
Exact p99 over billions of events does not fit in memory. Averaging the p99 of each shard is wrong: percentiles of averages are not averages of percentiles, and they are not the percentile of the mixture. The structure interviewers want is a sketch — a fixed-size summary you can update online, serialize, and combine across leaves → regions → global.
This hub is the map. The five sibling pages are the whiteboard depth. Latency SLIs that use histogram thresholds stay on histogram vs average latency. Unbounded metric labels stay on metric cardinality. Do not re-teach SLO design or tracing here.
You should be able to:
- Say why mergeable sketches beat “average the p99s” and when exact offline still wins.
- Name the sketch family that matches the question (quantile vs cardinality vs known-range latency).
- Point at KLL, T-Digest, merge pipelines, the comparison matrix, and ops without collapsing them into this page.
Why approximate?
| Property | What you buy |
|---|---|
| Memory | O(k) or O(centroids) instead of O(n) samples |
| Mergeability | Associative combine without replaying raw events |
| Streaming | One pass; also batch-friendly when you merge partitions |
| Query | Estimate any quantile (or rank) after the fact — not only pre-declared buckets |
Sketches trade bounded error for mergeable, fixed memory. Choose the error model (rank vs value vs bucket) that matches the question you will actually ask.
Cardinality aside (hub only)
HyperLogLog (HLL) estimates distinct counts with about 1.04 / √m relative error and tiny mergeable registers. Use HLL for unique users or IPs. Use KLL or T-Digest for value distributions. Do not confuse cardinality sketches with quantile sketches — different math, same pipeline shape (leaf merge → global).
This cluster does not teach HLL internals. If the interviewer switches to unique counts, say “HLL / Theta, same merge tree, different sketch type” and stay on quantiles unless they insist.
Sketch families (the map)
| Family | Job | Default when |
|---|---|---|
| Quantile / rank | KLL (provable rank error), T-Digest (heuristic, strong tails) | Mergeable p50 / p99 across shards |
| Latency histograms | HDRHistogram, DDSketch, Prometheus histograms — fixed or relative buckets | Known value range and SLI-friendly cuts — histogram SLIs |
| Cardinality | HLL / Theta | Distinct counts (this page only) |
| Exact | Sort or a tree of all values | Audit, small n, calibration truth sets |
Rule of thumb: need mergeable p50/p99 across shards → KLL or T-Digest. Need tight latency SLI with a known range → HDR / DDSketch / Prom hist. Need unique counts → HLL. Need audit-perfect → exact offline.
Depth: KLL, T-Digest, when to choose.
Architecture (leaf → global)
Each shard updates its own sketch. Regions merge serialized blobs. Global holds one sketch you query. A retry that re-merges the same leaf without an idempotent key double-counts.
Flow
- 1
1 Leaf sketches update
- next2 Serialize plus merge
- 2
2 Serialize plus merge
- next3 Hierarchical region merge
- relatedFail: retry without idempotent key
- 3
3 Hierarchical region merge
- next4 Global sketch
- 4
4 Global sketch
- next5 Query p99 or NDV
- 5
5 Query p99 or NDV
- 6
Fail: retry without idempotent key
Lesson map
Approximate Aggregations — Sketches for Quantiles, Cardinality & Merge Pipelines
Exact p99 over billions of events does not fit in memory, and averaging shard percentiles is wrong. Interviewers expect mergeable sketches: fixed-size summaries you update online, serialize, and combine leaves to regions to global.
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 l["1 Leaf sketches update"] s["2 Serialize plus merge"] h["3 Hierarchical region merge"] g["4 Global sketch"] l -->|1 Leaf sketches update| s s -->|2 Serialize plus merge| h h -->|3 Hierarchical region merge| g
Pipeline shape and failure modes: merge pipelines. Bytes, coverage, dual-read: production ops.
Sandbox: sketch picker (Python)
Educational chooser — not a production library. Cardinality returns hll as a hub-only pointer.
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.
How this relates to histograms and cardinality
- Histogram vs average latency SLIs chooses histogram threshold ratios vs averages for latency SLIs. This cluster covers mergeable approximate quantiles behind those panels. Do not redo SLO math here.
- Metric cardinality is series explosion from unbounded labels. Sketches shrink per-series cost; they do not fix
user_idon a metric. Bound the keys first.
Pitfalls
Three shards report p99 = 80 ms, 90 ms, 2 s. What is the average of those p99s? What is the p99 of the union if shard three is 1% of traffic vs 40%? Now replace the three numbers with three KLL blobs and merge. What question can you answer that the average could not?
Interview Q&A
Why not average p99 across shards?
Answer
Percentiles of averages are not averages of percentiles, and neither is the percentile of the mixture. Merge sketches (or raw samples) so the estimator sees the combined distribution.
Rank error vs value error?
Answer
Rank error bounds how far the estimated rank can be off (KLL speaks this language). Value error is distance on the numeric axis. T-Digest is heuristic on values and tails. Bucket histograms quantize the axis you configured.
When is HLL the right sketch?
Answer
Distinct counts (cardinality) — unique users, IPs, keys. Not latency distributions. Same leaf-to-global merge shape; different math. This hub only names it.
Streaming vs batch?
Answer
Same sketch API: update online on a leaf, or build one sketch per partition and merge in reduce. Do not compute a percentile per day and then average days.
Biggest merge failure mode?
Answer
Retrying a merge without idempotency keys double-counts weight and shifts quantiles. Depth: merge pipelines and ops.
How does this relate to histogram SLIs?
Answer
That lesson chooses histogram threshold ratios vs averages for latency SLIs. This cluster is mergeable approximate quantiles (and when HDR/Prom hist is the better structure). Do not redefine SLOs here.
How does this relate to metric cardinality?
Answer
High-cardinality labels explode series. Sketches reduce per-series memory; they do not fix unbounded user_id. Bound labels first.
When does exact still win?
Answer
Compliance, small n, or offline truth sets used to calibrate sketches. Exact is the audit path, not the fleet-online path.
What does mergeable mean here?
Answer
You can combine two summaries into one valid summary without the original events. Prefer associative, commutative combine (up to randomness for KLL).
KLL or T-Digest as the default?
Answer
Need a theorem and general quantiles → KLL. Need empirical tail fidelity in APM → T-Digest, then validate. Decision matrix: KLL vs T-Digest vs HDR vs exact.