DDSketch Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
])

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 ->
  idx = min(round(p * length(sorted)), length(sorted) - 1)
  Enum.at(sorted, idx)
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 well under alpha * 100 = 1%, regardless of the three-orders-of-magnitude gap between the two values.

Sizing: alpha trade-off

for alpha <- [0.05, 0.01, 0.005] 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

IO.puts("Count: #{DDSketch.count(sketch)}")
IO.puts("Min: #{Float.round(DDSketch.min_value(sketch), 3)}ms")
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")