Time-Series Compression: Delta Encoding and Variable-Length Integers Explained

Modern infrastructure produces massive volumes of time-series measurements every second: CPU utilization, free memory, disk I/O, API latencies, and transaction rates. Under normal operations, these systems run in a steady state, yielding values with low variance interrupted by occasional anomalies.

Storing millions of continuous integer data points in a naive format quickly overwhelms disk capacity, memory buffers, and I/O pipelines. To handle massive write and read throughput, specialized time-series databases (TSDBs) rely on lightweight, lossless compression algorithms that exploit low variance. At the heart of systems like Facebook’s Gorilla, MongoDB Time Series, and AWS Redshift are two foundational techniques:

1. Delta Encoding (and its cousin, Delta-of-Delta Encoding)
2. Variable-Length Integer Encoding (Varint)

---

The Problem: The Naive Integer Storage Tax

Consider a monitoring system tracking a single metric that records 1 million measurements (N = 1,000,000). If stored as raw 64-bit unsigned integers (uint64), each point requires 8 bytes:

$\text{Total Size} = 1,000,000 \times 8 \text{ bytes} = 8,000,000 \text{ bytes} \approx 8 \text{ MB}$

While 8 MB for 1 million records might seem modest, an enterprise tracking 100,000 metrics at 10-second intervals accumulates nearly 800 GB of raw uncompressed integer data per day for metrics alone.

Raw Stream (uint64, 8 bytes each):
[ 10000 ] [ 10005 ] [ 10007 ] [ 10009 ] [ 10011 ] ... [ 10022 ]
└─8 B──┘  └─8 B──┘  └─8 B──┘  └─8 B──┘  └─8 B──┘       └─8 B──┘

Notice that the metric values in steady-state operations (e.g., 10000, 10005, 10007, 10009, 10011) change very little from one tick to the next. The numbers themselves are large, but their differences are minuscule.

---

Step 1: Delta Encoding

Rather than recording the absolute value of every observation, Delta Encoding stores the difference between consecutive data points.

Given a sequence $V = [v_0, v_1, v_2, \dots, v_{n-1}]$, the delta-encoded sequence $D$ is defined as:

$$\begin{aligned} d_0 &= v_0 \\ d_i &= v_i - v_{i-1} \quad \text{for } i \ge 1 \end{aligned}$$

Example Transformation

Suppose the raw measurements are:

Original: [ 10000, 10005, 10007, 10009, 10011, 10015, 10019, 10022 ]

Computing the differences relative to prior entries:

• $d_0 = 10000$
• $d_1 = 10005 - 10000 = 5$
• $d_2 = 10007 - 10005 = 2$
• $d_3 = 10009 - 10007 = 2$
• $d_4 = 10011 - 10009 = 2$
• $d_5 = 10015 - 10011 = 4$
• $d_6 = 10019 - 10015 = 4$
• $d_7 = 10022 - 10019 = 3$

Delta-Encoded: [ 10000, 5, 2, 2, 2, 4, 4, 3 ]

Characteristics and Trade-offs

graph LR
    A[Raw Stream: High Values, Low Variance] --> B[Delta Encoding]
    B --> C[Compressed Representation: Small Numbers]
    C -->|Decompression / Read| D[Prefix Sum / Reconstruct Original]

• Zero Data Loss: For an input array of length $N$, the delta sequence also has length $N$. No precision is lost.
• The Read/CPU Trade-off: Reconstructing the original value $v_k$ requires a prefix sum over all preceding deltas: $v_k = d_0 + \sum_{i=1}^{k} d_i$. While write operations are fast and sequential reads are trivial, random access to index $k$ requires scanning from the nearest checkpoint/base value.
• The Storage Paradox: If these deltas are still written as standard 8-byte integers (uint64), no space is saved. Storing 2 in a 64-bit integer takes the exact same 8 bytes as storing 10000. Delta encoding alone does not compress data on disk—it merely shifts the distribution of values toward zero.

To capture storage savings, delta encoding must be paired with an encoding scheme capable of storing small numbers in fewer bytes.

---

Step 2: Variable-Length Integer Encoding (Varint)

Fixed-width integers assign 4 or 8 bytes regardless of the number’s magnitude. Variable-length integer encoding (Varint) allocates bytes dynamically: small numbers take 1 byte, slightly larger numbers take 2 bytes, and only very large numbers use full width.

A standard implementation uses continuation-bit encoding (similar to LEB128 or Protocol Buffers varints):

1. Divide the binary representation of the integer into groups of 7 bits.
2. In each byte, use the Most Significant Bit (MSB) as a continuation flag:
   • MSB = 1: More bytes follow for this integer.
   • MSB = 0: This is the final byte of the integer.
3. Pack the remaining 7 bits with data (typically in Little-Endian order).

Byte Layout:
 7   6   5   4   3   2   1   0
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ C │ D │ D │ D │ D │ D │ D │ D │
└───┴───┴───┴───┴───┴───┴───┴───┘
  │   └────────────┬────────────┘
  │                └─ 7 Bits of Data Payload
  └─ Continuation Bit (1 = More bytes, 0 = End)

Concrete Example: Encoding the Number 292

1. Binary Representation of $292$: $\text{Binary} = 100100100_2 \quad (9 \text{ bits})$

2. Split into 7-bit chunks (from least significant to most significant):

   • Lower 7 bits: 0100100
   • Remaining bits: 0000010 (padded with leading zeros)

3. Set the continuation bit:

   • First Byte: Contains 0100100. Because more bits remain, set MSB = 1: $\mathbf{1}\,0100100_2 = 0xA4$
   • Second Byte: Contains 0000010. Because no more bits follow, set MSB = 0: $\mathbf{0}\,0000010_2 = 0x02$

Instead of consuming 8 bytes (0x0000000000000124), the number $292$ is stored in just 2 bytes (0xA4 0x02). Any integer less than $128$ ($0$ to $127$) fits comfortably into a single byte.

---

Step 3: Benchmarking the Combination

When combining Delta Encoding with Varint, the pipeline performs as follows:

1. Compute the delta: $d_i = v_i - v_{i-1}$.
2. Encode $d_i$ using Varint.
3. Write the variable-length byte sequence to disk.

Because measurements in a steady state have low variance, most deltas are small numbers (e.g., $0, 1, 2, 5$). With Varint, every delta under 128 is stored in exactly 1 byte instead of 8 bytes.

Experimental Results (1,000,000 Integers)

Simulating 1,000,000 monotonically increasing measurements with low variance (random steps between 0 and 5, starting at 10,000):

Storage Strategy	Disk Usage	Compression Ratio	Savings
Raw 64-bit Integers (uint64)	8,000,000 bytes (~8 MB)	1.0x	Baseline
Varint Alone (Without Delta)	~3,000,000 bytes (~3 MB)	2.66x	62.5%
Delta Encoding + Varint	~1,000,000 bytes (~1 MB)	8.0x	87.5%

Why Varint Alone Squelched to 3 MB, but Delta Reached 1 MB

• Varint Alone: The raw numbers start at 10000 and increase up to roughly 2,500,000. Numbers in the hundreds of thousands require 3 bytes when encoded via Varint ($2^{14} \le x < 2^{21}$). The average footprint per number settles around 3 bytes.
• Delta + Varint: The base value (10000) takes 2 bytes, but all 999,999 subsequent deltas are integers between $0$ and $5$. Each delta requires only 1 byte. Thus, 1 million numbers collapse into $1 \text{ MB} + \text{minimal overhead} \approx 1 \text{ MB}$.

Raw Storage:
[ 8 Bytes ][ 8 Bytes ][ 8 Bytes ][ 8 Bytes ][ 8 Bytes ]  = 40 Bytes

Delta + Varint:
[ 2 Bytes ][ 1 Byte  ][ 1 Byte  ][ 1 Byte  ][ 1 Byte  ]  = 6 Bytes (85% reduction)

---

Step 4: The Advanced Case — Delta-of-Delta Encoding

What happens if the deltas themselves are large numbers?

For example, consider an event log or sensor timestamp sampled every minute:

Timestamps (Unix Epoch in seconds):
1700000000, 1700000060, 1700000122, 1700000181, 1700000240

Computing the first-order deltas ($D$):

Deltas: [ 1700000000, 60, 62, 59, 59 ]

Here, the deltas are small enough to fit in 1 byte each ($< 128$). But consider millisecond timestamps or network packet sequence IDs where the delta might average around $10,000$ to $10,005$:

Original: [ 100000, 110002, 120005, 130007, 140010 ]
First Delta (D): [ 100000, 10002, 10003, 10002, 10003 ]

Here, each delta is around $10,000$, which requires 2 bytes in Varint. To squeeze this further, databases compute the Delta of the Delta ($D^2$):

$D^2_i = D_i - D_{i-1}$

First Delta (D):        10002, 10003, 10002, 10003
Delta-of-Delta (D^2):         +1,    -1,    +1

The delta-of-deltas collapses to tiny values ($-1, 0, +1$), which can then be bit-packed or encoded using zigzag varints in just a few bits.

graph TD
    T0[Original Timestamps / Metric Stream] -->|First Difference| T1[First-Order Deltas]
    T1 -->|Second Difference| T2[Delta-of-Deltas]
    T2 -->|Variable Length / Bit-Packing| T3[Minimal Storage Footprint]

---

Real-World Implementations in Time-Series Databases

This exact technique is not merely theoretical—it underpins several high-performance storage engines:

1. Facebook Gorilla (now open-sourced in variants like Prometheus TSDB):
   • Timestamps: Uses delta-of-delta encoding combined with variable-length bit-packing (storing differences using 1, 7, 9, 12, or 32 bits depending on bucket size).
   • Float Values: Uses XOR encoding against the previous floating-point value, compressing IEEE 754 floats to only a few bits when variance is low.
2. MongoDB Time Series Collections:
   • Organizes time-series data into columnar bucket stores and applies delta and run-length encoding directly on internal column arrays.
3. Amazon Redshift & ClickHouse:
   • Both analytical engines offer DELTA and DoubleDelta column encodings, specifically recommended for auto-incrementing primary keys, sequence IDs, and date/timestamp columns.

---

Key Takeaways

• Raw integer storage is wasteful for time-series: Metrics in steady states feature low variance, making 64-bit fixed allocations highly redundant.
• Delta encoding shifts the distribution: Storing differences ($v_i - v_{i-1}$) converts large values into small values without losing data precision.
• Varint captures the savings: Delta encoding needs a dynamic-width representation (like 7-bit continuation Varint) to realize disk savings; otherwise, the byte count remains unchanged.
• Compounding gains: In empirical benchmarks, moving from raw integers to Varint alone reduced file size from 8 MB to 3 MB. Combining Delta Encoding with Varint dropped file size to 1 MB—an 87.5% reduction in disk and I/O overhead.
• Delta-of-Delta extends the pattern: For series where deltas are consistent but non-zero, calculating the second derivative ($D^2$) flattens the sequence near zero, enabling near-lossless single-bit representations.