A fast, concurrent DDSketch for relative-error quantiles.
DDSketch estimates quantiles such as p50 and p99 without storing every sample. Roughly, it is a histogram that covers any finite positive range with logarithmically many buckets. It does this by widening buckets as values increase, which also guarantees relative error: with 1% error, a true 100 ms quantile is estimated between 99 and 101 ms.
Relative-error matters for long-tailed measurements such as server latency. In other cases, a sketch with 0.5% rank error may answer a p99 query with any value from p98.5 to p99.5; for example, that interval may span from 2 to 20 seconds for real web-request latencies.
use quantile_sketch::ConcurrentDDSketch;
let combined = ConcurrentDDSketch::with_err_and_range(0.01, 1.0, 1_000_000.0);
let worker = ConcurrentDDSketch::with_err_and_range(0.01, 1.0, 1_000_000.0);
combined.insert(42.0);
worker.insert(100.0);
combined.merge(&worker).unwrap();
assert!(combined.quantile(0.99).is_some());
assert_eq!(combined.min(), 1.0);
assert_eq!(combined.max(), 1_000_000.0);The MSRV is Rust 1.71, except that the loom testing feature currently requires
Rust 1.73 through Loom's dependencies. std is enabled by default; disable
default features for no_std + alloc environments:
quantile-sketch = { version = "0.1", default-features = false }Enable serde for versioned, sparse serialization that is independent of the
sketch's lazy block allocation:
quantile-sketch = { version = "0.1", features = ["serde"] }Serialization reads each counter once, so inserts concurrent with serialization may or may not be included.
Portable atomics are used on every target. Targets without atomic CAS can
enable the critical-section feature and provide a critical-section
implementation.
The loom feature replaces the atomics with Loom's instrumented atomics for
model testing, including from a downstream crate. Enable it only in test builds
and create and use sketches inside loom::model.
| Structure | Strength | Trade-off |
|---|---|---|
DDSketch (sketches-ddsketch) |
Same relative-value guarantee; closest comparison | Single-writer implementation |
| HDR Histogram | Fast and accurate for bounded integers | Fixed range and higher memory here |
KLL (asap_sketchlib) |
Compact, mergeable rank-error sketch | Randomized; no relative-value guarantee |
Greenwald–Khanna (quantiles) |
Deterministic rank-error guarantee | No relative-value guarantee |
| Quantogram | Strong observed accuracy | More allocations and memory here |
| t-digest | Compact, mergeable, and strong at the tails | No strict relative-value guarantee |
The exact comparisons use mutable, single-writer inserts, so sharing
one instance requires synchronization such as a lock. Per-thread sketches can
be merged where supported; hdrhistogram also offers a separate
SyncHistogram/Recorder API.
Deterministic log-uniform distribution: 100,000 samples and 999 quantiles. Configurations use a 1% native error target where available and size 200 for KLL/t-digest; error guarantees differ by algorithm.
| Crate | Mean value error | Max value error | Mean rank error | Max rank error |
|---|---|---|---|---|
| quantile-sketch | 0.518% | 1.000% | 0.246% | 3.798% |
| sketches-ddsketch | 0.504% | 1.000% | 0.246% | 3.798% |
| hdrhistogram | 0.158% | 0.710% | 0.011% | 0.059% |
| asap_sketchlib | 5.812% | 50.000% | 0.341% | 1.122% |
| quantiles | 8.066% | 100.000% | 0.395% | 1.000% |
| quantogram | 0.346% | 1.724% | 0.023% | 0.111% |
| tdigest | 0.910% | 74.344% | 0.062% | 1.003% |
Median of 3 isolated runs with 128 sketches and 16,384 samples per sketch. Memory is an outcome of the error-targeted configurations, not a matched budget.
| Crate | Allocated bytes | Allocations | RSS |
|---|---|---|---|
| quantile-sketch | 4152 | 54 | 5888 |
| sketches-ddsketch | 4272 | 1 | 4640 |
| hdrhistogram | 14432 | 1 | 15136 |
| asap_sketchlib | 10352 | 3 | 11296 |
| quantiles | 6184 | 1 | 7264 |
| quantogram | 44309 | 1010 | 60768 |
| tdigest | 11304 | 2 | 13472 |
From the workspace root:
cargo bench -p quantile-sketch-bench --bench comparison --bench concurrency
python bench/scripts/plot_criterion.pyThe first command records the Criterion speed results. The Python script writes
target/benchmark-summary.png and updates the accuracy and memory tables.
Currently this crate only implements a concurrent DDSketch. I may add a non-concurrent version or more quantile sketch implementations (such as t-digest) in the future. If you are interested in a feature, please make an issue or like an existing issue.
ConcurrentDDSketch is conceptually a histogram spanning the full configured
range. To keep its initial memory small, it splits the buckets into chunks of 64
counters that are allocated lazily.
pointer array [ null | * | null | * | ... ]
│ │
▼ ▼
lazy histogram blocks [64 counts] [64 counts]
Both the block pointers and counters are atomic. A block remains null until an insert maps to it; once allocated, it never moves.
By default, ConcurrentDDSketch uses 1% relative error and handles values in
0.0..=f64::MAX. This produces 1.1k atomic block pointers and 70k logical buckets (that are lazily allocated on insert).
That sketch uses ~8.8 KiB (64-bit machine) when empty and ~568 KiB with all buckets allocated.
Across configurations, bucket count is O(log(max / min) / error) for positive
bounds.
An insert maps the value to a logarithmic bucket/counter and atomically increments it. If its block is null, the insert allocates and installs it with compare-and-swap. The steady-state path is lock-free where pointer and 64-bit atomics are lock-free.
with_range(0.1, 10.0); insert(0.42)
index(0.42)───────────────────────┐
│
pointer array [ null | ... | * | ... | null ]
│
▼
histogram block [ 0 | ... | 1 | ... | 0 ]
└─┰─┘
| count spans ≈0.419..0.427 |
└───── block spans ≈0.35..1.24 ─────┘
A quantile query sums contiguous bucket counts until summed / total reaches
the requested percentile, or its complement when scanning from the right. For
example, p99 scans from right to left until it has counted 1% of the samples,
then maps that bucket back to an estimated value.
Bucket indexing uses Datadog's cubic logarithm approximation instead of a general logarithm. Queries skip unallocated blocks and choose the shorter scan direction. Compatible sketches merge by atomically adding their counters. Portable fallback targets may use locks or critical sections.
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.