I've done a bunch of research and here is what I have figured out so far. At a high level we have the following decision points:

Shared memory histogram or not shared memory histogram.
Type of histogram to use. From my research the types of histograms roughly fall into three categories. a) Fixed bucket widths. b) Log linear bucket widths. c) HDR.

Each of the above decision points have very different tradeoffs in terms of memory usage, accuracy, ease of multi-threading, and general ease of programming.

Here is my current thinking on the above, but @jmarantz it would be great if you want to own a more complete analysis of the tradeoffs and what we should think about doing.

Shared memory vs. not

The pros of a shared memory implementation are that we would have correct histograms across hot restart. The cons of the shared memory implementation is that we are unlikely to be able to use existing libraries and the programming model will be more complicated, especially if we want to do something like HDR. My current opinion is that the extra complexity of shared memory for histogram data is not worth it and we should just assume that histogram values in the old process that is shutting down will get dropped. I don't think this will really matter that much from an operational perspective.

Type of histogram and programming model

In general, the accuracy of fixed bucket width histograms are going to be fairly poor, unless we think about somehow tuning the buckets on a per metric basis. From my research it seems it would make more sense to use log linear or HDR. Of these, the libraries that seem most promising are:

log linear: https://github.com/circonus-labs/libcircllhist
HDR: https://github.com/HdrHistogram/HdrHistogram_c

Both of the above implementations support merging. This means that we could easily have per-thread histograms which then get aggregated during a flush pass (say every 60s). In the case of log linear, per thread aggregation is demonstrated here: https://github.com/circonus-labs/libcircmetrics

Note that t-digest has also been mentioned to me (e.g., https://github.com/tdunning/t-digest) but I don't know much about it).

I don't yet have a strong opinion on HDR vs. log linear. It seems that HDR will require substantially more memory per histogram, but yield much more accurate results. To reduce memory usage, we could ask the user of the histogram to set reasonable bounds and help estimate the memory usage. The log linear implementation I think would be far less accurate at larger values than HDR. I think a more complete analysis needs to be done the tradeoffs.

Envoy programming model

Today, histograms are driven off the stats interfaces as well as sometimes as part of the stat creation macros: https://github.com/envoyproxy/envoy/blob/master/include/envoy/stats/stats_macros.h. It's quite possible that in order to make this work well, the user of each histogram will need to set bounds (especially if we use HDR). This may mean that we need to remove the histogram option from the stat macros and have users create histograms manually off of a stat scope. The reality is that this isn't that big of a deal as there aren't that many histograms in the code. But this needs more analysis in terms of how the user will interact with histograms and potentially set bounds.

Stat flushing model

Thought also needs to be given to where histogram computation lives. E.g., do we compute for all stat sinks even though statsd does not want the computations? What type of aggregation/rotation interval do we use? If it fixed for all histograms? (E.g., rotate every 60s). Is it configurable per histogram? Do we eventually want multiple aggregation intervals? (E.g, 60s, 5m, 15m). In general simpler is always better but it's worth thinking through all of this for future use cases.

@jmarantz I'm sure I forgot something above but hopefully this is enough to get started and we can discuss further as you dig in.

stats: add built-in log linear histogram support #1965

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions