Crate quantile_sketch

Expand description

§quantile-sketch

A fast, concurrent DDSketch for relative-error quantiles.

§What is DDSketch?

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.

§Example

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);

§Compatibility

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.

§Alternatives at a glance

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.

§Speed

§Accuracy

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%

§Memory

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

§Run Benchmarks

From the workspace root:

cargo bench -p quantile-sketch-bench --bench comparison --bench concurrency
python bench/scripts/plot_criterion.py

The first command records the Criterion speed results. The Python script writes target/benchmark-summary.png and updates the accuracy and memory tables.

§Future Features

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 Design

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.

§Insert

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 ─────┘

§Quantile

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.

§Optimizations

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.

§License

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.

§Contribution

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.

Structs§

ConcurrentDDSketch: DDSketch with atomic concurrent inserts.
MergeError: Error returned when sketches with different configurations are merged.