Quantile Sketches and Percentile Metrics
Quantile sketches estimate distribution percentiles using bounded memory; they do not store every sample or make independent percentile values additive.
Quantile Sketches and Percentile Metrics
Quantile sketches estimate distribution percentiles using bounded memory; they do not store every sample or make independent percentile values additive. Streaming quantile algorithms such as KLL and t-digest summarize observations with approximation guarantees that differ by algorithm. They support bounded-memory percentile estimates and often mergeable summaries. Error may be expressed in rank space or value space; the distinction matters for heavy-tailed latency distributions. Histogram buckets can also estimate quantiles when boundaries and aggregation are designed carefully.
Mechanism and worked example
Two regions report latency distributions. Merge compatible sketches or histogram buckets to estimate global p99. Do not average the regional p99 values: one region may have far more traffic, and the combined percentile depends on the full distribution.
| Method | Strength | Caution |
|---|---|---|
| Exact sort | Exact sample quantile | Needs retained samples or batch compute |
| KLL | Bounded-memory rank approximation | State merge and error parameters matter |
| t-digest | Tail-oriented quantile estimation | Implementation and merge behavior vary |
| Histogram | Simple aggregation | Bucket boundaries limit precision |
Failure modes and operations
Sketch merge compatibility depends on implementation and configuration. Small sample counts make extreme percentiles unstable. Sampling bias and coordinated omission distort latency distributions. Averaging already-computed percentiles loses the underlying population weights.
Trade-offs and design boundary
Exact sorting provides exact quantiles but needs storage or batch processing. KLL gives rank-error guarantees; t-digest often offers useful tail resolution but implementation behavior differs. Histograms are easy to aggregate when bucket boundaries are shared.
Interview transfer exercise
Explain why averaging two p99 latency numbers is incorrect and how to produce a global percentile from raw samples, compatible sketches or aggregatable histograms.
Read the diagram
Record observations into compatible sketches → Merge sketch state across instances → Estimate quantile from merged distribution → Report sample volume and error contract
Explain why averaging two p99 latency numbers is incorrect and how to produce a global percentile from raw samples, compatible sketches or aggregatable histograms.
Your design draft
Clarify assumptions, explain your approach, and test the difficult cases. Save your draft, then compare it with the study notes.
Self-review checklist
Self-guided practice. Automated AI feedback and code execution are not connected.