Computing accurate percentiles with DDSketch
DDSketch was created to compute accurate percentiles from massive, distributed monitoring datasets without storing every value. The post explains why averages and exact percentile calculations are impractical for latency data, and why existing quantile sketches produced too much noise—especially at high percentiles. DDSketch addresses these needs through compact, approximate, and mergeable data structures. ## Why Percentiles Matter for Monitoring - Application latency strongly affects user experience, sales, and revenue. - Averages can hide extreme values and fail to represent users with the worst experiences. - High percentiles, such as the 99th percentile, provide a more useful view of typical “bad” experiences while ignoring extreme outliers. ## Why Percentile Computation Is Difficult - Minima, maxima, sums, and counts can be calculated using constant memory. - Exact percentiles require retaining every value, sorting the collection, and selecting the value at the desired rank. - This approach is infeasible for streams containing millions of monitoring points. - Percentiles are also difficult to aggregate across distributed systems: - Partition-level maxima, minima, sums, and counts can be merged exactly. - Partition-level percentiles cannot determine the global percentile. - Sending all raw values across the network would eliminate the benefits of distributed aggregation. ## Quantile Sketches - Sketches compress data into smaller structures that preserve enough information to answer approximate queries. - They trade some accuracy for significantly lower memory usage. - Quantile sketches estimate percentiles without retaining every input value. - Mergeable sketches allow multiple independently generated sketches to be combined without introducing additional precision loss. - Mergeability supports distributed computation and pre-aggregation, such as processing data at individual hosts before sending it elsewhere. - Datadog initially used the Greenwald-Khanna (GK) sketch for percentile metrics and histogram generation. ## Accuracy Problems with Existing Sketches - Percentile graphs often contain noise and spikes, particularly at high percentiles. - Some variation reflects real changes in latency caused by load or network conditions. - GK approximation errors can add substantial artificial variation. - Comparisons with exact percentiles show that GK-generated errors can create spikes that do not exist in the underlying data. - Errors appear especially pronounced for the 99th percentile, reducing the reliability and usefulness of monitoring visualizations. ## Rank-Error Versus Relative-Error Guarantees - Sketch algorithms generally expose a parameter controlling the accuracy–memory trade-off. - Higher accuracy requires a larger sketch. - The post identifies the need for percentile approximations whose errors are appropriate for noisy, large-scale monitoring data, motivating the design of DDSketch. DDSketch is presented as a purpose-built solution for monitoring systems: it aims to provide accurate percentile estimates with compact storage and support for lossless merging across distributed data sources.
Read original(opens in new tab)