ExDataSketch.REQ (ExDataSketch v0.7.1)

REQ (Relative Error Quantiles) sketch for tail-accuracy quantile estimation.

The REQ sketch provides quantile estimates with a relative error guarantee on the value returned, with asymmetric accuracy that can be biased toward either high ranks (HRA) or low ranks (LRA). This makes it ideal for tail-latency analysis (p99, p99.9) and SLO monitoring.

Accuracy Modes

HRA (High Rank Accuracy, default): Better accuracy at high quantiles (p95, p99, p99.9). Use for tail-latency monitoring.
LRA (Low Rank Accuracy): Better accuracy at low quantiles (p1, p5). Use when the lower tail matters more.

How It Works

REQ uses biased compaction: in HRA mode, compaction preferentially discards low-value items, preserving more data points at the high end. This gives relative error guarantees where the error on a returned value v is proportional to v itself.

Binary State Layout (REQ1)

All multi-byte fields are little-endian.

HEADER:
  magic:           4 bytes  "REQ1"
  version:         u8       1
  flags:           u8       bit0 = hra (1=HRA, 0=LRA)
  reserved:        u16      0
  k:               u32 LE   accuracy parameter
  n:               u64 LE   total count
  min_val:         f64 LE   (NaN sentinel for empty)
  max_val:         f64 LE   (NaN sentinel for empty)
  num_levels:      u8
  compaction_bits: ceil(num_levels/8) bytes
  level_sizes:     num_levels x u32 LE
  items:           sum(level_sizes) x f64 LE

Options

:k - accuracy parameter, positive integer (default: 12). Larger values give better accuracy but use more memory.
:hra - high rank accuracy mode, boolean (default: true).
:backend - backend module (default: ExDataSketch.Backend.Pure).

Merge Properties

REQ merge is associative and commutative. Both sketches must have the same HRA/LRA mode to merge.

Summary

Types

t()

Functions

cdf(req, split_points)

Returns the CDF at the given split points.

count(req)

Returns the total number of items inserted into the sketch.

deserialize(binary)

Deserializes an EXSK binary into a REQ sketch.

from_enumerable(enumerable, opts \\ [])

Creates a new REQ sketch from an enumerable of numeric items.

max_value(req)

Returns the maximum value seen by the sketch, or nil if empty.

merge(sketch, req)

Merges two REQ sketch instances.

merge_many(sketches)

Merges a non-empty enumerable of REQ sketch instances into one.

merger(opts \\ [])

Returns a 2-arity merge function suitable for combining sketches.

min_value(req)

Returns the minimum value seen by the sketch, or nil if empty.

new(opts \\ [])

Creates a new REQ sketch.

pmf(req, split_points)

Returns the PMF at the given split points.

quantile(req, rank)

Returns the approximate value at the given normalized rank.

quantiles(sketch, ranks)

Returns approximate values at multiple normalized ranks.

rank(req, value)

Returns the approximate normalized rank of a given value.

reducer()

Returns a 2-arity reducer function suitable for Enum.reduce/3.

serialize(req)

Serializes the sketch to the ExDataSketch-native EXSK binary format.

size_bytes(req)

Returns the size of the sketch state in bytes.

update(sketch, value)

Updates the sketch with a single numeric value.

update_many(sketch, items)

Updates the sketch with multiple numeric values in a single pass.

Types

t()

@type t() :: %ExDataSketch.REQ{backend: module(), opts: keyword(), state: binary()}

Functions

cdf(req, split_points)

@spec cdf(t(), [number()]) :: [float()] | nil

Returns the CDF at the given split points.

Given split points [s1, s2, ..., sm], returns [rank(s1), rank(s2), ..., rank(sm)]. Returns nil if the sketch is empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many(1..100)
iex> cdf = ExDataSketch.REQ.cdf(sketch, [25.0, 75.0])
iex> length(cdf)
2

count(req)

@spec count(t()) :: non_neg_integer()

Returns the total number of items inserted into the sketch.

Examples

iex> ExDataSketch.REQ.new() |> ExDataSketch.REQ.count()
0

deserialize(binary)

@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}

Deserializes an EXSK binary into a REQ sketch.

Returns {:ok, sketch} on success or {:error, reason} on failure.

Examples

iex> ExDataSketch.REQ.deserialize(<<"invalid">>)
{:error, %ExDataSketch.Errors.DeserializationError{message: "deserialization failed: invalid magic bytes, expected EXSK"}}

from_enumerable(enumerable, opts \\ [])

@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: t()

Creates a new REQ sketch from an enumerable of numeric items.

Examples

iex> sketch = ExDataSketch.REQ.from_enumerable([1.0, 2.0, 3.0], k: 12)
iex> ExDataSketch.REQ.count(sketch)
3

max_value(req)

@spec max_value(t()) :: float() | nil

Returns the maximum value seen by the sketch, or nil if empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many([3.0, 1.0, 2.0])
iex> ExDataSketch.REQ.max_value(sketch)
3.0

merge(sketch, req)

@spec merge(t(), t()) :: t()

Merges two REQ sketch instances.

Both sketches must have the same HRA/LRA mode. The result is a sketch whose quantile estimates approximate the union of both input multisets.

Raises ExDataSketch.Errors.IncompatibleSketchesError if the sketches have different modes.

Examples

iex> a = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many([1.0, 2.0])
iex> b = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many([3.0, 4.0])
iex> merged = ExDataSketch.REQ.merge(a, b)
iex> ExDataSketch.REQ.count(merged)
4

merge_many(sketches)

@spec merge_many(Enumerable.t()) :: t()

Merges a non-empty enumerable of REQ sketch instances into one.

Raises Enum.EmptyError if the enumerable is empty.

Examples

iex> sketches = Enum.map(1..3, fn i ->
...>   ExDataSketch.REQ.new() |> ExDataSketch.REQ.update(i * 1.0)
...> end)
iex> merged = ExDataSketch.REQ.merge_many(sketches)
iex> ExDataSketch.REQ.count(merged)
3

merger(opts \\ [])

@spec merger(keyword()) :: (t(), t() -> t())

Returns a 2-arity merge function suitable for combining sketches.

Examples

iex> is_function(ExDataSketch.REQ.merger(), 2)
true

min_value(req)

@spec min_value(t()) :: float() | nil

Returns the minimum value seen by the sketch, or nil if empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many([3.0, 1.0, 2.0])
iex> ExDataSketch.REQ.min_value(sketch)
1.0

new(opts \\ [])

@spec new(keyword()) :: t()

Creates a new REQ sketch.

Options

:k - accuracy parameter, positive integer (default: 12).
:hra - high rank accuracy mode (default: true).
:backend - backend module (default: ExDataSketch.Backend.Pure).

Examples

iex> sketch = ExDataSketch.REQ.new(k: 12, hra: true)
iex> sketch.opts
[k: 12, hra: true]
iex> ExDataSketch.REQ.count(sketch)
0

pmf(req, split_points)

@spec pmf(t(), [number()]) :: [float()] | nil

Returns the PMF at the given split points.

Given split points [s1, s2, ..., sm], returns m+1 values representing the approximate fraction of items in each interval. Returns nil if empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many(1..100)
iex> pmf = ExDataSketch.REQ.pmf(sketch, [50.0])
iex> length(pmf)
2

quantile(req, rank)

@spec quantile(t(), float()) :: float() | nil

Returns the approximate value at the given normalized rank.

The rank must be in the range [0.0, 1.0], where 0.0 is the minimum and 1.0 is the maximum. Returns nil if the sketch is empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many(1..100)
iex> median = ExDataSketch.REQ.quantile(sketch, 0.5)
iex> is_float(median)
true

quantiles(sketch, ranks)

@spec quantiles(t(), [float()]) :: [float() | nil]

Returns approximate values at multiple normalized ranks.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many(1..100)
iex> [q25, q50, q75] = ExDataSketch.REQ.quantiles(sketch, [0.25, 0.5, 0.75])
iex> q25 < q50 and q50 < q75
true

rank(req, value)

@spec rank(t(), number()) :: float() | nil

Returns the approximate normalized rank of a given value.

The rank is the fraction of items in the sketch that are less than or equal to the given value. Returns nil if the sketch is empty.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many(1..100)
iex> r = ExDataSketch.REQ.rank(sketch, 50.0)
iex> is_float(r)
true

reducer()

@spec reducer() :: (number(), t() -> t())

Returns a 2-arity reducer function suitable for Enum.reduce/3.

Examples

iex> is_function(ExDataSketch.REQ.reducer(), 2)
true

serialize(req)

@spec serialize(t()) :: binary()

Serializes the sketch to the ExDataSketch-native EXSK binary format.

Examples

iex> sketch = ExDataSketch.REQ.new()
iex> binary = ExDataSketch.REQ.serialize(sketch)
iex> <<"EXSK", _rest::binary>> = binary
iex> byte_size(binary) > 0
true

size_bytes(req)

@spec size_bytes(t()) :: non_neg_integer()

Returns the size of the sketch state in bytes.

Examples

iex> sketch = ExDataSketch.REQ.new()
iex> ExDataSketch.REQ.size_bytes(sketch) > 0
true

update(sketch, value)

@spec update(t(), number()) :: t()

Updates the sketch with a single numeric value.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update(42.0)
iex> ExDataSketch.REQ.count(sketch)
1

update_many(sketch, items)

@spec update_many(t(), Enumerable.t()) :: t()

Updates the sketch with multiple numeric values in a single pass.

Examples

iex> sketch = ExDataSketch.REQ.new() |> ExDataSketch.REQ.update_many([1.0, 2.0, 3.0])
iex> ExDataSketch.REQ.count(sketch)
3