|
Seastar
High performance C++ framework for concurrent servers
|
This is a pseudo-exponential implementation of an estimated histogram.
An exponential-histogram with coefficient 'coef', is a histogram where for bucket 'i' the lower limit is coef^i and the higher limit is coef^(i+1).
A pseudo-exponential is similar but the bucket limits are an approximation.
The approximate_exponential_histogram is an efficient pseudo-exponential implementation.
The histogram is defined by a Min and Max value limits, and a Precision (all should be power of 2 and will be explained).
When adding a value to a histogram: All values lower than Min will be included in the first bucket (the assumption is that it's not suppose to happen but it is ok if it does).
All values higher than Max will be included in the last bucket that serves as the infinity bucket (the assumption is that it can happen but it is rare).
Note the difference between the first and last buckets. The first bucket is just like a regular bucket but has a second roll to collect unexpected low values. The last bucket, also known as the infinity bucket, collect all values that passes the defined Max, it only collect those values.
The buckets limits in the histogram are defined similar to a floating-point representation.
Buckets limits have an exponent part and a linear part.
The exponential part is a power of 2. Each power-of-2 range [2^n..2^n+1) is split linearly to 'Precision' number of buckets.
The total number of buckets is: NUM_BUCKETS = log2(Max/Min)*Precision +1
For example, if the Min value is 128, the Max is 1024 and the Precision is 4, the number of buckets is 13.
Anything below 160 will be in the bucket 0, anything above 1024 will be in bucket 13. Note that the first bucket will include all values below Min.
the range [128, 1024) will be split into log2(1024/128) = 3 ranges: 128, 256, 512, 1024 Or more mathematically: [128, 256), [256, 512), [512,1024)
Each range is split into 4 (The Precision). 128 | 256 | 512 | 1024 128 160 192 224| 256 320 384 448| 512 640 768 896|
To get the exponential part of an index you divide by the Precision. The linear part of the index is Modulus the precision.
Calculating the bucket lower limit of bucket i: The exponential part: exp_part = 2^floor(i/Precision)* Min with the above example 2^floor(i/4)*128 The linear part: (iPrecision) * (exp_part/Precision) With the example: (i%4) * (exp_part/4)
So the lower limit of bucket 6: 2^floor(6/4)* 128 = 256 (6%4) * 256/4 = 128 lower-limit = 384
The bucket index consist of two parts: higher bits (exponential part) are based on log2(value/min)
lower bits (linear part) are based on the 'n' MSB (ignoring the leading 1) where n=log2(Precision). Continuing with the example where the number of precision bits: PRECISION_BITS = log2(4) = 2
for example: 330 (101001010) The number of precision_bits: PRECISION_BITS = log2(4) = 2 higher bits: log2(330/128) = 1 MSB: 01 (the highest two bits following the leading 1) So the index: 101 = 5
For Min, Max and Precision, choose numbers that are a power of 2.
Limitation: You must set the MIN value to be higher or equal to the Precision.
| Min | - The lowest expected value. A value below that will be set to the Min value. |
| Max | - The highest number to consider. A value above that is considered infinite. |
| Precision | - The number of buckets in each range (where a range is the i^2..i^(2+1) ) |
#include <seastar/core/internal/estimated_histogram.hh>
Public Member Functions | |
| uint64_t | get_bucket_lower_limit (uint16_t bucket_id) const |
| Returns the bucket lower limit given the bucket id. The first and last bucket will always return the MIN and MAX respectively. | |
| uint64_t | get_bucket_upper_limit (uint16_t bucket_id) const |
| Returns the bucket upper limit given the bucket id. The last bucket (Infinity bucket) will return UMAX_INT. | |
| uint16_t | find_bucket_index (uint64_t val) const |
| Find the bucket index for a given value The position of a value that is lower or equal to Min will always be 0. The position of a value that is higher or equal to MAX will always be NUM_BUCKETS - 1. | |
| void | clear () |
| clear the current values. | |
| void | add (uint64_t n) |
| Add an item to the histogram Increments the count of the bucket holding that value. | |
| uint64_t | min () const |
| returns the smallest value that could have been added to this histogram This method looks for the first non-empty bucket and returns its lower limit. Note that for non-empty histogram the lowest potentail value is Min. More... | |
| uint64_t | max () const |
| returns the largest value that could have been added to this histogram. This method looks for the first non empty bucket and return its upper limit. If the histogram overflowed, it will returns UINT64_MAX. More... | |
| approximate_exponential_histogram & | merge (const approximate_exponential_histogram &b) |
| merge a histogram to the current one. | |
| uint64_t | get (size_t bucket) const |
| uint64_t | quantile (float quantile) const |
| get a histogram quantile More... | |
| uint64_t | mean () const |
| returns the mean histogram value (average of bucket offsets, weighted by count) It will return 0 if the histogram is empty. | |
| size_t | size () const |
| returns the number of buckets; | |
| uint64_t | count () const |
| returns the total number of values inserted | |
| approximate_exponential_histogram & | operator*= (double v) |
| multiple all the buckets content in the histogram by a constant | |
| uint64_t & | operator[] (size_t b) noexcept |
| int32_t | get_schema () const noexcept |
| get_schema the schema of a native histogram More... | |
| int32_t | min_as_native_histogram_id () const noexcept |
| return the histogram min as a native histogram ID More... | |
| seastar::metrics::histogram | to_metrics_histogram () const noexcept |
|
inlinenoexcept |
get_schema the schema of a native histogram
Native histograms (also known as sparse histograms), are an experimental Prometheus feature.
schema defines the bucket schema. Currently, valid numbers are -4 <= n <= 8. They are all for base-2 bucket schemas, where 1 is a bucket boundary in each case, and then each power of two is divided into 2^n logarithmic buckets. Or in other words, each bucket boundary is the previous boundary times 2^(2^-n).
|
inline |
returns the largest value that could have been added to this histogram. This method looks for the first non empty bucket and return its upper limit. If the histogram overflowed, it will returns UINT64_MAX.
It will return 0 if the histogram is empty.
|
inline |
returns the smallest value that could have been added to this histogram This method looks for the first non-empty bucket and returns its lower limit. Note that for non-empty histogram the lowest potentail value is Min.
It will return 0 if the histogram is empty.
|
inlinenoexcept |
return the histogram min as a native histogram ID
Native histograms (also known as sparse histograms), are an experimental Prometheus feature.
Native histograms always starts from 1, while approximate_exponential_histogram have a min first bucket This function returns approximate_exponential_histogram min value as the bucket id of native histogram.
|
inline |
get a histogram quantile
This method will returns the estimated value at a given quantile. If there are N values in the histogram. It would look for the bucket that the total number of elements in the buckets before it are less than N * quantile and return that bucket lower limit.
For example, quantile(0.5) will find the bucket that that sum of all buckets values below it is less than half and will return that bucket lower limit. In this example, this is a median estimation.
It will return 0 if the histogram is empty.
1.9.4