Variable-Length Integer (Varint) Encoding: How Databases Optimize Storage and Transmission

Standard integers in modern programming languages typically occupy fixed widths—most commonly 32 bits (4 bytes) or 64 bits (8 bytes). While a 32-bit unsigned integer can represent values from $0$ to over $4.29$ billion, real-world application workloads rarely distribute numbers uniformly across this vast range.

In practice, data follows an extreme skew: small numbers occur far more frequently than large numbers. For instance, sequence IDs, array lengths, status codes, counters, and small deltas usually fit within tiny numerical boundaries.

When storing or transmitting these values using standard fixed-width primitives, systems waste significant capacity. Variable-length integer encoding (commonly referred to as varint) solves this problem.

---

The Inefficiency of Fixed-Width Integers

Consider storing the number 21 in an unsigned 64-bit integer (uint64):

• Binary representation of 21: 10101 (requires only 5 bits).
• Fixed-width allocation: 64 bits.
• Wasted capacity: $64 - 5 = 59$ bits of pure zero-padding.

Fixed 64-bit Integer (Value: 21)
+-------------------------------------------------------------+-------+
| 00000000 00000000 00000000 00000000 00000000 00000000 00000 | 10101 |
+-------------------------------------------------------------+-------+
  59 wasted padding bits                                       5 data bits

If millions of small integers are serialized as 4-byte or 8-byte primitives to disk or across the network, systems experience:

1. Inflated Storage Footprint: Uncompressed database files grow substantially.
2. Wasted Network Bandwidth: Serialization protocols send mostly zero-bytes over the wire.
3. Cache Pollution: CPU cache lines and database buffer pools fill up with padding bytes instead of active payload data.

While developers could theoretically provision narrower types like uint8 or uint16, production schemas must anticipate worst-case scaling. Varint encoding delivers the best of both worlds: dynamic space allocation that scales with the magnitude of the integer.

---

Where Are Varints Used?

Because of its massive compression ratio for skewed datasets, varint encoding (and its variants like LEB128 or ZigZag encoding) is foundational to data-intensive software:

• Relational & Key-Value Databases: MySQL, Cassandra, Redis, LevelDB, and RocksDB use varints for internal indexing, log structured records, and write-ahead logs (WAL).
• Serialization Frameworks: Google Protocol Buffers (protobuf) and gRPC serialize all integer fields using varints by default.
• File Formats & Executables: WebAssembly (Wasm) and the DWARF debugging format rely on LEB128 (Little-Endian Base 128) encoding.

---

Core Concept: Continuation-Bit Encoding

The fundamental principle behind varint encoding is: Convert an integer into a variable-length byte array where smaller values use fewer bytes, and larger values use more.

The most widespread technique is the continuation-bit approach (used in Protobuf and LEB128):

1. Every byte is divided into two distinct components:
   • 1 Most Significant Bit (MSB): Acts as the continuation bit (flag).
   • 7 Lower Bits: Carry the actual data payload.
2. The Continuation Bit Rules:
   • 1: Indicates that further bytes follow in the sequence.
   • 0: Indicates that this is the final (terminal) byte of the integer.
3. Endianness: Data is usually arranged in Little-Endian order, meaning the least significant 7-bit group is stored in the first byte, followed by progressively higher-order groups.

+-------------------+-----------------------------------+
| Bit 7 (MSB)       | Bits 6 down to 0                  |
+-------------------+-----------------------------------+
| Continuation Flag | 7-bit payload of the integer      |
| 1 = More bytes    |                                   |
| 0 = Last byte     |                                   |
+-------------------+-----------------------------------+

---

Deep Dive: Encoding Step-by-Step

Let’s trace how the integer 292 is encoded into a varint byte sequence.

Step 1: Binary Representation

In standard binary, 292 is: $\text{Binary}(292) = 100100100_2 \quad (9\text{ bits})$

Step 2: Split into 7-Bit Groups

Starting from the least significant bit (LSB), divide the bits into 7-bit chunks:

• Group 1 (Least Significant 7 bits): 0100100 (Decimal 36)
• Group 2 (Remaining 2 bits, padded): 0000010 (Decimal 2)

Original Value (292):     1  0  0  1  0  0  1  0  0
                         |--|  |--------------------|
                       Group 2        Group 1
                      (0000010)      (0100100)

Step 3: Attach the Continuation Bit

• Byte 1 (Group 1): More bits remain to be encoded, so set the MSB to 1.
  • 1 (MSB) + 0100100 (Payload) = 10100100_2
  • Decimal equivalent: 164 (Hex: 0xA4)
• Byte 2 (Group 2): This is the final group, so set the MSB to 0.
  • 0 (MSB) + 0000010 (Payload) = 00000010_2
  • Decimal equivalent: 2 (Hex: 0x02)

Step 4: Final Output Array

The integer 292, which normally requires 4 bytes in an int32, is stored in just 2 bytes:

Serialized Byte Array: [164, 2] (or 0xA4, 0x02)

Savings: $50\%$ reduction in size compared to a 32-bit integer, and $75\%$ reduction compared to a 64-bit integer.

Single-Byte Case (Value < 128)

If the value is 123, its binary representation is 01111011 (7 bits).

• Since it fits entirely in 7 bits, the MSB is 0.
• Encoded byte: 01111011 (Decimal 123).
• Output array: [123] (1 byte only).

---

Decoding Step-by-Step

Decoding reverses the process by sequentially reading bytes from a stream until a terminal byte is reached.

Given the input array [164, 2]:

flowchart TD
    A[Read Byte 0: 164 / 0b10100100] --> B{Is MSB == 1?}
    B -- Yes --> C[Extract lower 7 bits: 0100100] 
    C --> D[Shift 0 positions into accumulator]
    D --> E[Read Byte 1: 2 / 0b00000010]
    E --> F{Is MSB == 1?}
    F -- No --> G[Extract lower 7 bits: 0000010]
    G --> H[Shift 7 positions left and OR with accumulator]
    H --> I[Terminal byte reached: Return integer 292]

1. Read Byte 1 (164 / 10100100_2):
   • MSB is 1 $\rightarrow$ More bytes follow.
   • Extract payload: 164 & 0x7F = 0100100.
   • Shift by $0$ bits into the accumulator: Result = 00000000 00100100.
2. Read Byte 2 (2 / 00000010_2):
   • MSB is 0 $\rightarrow$ Final byte.
   • Extract payload: 2 & 0x7F = 0000010.
   • Shift by $7$ bits into the accumulator: 0000010 << 7 = 00000001 00000000.
   • Bitwise OR with previous accumulator: $\begin{aligned} & 00000000\;00100100 \\ |\; & 00000001\;00000000 \\ \hline =\; & 00000001\;00100100_2 \;(= 292_{10}) \end{aligned}$
3. Result: Reconstructed standard int32 / int64 value 292.

---

Reference Implementation (Go)

The following implementation demonstrates the core bitwise mechanics used in systems like DiceDB (an in-memory Redis-compatible engine).

package main

import (
	"fmt"
)

// EncodeUint64 encodes a uint64 into a varint byte slice.
func EncodeUint64(v uint64) []byte {
	var buf []byte
	for {
		// Extract the lowest 7 bits
		b := byte(v & 0x7F)
		v >>= 7

		if v == 0 {
			// Terminal byte: MSB is 0
			buf = append(buf, b)
			break
		}

		// More bytes follow: set MSB to 1
		b |= 0x80
		buf = append(buf, b)
	}
	return buf
}

// DecodeUint64 decodes a varint byte slice into a uint64.
func DecodeUint64(buf []byte) (uint64, int) {
	var x uint64
	var shift uint

	for i, b := range buf {
		// Check if the continuation bit is set
		if (b & 0x80) == 0 {
			// Terminal byte
			x |= uint64(b) << shift
			return x, i + 1
		}

		// Extract 7 data bits and accumulate
		x |= uint64(b&0x7F) << shift
		shift += 7
	}

	return 0, 0 // Incomplete buffer
}

func main() {
	values := []uint64{21, 123, 292, 1048576}
	for _, val := range values {
		encoded := EncodeUint64(val)
		decoded, bytesRead := DecodeUint64(encoded)
		fmt.Printf("Value: %-7d -> Encoded: %-15v -> Decoded: %-7d (Bytes: %d)\n",
			val, fmt.Sprintf("%v", encoded), decoded, bytesRead)
	}
}

---

Engineering Trade-offs

Varint encoding is not a silver bullet; it introduces specific trade-offs between space and compute.

Dimension	Fixed-Width Integer (e.g., uint64)	Varint Encoding
Storage Size	Always constant (8 bytes)	Dynamic (1 to 10 bytes)
Network Footprint	Large (redundant zeros transmitted)	Highly compact for typical workloads
CPU Processing	$\mathcal{O}(1)$ memory copy, zero parsing	Loops, bit-shifts, masking, and branching
Random Access	Direct offset access ($O(1)$)	Sequential scanning required to locate offsets
Worst-Case Overhead	Predictable	$10$ bytes for values $> 2^{63}$ ($25\%$ size penalty)

1. The Space Advantage

For systems where disk I/O or network throughput is the primary bottleneck, saving $50\%$ to $75\%$ of serialized bytes translates directly into lower tail latencies and reduced operational infrastructure costs.

2. The CPU Cost

Reading an integer is no longer a simple pointer dereference or machine word load. Deserialization requires bitwise operations (&, |, <<), conditional checks for the continuation bit, and sequential byte reading. In pure in-memory compute engines that are CPU-bound, unconditional varint encoding can introduce overhead.

3. The 64-Bit Worst Case

Because each byte carries only 7 bits of data instead of 8, encoding a 64-bit integer whose value is near math.MaxUint64 requires: $\lceil 64 / 7 \rceil = 10 \text{ bytes}$ If an application predominantly deals with exceptionally large integers, varint encoding will use 10 bytes instead of 8 bytes, creating a $25\%$ storage penalty.

---

Summary

• Varint encoding dynamically represents integers using a variable number of bytes based on numerical magnitude.
• By sacrificing 1 bit per byte as a continuation indicator, the system signals whether further bytes are required to reconstruct the number.
• It is designed specifically for standard power-law or zipfian numerical distributions where smaller values dominate traffic.
• While it trades away minor CPU cycles for bit manipulation, the resulting savings in network serialization bandwidth and disk storage make it a default architecture choice across modern distributed storage engines and RPC protocols.