Deep Dive into Avro Integer Encoding

Introduction

In the world of data serialization and network protocols, efficiently encoding integers is crucial for minimizing storage space and transmission bandwidth. Variable-length integer encoding (often called varint ) is a technique that uses fewer bytes to represent smaller numbers, making it ideal for scenarios where most values are small but the encoding must still support the full integer range.

Apache Avro, a popular data serialization framework, employs variable-length encoding combined with a clever technique called zigzag encoding to efficiently represent both positive and negative integers. This article explores how these techniques work, why they matter, and how they're implemented in practice.

The Problem: Fixed-Width vs. Variable-Width Encoding

Traditional integer representation uses fixed-width encoding. A 32-bit integer always uses 4 bytes, and a 64-bit integer always uses 8 bytes, regardless of the actual value:

• The number 1 stored as int32: 00 00 00 01 (4 bytes)

• The number 127 stored as int32: 00 00 00 7F (4 bytes)

• The number 1000000 stored as int32: 00 0F 42 40 (4 bytes)

This is wasteful when dealing with data where most values are small. In many real-world datasets—counters, IDs, timestamps deltas, array lengths—values tend to cluster toward zero or small positive numbers.

Variable-length encoding solves this by using fewer bytes for smaller values:

• Small numbers use 1 byte

• Medium numbers use 2-3 bytes

• Large numbers use 4-5 bytes (or more for 64-bit)

Base-128 Varint Encoding

The most common variable-length encoding scheme is base-128 varint, used by Protocol Buffers, Avro, and other formats. Here's how it works:

The Continuation Bit Mechanism

Each byte in a varint has two parts:

1. The continuation bit (bit 7, the MSB - most significant bit): Indicates whether more bytes follow

   • 1 means "more bytes coming"

   • 0 means "this is the last byte"

2. The payload (bits 0-6, the lower 7 bits): Contains actual data

In byte notation: [continuation bit][bit 6][bit 5][bit 4][bit 3][bit 2][bit 1][bit 0]

This means each byte carries 7 bits of meaningful data (bits 0-6), with bit 7 reserved to signal if the more bytes need to be read to continue constructing the number.

Encoding Algorithm

To encode an unsigned integer:

1. Take the lowest 7 bits of the number

2. If the number has more bits remaining, set the continuation bit to 1

3. Write this byte to output

4. Right-shift the number by 7 bits

5. Repeat until the number becomes zero

Example: Encoding 300

Let's encode the number 300 step by step:

Original value: 300 (decimal)
Binary representation: 100101100 (9 bits needed)

Step 1: Extract the lowest 7 bits (bits 0-6)
        300 in binary: 100101100
        Lowest 7 bits: 0101100 (this is 44 in decimal)

        Check if more bits remain: 300 >> 7 = 2 (non-zero, so yes)
        Set bit 7 (continuation bit) to 1
        First byte: [1][0101100] = 10101100 = 0xAC
                     ↑  ↑------↑
                     |  bits 0-6 (payload)
                     bit 7 (continuation=1, more bytes follow)

Step 2: Process remaining value (2)
        2 in binary: 10
        This fits in 7 bits: 0000010

        Check if more bits remain: 2 >> 7 = 0 (done!)
        Set bit 7 (continuation bit) to 0
        Second byte: [0][0000010] = 00000010 = 0x02
                      ↑  ↑------↑
                      |  bits 0-6 (payload)
                      bit 7 (continuation=0, last byte)

Encoded result: [0xAC, 0x02]

Important: Varint encoding uses little-endian byte order - the least significant bits come first. So when we decode:

• First byte (0xAC) gives us bits 0-6 of the original number: 0101100

• Second byte (0x02) gives us bits 7-8 of the original number: 10

• Combined: 10|0101100 = 100101100 = 300

Decoding Algorithm

To decode a varint:

1. Read a byte

2. Extract the lower 7 bits and add them to the result (shifted appropriately)

3. If the continuation bit is 1, read another byte and repeat

4. If the continuation bit is 0, decoding is complete

Example: Decoding [0xAC, 0x02]

Byte 1: 0xAC = 10101100
        Continuation bit (bit 7): 1 (more bytes coming)
        Payload (bits 0-6): 0101100 (44 in decimal)
        Place at position 0: 44 << 0 = 44
        Result so far: 44

Byte 2: 0x02 = 00000010
        Continuation bit (bit 7): 0 (this is the last byte)
        Payload (bits 0-6): 0000010 (2 in decimal)
        Place at position 7: 2 << 7 = 256

Final result: 44 + 256 = 300

Verification: 44 = 0101100 (bits 0-6)
              256 = 100000000 (bit 8 set)
              Combined: 100101100 = 300 ✓

The Signed Integer Problem

Base-128 varint works beautifully for unsigned integers, but there's a problem with signed integers. To understand why, we first need to understand how computers represent negative numbers.

Two's Complement Representation

Modern computers use a system called two's complement to represent signed integers. This is the universal standard across virtually all computer architectures today.

In two's complement:

• Positive numbers are represented normally in binary

• Negative numbers are represented by inverting all bits and adding 1

Here's how it works for an 8-bit signed integer:

Positive numbers (0 to 127):
  0 = 00000000
  1 = 00000001
  2 = 00000010
 127 = 01111111

Negative numbers (-128 to -1):
 -1 = 11111111
 -2 = 11111110
 -3 = 11111101
-128 = 10000000

Key properties:

1. The most significant bit (MSB) is the sign bit: 0 = positive, 1 = negative

2. There's only one representation for zero (unlike sign-magnitude)

3. Addition and subtraction work the same way for positive and negative numbers

4. Negative numbers have all their high-order bits set to 1

Example: How to calculate -3 in two's complement (8-bit)

Start with +3:

Step 1: 3 in binary = 00000011
Step 2: Invert all bits = 11111100
Step 3: Add 1         = 11111101
Result: -3 = 11111101

For 32-bit integers, the same principle applies but with 32 bits:

 1 (32-bit) = 00000000 00000000 00000000 00000001
-1 (32-bit) = 11111111 11111111 11111111 11111111

The Problem with Varint Encoding

Now that we understand two's complement, we can see the problem. Negative numbers have all high-order bits set to 1.

Consider encoding -1 as a signed 32-bit integer:

-1 in two's complement (32-bit): 11111111 11111111 11111111 11111111

If we naively apply varint encoding to this, we get:

Byte 1: 11111111 (continuation bit: 1, payload: 1111111)
Byte 2: 11111111 (continuation bit: 1, payload: 1111111)
Byte 3: 11111111 (continuation bit: 1, payload: 1111111)
Byte 4: 11111111 (continuation bit: 1, payload: 1111111)
Byte 5: 00001111 (continuation bit: 0, payload: 0001111)

Result: 5 bytes to encode -1!

Why 5 bytes when the original was only 4 bytes? Because varint encoding only uses 7 bits per byte for data (the 8th bit is the continuation bit). So 32 bits of data requires ⌈32 ÷ 7⌉ = 5 bytes. This defeats the entire purpose of variable-length encoding.

The problem is that small negative numbers (like -1, -2, -3) have many high-order bits set due to two's complement representation, causing them to be encoded as if they were very large numbers.

Zigzag Encoding: The Solution

Zigzag encoding is a transformation that maps signed integers to unsigned integers in a way that ensures small absolute values (whether positive or negative) map to small unsigned values. This allows varint encoding to work efficiently for signed integers.

The Mapping

Zigzag encoding creates this mapping:

Signed    Unsigned (Zigzag)
  0    →       0
 -1    →       1
  1    →       2
 -2    →       3
  2    →       4
 -3    →       5
  3    →       6
 -4    →       7
  4    →       8
...

Notice the pattern:

• Zero maps to zero

• Negative numbers map to odd unsigned values

• Positive numbers map to even unsigned values

• The absolute value determines the magnitude of the encoded value

The Formula

For a signed integer n, the zigzag encoding is:

32-bit integers:

zigzag(n) = (n << 1) ^ (n >> 31)

64-bit integers:

zigzag(n) = (n << 1) ^ (n >> 63)

Let's break down how this works:

1. n << 1: Left shift by 1 (multiply by 2)

2. n >> 31 (or n >> 63): Arithmetic right shift by 31/63 positions

   • For positive numbers: Results in 0x00000000

   • For negative numbers: Results in 0xFFFFFFFF (sign extension)

3. ^ (XOR): Combines the two results

Why This Works

For positive numbers (e.g., n = 3):

n = 3 = 00000000 00000000 00000000 00000011

n << 1  = 00000000 00000000 00000000 00000110 (6)
n >> 31 = 00000000 00000000 00000000 00000000 (0, sign bit was 0)

XOR: 6 ^ 0 = 6

For negative numbers (e.g., n = -3):

n = -3 = 11111111 11111111 11111111 11111101 (two's complement)

n << 1  = 11111111 11111111 11111111 11111010 (-6 in two's complement)
n >> 31 = 11111111 11111111 11111111 11111111 (-1, sign bit was 1)

XOR: -6 ^ -1 = 5

The XOR operation effectively flips all bits when dealing with negative numbers, transforming the two's complement representation into the zigzag-encoded value.

Decoding Zigzag

To decode a zigzag-encoded unsigned integer n back to a signed integer:

decode(n) = (n >>> 1) ^ -(n & 1)

Where:

• >>> is unsigned right shift (logical right shift)

• & is bitwise AND

• - negates the value

Example: Decoding 5 back to -3:

n = 5 = 00000000 00000000 00000000 00000101

n >>> 1 = 00000000 00000000 00000000 00000010 (2)
n & 1   = 00000000 00000000 00000000 00000001 (1)
-(n & 1)= 11111111 11111111 11111111 11111111 (-1)

XOR: 2 ^ -1 = -3

Avro's Implementation

Apache Avro uses zigzag encoding for its int (32-bit) and long (64-bit) types in its binary encoding format.

Encoding Process in Avro

1. Apply zigzag encoding to convert signed integer to unsigned

2. Apply varint encoding to the resulting unsigned integer

Space Efficiency

Here's how various integers are encoded in Avro:

Notice that values from -64 to 63 fit in a single byte, while traditional fixed-width encoding would require 4 or 8 bytes.

Implementation in Code

Here's a practical implementation in multiple languages:

Python

def zigzag_encode(n):
    """Encode signed integer using zigzag encoding"""
    return (n << 1) ^ (n >> 31) if n.bit_length() <= 32 else (n << 1) ^ (n >> 63)

def zigzag_decode(n):
    """Decode zigzag-encoded integer back to signed"""
    return (n >> 1) ^ -(n & 1)

def write_varint(n, output):
    """Write unsigned integer as varint to output buffer"""
    while n > 0x7F:
        output.append((n & 0x7F) | 0x80)
        n >>= 7
    output.append(n & 0x7F)

def read_varint(data, offset):
    """Read varint from data buffer starting at offset"""
    result = 0
    shift = 0
    pos = offset

    while True:
        byte = data[pos]
        result |= (byte & 0x7F) << shift
        pos += 1

        if (byte & 0x80) == 0:
            break
        shift += 7

    return result, pos

# Complete encoding/decoding
def encode_signed_varint(n):
    """Encode signed integer using zigzag + varint"""
    output = []
    zigzag = zigzag_encode(n)
    write_varint(zigzag, output)
    return bytes(output)

def decode_signed_varint(data, offset=0):
    """Decode signed integer from zigzag + varint"""
    zigzag, new_offset = read_varint(data, offset)
    return zigzag_decode(zigzag), new_offset

Performance Characteristics

Space Complexity

For random uniformly distributed integers, varint encoding averages about the same space as fixed-width encoding. However, for real-world data with small values:

32-bit integers:

• Values [-64, 63]: 1 byte (vs. 4 bytes fixed)

• Values [-8192, 8191]: 2 bytes (vs. 4 bytes fixed)

• Values up to ±1M: 3 bytes (vs. 4 bytes fixed)

• Worst case: 5 bytes (vs. 4 bytes fixed)

64-bit integers:

• Values [-64, 63]: 1 byte (vs. 8 bytes fixed)

• Worst case: 10 bytes (vs. 8 bytes fixed)

Time Complexity

• Encoding: O(log n) where n is the value (proportional to number of bytes needed)

• Decoding: O(bytes read)

The performance overhead is minimal—typically a few CPU cycles per integer—and is vastly outweighed by the I/O savings from smaller data sizes.

Comparison with Other Schemes

Protocol Buffers

Protocol Buffers uses the same varint + zigzag encoding scheme as Avro for signed integers (sint32/sint64 types). However, regular int32/int64 in protobuf use only varint without zigzag, making them efficient only for non-negative values.

MessagePack

MessagePack uses different integer formats with fixed-size headers to indicate the integer type and size, offering a different trade-off between encoding complexity and efficiency.

UTF-8 (for comparison)

UTF-8 uses a similar continuation bit mechanism for variable-length character encoding, demonstrating the broad applicability of this technique.

Practical Considerations

When to Use Varint + Zigzag

Ideal use cases:

• Counter values ( eg Age )

• Deltas between timestamps or IDs

• Array/collection sizes

• Values with a Zipfian or power-law distribution

• Sequential IDs or version numbers

Not ideal for:

• Cryptographic data (uniformly random)

• Already compressed data

• Fixed-size binary structures where alignment matters

• Large negative numbers (though zigzag helps significantly)

Alignment and Memory Access

Varint encoding produces unaligned data, which can complicate direct memory mapping and random access. This is acceptable for serialization formats but unsuitable for in-memory data structures requiring fast random access.

Endianness

Varint encoding is inherently endian-neutral since it processes bytes sequentially from least significant to most significant. This makes it excellent for cross-platform serialization.

Conclusion

Variable-length integer encoding with zigzag transformation represents an elegant solution to the problem of efficiently encoding integers in serialization formats. By recognizing that most real-world data consists of small values and applying a clever bit-manipulation technique to handle signed integers, Avro and similar formats achieve significant space savings with minimal computational overhead.

The combination of varint and zigzag encoding demonstrates several important principles in systems design:

1. Understand your data distribution: The technique exploits the fact that small values are common

2. Transform to simplify: Zigzag encoding converts a difficult problem (negative numbers) into an easy one (unsigned numbers)

3. Bit-level thinking: Elegant solutions often emerge from careful consideration of bit patterns

4. Trade-offs matter: Accepting slightly more complex encoding/decoding logic yields substantial space savings

For anyone working with data serialization, network protocols, or storage systems, understanding these techniques provides both practical benefits and insight into the kind of creative thinking that optimizes modern systems.