# `Mobius.DDSketch`
[🔗](https://github.com/mobius-home/mobius/blob/v0.8.0/lib/mobius/dd_sketch.ex#L1)

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`).

# `bin_index`

```elixir
@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`

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

An ETS-friendly identifier for one bin counter.

# `bin_map`

```elixir
@type bin_map() :: %{required(bin_index()) =&gt; pos_integer()}
```

Sparse map from bin index to observation count.

# `on_overflow`

```elixir
@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`

```elixir
@type snapshot() ::
  {%{required(integer()) =&gt; pos_integer()},
   %{required(integer()) =&gt; 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`

```elixir
@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()
}
```

# `bin_estimates`

```elixir
@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`

```elixir
@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`

```elixir
@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`

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

Number of observations whose value is strictly greater than `threshold`.

# `count_below`

```elixir
@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`

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

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

# `delta`

```elixir
@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?`

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

Whether this sketch has any observations.

# `from_bins`

```elixir
@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`

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

Reconstruct a sketch directly from a stored snapshot.

Accepts either the raw `t: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`

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

Insert a single observation into the sketch.

# `insert_n`

```elixir
@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`

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

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

# `merge`

```elixir
@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`

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

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

# `new`

```elixir
@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 `t: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`

```elixir
@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`

```elixir
@spec quantiles(t(), [float()]) :: %{required(float()) =&gt; 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`

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

Total observation count across all bins.

# `validate_opts`

```elixir
@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.

---

*Consult [api-reference.md](api-reference.md) for complete listing*
