Expand description
Percentile sketches (PERF-09, #242): a DDSketch-based bounded-memory mergeable quantile sketch with relative-error guarantees, replacing the previous ring-buffer + nearest-rank approach in the live sketches.
DDSketch (from Datadog) is a quantile sketch that provides
relative-error guarantees: the returned quantile is within
(1 + alpha) of the true quantile. This is ideal for latency
distributions, which span several orders of magnitude (sub-ms to
seconds), where absolute-error sketches (like t-digest with
uniform centroids) lose resolution in the tail.
§Algorithm
DDSketch buckets values by their logarithm. The bucket index for a
positive value v is floor(log(v) / log(gamma)) where
gamma = (1 + alpha) / (1 - alpha). Each bucket stores a count.
The number of buckets is bounded by the range of values (not the
number of samples), so memory is bounded regardless of traffic
volume. Negative values are not supported (latencies are
non-negative); zero is handled as a special bucket.
§Mergeability
Two DDSketches with the same alpha can be merged by adding their
bucket counts. This enables window-to-window aggregation and
distributed merging (future: fleet-wide percentiles).
§References
- Charles Masson, Jee E. Rim, Homin K. Lee. “DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees.” arXiv:1908.10693 [cs.DB], 2019.
Structs§
- DDSketch
- A DDSketch quantile sketch with relative-error guarantees.