存储算法 #10：Varint 与 ZigZag 编码

Varint 与 ZigZag 编码解决了固定长度整数编码浪费空间的问题，广泛应用于 Protobuf、Thrift、Avro 等序列化框架，小数值可节省 50%~75% 存储空间。

相关文章：Delta 编码 · LZ4 与 Snappy 与 Zstd

目录

问题背景

在二进制序列化中，固定长度编码是最直接的整数表示方式：

实际业务场景中，大量整数字段（用户 ID 增量、状态码、枚举值、消息长度）的值都集中在较小范围内。Google 的内部统计显示，Protobuf 消息中约 80% 的整数字段值小于 128，可用 1 字节编码。

使用 Varint 的系统：

• Protobuf：Google Protocol Buffers，wire type 0
• Thrift：Apache Thrift compact protocol
• Avro：Apache Avro 的 long/int 编码
• LevelDB / RocksDB：内部 key-value 长度编码
• LLVM Bitcode：LLVM IR 的二进制格式

Varint 编码原理（LEB128）

Varint 全称 Variable-length integer，采用 LEB128（Little-Endian Base-128） 编码格式：

每个字节的结构：
┌─────┬────────────────┐
│ MSB │   7-bit data   │
└─────┴────────────────┘
  ↑
  MSB = 1：后续还有字节
  MSB = 0：这是最后一个字节

核心规则：

1. 每字节仅用低 7 位存储数据，最高位（bit 7）为续位标志（MSB）
2. MSB = 1：表示后续还有更多字节
3. MSB = 0：表示当前字节是最后一个字节
4. 多字节时，低位字节先输出（小端序）

空间对比：

encode_varint 伪代码（无符号整数）

function encode_varint(n: uint64) -> bytes:
    result = []
    
    while n >= 128:                    // 还有高位需要编码
        byte = (n & 0x7F) | 0x80      // 取低7位，设置续位标志 MSB=1
        result.append(byte)
        n = n >> 7                     // 丢弃已编码的低7位，处理剩余高位
    
    result.append(n & 0x7F)           // 最后一组（n < 128），MSB=0（不设置）
    return result

关键操作说明：

• n & 0x7F：提取低 7 位数据（掩码 0111 1111）
• | 0x80：设置最高位为 1（续位标志，掩码 1000 0000）
• n >> 7：右移 7 位，等价于除以 128，丢弃已编码的低 7 位
• 循环终止条件：n < 128 即剩余数据只需 1 字节

decode_varint 伪代码

function decode_varint(bytes: byte[]) -> (uint64, int):
    result = 0
    shift  = 0
    
    for i, b in enumerate(bytes):
        data = b & 0x7F                // 提取低7位数据（去掉续位标志）
        result = result | (data << shift)  // 将数据放到正确的位位置
        shift += 7                     // 下一个字节的数据位移偏量增加7
        
        if (b & 0x80) == 0:           // MSB=0：这是最后一个字节
            return (result, i + 1)    // 返回解码结果和消耗的字节数
    
    // 走到这里说明字节流不完整（所有字节 MSB 都是1）
    raise IncompleteVarintError("unexpected end of varint bytes")

关键操作说明：

• b & 0x7F：提取数据位（忽略续位标志）
• data << shift：将数据放到结果的正确位置（第 0 字节占 bit 0-6，第 1 字节占 bit 7-13，...）
• result | (data << shift)：OR 合并，累积结果（每次处理不重叠的 bit 区间）
• shift += 7：每个字节贡献 7 个数据位

执行追踪：编码 300

输入：n = 300 = 0b100101100（二进制）

Step 1：n = 300 = 0b1_0010110_0（分组视角：低7位=0010110_0=44，高位=10=2）
         ↓ 更清晰：300 = 0b00000010_0101100
         低7位 = 0b0101100 = 44
         
         byte1 = (300 & 0x7F) | 0x80
               = 44 | 128
               = 0b00101100 | 0b10000000
               = 0b10101100
               = 0xAC = 172（十进制）
               
         n = 300 >> 7 = 2（还剩高位数据）

Step 2：n = 2 < 128，退出循环
         byte2 = 2 & 0x7F
               = 0b00000010
               = 0x02 = 2（十进制）

结果：[0xAC, 0x02] = [172, 2]，共 2 字节

验证解码：

b0 = 0xAC = 0b10101100，MSB=1（继续）
     data0 = 0xAC & 0x7F = 0b00101100 = 44
     result = 44 << 0 = 44
     shift = 7

b1 = 0x02 = 0b00000010，MSB=0（结束）
     data1 = 0x02 & 0x7F = 2
     result = 44 | (2 << 7) = 44 | 256 = 300 ✓

对比固定编码：

int32 固定4字节：00 00 01 2C
Varint 2字节：   AC 02
节省：50%

ZigZag 编码原理

负数问题：有符号整数的补码表示使得小负数在 Varint 下非常占空间。

-1 的补码（int32）：0xFFFFFFFF = 0b11111111_11111111_11111111_11111111
用 Varint 编码 -1：需要 5 组 7 位 = 5 字节（int32），或 10 字节（int64）

这完全抵消了 Varint 的优势。

ZigZag 映射：将有符号整数映射为非负整数，使绝对值小的数映射结果也小：

映射规律：正数 n → 2n，负数 n → -2n - 1（即正负数交替排列在非负整数轴上）

编码公式（位运算实现，无条件分支）：

encode_zigzag(n: int32) -> uint32:
    return (n << 1) ^ (n >> 31)
    //      ↑             ↑
    //      乘以2        算术右移31位
    //      正数高位补0  正数→全0，负数→全1（0xFFFFFFFF）
    //      XOR 结果：正数末位为0，负数末位为1

解码公式：

decode_zigzag(n: uint32) -> int32:
    return (n >>> 1) ^ -(n & 1)
    //      ↑              ↑
    //      逻辑右移1位    提取末位符号，生成掩码
    //                     n末位=0 → 0，n末位=1 → -1（0xFFFFFFFF）

执行追踪：ZigZag 编码 -1

输入：n = -1（int32）

Step 1：计算 n << 1
        -1 = 0xFFFFFFFF（32位补码）
        -1 << 1 = 0xFFFFFFFE = -2（算术左移，最低位变0）

Step 2：计算 n >> 31（算术右移）
        -1 >> 31：算术右移，符号位扩展
        -1 >> 31 = 0xFFFFFFFF = -1（全1，即-1）

Step 3：XOR
        0xFFFFFFFE ^ 0xFFFFFFFF
        = 0x00000001
        = 1

ZigZag(-1) = 1

Step 4：用 Varint 编码 1
        1 < 128，直接输出 [0x01]
        共 1 字节！（vs 不用 ZigZag 需要 5~10 字节）

验证解码：

ZigZag解码 1：
n = 1
n >>> 1 = 0（逻辑右移）
n & 1 = 1 → -(n & 1) = -1 = 0xFFFFFFFF
0 ^ 0xFFFFFFFF = 0xFFFFFFFF = -1 ✓

编码 -64 示例：

-64 = 0xFFFFFFC0
-64 << 1 = 0xFFFFFF80 = -128
-64 >> 31 = 0xFFFFFFFF = -1
-128 ^ -1 = 0x0000007F = 127
Varint(127) = [0x7F]，1 字节

各框架的选择

Protobuf Wire Type 0

message Example {
    int32  a = 1;   // Varint，不适合负数（-1 需 5 字节）
    sint32 b = 2;   // ZigZag + Varint，适合有正有负
    uint32 c = 3;   // 无符号 Varint，适合非负整数
    fixed32 d = 4;  // 固定 4 字节，适合大数值（> 228 时比 Varint 更小）
    sfixed32 e = 5; // 固定 4 字节有符号
}

选型决策树：

整数字段
├── 值域确定为非负 → uint32/uint64（Varint）
├── 可能为负数
│   ├── 负数罕见 → int32/int64（Varint，负数时较大）
│   └── 正负都常见 → sint32/sint64（ZigZag + Varint）
└── 大数值（> 2^28）→ fixed32/fixed64（固定长度更优）

Thrift Compact Protocol

i16/i32/i64 字段：均采用 ZigZag + Varint（统一处理有符号整数）

Avro

int/long 类型：ZigZag + Varint（与 Thrift 类似）

异常与边界场景

场景 1：Varint 超过最大字节数（防止无限读取）

问题：恶意或损坏的数据可能包含所有字节 MSB 都为 1 的无限序列。

处理：设置最大字节数限制

// int32 最多 5 字节，int64 最多 10 字节
if i >= MAX_VARINT_BYTES:
    raise MalformedVarintError(f"varint exceeds {MAX_VARINT_BYTES} bytes")

Protobuf 实现中，uint32 限制为 5 字节，uint64 限制为 10 字节，超过则抛出解析异常。

场景 2：ZigZag 64 位整数边界溢出

问题：对 int64 最小值 Long.MIN_VALUE = -9223372036854775808 = 0x8000000000000000 执行 ZigZag 编码时：

n = Long.MIN_VALUE = 0x8000000000000000
n << 1 = 0x0000000000000000 = 0（溢出！）
n >> 63 = 0xFFFFFFFFFFFFFFFF = -1
0 ^ -1 = 0xFFFFFFFFFFFFFFFF = Long.MAX_VALUE * 2 + 1 = 18446744073709551615

结果是 uint64 的最大值，仍然正确（是合法的 ZigZag 映射），Varint 编码需要 10 字节。解码时能正确还原 Long.MIN_VALUE。这是设计层面的边界，不是 Bug。

场景 3：网络传输截断（读到不完整的 Varint）

问题：TCP 流式传输可能在 Varint 中间截断，导致读取到部分字节。

现象：循环结束时所有字节 MSB 均为 1，从未遇到 MSB=0 的终止字节。

处理：

// 读完所有可用字节仍未找到 MSB=0
raise IncompleteVarintError("stream ended in the middle of a varint")

// 上层应：
// 1. 等待更多数据到达（流式场景）
// 2. 记录读取位置，等数据补齐后重试
// 3. 标记连接为损坏状态，关闭并重连

场景 4：值为 0 的编码

问题：0 是否需要特殊处理？

分析：

n = 0 < 128，跳过 while 循环
输出 [0 & 0x7F] = [0x00]
结果：[0x00]，1 字节，正确

不需要特殊处理，算法自然覆盖。

场景 5：负数直接用 Varint（不用 ZigZag）

问题：如果 int32 字段存储 -1，不经过 ZigZag 直接 Varint 编码？

分析（Protobuf int32 的实际行为）：

-1（int32）扩展为 int64 后 = 0xFFFFFFFFFFFFFFFF
Varint 编码需要 10 字节（每 7 位一组，共 10 组）
结果：FF FF FF FF FF FF FF FF FF 01（10字节）

对比 ZigZag(-1) = 1 → Varint([0x01])（1字节）
差异：10倍空间！

这就是 Protobuf 中 int32 不适合负数、应使用 sint32 的原因。

参考资料

1. Protocol Buffers Encoding — Google官方文档
   https://protobuf.dev/programming-guides/encoding/

2. LEB128 — Wikipedia
   https://en.wikipedia.org/wiki/LEB128

3. DWARF Debugging Standard（LEB128 最早的规范化定义）
   http://dwarfstd.org/

4. 《Designing Data-Intensive Applications》 — Martin Kleppmann
   第 4 章 Encoding and Evolution，详细讲解 Protobuf / Thrift / Avro 编码格式

5. Apache Thrift Compact Protocol Spec
   https://github.com/apache/thrift/blob/master/doc/specs/thrift-compact-protocol.md

6. Apache Avro Specification（int/long encoding 章节）
   https://avro.apache.org/docs/current/spec.html#binary_encoding

7. Google Protocol Buffers Source Code（varint 实现参考）
   https://github.com/protocolbuffers/protobuf/blob/main/src/google/protobuf/io/coded_stream.cc