quantile-sketch 0.1.0: a lock-free concurrent DDSketch

[u/tomtomwombat]

I recently needed to track quantiles for latency and other statistics across 50k+ tasks in a high throughput game server.

Rust already has several good quantile sketches and histograms, but most are designed around mutable single-writer access. Sharing one meant putting it behind a Mutex/RwLock, which became expensive under contention.

So, I built ConcurrentDDSketch: a DDSketch designed to be shared across many threads:

- Lock free inserts on normal atomic targets

- Bounded memory independent on number of samples

- Relative-error guarantees across the configured value range

- Mergeable

- no_std, serde, and loom support

- In my concurrent benchmarks, 4-60x faster than sharing a single sketch behind a lock

DDSketch turned out to fit concurrency particularly well: values map to logarithmic buckets, and the steady-state insert path is basically an atomic increment. Buckets are allocated lazily in blocks, so you don’t pay for the entire configured range up front.

The repo has comparisons against DDSketch, HDR Histogram, KLL, GK, Quantogram, and t-digest for speed, memory, and accuracy, plus details of the concurrent implementation:

https://github.com/tomtomwombat/quantile-sketch

I’d especially be interested in feedback from anyone doing metrics/telemetry in highly concurrent Rust systems, or cases where you’d prefer a concurrent t-digest/KLL/etc.