Computing accurate percentiles with DDSketch | Datadog

Datadog’s post explains why accurately computing percentiles is difficult when monitoring large-scale, distributed systems. Traditional approaches either require retaining every observation or sacrifice accuracy through fixed-size summaries, especially for long-tailed data such as request latency. DDSketch addresses this by providing mergeable percentile estimates with a guaranteed relative-error bound and memory usage that remains effectively constant.

Why Percentiles Matter

• Averages can hide slow requests and do not describe the tail of a distribution.
• Percentiles such as p95, p99, and p99.9 are more useful for measuring latency and reliability.
• Monitoring systems must calculate these values from enormous numbers of observations across many hosts and services.
• Storing every measurement is too expensive, while calculating percentiles independently on each machine and averaging the results is mathematically incorrect.

Limitations of Common Approaches

• Exact percentile calculation requires sorting or retaining all values, which is impractical for high-volume metrics.
• Histograms use predefined buckets, making their accuracy dependent on bucket boundaries.
• Fixed-width buckets are inefficient for distributions spanning several orders of magnitude:
  • Small values may require fine-grained buckets.
  • Large values may require a huge number of buckets.
• Many quantile sketches optimize for rank accuracy, but a small rank error can still produce a large value error in heavy-tailed distributions.
• Summaries must also be mergeable so that data collected from multiple agents can be combined without losing their accuracy guarantees.

DDSketch’s Logarithmic Mapping

• DDSketch groups values into logarithmically spaced bins rather than equally sized intervals.
• Values close together near zero receive finer absolute resolution, while larger values receive wider buckets.
• Each value is mapped to a key based on its logarithm:
  • Positive and negative values are handled separately.
  • Zero and values sufficiently close to zero use a dedicated zero bucket.
• A representative value is chosen for each bucket, typically using the bucket’s geometric center.
• Because adjacent buckets have a fixed ratio, the estimated value is bounded by a predictable relative error rather than a fixed absolute error.

Relative-Error Guarantees

• DDSketch is configured with a target relative accuracy, such as 1%.
• Its logarithmic base is selected so that the returned quantile is within that relative-error bound of the true value.
• Relative error is particularly appropriate for latency data:
  • An error of a few milliseconds matters greatly for a 10 ms request.
  • The same absolute error is much less significant for a 10-second request.
• The sketch preserves accuracy across a wide range of values without requiring a proportional increase in the number of buckets.

Distributed Aggregation and Memory Use

• DDSketches can be merged by adding the bucket counts from separate sketches.
• This allows agents, hosts, containers, and regional services to aggregate measurements into a global percentile.
• Merging does not require access to the original observations.
• The sketch stores counts rather than individual values, substantially reducing memory and network costs.
• Datadog also describes bounded-memory variants that collapse older or less significant bins when necessary, allowing sketches to maintain a fixed storage limit while retaining useful tail information.

Practical Trade-offs

• Higher accuracy requires more buckets and therefore more memory.
• Lower accuracy reduces resource usage but produces wider estimates.
• The choice of relative accuracy should reflect the metric’s operational needs rather than defaulting to the smallest possible error.
• Implementations must account for negative values, zeros, very small values, and values outside the normal range.
• Accurate percentile reporting depends not only on the sketch algorithm but also on correct aggregation and consistent configuration across producers.

DDSketch is therefore a practical choice for observability systems that need scalable, mergeable, and predictable percentile calculations. Its logarithmic buckets and relative-error guarantees make it especially well suited to latency and other long-tailed measurements where fixed-width histograms or rank-based approximations can be misleading.