This module defines a sliding time-window histogram with execution cost control.
.
The problem with traditional histograms is that every sample is stored and processed, no matter what the desired resolution is.
If a histogram has a sliding window of 100 seconds, and we have a sample rate of 100Hz will give us 10000 elements to process every time we want to calculate that average, which is expensive. The same goes for min/max finds, percentile calculations, etc.
The solution is to introduce cost-control, where we can balance execution time against sample resolution.
The obvious implementation is to lower the sample rate by throwing away samples and just store evey N samples. However, this will mean potentially missed min/max values, and other extreme data that is seen by the edge code but is thrown away.
A slotted slide histogram will define a number of time slots, each spanning a fixed number of milliseconds. The slider then stores slots that cover a given timespan into the past (a rolling historgram). All slots older than the timespan are discarded.
The "current" slot is defined as the time period between the time stamp of the last stored slot and the time when it is time to store the next slot. If the slot period (size) is 100ms, and the last slot was stored in the histogram at msec 1200, the current slot period ends at msec 1300.
All samples received during the current slot are processed by a low-cost fun that updates the current slot state. When the current slot ends, another fun is used to transform the current slot state to a value that is stored in the histogram.
If a simple average is to be calculated for all samples received, the sample-processing fun will add to the sum of the received samples, and increment sample counter. When the current slot expires, the result of SampleSum / SampleCount is stored in the slot.
If min/max are to be stored by the slotted histograms, the current slot state would have a { Min, Max } tuple that is upadted with the smallest and largest values received during the period. At slot expiration the min/max tuple is simply stored, by the transformation fun, in the histogram slots.
By adjusting the slot period and the total histogram duration, the cost of analysing the entire histogram can be balanced against the resolution of that analysis.
The slide state maintains a list of { TimeStamp, SlotElem } slot tuples. TimeStamp is the time period (in monotonic ms), rounded down to the resolution of the slot period, and SlotElem is the tuple generated by the current slot transformation MFA. The list is sorted on descending time stamps (newest slot first).
Normally each element in the list has a timestamp that is SlotPeriod milliseconds newer than the next slot in the list. However, if no samples are received during the current slot, no slot for that time stamp will be stored, leaving a hole in the list. Normally, the the slot list would look like this (with a 100 msec slot period and a simple average value):
[ { 1400, 23.2 }, { 1300, 23.1 }, { 1200, 22.8 }, { 1100, 23.0 } ]If no samples were received during the period between 1200 and 1300 (ms), no slot would be stored at that time stamp, yielding the following list:
[ { 1400, 23.2 }, { 1300, 23.1 }, { 1100, 23.0 } ]This means that the total length of the slot list may vary, even if it always covers the same time span into the past.
The slotted slider stores its slots in two lists, list1, and list2. list1 contains the newest slots. Once the oldest element in list1 is older than the time span covered by the histogram, the entire content of list1 is shifted into list2, and list1 is set to []. The old content of list2, if any, is discarded during the shift.
When the content of the histogram is to be retrieved (through fold{l,r}(), or to_list()), the entire content of list1 is prepended to the part of list2 that is within than the time span covered by the histogram.
If the time span of the histogram is 5 seconds, with a 1 second slot period, list1 can look like this :
list1 = [ {5000, 1.2}, {4000, 2.1}, {3000, 2.0}, {2000, 2.3}, {1000, 2.8} ]When the next slot is stored in the list, add_slot() will detect that the list is full since the oldest element ({1000, 20.8}) will fall outside the time span covered by the histogram. List1 will shifted to List2, and List1 will be set to the single new slot that is to be stored:
list1 = [ {6000, 1.8} ]
list2 = [ {5000, 1.2}, {4000, 2.1}, {3000, 2.0}, {2000, 2.3}, {1000, 2.8} ]To_list() and fold{l,r}() will return list1, and the first four elements of list2 in order to get a complete histogram covering the entire time span:
[ {6000, 1.8}, {5000, 1.2}, {4000, 2.1}, {3000, 2.0}, {2000, 2.3} ]Two funs are provided to the new() function of the slotted slide histogram. The processing function is called by add_element() and will take the same sample value provided to that function together with the current timestamp and slot state as arguments. The function will return the new current slot state.
M:F(TimeStamp, Value, State) -> NewStateThe first call to the sample processing fun when the current slot is newly reset (just after a slot has been added to the histogram), state will be set to 'undefined'
M:F(TimeStamp, Value, undefined) -> NewStateThe transformation fun is called when the current slot has expired and is to be stored in the histogram. It will receive the current timestamp and slot state as arguments and returns the element to be stored (together with a slot timestamp) in the slot histogram.
M:F(TimeStamp, State) -> ElementElement will present in the lists returned by to_list() and fold{l,r}(). If the transformation MFA cannot do its job, for example because no samples have been processed by the sample processing fun, the transformation fun should return 'undefined'
See new/2 and its avg_sample() and avg_transform() functions for an example of a simple average value implementation.
cur_state() = any()
sample_fun() = fun((timestamp(), value(), cur_state()) -> cur_state())
timestamp() = integer()
transform_fun() = fun((timestamp(), cur_state()) -> cur_state())
value() = any()
| add_element/2 | |
| add_element/3 | |
| add_element/4 | |
| foldl/3 | |
| foldl/4 | |
| foldr/3 | |
| foldr/4 | |
| new/2 | |
| new/4 | |
| new/5 | |
| reset/1 | |
| to_list/1 |
add_element(Val::any(), Slide::#slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}) -> #slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}
add_element(TS, Val, Slide) -> any()
add_element(TS, Val, Slide, Wrap) -> any()
foldl(Fun, Acc, Slide) -> any()
foldl(TS, Fun, Acc, Slide) -> any()
foldr(Fun, Acc, Slide) -> any()
foldr(TS, Fun, Acc, Slide) -> any()
new(HistogramTimeSpan::integer(), SlotPeriod::integer()) -> #slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}
new(HistogramTimeSpan::integer(), SlotPeriod::integer(), SampleF::sample_fun(), TransformF::transform_fun()) -> #slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}
new(HistogramTimeSpan::integer(), SlotPeriod::integer(), SampleF::sample_fun(), TransformF::transform_fun(), Options::list()) -> #slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}
reset(Slide::#slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}) -> #slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}
to_list(Slide::#slide{timespan = integer(), sample_fun = sample_fun(), transform_fun = transform_fun(), slot_period = integer(), cur_slot = integer(), cur_state = any(), list1_start_slot = integer(), list1 = list(), list2 = list()}) -> list()