Histogram Done Right: 2KB Memory, 0.2% Error

The Problem: Tracking Request Latency Without Slowing Things Down

When we were building Databend and OpenRaft, we ran into a familiar need: we wanted to see how request latency was distributed across the system, in real time, without burning CPU or memory to do it. This article explains the design behind base2histogram, the library we built to solve it.

Consider the life of a single Raft log entry. It passes through several stages, and each one has its own latency profile:

• Received → written to storage
• Persisted to local disk
• Replicated to remote nodes
• Acknowledged by a majority quorum
• Committed → applied to the state machine

A histogram is the natural tool here — plot latency on the x-axis, request count on the y-axis, and you get an immediate picture of where time is being spent.

This kind of visibility is what lets you find bottlenecks and fix the right thing.

But there’s a catch: collecting metrics can’t get in the way of doing actual work. So the histogram needs to be:

• O(1) to record — no sorting, no rebalancing, nothing that can stall a hot path
• Tiny in memory — the system may run hundreds or thousands of these at once
• Queryable for percentiles — P50, P95, P99

Let’s walk through how we designed one that hits all three.

Recording: Getting Samples Into Buckets

Why Log-Scale Buckets

Most requests cluster around some typical latency, with a few outliers on both ends. This is a log-normal distribution — take the log of the latency values, and the shape becomes a classic bell curve.

The signature look: a peak at lower values, then a gradual long tail stretching to the right.

To build a histogram, we divide the x-axis into buckets and count how many samples land in each one.

The key question is how to size those buckets. Equal-width buckets work great for a normal distribution, but latency is log-normal — the data only looks uniform on a logarithmic scale. So the buckets need to grow on a log scale, not a linear one.

The simplest version of this: each bucket…