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}.
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
@type bin_index() :: integer()
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.
@type bin_map() :: %{required(bin_index()) => pos_integer()}
Sparse map from bin index to observation count.
@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.
@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.
@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
@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
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.
@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.
@spec count_above(t(), number()) :: non_neg_integer()
Number of observations whose value is strictly greater than 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?"
@spec count_between(t(), number(), number()) :: non_neg_integer()
Number of observations whose value lies in [lo, hi] (inclusive).
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).
Whether this sketch has any observations.
@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.
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 a single observation into the sketch.
@spec insert_n(t(), number(), pos_integer()) :: t()
Insert count observations of value.
For batched writes or reconstructing a sketch from already-aggregated counts.
Largest value estimate in the sketch, or nil if empty.
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.
Smallest value estimate in the sketch, or nil if empty.
Create a new, empty sketch.
Options:
:relative_accuracy— α, the bound on relative quantile error. Number in (0, 1). Defaults to0.1.:min_indexable_value— values whose magnitude is below this fold into the zero bucket. Defaults to1.0e-9.:max_indexable_value— values whose magnitude exceeds this clamp to the top bin (or drop). Defaults to1.0e18; tighten to cap bin growth.:on_overflow—:clamp(default) or:drop. Seeon_overflow/0.
Integer values are accepted and cast to floats. Raises ArgumentError
on invalid options; use validate_opts/1 for a non-raising check.
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.
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.
@spec total_count(t()) :: non_neg_integer()
Total observation count across all bins.
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.