Quantiles at Scale: Choosing the Right Estimation Algorithms for Observability
summary
Benchmarking on 7 billion rows in ClickHouse shows exact sort costs 39 GB RAM and 15 seconds and is impractical; Prometheus native histogram schema 4 yields ~2–4% error while hand-picked classic buckets hit 13–15% error; DD sketch: tunable to 0.1% value error, stores a few KB, costs ~50% more CPU to build but queries fast; Quantile BFloat16: ~0.67% worst error, very fast; t‑digest and reservoir sampling fail on heavy spike distributions.
AI-written summary · about
chapters (10)
- 0:00Quantiles and their importance
- 4:10Exact vs sketch algorithms
- 7:37Key properties of algorithms
- 10:24Error types in estimation
- 13:35Error models and algorithm families
- 15:18Benchmark with 7B rows
- 18:04Accuracy results
- 20:32Sketch cost and state size
- 22:37Trade-offs and recommendations
- 23:39Q&A
related talks
43mPrometheus Puzzlers: Traps, Pitfalls, and Corner Cases
21mSparse High-resolution Histograms in the Prometheus TSDB
21mPrometheus Native Histograms in Production
19mFirst Principles of Observability Systems
28mExperiments in Backing Prometheus with Clickhouse
42mTips & Tricks to Keep Your Queries under 100ms with ClickHouse®
30mBuilding For Fast
27mFast DIY O11y with OpenSrc Analytics & Visualization