DDSketch Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])

Introduction

ExDataSketch.DDSketch maps every value into a logarithmically-spaced bucket (index = log(value) / log(gamma), where gamma is derived from alpha) and just counts how many values landed in each bucket. Because bucket boundaries are geometric rather than linear, every bucket represents the same relative width regardless of where it sits in the range -- which gives a guaranteed relative error on the value, not the rank. A query for quantile q returns a value v such that the true value v' satisfies v' * (1 - alpha) <= v <= v' * (1 + alpha) -- the same relative accuracy whether you're looking at a 2ms value or a 20,000ms one:

flowchart LR
    A[value] --> B["index =\nlog(value) / log(gamma)"]
    B --> C["buckets[index] += 1"]
    C --> D["quantile query:\nwalk buckets by rank"]
    D --> E["value = geometric\nmidpoint of bucket"]

Use it for: latency/telemetry percentiles spanning several orders of magnitude, where "off by 1ms" matters a lot at the low end and not at all at the high end -- SLO/SLA tracking that needs the same accuracy promise at p50 and at p99.9, not just wherever most of the mass sits.

Don't use it for: negative values (rejected outright -- zero is handled separately via a dedicated zero_count, but negative inputs aren't representable); data with a narrow, known range where ExDataSketch.KLL's uniform rank error would use less memory for comparable effective precision; exact percentiles where correctness must be exact.

What it buys you: at the library default alpha: 0.01 (1% relative error), a real 1,000,000-value latency distribution spanning roughly 1ms-5000ms measured ~3.4 KB -- bucket count scales with the range of magnitudes observed, not the item count, so a wider dynamic range costs more buckets but more data at the same range costs nothing extra:

Approach	Memory (1M values, ~1-5000ms range)	Guarantee
Exact (sorted array of `f64`)	~7.6 MB	Exact
`ExDataSketch.DDSketch` (alpha=0.01)	~3.4 KB	+-1% relative value error, everywhere

Sample data (cached locally)

1,000,000 operation durations (ms) spanning several orders of magnitude: fast API calls (~1-50ms), medium DB queries (~50-500ms), and rare slow batch jobs (~10,000-100,000ms). DDSketch only accepts non-negative values.

durations = ExDataSketch.SampleData.ddsketch_durations()
sorted = Enum.sort(durations)
IO.puts("#{length(durations)} duration samples ready, spanning #{Float.round(List.first(sorted), 2)}ms to #{Float.round(List.last(sorted), 0)}ms")

Basic usage

alias ExDataSketch.DDSketch

sketch = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(durations)

DDSketch.quantiles(sketch, [0.5, 0.9, 0.99, 0.999])

Relative accuracy at both ends of the scale

Compare DDSketch's error at a small quantile value against a large one -- both should be within alpha, unlike a fixed absolute-error sketch, where the large value's error would dwarf the small one's:

exact_percentile = fn p ->
  # Matches ExDataSketch.DDSketch.quantile/2's own rank convention exactly
  # (target = p * n, returns the value once cumulative count reaches that
  # target -- effectively the target-th smallest item, 1-indexed) rather
  # than an independently-chosen indexing scheme. A plain
  # `Enum.at(sorted, round(p * n))` is 0-indexed and off by one rank from
  # what DDSketch itself targets; that one-rank gap is usually
  # inconsequential, but exactly at a bucket boundary it can land the
  # "exact" reference value in the *next* bucket over from the one
  # DDSketch correctly answered for, making a correct estimate look like
  # it exceeded `alpha` when it didn't.
  rank = max(1, round(p * length(sorted)))
  Enum.at(sorted, min(rank - 1, length(sorted) - 1))
end

# p50 is in the "fast API calls" range (small values); p99.5 is in the
# "slow batch jobs" range (large values) -- three orders of magnitude apart.
for p <- [0.5, 0.995] do
  exact = exact_percentile.(p)
  estimate = DDSketch.quantile(sketch, p)
  relative_error = abs(estimate - exact) / exact * 100
  IO.puts("p#{p}: exact=#{Float.round(exact, 2)}ms, estimate=#{Float.round(estimate, 2)}ms, relative error=#{Float.round(relative_error, 2)}%")
end

Both relative errors should be at most alpha * 100 = 1%, regardless of the three-orders-of-magnitude gap between the two values -- that's the DDSketch guarantee, and it's a tight bound (achieved at a bucket's edges), not a "usually comfortably inside" one, so don't be surprised to see values sitting close to 1% rather than well under it.

Sizing: alpha trade-off

for alpha <- [0.05, 0.01, 0.005, 0.001] do
  s = DDSketch.new(alpha: alpha) |> DDSketch.update_many(durations)
  estimate = DDSketch.quantile(s, 0.99)
  exact = exact_percentile.(0.99)
  error_pct = abs(estimate - exact) / exact * 100
  IO.puts("alpha=#{alpha} (#{DDSketch.size_bytes(s)} bytes): p99 error=#{Float.round(error_pct, 2)}%")
end

count, min, max

min_value/1/max_value/1 track the raw minimum/maximum ever inserted at full precision -- independent of alpha and of the log-scale bucket machinery entirely. With 900,000 samples drawn uniformly from [0, 50) for the "fast API calls" bucket, the smallest of that many draws lands well under 0.001ms (expected order of magnitude ~50 / 900_000), so don't be surprised to see Min: 0.0ms if you round to only 3 decimal places -- it's rounding display precision, not the sketch losing the value:

IO.puts("Count: #{DDSketch.count(sketch)}")
IO.puts("Min: #{DDSketch.min_value(sketch)}ms (exact, not rounded)")
IO.puts("Max: #{Float.round(DDSketch.max_value(sketch), 0)}ms")

Merging

half = div(length(durations), 2)
{first_half, second_half} = Enum.split(durations, half)

worker_a = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(first_half)
worker_b = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(second_half)

merged = DDSketch.merge(worker_a, worker_b)
IO.puts("Merged p99: #{Float.round(DDSketch.quantile(merged, 0.99), 1)}ms")

Serialization

binary = DDSketch.serialize(sketch)
{:ok, restored} = DDSketch.deserialize(binary)
IO.puts("Round-tripped p50: #{Float.round(DDSketch.quantile(restored, 0.5), 2)}ms")