The Problem: Tracking Request Latency Without Slowing Things DownFor a cloud data warehouse, performance is not just about average query time. What often matters more is tail latency, predictability, and the ability to pinpoint where things go wrong. In a cloud-native data warehouse like Databend, a single request may pass through multiple stages: SQL planning, distributed execution, remote storage, Raft logging, and state machine apply. Tail latency in any one of these stages can affect the query stability users actually experience. That means we need a way to continuously track latency distributions inside the system — lightweight enough to stay off the hot path, accurate enough to be useful, and cheap enough to run everywhere. This article walks through the design of base2histogram, the lightweight histogram library we built for that purpose. Consider the lifecycle of a single Raft log entry. It passes through several stages, each with 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 a natural fit here: put latency on the x-axis and request count on the y-axis, and you get an immediate view of where time is being spent. This kind of visibility helps you identify bottlenecks and fix the right part of the system. But there is a catch: collecting metrics must not get in the way of doing actual work. The histogram needs to be: O(1) to record: No sorting, no rebalancing, and nothing that can stall a hot path Tiny in memory: A system may run hundreds or thousands of histograms at once Queryable for percentiles: P50, P95, P99 Let's walk through how we designed a histogram that meets all three requirements. Recording: Getting Samples Into Buckets Why Log-Scale BucketsMost requests cluster around a typical latency, with a few outliers on both ends. This often produces a log-normal distribution: take the log of the latency values, and the shape becomes a classic bell curve. The signature shape is a peak at lower values, followed by a gradual long tail to the right. To build a histogram, we divide the x-axis into buckets and count how many samples fall into each one. The key question is how to size those buckets. Equal-width buckets work well for a normal distribution, but latency is often log-normal. The data only looks roughly uniform on a logarithmic scale, so the buckets should grow on a log scale, not a linear one. The simplest version is to make each bucket twice as wide as the previous one:[0,1), [1,2), [2,4), [4,8), [8,16), ...Why powers of 2? Because multiplying by 2 is cheap on a CPU, and mapping a value to its bucket takes a single leading-zero-count instruction. If we simulate a log-normal workload and plot bucket counts with the bucket index on the x-axis — effectively applying a log transform — the result is a clean bell curve: This is great for storage: 65 buckets cover the entire u64range. But the resolution is poor. The last bucket spans half of all possible values, so everything that lands there becomes a blur. A Tempting Fix We Passed OnAn obvious improvement is to use a smaller growth factor, such as 1.1× instead of 2×. That gives us more buckets and finer resolution: The problem is cost. Finding the right bucket for a value l means solving for the smallest x where 1 + 1.1 + 1.1^2 + ... + 1.1^x >= l, which requires floating-point logarithms. That is real overhead on a hot path. We wanted to stay in the world of integers and bit operations. The Trick: Float-Like EncodingHere is the idea that makes the design work: keep bucket sizes roughly exponential, but encode each bucket using a fixed number of bits — a parameter we call WIDTH. Think of a bucket's lower bound as a tiny floating-point number. The MSB position gives the exponent, which tells us which bucket group the value belongs to. The next few bits give the offset within that group. With WIDTH=3, the default configuration, a bucket boundary looks like this in binary: Plain Text 00..00 1 xx 00..00 | MSB