ddskerl_bound (ddskerl v0.5.0)

View Source

DDSketch implementation in Erlang.

This implements an bounded bucket count, that is, on a degenerate case, memory consumption won't grow but lower quantiles will lose accuracy as the summary saturates.

When the number of buckets exceeds the limit, the two smallest buckets are collapsed into one and the limit is kept.

The implementation uses a local and non-shared gb_trees, and the buckets are not preallocated, but are rather created on demand, without bounds on their indexes.

Because the data structure cannot be accessed concurretly (share-nothing semantics), a good strategy would be to keep many running in parallel, and running queries over a merge.

When to use

This is a good choice when the summary is tracked by a process and updates the state through its mailbox.

For example, the following could be used as a template:

...
-behaviour(gen_server).

-spec start_link(ddskerl_bound:opts()) -> gen_server:start_ret().
start_link(Opts) ->
   gen_server:start_link(?MODULE, Opts, [{spawn_opt, [{message_queue_data, off_heap}]}]).

-spec init(ddskerl_bound:opts()) -> {ok, ddskerl_bound:ddsketch()}.
init(Opts) ->
   {ok, ddskerl_bound:new(Opts)}.

handle_call({get_quantile, Q}, _From, Sketch) ->
   {reply, ddskerl_bound:quantile(Sketch, Q), Sketch}.

handle_cast({new_value, Value}, Sketch) ->
   {noreply, ddskerl_bound:insert(Sketch, Value)}.
...

Summary

Types

ddsketch()

DDSketch instance.

opts()

Options for the DDSketch.

Functions

buckets/1

Export all non-empty buckets of the DDSketch, in ascending order of value.

foldl/3

Fold over all non-empty buckets of the DDSketch, in ascending order of value.

insert/2

Insert a value into the DDSketch.

merge/2

Merge two DDSketch instances.

new/1

Create a new DDSketch instance.

quantile/2

Calculate the quantile of a DDSketch.

sum/1

Get the sum of elements in the DDSketch.

total/1

Get the total number of elements in the DDSketch.

Types

ddsketch()

-opaque ddsketch()

DDSketch instance.

opts()

-type opts() :: #{error := float(), bound := non_neg_integer()}.

Options for the DDSketch.

Functions

buckets/1

-spec buckets(ddsketch()) -> [ddskerl:bucket()].

Export all non-empty buckets of the DDSketch, in ascending order of value.

foldl/3

-spec foldl(ddsketch(), Fun, Acc0) -> Acc1
               when
                   Fun :: fun((Bucket :: ddskerl:bucket(), AccIn :: term()) -> AccOut :: term()),
                   Acc0 :: term(),
                   Acc1 :: term().

Fold over all non-empty buckets of the DDSketch, in ascending order of value.

Note that once the sketch saturates and buckets start being collapsed, the lower bound of the smallest bucket is only a lower estimate, as it accumulates all the values that were collapsed into it.

insert/2

-spec insert(ddsketch(), number()) -> ddsketch().

Insert a value into the DDSketch.

merge/2

-spec merge(ddsketch(), ddsketch()) -> ddsketch().

Merge two DDSketch instances.

new/1

-spec new(opts()) -> ddsketch().

Create a new DDSketch instance.

quantile/2

-spec quantile(ddsketch(), float()) -> float() | undefined.

Calculate the quantile of a DDSketch.

sum/1

-spec sum(ddsketch()) -> number().

Get the sum of elements in the DDSketch.

total/1

-spec total(ddsketch()) -> non_neg_integer().

Get the total number of elements in the DDSketch.