Circular buffer for latency samples with percentile calculation.
Uses :queue for O(1) FIFO insertion and eviction. A sorted list is
cached on write so that percentile queries are O(1) lookups.
How it works
The buffer maintains two parallel representations of the same data:
:queue(FIFO order) — An Erlang:queuethat preserves insertion order. When the buffer is full (size equalsmax_size), the oldest element is dequeued before the new element is enqueued. This gives O(1) amortized insertion and eviction.Sorted list + tuple (value order) — A plain Elixir list kept in ascending sorted order, plus a pre-built tuple copy of that list. On each
add/2, the evicted value (if any) is removed from the sorted list via a linear scan, and the new value is inserted at its sorted position via another linear scan. The sorted list is then converted to a tuple withList.to_tuple/1.
Percentile queries use the tuple for O(1) indexed access. Given a
percentile p (0--100) and buffer size n, the index is computed as
ceil(p / 100 * n) - 1, clamped to [0, n - 1]. The value at that
index in the sorted tuple is the answer. This avoids sorting on every
query — the cost is paid once on write instead.
The trade-off is intentional: writes are O(n) due to the sorted-list maintenance, but queries are O(1). In the hedged-request use case, writes happen once per completed request while queries happen once per incoming request — so fast queries matter more.
Algorithm Complexity
| Function | Time | Space |
|---|---|---|
new/1 | O(1) | O(1) |
add/2 | O(n) where n = current buffer size — linear scan for sorted insert and (when full) sorted delete, plus O(n) List.to_tuple/1 | O(n) — queue, sorted list, and sorted tuple each hold at most max_size elements |
query/2 | O(1) — single elem/2 call on the pre-built tuple | O(1) |
Summary
Functions
Adds a sample value to the buffer, evicting the oldest if full.
Creates a new percentile buffer with the given maximum size.
Computes the given percentile (0--100) from the buffered samples.
Types
@type t() :: %Resiliency.Hedged.Percentile{ max_size: pos_integer(), samples: any(), size: non_neg_integer(), sorted: [number()], sorted_tuple: tuple() }
Circular buffer holding latency samples for percentile queries.
Functions
Adds a sample value to the buffer, evicting the oldest if full.
Parameters
buf-- aResiliency.Hedged.Percentile.t()struct representing the current buffer.value-- a number (the latency sample) to add to the buffer.
Returns
An updated Resiliency.Hedged.Percentile.t() struct with the new sample added. If the buffer was already at capacity, the oldest sample is evicted first.
Examples
iex> buf = Resiliency.Hedged.Percentile.new() |> Resiliency.Hedged.Percentile.add(42)
iex> buf.size
1
iex> buf = Resiliency.Hedged.Percentile.new(2) |> Resiliency.Hedged.Percentile.add(1) |> Resiliency.Hedged.Percentile.add(2) |> Resiliency.Hedged.Percentile.add(3)
iex> buf.size
2@spec new(pos_integer()) :: t()
Creates a new percentile buffer with the given maximum size.
Parameters
max_size-- the maximum number of latency samples the buffer will hold. Must be a positive integer. Defaults to1000.
Returns
A new Resiliency.Hedged.Percentile.t() struct with an empty sample buffer.
Raises
Raises FunctionClauseError if max_size is not a positive integer.
Examples
iex> buf = Resiliency.Hedged.Percentile.new()
iex> buf.max_size
1000
iex> buf = Resiliency.Hedged.Percentile.new(50)
iex> buf.max_size
50Computes the given percentile (0--100) from the buffered samples.
Returns nil if the buffer is empty.
Parameters
buf-- aResiliency.Hedged.Percentile.t()struct containing latency samples.p-- the percentile to compute, a number between0and100(inclusive).
Returns
The computed percentile value as a number, or nil if the buffer is empty.
Raises
Raises FunctionClauseError if p is not a number between 0 and 100.
Examples
iex> Resiliency.Hedged.Percentile.query(Resiliency.Hedged.Percentile.new(), 50)
nil
iex> buf = Enum.reduce(1..100, Resiliency.Hedged.Percentile.new(), &Resiliency.Hedged.Percentile.add(&2, &1))
iex> Resiliency.Hedged.Percentile.query(buf, 50)
50
iex> buf = Enum.reduce(1..100, Resiliency.Hedged.Percentile.new(), &Resiliency.Hedged.Percentile.add(&2, &1))
iex> Resiliency.Hedged.Percentile.query(buf, 95)
95