Mobius.DDSketch (Mobius v0.8.0)

Copy Markdown View Source

A sparse, mergeable quantile sketch with bounded relative error.

Properties Mobius relies on:

  • Ingress-time aggregation. Each value maps to a bin counter at observation time — no time-bucketing.
  • Mergeable. Bin counters sum across windows, so window queries are bin-by-bin subtraction of two snapshots.
  • Bounded memory. Bin count grows with the diversity of observed magnitudes, not with uptime.
  • Clock-invariant. Bin indices are value-derived; wall-clock drift can't corrupt the structure.

Each populated bin is one integer counter:

%Mobius.DDSketch{
  relative_accuracy: 0.1,
  zero_count: 12,
  positive_bins: %{42 => 3, 43 => 17},
  negative_bins: %{}
}

bins/1 projects to a list of {bin_key, count} pairs for storage, from_bins/2 reconstructs.

Configuration

Pick :relative_accuracy (α): the relative error bound on any quantile estimate. Default 0.1 (±10%). Smaller α produces more bins. α can't change after the sketch has data — bin indices depend on it.

Values below :min_indexable_value fold into the zero bucket. Values above :max_indexable_value clamp to the top bin (default) or drop (:on_overflow: :drop).

Summary

Types

Index of a positive or negative bin. Derived from the value's magnitude and the sketch's :relative_accuracy.

An ETS-friendly identifier for one bin counter.

Sparse map from bin index to observation count.

What to do with an observation whose magnitude exceeds :max_indexable_value.

Point-in-time capture of one sketch's bin state: a tuple of {positive_bins, negative_bins, zero_count}.

t()

Functions

The populated bins as {representative_value, count} pairs, ascending by value.

Map a value to the bin_key it would land in.

Project the sketch to a list of {bin_key, count} pairs.

Number of observations whose value is strictly greater than threshold.

Count of observations whose value is strictly less than threshold.

Number of observations whose value lies in [lo, hi] (inclusive).

Compute the bin-by-bin difference later - earlier.

Whether this sketch has any observations.

Reconstruct a sketch from a list of {bin_key, count} pairs.

Reconstruct a sketch directly from a stored snapshot.

Insert a single observation into the sketch.

Insert count observations of value.

Largest value estimate in the sketch, or nil if empty.

Merge two sketches into one by summing bin counters.

Smallest value estimate in the sketch, or nil if empty.

Create a new, empty sketch.

Estimate the value at quantile q (0.0–1.0).

Batch version of quantile/2. Returns %{q => value}.

Total observation count across all bins.

Validate and normalize sketch options without raising.

Types

bin_index()

@type bin_index() :: integer()

Index of a positive or negative bin. Derived from the value's magnitude and the sketch's :relative_accuracy.

bin_key()

@type bin_key() ::
  {:hist, :pos, bin_index()} | {:hist, :neg, bin_index()} | {:hist, :zero}

An ETS-friendly identifier for one bin counter.

bin_map()

@type bin_map() :: %{required(bin_index()) => pos_integer()}

Sparse map from bin index to observation count.

on_overflow()

@type on_overflow() :: :clamp | :drop

What to do with an observation whose magnitude exceeds :max_indexable_value.

  • :clamp — map the value to the top bin (saturate). The histogram keeps counting; quantiles above the configured range collapse to the top bin's estimator. This is the default and matches how Prometheus and HdrHistogram handle the tail.
  • :drop — silently skip the observation. Use only when you would rather have an under-count than let outliers register at the top of the distribution.

snapshot()

@type snapshot() ::
  {%{required(integer()) => pos_integer()},
   %{required(integer()) => pos_integer()}, non_neg_integer()}

Point-in-time capture of one sketch's bin state: a tuple of {positive_bins, negative_bins, zero_count}.

This is the per-metric histogram payload stored in each Mobius RRD scrape. At rest it is encoded with :erlang.term_to_binary/1 — one opaque binary per metric series — so the retained snapshots stay compact and off the owning process heap.

t()

@type t() :: %Mobius.DDSketch{
  gamma: float(),
  log_gamma: float(),
  max_indexable_value: float(),
  max_positive_index: integer(),
  min_indexable_value: float(),
  negative_bins: bin_map(),
  on_overflow: on_overflow(),
  positive_bins: bin_map(),
  relative_accuracy: float(),
  zero_count: non_neg_integer()
}

Functions

bin_estimates(sketch)

@spec bin_estimates(t()) :: [{float(), pos_integer()}]

The populated bins as {representative_value, count} pairs, ascending by value.

This is the same bin walk quantile/1 uses, exposed so callers can read a sketch's distribution without coupling to the internal bin-key format or the gamma field.

Ordering is ascending by representative value. The representative value of a positive bin of index k is the canonical DDSketch within-bin estimator 2·gamma^k / (gamma + 1); the zero bucket reports 0.0, and negative bins are the mirrored negatives of their positive-index counterparts. Counts are exact integers; the representative values carry the sketch's relative-accuracy error (each is within relative_accuracy of every value in its bin).

iex> sketch = Mobius.DDSketch.new()
iex> sketch = Enum.reduce([10.0, 10.0, 1000.0], sketch, &Mobius.DDSketch.insert(&2, &1))
iex> [{v1, 2}, {_v2, 1}] = Mobius.DDSketch.bin_estimates(sketch)
iex> abs(v1 - 10.0) / 10.0 <= sketch.relative_accuracy
true

bin_key_for_value(sketch, value)

@spec bin_key_for_value(t(), number()) :: bin_key() | :drop

Map a value to the bin_key it would land in.

Used by ingress to know which ETS row to increment. Returns the top-bin key for over-max values when :on_overflow is :clamp (the default), or :drop when :on_overflow is :drop.

bins(sketch)

@spec bins(t()) :: [{bin_key(), pos_integer()}]

Project the sketch to a list of {bin_key, count} pairs.

Each entry maps onto one ETS counter row. The ordering of the returned list is unspecified.

count_above(sketch, threshold)

@spec count_above(t(), number()) :: non_neg_integer()

Number of observations whose value is strictly greater than threshold.

count_below(sketch, threshold)

@spec count_below(t(), number()) :: non_neg_integer()

Count of observations whose value is strictly less than threshold.

For SLO-style queries — "how many requests met the 200 ms budget?"

count_between(sketch, lo, hi)

@spec count_between(t(), number(), number()) :: non_neg_integer()

Number of observations whose value lies in [lo, hi] (inclusive).

delta(later, earlier)

@spec delta(t(), t()) :: {:ok, t()} | {:error, :reset}

Compute the bin-by-bin difference later - earlier.

Used to materialise a window sketch from two RRD snapshots. Both sketches must share the same :relative_accuracy (mismatched accuracies raise — that is a caller bug). Bins that net to zero drop out.

Returns {:ok, sketch}, or {:error, :reset} when any per-bin delta is negative. Counters are cumulative and monotonically nondecreasing within a series, so a negative delta means the accumulator was lost or rebuilt between the two snapshots — corrupt counter persistence or a sketch-config change, not a routine reboot (counters are persisted and restored intact across reboots). Callers decide how to degrade: skip the interval, or fall back to later alone (everything observed since the reset).

empty?(sketch)

@spec empty?(t()) :: boolean()

Whether this sketch has any observations.

from_bins(opts, bins)

@spec from_bins(keyword(), [{bin_key(), non_neg_integer()}]) :: t()

Reconstruct a sketch from a list of {bin_key, count} pairs.

opts are passed to new/1 and must match the original sketch's :relative_accuracy — bin indices depend on it, so a mismatch produces wrong quantile estimates.

from_snapshot(opts, binary)

@spec from_snapshot(keyword(), snapshot() | binary()) :: t()

Reconstruct a sketch directly from a stored snapshot.

Accepts either the raw snapshot/0 tuple or its :erlang.term_to_binary/1 encoding (the at-rest form).

This is the cheap path used by window queries: the snapshot already mirrors the sketch's internal bin layout, so a single struct update produces the sketch — no per-bin work. opts must match the original sketch's configuration (most importantly :relative_accuracy).

insert(sketch, value)

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

Insert a single observation into the sketch.

insert_n(sketch, value, count)

@spec insert_n(t(), number(), pos_integer()) :: t()

Insert count observations of value.

For batched writes or reconstructing a sketch from already-aggregated counts.

max(sketch)

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

Largest value estimate in the sketch, or nil if empty.

merge(s1, s2)

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

Merge two sketches into one by summing bin counters.

Both sketches must share the same :relative_accuracy. Other sketch parameters are taken from the first argument.

min(sketch)

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

Smallest value estimate in the sketch, or nil if empty.

new(opts \\ [])

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

Create a new, empty sketch.

Options:

  • :relative_accuracy — α, the bound on relative quantile error. Number in (0, 1). Defaults to 0.1.
  • :min_indexable_value — values whose magnitude is below this fold into the zero bucket. Defaults to 1.0e-9.
  • :max_indexable_value — values whose magnitude exceeds this clamp to the top bin (or drop). Defaults to 1.0e18; tighten to cap bin growth.
  • :on_overflow — :clamp (default) or :drop. See on_overflow/0.

Integer values are accepted and cast to floats. Raises ArgumentError on invalid options; use validate_opts/1 for a non-raising check.

quantile(sketch, q)

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

Estimate the value at quantile q (0.0–1.0).

Returns nil for an empty sketch. The returned value is within :relative_accuracy of every value that could have landed in the chosen bin.

quantiles(sketch, qs)

@spec quantiles(t(), [float()]) :: %{required(float()) => float() | nil}

Batch version of quantile/2. Returns %{q => value}.

Walks the ordered entry list once per quantile rather than rebuilding it for each call — cheaper than repeated quantile/2 calls when the bin set is large.

total_count(sketch)

@spec total_count(t()) :: non_neg_integer()

Total observation count across all bins.

validate_opts(opts)

@spec validate_opts(term()) :: {:ok, keyword()} | {:error, String.t()}

Validate and normalize sketch options without raising.

Integer values for :relative_accuracy, :min_indexable_value, and :max_indexable_value are cast to floats. Returns the normalized option list with every option filled in, or {:error, message} describing the first problem found — including unknown option keys, which would otherwise be silently ignored and leave a misconfiguration undetected.