# quantile-sketch
[](https://github.com/tomtomwombat/quantile-sketch)
[](https://crates.io/crates/quantile-sketch)
[](https://docs.rs/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](https://arxiv.org/abs/1908.10693),
that interval may span from 2 to 20 seconds for real web-request latencies.
## Example
```rust
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:
```toml
quantile-sketch = { version = "0.1", default-features = false }
```
Enable `serde` for versioned, sparse serialization that is independent of the
sketch's lazy block allocation:
```toml
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
| 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
<img width="1260" height="1142" alt="benchmark-summary" src="https://github.com/user-attachments/assets/d6ab3704-0c22-4a89-b48c-9a5408967693" />
## 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.
| 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.
| 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:
```sh
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.
```text
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.
```text
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](https://github.com/DataDog/sketches-go/blob/master/ddsketch/mapping/cubically_interpolated_mapping.go)
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](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
* MIT license
([LICENSE-MIT](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.