Data engineering
Part 2 of 6 · Approximate AggregationsKLL Quantile Sketches — Error Bounds, k Parameter & Merge Semantics
KLL (Karnin–Lang–Liberty) is a mergeable quantile sketch with a provable rank-error bound. Interviewers want the k parameter, what ε means, and how merges preserve guarantees — not vendor trivia.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How you defend a quantile in interview
Prefer
KLL with a cited rank-ε(k)
Compactors keep ~k items per level. Compaction randomly halves. Rank error shrinks as k grows. Merges combine capacity — they do not average child ε.
- Apache DataSketches KLL in production; this page is the mental model.
- Same object for stream update and map-reduce merge.
- Validate tails with traces when a value cliff matters.
Alternative
Reservoir sample, or 'accurate p99'
Plain sampling wastes budget versus structured compaction. Saying 'accurate latency' is the wrong error model — KLL bounds rank, not milliseconds.
- T-Digest may win empirical tails; it has no KLL-style theorem.
- Exact sort is ε = 0 and O(n).
- Mismatched k without reduce is a silent accuracy change.
Overview
KLL (Karnin–Lang–Liberty) gives a mergeable quantile sketch with a provable bound on rank error. Interviewers want the k parameter, what ε means, and how merges preserve (or degrade) guarantees — not vendor trivia.
KLL keeps a hierarchy of compactors (levels). Each level holds up to about k items. When a level fills, it randomly halves (compact) into the next level. Newer variants tighten constants; the mental model stays: controlled random downsampling with height that grows slowly with n.
You should be able to:
- Write ε in terms of k and say it is a rank bound.
- Compact a full level (even vs odd ranks at random).
- Refuse to treat KLL as a latency-ms SLA by itself.
Error model (rank)
With parameter k, KLL achieves rank error roughly ε ≈ O(1/k) (constants vary by variant: classic KLL vs optimized). Rank error ε means: for quantile φ, the returned value’s true rank is within ε·n of φ·n with high probability.
That is not the same as “value within X ms of true p99.” A sharp cliff in value space can still sit inside a tight rank band. Validate tails with traces or an exact sample when the product question is milliseconds.
k parameter tradeoffs
| k | ε | Memory / merge | When |
|---|---|---|---|
| Larger | Tighter rank bands | More RAM; capacity in the O(k log log n) class — treat as “grows slowly with k” | SLO needs a narrow rank window |
| Smaller | Wider rank bands | Cheaper serialize and merge | Dashboards, coarse p50 |
Pick k from the question: if you need p99 within 0.5% rank, size k accordingly and validate on traces. Do not copy a blog’s default k and call it an SLO.
Update, query, rank
- update(x) — insert into the lowest level; compact upward as levels fill.
- quantile(φ) — merge levels conceptually and pick by weight / rank.
- get_rank(v) — inverse: estimate the fraction ≤ v.
Production: Apache DataSketches KLL (Java / C++ / Python / Go ports). The sandbox below is a toy.
Merge semantics
Merging two KLL sketches of the same family is associative and commutative up to randomness. Practical rules:
- Prefer the same k (or merge, then reduce to the target k).
- Merging never needs raw samples again.
- Error after merge is governed by the merged sketch’s effective capacity — not by averaging the children’s ε.
Compaction uses randomness, so two runs are consistent in distribution, not bit-identical. Ops that need byte-stable rebuilds belong on production sketch ops.
KLL vs cousins
| Structure | Wins | Loses |
|---|---|---|
| KLL | Mergeable, provable rank ε, general quantiles | Rank ≠ millisecond accuracy |
| GK / Greenwald–Khanna | Classic streaming quantiles | Merge story weaker / heavier than modern KLL |
| Q-Digest | Integer domains; tree of buckets | Domain restriction |
| T-Digest | Empirical tails | No rank-ε theorem like KLL — T-Digest |
| Exact sort | ε = 0 | Memory O(n) |
Streaming vs batch
Same sketch: stream updates on a leaf, or build one sketch per Parquet partition and merge in reduce. Batch merge is where KLL shines versus “compute percentile in SQL per day then average days.” Tree reduce: merge pipelines.
Architecture (compact + merge)
Insert at level 0. A full level randomly keeps even or odd ranks and promotes survivors. Query after a peer merge. Mismatched k without reduce is the fail.
Flow
- 1
1 Stream value x
- next2 Level 0 buffer
- 2
2 Level 0 buffer
- next3 Full: random compact
- relatedFail: mismatched k without reduce
- 3
3 Full: random compact
- next4 Compact into higher levels
- 4
4 Compact into higher levels
- next5 Merge peer sketch
- 5
5 Merge peer sketch
- next6 quantile phi
- 6
6 quantile phi
- 7
Fail: mismatched k without reduce
Lesson map
KLL Quantile Sketches — Error Bounds, k Parameter & Merge Semantics
KLL (Karnin–Lang–Liberty) is a mergeable quantile sketch with a provable rank-error bound. Interviewers want the k parameter, what ε means, and how merges preserve guarantees — not vendor trivia.
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 x["1 Stream value x"] l0["2 Level 0 buffer"] c["3 Full: random compact"] up["4 Compact into higher levels"] x -->|1 Stream value x to 2 Level 0 buffer| l0 l0 -->|2 Level 0 buffer to 3 Full: random compact| c c -->|3 Full: random compact| up
Sandbox: conceptual KLL (Python)
Educational toy — not production DataSketches. Compaction randomly keeps even or odd ranks. Merge re-inserts (naive); real KLL merges level-wise.
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
You need p99 within 0.5% rank on a 1e9-event day. What does ε ≈ 0.005 imply for k at O(1/k)? If a latency cliff sits between 200 ms and 5 s, why might the rank band still look “fine” while users feel the cliff? What evidence would you attach?
Interview Q&A
What does k control?
Answer
Capacity versus ε. Larger k, tighter rank error, more RAM. Smaller k, cheaper serialize and merge, wider rank bands.
Is KLL deterministic?
Answer
Compaction uses randomness. Merges are consistent in distribution, not bit-identical. Do not treat two serialized blobs from equivalent streams as a byte-equality test.
Rank vs absolute error on latency?
Answer
Rank ε can still miss a sharp cliff in value space. If the product question is milliseconds, validate tails with traces or an exact subsample.
Can I merge different k?
Answer
Yes with care; reduce to min or target k afterward so the surviving sketch’s ε is the one you quote.
Why better than naive sampling?
Answer
Structured multi-level compaction yields better ε for the same memory than a plain reservoir when the query is quantiles.
Batch reduce pattern?
Answer
One sketch per partition → tree merge → global quantile. Do not percentile-each-day then average days.
Production library?
Answer
Apache DataSketches KLL (Java, C++, Python, Go ports). Cite the paper for the theorem; cite DataSketches for the bytes.
What happens at query time?
Answer
Conceptually flatten levels by weight and pick the item at rank φ·n. Inverse: get_rank(v) estimates the fraction ≤ v.
How does merge error combine?
Answer
Not by averaging the children’s ε. The merged sketch has an effective capacity; that capacity sets the bound.
KLL vs T-Digest in one sentence?
Answer
KLL: provable rank error, general quantiles. T-Digest: heuristic, empirically strong tails. Depth: T-Digest.