Exponential Histograms and the Mergeable Bucket Layout

An explicit-bucket histogram fixes its boundaries at instrumentation time, which means the resolution is best where the boundaries were placed and worst everywhere else. That is acceptable when the distribution is known in advance and unacceptable when it is not, which is the normal case: a latency histogram configured for a service at ten milliseconds is useless when the service later operates at ten seconds.

An exponential histogram replaces the fixed boundary list with a formula. The boundaries are powers of a base slightly greater than one, so the ratio between adjacent boundaries is constant and the relative error at any magnitude is the same. The layout is described by a small amount of metadata rather than a long list, which is what makes histograms of different sizes mergeable without loss.

The bucket index is a logarithm

With a base $b > 1$, for instance $b = 2^{1/64}$, boundaries sit at $b^k$ for integer $k$. A positive observation $x$ falls in bucket $k = \lceil \log_b x \rceil$, and the bucket covers the interval $(b^{k-1}, b^k]$. The bucket width grows in proportion to the value, so the ratio $b^k / b^{k-1} = b$ is constant, and any quantile estimate is accurate to within a factor of $b$ regardless of whether the value is a microsecond or an hour.

With $b = 2^{1/64}$, adjacent boundaries differ by about 1.1 percent, so the maximum relative error from bucket width alone is roughly 1.1 percent, the same bound at every scale. Fewer buckets, such as a coarser base $2^{1/16}$, give about 4.4 percent and a much smaller array. The trade is explicit and stated in the same units at every magnitude, which is the property the fixed-boundary layout cannot offer.

Computing $\lceil \log_b x \rceil$ in floating point is slow and, worse, inaccurate near boundaries: a value that should land exactly on $b^k$ can round to either side depending on the order of operations, so two processes recording the same value can place it in different buckets. Implementations therefore avoid the logarithm and extract the exponent and mantissa bits of the float directly, deriving the index arithmetically from the IEEE 754 representation. This is exact, branch-free, and identical across processes, which is a precondition for merging.

Zero and negative observations need separate handling. Zero has no logarithm and is stored in a dedicated zero count. Negative values are either rejected or recorded in a mirrored set of buckets, depending on the format; for latency and size measurements, which are the dominant use, negatives do not occur.

Offset and scale instead of a boundary list

Because the boundaries are generated, a histogram does not need to store them. It stores:

• a scale, which determines the base and therefore the bucket width;
• an offset, the index of the lowest bucket present, so that the array can be stored sparsely;
• the counts for consecutive buckets starting at that offset;
• the zero count, and the total count.

The offset exists because a distribution can occupy a narrow range of indices. A latency distribution between one millisecond and one second spans $\log_b(1000)$ buckets, which at $b = 2^{1/64}$ is about 640. Storing 640 counts is fine; storing the full range from $2^{-1074}$ to $2^{1024}$ is not, so the array is trimmed to the occupied range and the offset records where it starts.

Merging two histograms with the same scale is a shift and an add. The result’s offset is the minimum of the two offsets, and each input’s counts are copied into the result at a position shifted by the difference. Buckets present in one input and absent in the other are simply zero. The merged histogram is exactly the histogram of the pooled observations, with no loss and no approximation beyond what each input already carried.

When the scales differ, the merge must downscale one input. Downscaling by a factor of two combines adjacent buckets pairwise, which doubles the bucket width and therefore the error bound. Downscaling is exact in the sense that no observations are lost, but the error bound of the result is the coarser of the two inputs. Merging is therefore associative and commutative over a fixed scale, and requires a deterministic downscale rule when scales differ, because otherwise the order of merging changes the answer.

Why mergeability is a design constraint, not a convenience

The alternative to a mergeable histogram is to ship raw observations to a central store and compute quantiles there, which costs bandwidth proportional to request volume. It is also impossible for any system that pre-aggregates in the collector, which is the standard architecture precisely because shipping raw data does not scale.

A summary-type instrument avoids shipping raw values by computing quantiles locally, but the quantiles it produces cannot be merged, as discussed in Aggregation Laws: Which Metric Operations Commute. The mergeable histogram is the construction that keeps both properties: bounded local storage and lossless combination. That combination is the reason the exponential layout is the default in formats that were designed after the trade-off was understood, rather than a refinement of the fixed-boundary one.

Mergeability also determines what a fleet-wide percentile means. With mergeable histograms, the percentile of the merged histogram is the percentile of all observations, which is the quantity operators intend when they ask for the 99th percentile across a service. With per-instance percentiles, it is not.

Resolution, memory, and the downscale path

The memory cost is proportional to the number of occupied buckets, which is proportional to the dynamic range of the observed values divided by the resolution. A service whose latencies span three orders of magnitude occupies about $\log_b(1000)$ buckets; the same service at ten times the resolution occupies twice as many.

There is a second cost that is easy to miss: each series carries its own histogram, so the total memory is the number of series times the buckets per histogram. A histogram with 640 occupied buckets and a thousand series is 640,000 counters, which is manageable. The same layout on a hundred thousand series is 64 million counters, which is not. Resolution and cardinality are two independent multipliers on the same memory budget, and the second is usually the one that arrives unexpectedly, as Cardinality Explosion and Where It Comes From describes. Cardinality and resolution multiply, exactly as bucket count and label count multiply in the explicit layout.

The usual mitigation is to downscale at the collector: aggregate histograms locally, then reduce the scale before forwarding, so that the central store receives fewer buckets per series. The reduction is lossless in count and lossy in resolution, and the error bound of the stored data becomes the reduced scale’s bound rather than the instrumentation’s. Choosing where to downscale is choosing which error to accept, and it should be chosen once rather than per pipeline stage.

A third constraint is that the scale must be representable. Formats that encode the scale as a small integer bound it to a modest range, and a requested resolution finer than the format supports must be rounded down to the nearest supported scale. The rounding is silent unless the instrumentation reports it, so an operator who configures an impossible resolution gets a coarser histogram without an error.

Failure modes specific to the layout

The index computation from float bits is exact for normal numbers but breaks at the subnormal boundary, where the exponent field is zero and the implicit leading bit is absent. Observations in that range, below about $2^{-1022}$, either land in a dedicated bucket or are clamped, depending on the implementation. For latency and size measurements this never matters; for a metric that records very small ratios it can.

Infinity and NaN have no bucket. A NaN observation must be dropped or counted separately, because it has no ordering relative to the boundaries and would corrupt the interpolation if assigned an index. Implementations typically increment a separate count, which is a detail worth knowing because a histogram that silently discards NaN observations will report a total count lower than the number of recordings.

The interpolation inside a bucket uses the same linear assumption as the explicit layout, but on a logarithmic axis. The estimate is $b^{k-1} \cdot b^{(qN - c_{\text{lower}})/(c_{\text{upper}} - c_{\text{lower}})}$, which assumes observations are uniformly distributed in log space within the bucket. For a bucket that is 1.1 percent wide, the difference between that assumption and any other is bounded by 1.1 percent, so the assumption matters far less than it does in a wide explicit bucket. This is the quiet benefit of uniform relative spacing: every approximation in the pipeline is bounded by the same small number.