DDSketch Tutorial

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

Introduction

ExDataSketch.DDSketch estimates quantiles like ExDataSketch.KLL, but with a different accuracy guarantee: 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. That makes it well suited to latency/telemetry data that spans several orders of magnitude, where "off by 1ms" matters a lot at the low end and not at all at the high end.

Sample data (cached locally)

cache_path = Path.join(System.tmp_dir!(), "ex_data_sketch_livebook_cache/ddsketch_sample.bin")

durations =
  if File.exists?(cache_path) do
    IO.puts("Loading cached sample data from #{cache_path}")
    cache_path |> File.read!() |> :erlang.binary_to_term()
  else
    IO.puts("Generating sample data (this takes a few seconds)...")

    # 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 =
      for _ <- 1..1_000_000 do
        case :rand.uniform(1000) do
          n when n <= 900 -> :rand.uniform() * 50
          n when n <= 990 -> 50 + :rand.uniform() * 450
          _ -> 10_000 + :rand.uniform() * 90_000
        end
      end

    File.mkdir_p!(Path.dirname(cache_path))
    File.write!(cache_path, :erlang.term_to_binary(durations))
    durations
  end

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")