Delta-of-Delta Timestamps and XOR Float Encoding on Disk

A scraped series is a sequence of timestamp-value pairs at a nearly fixed period. Stored naively, each pair costs sixteen bytes: eight for a float64 and eight for an int64 timestamp. At a fifteen-second interval, a single series produces 5,760 pairs per day, which is about 92 kilobytes per day per series. Multiply by a few million series and the storage problem is the dominant cost of the whole system.

The compression that makes this affordable rests on two observations about the data. Timestamps arrive at a regular period, so their differences are nearly constant and the differences of the differences are almost always zero. Values in a counter rise smoothly, so consecutive floats share most of their leading bits and the XOR of two adjacent values has long runs of zeros at both ends. Both facts are exploited by encoding schemes that were designed for exactly this shape of data.

Why timestamps compress to a bit or two

The first timestamp is stored in full and the first delta in a modest number of bits. From the third sample onward, what gets stored is the difference between consecutive deltas. If the scrape period is exactly fifteen seconds and the collector is punctual, that second difference is zero for every sample, and the encoding of zero can be a single bit.

The scheme that does this uses a prefix code over the magnitude of the second difference, with five ranges:

Second difference	Prefix	Payload bits
0	0	0
$[-63, 64]$	10	7
$[-255, 256]$	110	9
$[-2047, 2048]$	1110	12
otherwise	1111	32

A perfectly regular series therefore spends one bit per timestamp after the first two. Jitter of a few milliseconds costs eight bits, made of a seven-bit payload and a two-bit prefix. A single gap in the scrape, from a restart or a network failure, costs thirty-six bits and then returns to one bit per sample, because the delta after the gap is restored to the regular period and the second difference is small again.

The scheme assumes timestamps are monotonically increasing and that the second difference fits in a signed 32-bit range. Both hold for scraped data. A series that is out of order, whether from a backfilled sample or from two samples with the same timestamp, breaks the assumption, and the encoder must either reject the sample or fall back to a full-width encoding for the affected pair.

XOR of adjacent floats and the meaningful window

The value encoding is the more interesting half. Two consecutive float64 values, read as 64-bit integers and XORed, produce all zeros when the values are identical. Values that differ slightly produce a word with a long run of leading zeros and a long run of trailing zeros, because the exponent and the high mantissa bits are shared.

The encoding stores a control bit saying whether the XOR is zero, and if not, whether the block of significant bits falls inside the meaningful window established by the previous non-zero XOR. The window is a pair of numbers: the count of leading zeros and the count of trailing zeros. If the current XOR’s significant bits fit inside the previous window, only the bits inside that window are stored, with a two-bit prefix. If they do not fit, a new window is written with the counts encoded in five and six bits, and the significant bits follow.

The result for a counter that increments by one is close to ideal. Consecutive float64 values differing by one at a magnitude around $2^{20}$ change only the lowest mantissa bits, so the XOR has about 40 leading zeros and no trailing zeros, and the significant portion is a handful of bits. Storing a few bits per sample is common for smooth counters.

The scheme degrades for values that change wildly between samples. A gauge holding a random value produces an XOR with no structure, and the encoder falls back to storing all 64 bits with a small overhead. This is the honest behaviour: the compression is a property of the data’s smoothness, not of the format, and a series that is not smooth is not compressible by this method. The alternative for such series is to not store them at that resolution.

Where the two encodings interact

The block structure matters as much as the per-sample encoding. Samples are grouped into fixed-size blocks, and each block is compressed independently so that a query can decompress one block without touching the rest. That independence is what allows a range query over a day to skip the blocks outside its time bounds, and it is why the block size is a tuning parameter: larger blocks compress better, because the timestamp state and the value window persist longer, but a larger block costs more to decompress when a query needs only a small part of it.

A typical block holds 120 samples, which at fifteen seconds is thirty minutes. The first two timestamps in a block are stored in full or near-full width, so the per-block overhead is amortised over the block. A series with only a few samples per block pays that overhead repeatedly, which is why very sparse series compress poorly and why short-lived series are expensive relative to their sample count.

The value window also resets at block boundaries, so the first value of a block is stored with a fresh window. A block boundary in the middle of a slowly changing series therefore costs a few extra bytes, and a block boundary placed at a discontinuity costs nothing extra because the window would have reset anyway. There is no practical way to place boundaries adaptively without losing the seekability that makes the blocks useful.

The interaction with resets and with counter semantics

Compression is transparent to the reset handling described in Counter Resets and the Extrapolation Inside rate(), because the decompressed samples are exactly the samples that were written. A reset appears as a drop in the value sequence, and the XOR encoding of the pair straddling the drop has a large significant window, costing a full-width entry for that one pair and then returning to compact encoding.

That is the right behaviour, and it is worth contrasting with a scheme that delta-encodes values rather than XOR-ing them. Delta encoding of a counter would store small increments cheaply and would store a reset as a large negative number, which is also cheap in bits but requires the decoder to reconstruct by summation. Reconstruction by summation is fragile across block boundaries and makes random access expensive, because reaching sample $n$ requires decoding samples $0$ through $n-1$. XOR encoding keeps every sample independently decodable given the block’s state, which is what makes the block-level seek work.

The cost of XOR encoding is that it does not exploit the smallness of increments, only the similarity of adjacent values. For a counter incrementing by one, similarity is high and the encoding is compact, so the two approaches converge. For a counter incrementing by a large random amount, the increments are not small and neither approach helps.

What this means for retention planning

The practical arithmetic follows from the bits per sample, and it is the second half of the budget set by the collection period, which Scrape Interval, Lookback Delta, and the Resolution of a Rate covers from the collection side. A smooth counter at one bit per sample plus overhead lands near two bits per sample including the block header, and a noisy gauge near sixty-four. Real deployments see a range, and the range is dominated by how smooth the data is rather than by the format.

That variance is why storage planning based on series count alone is unreliable, since two fleets with identical series counts can differ in stored bytes by an order of magnitude, and it compounds with the multiplication described in Cardinality Explosion and Where It Comes From., and why the byte count of the actual data is the quantity to measure. It also explains why the same fleet can have a retention policy that works for counters and fails for gauges, and why the compression ratio is a property of the workload that changes when the workload does. A service that starts emitting a per-request gauge with a wide value range will consume far more space than its series count suggests.

The scheme’s limits are the limits of its assumptions: regular timestamps, smooth values, and independent blocks. A workload that violates any of them still stores correctly, just less compactly, and the degradation is gradual rather than a cliff. That is the property that makes this encoding a reasonable default even when the data is not ideal, and it is why the format has survived largely unchanged while the systems around it were rewritten.