Base-2 Exponential Histogram

Design

This is a fixed-size data structure for aggregating the OpenTelemetry base-2 exponential histogram introduced in OTEP 149 and described in the metrics data model. The exponential histogram data point is characterized by a scale factor that determines resolution. Positive scales correspond with more resolution, and negatives scales correspond with less resolution.

Given a maximum size, in terms of the number of buckets, the implementation determines the best scale possible given the set of measurements received. The size of the histogram is configured using the WithMaxSize() option, which defaults to 160.

The implementation here maintains the best resolution possible. Since the scale parameter is shared by the positive and negative ranges, the best value of the scale parameter is determined by the range with the greater difference between minimum and maximum bucket index:

func bucketsNeeded(minValue, maxValue float64, scale int32) int32 {
	return bucketIndex(maxValue, scale) - bucketIndex(minValue, scale) + 1
}

func bucketIndex(value float64, scale int32) int32 {
	return math.Log(value) * math.Ldexp(math.Log2E, scale)
}

The best scale is uniquely determined when maxSize/2 < bucketsNeeded(minValue, maxValue, scale) <= maxSize. This implementation maintains the best scale by rescaling as needed to stay within the maximum size.

Layout

Mapping function

The mapping sub-package contains the equations specified in the data model for Exponential Histogram data points.

There are two mapping functions used, depending on the sign of the scale. Negative and zero scales use the mapping/exponent mapping function, which computes the bucket index directly from the bits of the float64 exponent. This mapping function is used with scale -10 <= scale <= 0. Scales smaller than -10 map the entire normal float64 number range into a single bucket, thus are not considered useful.

The mapping/logarithm mapping function uses math.Log(value) times the scaling factor math.Ldexp(math.Log2E, scale). This mapping function is used with 0 < scale <= 20. The maximum scale is selected because at scale 21, simply, it becomes difficult to test correctness--at this point math.MaxFloat64 maps to index math.MaxInt32 and the math/big logic used in testing breaks down.

Data structure

The structure sub-package contains a Histogram aggregator for use by the OpenTelemetry-Go Metrics SDK as well as OpenTelemetry Collector receivers, processors, and exporters.

Implementation

The implementation maintains a slice of buckets and grows the array in size only as necessary given the actual range of values, up to the maximum size. The structure of a single range of buckets is:

type buckets struct {
	backing    bucketsVarwidth[T]  // for T = uint8 | uint16 | uint32 | uint64
	indexBase  int32
	indexStart int32
	indexEnd   int32
}

The backing field is a generic slice of []uint8, []uint16, []uint32, or []uint64.

The positive and negative backing arrays are independent, so the maximum space used for buckets by one Aggregator is twice the configured maximum size.

Backing array

The backing array is circular. The first observation is counted in the 0th index of the backing array and the initial bucket number is stored in indexBase. After the initial observation, the backing array grows in either direction (i.e., larger or smaller bucket numbers), until rescaling is necessary. This mechanism allows the histogram to maintain the ideal scale without shifting values inside the array.

The indexStart and indexEnd fields store the current minimum and maximum bucket number. The initial condition is indexBase == indexStart == indexEnd, representing a single bucket.

Following the first observation, new observations may fall into a bucket up to size-1 in either direction. Growth is possible by adjusting either indexEnd or indexStart as long as the constraint indexEnd-indexStart < size remains true.

Bucket numbers in the range [indexBase, indexEnd] are stored in the interval [0, indexEnd-indexBase] of the backing array. Buckets in the range [indexStart, indexBase-1] are stored in the interval [size+indexStart-indexBase, size-1] of the backing array.

Considering the aggregation.Buckets interface, Offset() returns indexStart, Len() returns indexEnd-indexStart+1, and At() locates the correct bucket in the circular array.

Determining change of scale

The algorithm used to determine the (best) change of scale when a new value arrives is:

func newScale(minIndex, maxIndex, scale, maxSize int32) int32 {
    return scale - changeScale(minIndex, maxIndex, scale, maxSize)
}

func changeScale(minIndex, maxIndex, scale, maxSize int32) int32 {
    var change int32
    for maxIndex - minIndex >= maxSize {
	   maxIndex >>= 1
	   minIndex >>= 1
	   change++
    }
	return change
}

The changeScale function is also used to determine how many bits to shift during Merge.

Downscale function

The downscale function rotates the circular backing array so that indexStart == indexBase, using the "3 reversals" method, before combining the buckets in place.

Merge function

Merge first calculates the correct final scale by comparing the combined positive and negative ranges. The destination aggregator is then downscaled, if necessary, and the UpdateByIncr code path to add the source buckets to the destination buckets.

Scale function

The Scale function returns the current scale of the histogram.

If the scale is variable and there are no non-zero values in the histogram, the scale is zero by definition; when there is only a single value in this case, its scale is MinScale (20) by definition.

If the scale is fixed because of range limits, the fixed scale will be returned even for any size histogram.

Handling subnormal values

Subnormal values are those in the range [0x1p-1074, 0x1p-1022), these being numbers that "gradually underflow" and use less than 52 bits of precision in the significand at the smallest representable exponent (i.e., -1022). Subnormal numbers present special challenges for both the exponent- and logarithm-based mapping function, and to avoid additional complexity induced by corner cases, subnormal numbers are rounded up to 0x1p-1022 in this implementation.

Handling subnormal numbers is difficult for the logarithm mapping function because Golang's math.Log() function rounds subnormal numbers up to 0x1p-1022. Handling subnormal numbers is difficult for the exponent mapping function because Golang's math.Frexp(), the natural API for extracting a value's base-2 exponent, also rounds subnormal numbers up to 0x1p-1022.

While the additional complexity needed to correctly map subnormal numbers is small in both cases, there are few real benefits in doing so because of the inherent loss of precision. As secondary motivation, clamping values to the range [0x1p-1022, math.MaxFloat64] increases symmetry. This limit means that minimum bucket index and the maximum bucket index have similar magnitude, which helps support greater maximum scale. Supporting numbers smaller than 0x1p-1022 would mean changing the valid scale interval to [-11,19] compared with [-10,20].

UpdateByIncr interface

The OpenTelemetry metrics SDK Aggregator type supports an Update() interface which implies updating the histogram by a count of 1. This implementation also supports UpdateByIncr(), which makes it possible to support counting multiple observations in a single API call. This extension is useful in applying Histogram aggregation to sampled metric events (e.g. in the OpenTelemetry statsd receiver).

Another use for UpdateByIncr is in a Span-to-metrics pipeline following probability sampling in OpenTelemetry tracing (WIP).

Acknowledgements

This implementation is based on work by Yuke Zhuge and Otmar Ertl. See NrSketch and DynaHist repositories for more detail.