LESSON 23.4
Sampling and percentile sketches
Reservoir sampling for a fair sample of an endless stream, why percentiles can't be averaged, and the histograms and sketches (HDR, t-digest, DDSketch) that make p99 mergeable.
6 min read
Earlier lessons in this module counted things approximately. Two more problems come up constantly in monitoring and analytics: keeping a fair sample of a stream too large to store, and computing percentiles like p99 across many machines.
Reservoir sampling
You want 1,000 random events from a stream whose length you don't know: today's requests, a log file being written. Reservoir sampling does it in one pass with fixed memory:
- Keep the first 1,000 events.
- For event number n (n above 1,000), pick a random number from 1 to n. If it is 1,000 or less, replace that slot with the new event.
- At any moment, every event seen so far has the same chance, 1000/n, of being in the reservoir.
Weighted variants sample proportionally to some value (say, bytes), and per-key reservoirs keep a sample for each customer.
Sampling traces and logs
At high volume, keeping every trace or debug log costs too much. Two strategies:
Head-based sampling
- Cheap: decided at the start
- Consistent across services via a trace flag
- Blind to outcome; misses rare errors
Pick it when: High-volume, healthy traffic.
Tail-based sampling
- Keeps every error and slow request
- Must buffer whole traces before deciding
Pick it when: When the interesting requests are rare.
Whatever you sample, record the sampling rate with the data, so counts can be scaled back up correctly.
Percentiles don't average
Latency is reported as percentiles because averages hide the slow tail. But percentiles have an awkward property: you can't combine them. The average of ten servers' p99s isn't the fleet's p99, and the average of 60 one-minute p99s isn't the hour's p99.
- Server A: 9,900 requests, p99 = 50 ms
- healthy, most traffic
- Server B: 100 requests, two of them very slow, p99 = 2,000 ms
- little traffic
- Average of p99s
- 1,025 ms - wrong
- True fleet p99 (from merged data)
- about 50 ms - B is only 1% of requests
To aggregate correctly, each server must send something that can be merged: the distribution itself, compressed.
Mergeable latency sketches
Fixed-bucket histogram
- Trivially mergeable (add bucket counts)
- Used by Prometheus
- Accuracy depends on the bucket boundaries you picked
Pick it when: Known latency ranges, standard dashboards.
HDR histogram
- Log-scaled buckets with bounded relative error
- Fixed value range
Pick it when: Latency measurement in services and benchmarks.
t-digest
- Small, very accurate at the extremes (p99, p99.9)
- Merge results vary slightly with order
Pick it when: Analytics and percentile queries over large data.
DDSketch
- Guaranteed relative error, fully mergeable
- Slightly larger than t-digest
Pick it when: Metrics pipelines needing accuracy guarantees.
Each server keeps a sketch per metric per interval, sends it, and the backend merges sketches across servers and time before computing any percentile. A few kilobytes per sketch replaces millions of raw latency values.
Try it
Metrics Ingestion HLD
Store latency distributions so percentiles can be queried at any granularity.