Efficient sliding-window buffer.
Authors: Tony Rogvall ([email protected]), Ulf Wiger ([email protected]), Magnus Feuer ([email protected]).
Initial implementation: 29 Sep 2009 by Tony Rogvall
This module implements an efficient sliding window, maintaining
two lists - a primary and a secondary. Values are paired with a
timestamp (millisecond resolution, see exometer_util:timestamp/0)
and prepended to the primary list. When the time span between the oldest
and the newest entry in the primary list exceeds the given window size,
the primary list is shifted into the secondary list position, and the
new entry is added to a new (empty) primary list.
The window can be converted to a list using to_list/1 or folded
over using foldl/3.
cur_state() = any()
fold_acc() = any()
fold_fun() = fun(({timestamp(), value()}, fold_acc()) -> fold_acc())
sample_fun() = fun((timestamp(), value(), cur_state()) -> cur_state())
timestamp() = exometer_util:timestamp()
transform_fun() = fun((timestamp(), cur_state()) -> cur_state())
value() = any()
| add_element/2 | Add an element to the buffer, tagging it with the current time. |
| add_element/3 | Add an element to the buffer, tagged with the given timestamp. |
| add_element/4 | Add an element to the buffer, optionally indicating if a swap occurred. |
| foldl/3 | Fold over all values in the sliding window. |
| foldl/4 | Fold over the sliding window, starting from Timestamp. |
| new/2 | Create a new sliding-window buffer. |
| new/5 | Callback function for exometer_histogram. |
| reset/1 | Empty the buffer. |
| to_list/1 | Convert the sliding window into a list of timestamped values. |
add_element(Evt::value(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Add an element to the buffer, tagging it with the current time.
Note that the buffer is a sliding window. Values will be discarded as they move out of the specified time span.
add_element(TS::timestamp(), Evt::value(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Add an element to the buffer, tagged with the given timestamp.
Apart from the specified timestamp, this function works just like
add_element/2.
add_element(TS::timestamp(), Evt::value(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}, Wrap::true) -> {boolean(), #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}}
add_element(TS::timestamp(), Evt::value(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}, Wrap::false) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Add an element to the buffer, optionally indicating if a swap occurred.
This function works like add_element/3, but will also indicate
whether the sliding window buffer swapped lists (this means that the
'primary' buffer list became full and was swapped to 'secondary', starting
over with an empty primary list. If Wrap == true, the return value will be
{Bool,Slide}, where Bool==true means that a swap occurred, and
Bool==false means that it didn't.
If Wrap == false, this function works exactly like add_element/3.
One possible use of the Wrap == true option could be to keep a sliding
window buffer of values that are pushed e.g. to an external stats service.
The swap indication could be a trigger point where values are pushed in order
to not lose entries.
foldl(Fun::fold_fun(), Acc::fold_acc(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> fold_acc()
Fold over all values in the sliding window.
The fun should as fun({Timestamp, Value}, Acc) -> NewAcc.
The values are processed in order from oldest to newest.
foldl(Timestamp::timestamp(), Fun::fold_fun(), Acc::fold_acc(), Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> fold_acc()
Fold over the sliding window, starting from Timestamp.
The fun should as fun({Timestamp, Value}, Acc) -> NewAcc.
The values are processed in order from oldest to newest.
new(_Size::integer(), _Options::list()) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Create a new sliding-window buffer.
Size determines the size in milliseconds of the sliding window.
The implementation prepends values into a primary list until the oldest
element in the list is Size ms older than the current value. It then
swaps the primary list into a secondary list, and starts prepending to
a new primary list. This means that more data than fits inside the window
will be kept - upwards of twice as much. On the other hand, updating the
buffer is very cheap.
new(Size::integer(), Period::integer(), SampleFun::sample_fun(), TransformFun::transform_fun(), Opts::list()) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Callback function for exometer_histogram
This function is not intended to be used directly. The arguments
_SampleFun and _TransformFun are ignored.
reset(Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> #slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}
Empty the buffer
to_list(Slide::#slide{size = integer(), n = integer(), max_n = undefined | integer(), last = integer(), buf1 = list(), buf2 = list()}) -> [{timestamp(), value()}]
Convert the sliding window into a list of timestamped values.