REQ (Relative Error Quantiles) Tutorial

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

Introduction

ExDataSketch.REQ uses the same level-and-compaction shape as ExDataSketch.KLL, but with one deliberate asymmetry: compaction doesn't discard a random half uniformly -- it prefers to discard the half that matters least. In HRA mode (High Rank Accuracy, the default), that means preferentially discarding low-value detail and keeping high-quantile detail; LRA does the opposite. The result is a sketch that spends its entire error budget where you told it to care, instead of spreading it evenly like KLL does:

flowchart LR
    A[value] --> B["level 0 buffer"]
    B --> C{"level full?"}
    C -->|no| D[stored]
    C -->|yes| E["HRA: discard low half,\nkeep high-rank detail"]
    E --> F["level 1 buffer\n(promoted at 2x weight)"]
    F --> G["... more levels"]
    G --> H["quantile/rank query:\nweighted merge across levels"]

Use it for: SLO/tail-latency monitoring where "how bad is our worst 1%" (p99, p99.9) matters far more than the median -- HRA concentrates accuracy exactly there. LRA does the mirror-image job for low-tail questions (p1, p5).

Don't use it for: anywhere you need uniform accuracy across the whole distribution, median included -- that's what ExDataSketch.KLL's unbiased compaction is for; REQ's tail accuracy is bought by deliberately sacrificing accuracy at the other end. Also worth knowing: unlike most families here, REQ has no Rust NIF acceleration at all (see its moduledoc) -- fine at REQ's typically small k, but a factor at very high ingest rates.

What it buys you: aggressive biased compaction makes REQ very compact at its typically-small k. A k: 12, HRA sketch (the library default) over 1,000,000 latency samples measured 524 bytes -- against ~7.6 MB to store every raw value, roughly 14,500x smaller -- while still resolving p99.9 accurately, which is the one number a uniform-error sketch of similar size would blur:

Approach	Memory (1M samples)	Where accuracy lives
Exact (sorted array of `f64`)	~7.6 MB	Everywhere (exact)
`ExDataSketch.REQ` (k=12, HRA)	524 bytes	Concentrated at high ranks

Sample data (cached locally)

1,000,000 latencies (ms): tight and boring in the bulk (10-30ms), with a long, important tail (a few requests taking seconds) -- exactly the shape where p99.9 accuracy matters more than p50 accuracy.

latencies = ExDataSketch.SampleData.req_latencies()
sorted = Enum.sort(latencies)
IO.puts("#{length(latencies)} latency samples ready")

Basic usage (HRA mode, the default)

alias ExDataSketch.REQ

sketch = REQ.new(k: 12, hra: true) |> REQ.update_many(latencies)

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

HRA vs LRA: where the accuracy budget goes

Build the same data into both modes and compare error at a low quantile (p10) against a high one (p99.9) -- HRA should be visibly more accurate at p99.9 and less accurate at p10; LRA the reverse.

This sample is a hard case for a small k: 99.9% of it is squeezed into just 20 distinct discrete values (11-30ms), with the "important" tail (500-5000ms) only 0.1% of the data. At k: 12 (REQ's default) there isn't enough retained resolution left for the HRA/LRA bias to show up at all -- both modes converge to nearly the same (poor) answer at p99.9. Push k up to 800 and the intended asymmetry reappears clearly:

exact_percentile = fn p ->
  idx = min(round(p * length(sorted)), length(sorted) - 1)
  Enum.at(sorted, idx)
end

hra_sketch = REQ.new(k: 800, hra: true) |> REQ.update_many(latencies)
lra_sketch = REQ.new(k: 800, hra: false) |> REQ.update_many(latencies)

for {label, s} <- [{"HRA", hra_sketch}, {"LRA", lra_sketch}] do
  IO.puts("== #{label} ==")

  for p <- [0.1, 0.999] do
    exact = exact_percentile.(p)
    estimate = REQ.quantile(s, p)
    error_pct = abs(estimate - exact) / exact * 100
    IO.puts("  p#{p}: exact=#{Float.round(exact, 2)}, estimate=#{Float.round(estimate, 2)}, error=#{Float.round(error_pct, 1)}%")
  end
end

HRA's p99.9 error should now be clearly smaller than LRA's (LRA barely escapes the 11-30ms bulk at all, typically still reporting something near 30), and LRA's p10 error should be clearly smaller than HRA's -- the intended trade-off, showing up as designed. Don't expect HRA's own p99.9 error to be small in absolute terms, though: p99.9 sits right at the boundary between the dense bulk and the sparse tail, the same kind of density cliff covered in ExDataSketch.KLL's moduledoc -- a correctly-working sketch can still land far from the exact value there, because a tiny rank shift crosses from "extremely common" to "extremely rare" data.

rank/2, cdf/2, pmf/2

rank_at_1s = REQ.rank(sketch, 1000.0)
IO.puts("#{Float.round(rank_at_1s * 100, 2)}% of requests were under 1 second")

REQ.cdf(sketch, [50.0, 500.0, 2000.0])

count, min, max

IO.puts("Count: #{REQ.count(sketch)}")
IO.puts("Min: #{Float.round(REQ.min_value(sketch), 2)}ms")
IO.puts("Max: #{Float.round(REQ.max_value(sketch), 0)}ms")

Merging

Both sketches being merged must share the same :hra mode:

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

worker_a = REQ.new(k: 12, hra: true) |> REQ.update_many(first_half)
worker_b = REQ.new(k: 12, hra: true) |> REQ.update_many(second_half)

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

Serialization

binary = REQ.serialize(sketch)
{:ok, restored} = REQ.deserialize(binary)
IO.puts("Round-tripped p99: #{Float.round(REQ.quantile(restored, 0.99), 1)}ms")