Referendum on Histogram format

[jmacd]

What are you trying to achieve?

This issue aims to achieve consensus from OpenTelemetry maintainers and approvers over a choice of histogram formats.

There has been a lengthy process to standardize an exponential histogram protocol for OpenTelemetry, culminating in OTEP 149 which arrived at a consensus on exponential histograms.

Contemporaneously, the OpenHistogram code base was re-licensed (formerly the Circonus Log-linear Histogram), making it an appealing option for both OpenTelemetry (and OpenMetrics) to use, but it is not the same as an exponential histogram. The goal of this issue is to summarize these options to allow a wider audience to participate in the selection process.

It is important that we choose only one of these options for several reasons: (1) because there is a loss of fidelity whenever we translate between incompatible histogram types, (2) because there will be a large amount of code dedicated to handling each of these types in many downstream vendor and OSS systems.

OTEP 149: Exponential histograms

OTEP 148, discussed and debated in open-telemetry/oteps#149, lists considerations around specifying an exponential histogram for OTLP. In an exponential histogram, boundaries are located at integer powers of a specific base value. If the base value is 1.1, then there are boundaries at 1.1, 1.1^2, 1.1^3, 1.1^4, and so on.

Merging exponential histograms

While this form of histogram is almost trivial in concept, there was an early concern about loss of fidelity when merging arbitrary histograms, due to residual "artifacts". This consideration leads in two directions, both of which have been explored.

The first avenue is to fix the histogram parameters completely--when there are no parameters then you can merge histograms without loss of fidelity. The second avenue is to choose a parameterization scheme that has "perfect subsetting", which is when buckets of a high-resolution histogram perfectly map into buckets of a lower-resolution histogram.

Perfect subsetting for exponential histograms

Following UDDSketch and unpublished work at Google, OTEP 149 lands on the idea of a powers-of-2 exponential histogram, one that ensures perfect subsetting.

scale	boundaries, e.g.	number of buckets spanning 1..100
0	1, 2, 4, 8	7
1	1, 1.4, 2, 2.8, 4	14
2	1, 1.2, 1.4, 1.7, 2,	27
3	1, 1.09, 1.19, ... 1.7, 1.83, 2	54
4	1, 1.04, 1.09, ... 1.83, 1.92, 2	107
5	1, 1.02, 1.04, ... 1.92, 1.96,	213
6	1, 1.01, 1.02, ... 1.92, 1.96,	426

OpenHistogram: Log-linear histograms

OpenHistogram uses a base-10 exponential scheme with 90 buckets linearly dividing each "decade", so for example there are 90 buckets between 0.1 and 1, 90 buckets between 1 and 10, 90 buckets between 10 and 100, and so on. This approach maps well to human intuition about logarithmic scale. This approach is also tailored for environments without floating point processors.

Merging OpenHistogram histograms

OpenHistogram has fixed parameterization, thus avoids loss of fidelity when merging.

Perfect subsetting for OpenHistogram-like histograms

The goal of perfect subsetting is to select parameters that support merging of high- and low-resolution histograms. OpenHistogram makes a strong case for the use of 90 buckets per decade, which is relatively high resolution, because any factor of 9 ensures integer boundaries >= 1 in a base-10 scheme.

Resolution factors that are compatible with OpenHistogram and have perfect subsetting:

resolution	boundaries, e.g.	number of buckets spanning 1..100
1	1, 10	2
3	1, 4, 7, 10	6
9	1, 2, 3, ... 8, 9, 10	18
18	1, 1.5, 2, ... 9, 9.5, 10	36
90	1, 1.1, 1.2, ... 9.8, 9.9, 10	180
180	1, 1.05, 1.1, ... 9.9, 9.95, 10	360

Note that while OpenHistogram fixes resolution at 90, OpenTelemetry could adopt a protocol with support for other resolutions and still adopt OpenHistogram libraries for its SDKs, allowing metrics processing pipelines to automatically lower resolution for collected metrics.

Protocol considerations

Regardless of which choice is made for the options above above, there are several choices remaining.

Sparse vs. Dense encoding

A dense encoding is optimized for the case where non-empty buckets will be clustered together, making it efficient to encode a single offset and one (if exponential) or two (if log-linear) arrays of counts.

A sparse encoding is optimized for the case where non-empty buckets are not clustered together, making it efficient to encode every bucket index separately.

Sparse histograms can be converted into denser, lower-resolution histograms by perfect subsetting; bucket indexes are are sometimes compressed using delta-encoding techniques.

Zero bucket handling

The zero value must be handled specially in an exponential histogram. There is a question about how to recognize values that are close to zero, whether they "fall into" the zero bucket for example.

Converting from other histogram formats

Both the exponential and log-linear family of histogram are expected to improve the resolution-per-byte of encoded data that is achieved, relative to the explicit-boundary histogram currently included in OTLP. Metrics processors that operate on this data will require helper methods to assist in translating from other histogram formats into the exponential histogram that we choose.

To translate from another histogram format, often we use interpolation. Rules for interpolating between histogram buckets should specify how to handle the buckets that span zero and buckets with boundaries at infinity, since both are valid configurations. To interpolate from arbitrary-boundary buckets, we have to calculate bucket indexes for each boundary in the input.

Calculating bucket indexes: Exponential case

To calculate the bucket index for an arbitrary exponential base generally means calculating a logarithm of the value.

For the special case of base-2 exponential histograms, the IEEE 754 floating point representation has the data in the correct format, it can be directly extracted using bitwise operations.

To calculate bucket indexes without floating point hardware, a recursion relationship can be used.

Calculating bucket indexes: Log-linear case

OpenHistogram defines a recursion relation for calculating the bucket index.

Summary

Thank you to the experts that have guided us to this point. @yzhuge, @postwait, @oertl, @githomin, @CharlesMasson, @HeinrichHartmann, and @jdmontana.

This is now a question for the community. There are two major options presented here, a base-2 exponential histogram and a base-10 log-linear histogram. Both have technical merits.

There are also non-technical merits to consider. OpenHistogram is readily available and has already been adopted in a number of OSS systems, such as Envoy. An out-of-the-box Prometheus client uses 12 buckets with default boundaries that map exactly onto OpenHistogram boundaries, which cannot be said for the binary-exponential approach.

My personal opinion (@jmacd): I am in favor of adopting a protocol with support for OpenHistogram's histogram as long as the protocol supports the lower resolution factors listed above, 3, 9, 18, which appears to be a trivial extension to the OpenHistogram model. I am assuming this approach will be legally acceptable as far as the OpenHistogram project is concerned.

[oertl]

@jmacd thanks for your effort and your comparison. I just miss a discussion about the space-efficiency:

One of the main reasons to use histogram-like sketches for the summarization of distributions is that they provide strict error guarantees when estimating quantiles. (This is in contrast to other sketches like KLL or t-digest). If you want to estimate a certain quantile, histograms allow you to determine the bucket which contains that quantile value. The corresponding bucket boundaries will obviously bracket that quantile and can be used for estimation. The maximum relative estimation error is therefore dependent on the maximum relative bucket width (relative distance between subsequent boundaries).

Assume you want to estimate quantiles with a relative accuracy of 2.5%. This would roughly require a maximum relative bucket width of 5%, if the mid-point of the bucket is used as estimate. When using the base-2 solution, you would therefore have to choose scale=4 with a relative bucket width of 4.4%. According to the first table above, the number of buckets needed to cover the range from 1 to 100 is 107.

To have the same maximum relative error when using OpenHistogram, you would have to choose resolution=180. This configuration results in the desired maximum relative bucket width of 5% (given by the first 2 bucket boundaries listed in the table). The second table above shows that 360 buckets are needed to cover the range from 1 to 100, which is more than a factor of 3!!! more compared to the base-2 solution. Since space-efficiency and the estimation of quantiles is important for us, we favor the base-2 solution.

[CharlesMasson]

We also think that computation cost and space efficiency should be driving the choice of the bucket index calculation, and in this regard, a base-2 solution makes more sense to us.

It is also not very clear to us why a base-10 approach is more tailored for environments without floating point processors. Base-2 log-linear bucket indexes can also be computed without floating point operations (using the number of leading zeros and the trailing part of the binary representation of integers, as we use the exponent and the mantissa of the binary representation of floating-point values). Unless I'm mistaken, that is essentially what HDR histograms do.

In addition, while a base 10 might be more intuitive, we do not think that end users, especially non-technical people, who see the output of such histogram-like sketches through the quantiles that they produce, or the visualizations that are built from them, should have to reason about it. Most visualizations (histograms, heatmaps, etc.) generally require bucket remapping anyway (e.g., into constant-width buckets), and this can be achieved satisfactorily using an appropriate remapping method (e.g., allocating counts based on bucket overlapping), independently of the internal bucket index calculation. Even when interfacing with the bucket index mapping is necessary, we found out that a proper bucket mapping abstraction (which properly exposes the bucket index a value belongs to, the boundaries of a bucket of a given index, etc.) allows abstracting away the internal index calculation method.

[HeinrichHartmann]

Space Efficiency

The second table above shows that 360 buckets are needed to cover the range from 1 to 100, which is more than a factor of 3!!! more compared to the base-2 solution -- @oertl

This is a good observation. I just re-ran the math and come to the same conclusion (cf. tables below). In principle the relative accuracy is inverse-proportional to the bucket count in 1-100, irrespective of the exact bucket layout (more buckets => more accuracy). The phenomenon we are running into is that the relative size of the bucket at the low end of the linear scale is much larger than on the high end of the linear scale: (1.0 .. 1.1) has ~10% the size of the bucket boundary, whereas (9.9 ... 10) as ~1%-the size of the bucket boundary. Hence OpenHistogram needs more buckets to bound the worst-case error.

OpenHistogram and Floating Point

It is also not very clear to us why a base-10 approach is more tailored for environments without floating point processors. -- @CharlesMasson

There are two properties that make inserting data into OpenHist work well without floating-point math:

• The linear-part of the scale only requires integer divisions to determine the bucket no logarithms
• Base-10 allows trivial conversion between SI units (n,u,m,k,M,G), which is relevant if you are inserting, e.g. nano-seconds, micro-seconds, seconds, etc. into your histogram.

Here is a pointer to the C implementation: https://github.com/openhistogram/libcircllhist/blob/master/src/circllhist.c#L793
This code compiles to BPF and can be used this for in-kernel latency measurements (-> blog) - where you don't have floats.

Base-10 and Human Readability

In addition, while a base 10 might be more intuitive, we do not think that end users, ..., should have to reason about it. -- @CharlesMasson

The most significant advantage for the end-users of using base-10 (and linear sub-binning) is that you get exact upper/lower counts for the human-readable thresholds. This is relevant for, e.g. for Latency SLOs, where you want to know which percentage of requests was faster than a human-set threshold (e.g. 100ms) over the last month. With resolution=9 OpenHistograms you can cover all practically relevant SLO thresholds (100ms, 200ms, ...) and get exact results.

Accuracy Tables

@jmacd -- If you add those error columns to the tables in the description, I'll remove these tables here.

OTEP-149

scale	base	buckets in 1..100	Max relative error
0	2.000	7	33.33%
1	1.414	14	17.15%
2	1.189	27	8.63%
3	1.091	54	4.35%
4	1.044	107	2.15%
5	1.022	213	1.09%
6	1.011	426	0.55%

OpenHistogram

resolution	bucket-boundary*	buckets in 1..100	Max relative error
1	10	2	81.82%
3	4	6	60.00%
9	2	18	33.33%
18	1.5	36	20.00%
90	1.1	180	4.76%
180	1.05	360	2.44%

*) for the worst-case bucket with boundary [1,x)

[giltene]

As consideration for histogram formats is evolving here, both for new formats and existing ones, it's probably worth looking at HdrHistogram and it's established data structure and wire-form as one possible format to use.

HdrHistogram has been around for roughly 10 years now, as a pure (and permissive) OSS thing, and is currently supported with community-created implementations in Java, JavaScript, Python, Go, C/C++, C#/.NET, Rust, and Erlang. It has evolved from a super-fast log-linear Java implementation to a common data structure and compact (compressed) wire format that is shared across multiple language implementations. It has support for both integer and floating point histogram forms, as well as sparse or packed in-memory representations in various implementations. The wire format is specifically decoupled from the in-memory representation, allowing end points to make local tradeoffs of e.g. speed vs memory footprint (e.g. a packed histogram and a non-packed one have the same wire format), or recording time vs iteration/quantile calculation time (packed representations are slower to record into, but faster to iterate and compute on). The wire form itself has proven to be quite compact for real-world applications, and it's BLOB is commonly shared/stored in single (Base64 or binary) string when not being actively recorded into (see example in e.g. a jHiccup log where each line represents a fully recorded histogram capturing 1 second of (~1000) recorded samples).

It would be interesting to see what the footprint (in bytes in a wire form used in e.g. a database or data transmittal) looks like for the various histogram format choice alternatives, as well as what basic metrics like recording speed/cost, memory footprint, and integration time look like.

[oertl]

I did a recording speed benchmark a month ago. The results show that the proposed base-2 solution (RecordingSpeedBenchmark.recordDynaHistDynamicOpenTelemetryExponentialBuckets) can be as fast as HdrHistogram.DoubleHistogram. If a static array is used (RecordingSpeedBenchmark.recordDynaHistStaticOpenTelemetryExponentialBuckets) it is even faster. As always, benchmark results need to be used with a lot of caution. @giltene, please help in improving this benchmark in case you think I should configure DoubleHistogram in a different way to have a more fair comparison.

Regarding space efficiency, log-linear bucketing has an inherent space overhead and needs roughly 44% more buckets to limit the maximum relative error over a certain value range compared to an ideal bucketing as we have already discussed 6 years ago (see HdrHistogram/HdrHistogram#54). Reducing this space overhead was actually one of the main motivations to develop DynaHist (https://github.com/dynatrace-oss/dynahist).

[giltene]

I’ll take a look at the benchmark. But regarding space efficiency, I think that space spent in the wire form (serialized) and in various in memory implementations (packed vs flat) would lead to very different comparisons. The wire forms of HdrHistogram, for example, takes advantage of the sparse nature of real world data to dramatically reduce footprint while still maintaining the same bounded value error characteristics. Using a combination of ZigZag, Run Length encoding, and compression, the actual BLOBs transmitted and stored are extremely compact , to the point where they can (literally) be tweeted. The same concept is used for the in-memory packed forms (see e.g. PackedDoubleHistogram). These techniques are obviously not limited to HdrHistogram, and I assume that similar packing and compression techniques can be used for other forms of log-linear and exponential (small base, as in 1.01) histograms, but the post-packing footprint differences between the base layouts will likely be insignificant, and the work on this in HdrHistogram is already done.

[giltene]

Some thoughts on comparing possible encodings and formats:

• We should probably start with some baseline data sets to use. Stuff recorded from actual systems is much preferred to synthetically generated sets. E.g. get our hands on some actual response time or latency (per operation) data and use those sets of data for comparison.

• Comparing speed: there are multiple operations for which speed can/should be compared:

  • Recording speed. This is the fundamental metric the data gatherers will care about, as this will be their "performance tax". "How great it needs to be" can widely vary by application. E.g. endpoints that record 100s of operations per second will car less about this than ones that record 100s of thousands of operations per second.
  • Data extraction speed (e.g. extracting quantiles): this matter more for the backend than the front ends.
  • Ecoding and decoding speed: measuring the cost of serializing/deserializing data to/from wire and storage formats.

• Comparing footprint: There are multiple forms of footprint, and they should all be compared sin actual data sets.

  • "wire form" (aka serialized form) footprint: The size of the data "at rest", in either binary or text-friendly (e.g. Base64 encoded json BLOBs) forms.
  • "in memory" footprint: there are potentially multiple forms for this:
    • Speed-optimized footprint (e.g. flat array HdrHistogram)
    • Space-optimized in-memory footprint (e.g. Packed HdrHistograms)

[jmacd]

Thank you for joining this discussion, @giltene!

The HDR Histogram documentation focuses a lot on the Java API, so it's not easy to find a specification for the wire format.
Will you please help us in providing a link to a summary of the HDR histogram wire format?

Because OTLP uses Google protobufs, OpenTelemetry will (I assume, speaking for myself) prefer to the interpret histogram data in a .proto representation, and "HDR Histogram" compatibility would mean being able to convert to and from a traditional HDR Histogram representation without loss and without significant requiring computation.

[jmacd]

I've corrected the link to OTEP 149: https://github.com/open-telemetry/oteps/blob/main/text/0149-exponential-histogram.md

[giltene]

@jmacd a specification of the integer histogram encoding can currently be found here as part of the .NET implementation. DoubleHistograms are not specified there, but since DoubleHistograms use integer histograms internally, they differ from the integer variant only in the cookie and header parts [an implementation can be found here, and yes, a common spec would be better].

As to interaction with protobuf and/or other storage/transmission formats, I'd expect histograms to show up a a "histogram BLOB" in any such protocol. with a specified internal format, and for there to be histogram encoders/decoders in various languages for whatever the format chosen is. There are many advantages to doing so (detached from the encompassing protocol), including a dramatic footprint impact, and portability across tools and such.

[yzhuge]

Space cost

Log linear costs more than exponential at the same quantile relative error. And the larger the base, the higher the cost. As pointed out in other comments, at the relative error of a few percent, base2 log linear costs 44% more than base2 scaled exponential, base10 log linear costs 3x more than base2 scale exponential.

On the client side (an app being monitored), 1kB vs. 3kB might not look like much in today's systems of Gigabytes of memory (even on a cell phone). But on the server side (the backend that stores and queries the data), with billions of metric data points, 3x memory is a lot of $$$.

Cpu cost

What is most important is the value to bucket mapping, which is in the critical path of inserting a value to a histogram. Other parts, like bucket management, are largely portable across different mapping methods. For dense arrays, bucket addressing can be as simple as array indexing.

Base10 log linear

For base10 (OpenHistogram) value to bucket mapping, there is a significant cost of binary to decimal conversion, because input is always binary, for integer and floating point. An example can be found at int_scale_to_hist_bucket(), where a loop of integer division is used (https://github.com/openhistogram/libcircllhist/blob/master/src/circllhist.c#L807). And in double_to_hist_bucket(), where a log10() call is used (https://github.com/openhistogram/libcircllhist/blob/master/src/circllhist.c#L831)

Base2 log linear

Base2 log linear is very fast, when using exponent and mantissa from the native “double” representation. An example is https://github.com/DataDog/sketches-java/blob/master/src/main/java/com/datadoghq/sketch/ddsketch/mapping/BitwiseLinearlyInterpolatedMapping.java#L60, which is essentially just a few bit wise operations.

Base2 scaled exponential

Base2 scaled exponential can be made nearly as fast as base2 log linear. As shown in this example from @oertl lookup table

int i = indices[(int) (mantissa >>> (52 - precision))];
int k = i + ((mantissa >= boundaries[i]) ? 1 : 0) + ((mantissa >= boundaries[i + 1]) ? 1 : 0);
return (exponent << precision) + k + indexOffset;

Here “indices” and “boundaries” are precomputed arrays of 2^scale entries each. The core computation involves a few bitwise operations, plus 3 array lookups. The only method that is faster is base2 log linear. But that costs 44% more buckets at the same relative error. Other methods in the log or log linear family won’t even get close.

I had previously thought about this and came up with a similar method, where the arrays have 2^(scale+1) entries, so that each linear bucket represented by the arrays spans at most 2, instead of 3 log scale buckets, so that it is not necessary to look at boundaries[i + 1]. This further reduces cpu cost, at the expense of static array size. An example of the enhanced method (equivalent to computing "k" in the example above):

public long getSubBucketIndex(final long mantissa) {
    final int linearArrayIndex = (int) (mantissa >>> linearMantissaShift);
    final int logBucketIndex = logBucketIndexArray[linearArrayIndex];
    return mantissa >= logBucketEndArray[linearArrayIndex] ? logBucketIndex + 1 : logBucketIndex;
}

The lookup methods essentially use precomputed lookup tables to quickly map a value from a linear bucket into a log bucket. At the scale of interest, where relative error is a few percent, lookup array size is totally manageable (the arrays are static arrays shared across all instances in a process).

scale	base	buckets in 1..100	Max relative error	lookup array size	enhanced lookup array size
3	1.091	54	4.35%	8	16
4	1.044	107	2.15%	16	32
5	1.022	213	1.09%	32	64

Log linear has long been used as a fast approximation of pure log scale buckets. But now with lookup tables, pure log scale can be computed nearly as fast as base2 log linear, yet cost 44% less memory. And it is easy to understand and implement. Everybody understands log scale, and when performance is not critical, a simple implementation can call standard log() function to avoid the lookup table logic.

Use cases

Let's consider the pros and cons of the options in various use cases:

Histogram charting

Histogram charting in linear scale

In this case, base10 log linear does have the advantage of bucket bounds aligning up with decimal numbers. However, at the relative error of a few percent, hundreds of buckets are needed even for a small range of 1..100. With this many buckets, individual buckets are hard to see on a curve. Unless a user is “bucket peeking” (as in pixel peeking on an image), they will hardly notice the underlying buckets’ bounds.

This comes to the most significant advantage of a base10 histogram: more human friendly when a human is actually eyeballing the individual buckets. But this use case is more limited to scenarios like debugging than a common end user use case (Can you imagine a business person scrolling through hundreds of histogram buckets?).

Histogram charting in log scale

If the chart is rendered in log scale, a pure log scale histogram such as scaled base2 actually has advantage over a log linear histogram, because a pure log scale histogram’s bucket are of equal width on log scale, while log linear buckets are not.

SLO measurement

A typical SLO is like: 99% of requests must be processed in less than 100ms.
There are two ways to check if SLI meets the SLO:

1. Check that 99% percentile of response time is less than 100ms
2. Check that the percentage of requests shorter than 100ms is higher than 99%.

For method 2, base10 log linear can give the exact answer when the target ms falls on bucket bound, which is expected to be common because people set the target. But this method is less intuitive in practice. Suppose the SLI says 97% when SLO is 99%. You know 2% of requests are longer than desired, but not how much longer. And it is hard to explain to the user the precision of the system. Business people are not going to like a statement like “if the target ms is on the series of 100, 105, 110 …, 1000, 1050, 1100 …, the result percentage has zero error, otherwise, the error is variable (data dependent)”.

Mathematically, “variable (data dependent)” is the accurate statement. If the requested ms falls into a bucket of 5% total population, the error is +/- 2.5% (absolute error on percentage, assuming the query returns the mid point of the bucket). If it’s in a bucket of 10% population, the error is +/- 5%. For this reason, you might as well just say there is no error guarantee. Alternatively, you can return two numbers, both with zero error, like “the percentage of requests faster than 103ms is between 91.62% and 97.34%”. But the user friendliness of such a system is not going to be good.

Method 1, the percentile method is more user friendly. For example, SLI says 99% is 127ms, when SLO is 100ms. You know you are 27ms away. In this use case, it is important to give the user the upper bound of relative errors. For example, if the histogram has an error bound of 2%, the user knows that 127ms is meaningful against the 100ms target.
For method 1, base10 has no advantage over base2. Users are used to measurement not on “whole numbers”.

Closing thoughts

Survey questions are full of pitfalls. If you ask users: would you like your histogram bounds to be on decimal? They are going to say yes. But if you add: for 3x more money, many will say otherwise. And even when money is not an object, decimal comes with log-linear scale, which has its own pros and cons.

Back to the beginning:
In open-telemetry/opentelemetry-proto#226, I actually started by adding both log and log linear format, with log for space optimization and log linear for cpu optimization. But now with lookup tables for scaled base2 histograms (a pure log histogram), we no longer have to make a choice between cpu and space. We can have both.

Another lesson I learned from that PR is that log linear is harder to explain. You would think “linear subbuckets in log buckets” is easy to understand, but I had to explain it to people again and again, while everybody instantly understood log scale histograms. Log scale (exponential) histogram is mathematically well understood and with many implementations. As long as an implementation can set the base, it can produce scaled base2 histograms (just set base to a base from the scaled series).