Limen.Sketch.CountMin (limen v0.2.1)

Copy Markdown View Source

A lock-free Count-Min Sketch on :atomics.

Estimates how many times each key was counted using a fixed depth × width grid of counters, whatever the number of distinct keys. Estimates never undercount; with N total increments they overcount by at most e / width × N with probability 1 - e^-depth.

Row indexes are derived from two :erlang.phash2/2 hashes with the Kirsch–Mitzenmacher construction, so an update costs two hashes and depth atomic increments regardless of depth.

Summary

Types

t()

Functions

add(count_min, key, count \\ 1)

Adds count to key and returns its new estimate.

estimate(count_min, key)

Returns the estimated count for key.

memory(count_min)

Memory used by the counters, in bytes.

new(width, depth)

Creates a sketch with width columns and depth rows.

new_with_error(epsilon, delta)

Creates a sketch sized for an error of at most epsilon × N with probability 1 - delta.

reset(count_min)

Resets every counter to zero.

Types

t()

@type t() :: %Limen.Sketch.CountMin{
  depth: pos_integer(),
  ref: :atomics.atomics_ref(),
  width: pos_integer()
}

Functions

add(count_min, key, count \\ 1)

@spec add(t(), term(), pos_integer()) :: non_neg_integer()

Adds count to key and returns its new estimate.

estimate(count_min, key)

@spec estimate(t(), term()) :: non_neg_integer()

Returns the estimated count for key.

memory(count_min)

@spec memory(t()) :: non_neg_integer()

Memory used by the counters, in bytes.

new(width, depth)

@spec new(pos_integer(), pos_integer()) :: t()

Creates a sketch with width columns and depth rows.

new_with_error(epsilon, delta)

@spec new_with_error(float(), float()) :: t()

Creates a sketch sized for an error of at most epsilon × N with probability 1 - delta.

reset(count_min)

@spec reset(t()) :: :ok

Resets every counter to zero.

Runs in O(width × depth) and is not atomic: concurrent updates may land on either side of the reset. Limen only resets sketches of windows no request writes to any more.