[Protobuf] 二进制编码 | Varint & Zigzag(-)

id: proto-flow
name: Protobuf编解码流程
type: mermaid
content: |-
  graph TD
    A[原始数据结构] --> B{序列化}
    B --> C[字段值检测]
    C --> D[Varint/Zigzag编码]
    D --> E[TLV数据封装]
    E --> F[二进制流]
    F --> G{反序列化}
    G --> H[TLV解析]
    H --> I[Varint/Zigzag解码]
    I --> J[重建数据结构]

二、整型

Protobuf 的整型分为两类：定长编码和变长编码。

这两类的区别在于底层存储方式的不同，分别适用于不同的场景。

1. 定长编码

- 定长编码的特点是序列化后占用固定大小的空间。
- 类型及解释：

Protobuf 类型	解释	C++ 类型
`fixed32`	定长 4 字节无符号整型	`uint32_t`
`fixed64`	定长 8 字节无符号整型	`uint64_t`
`sfixed32`	定长 4 字节有符号整型	`int32_t`
`sfixed64`	定长 8 字节有符号整型	`int64_t`

- 示例定义：

message base {
    fixed32 a = 1;
    fixed64 b = 2;
    sfixed32 c = 3;
    sfixed64 d = 4;
}

- 编译后的 C++ 实现：
  在生成的 C++ 文件中，这些字段会被统一管理在一个内部类 Impl_ 中：

struct Impl_ {
    inline explicit constexpr Impl_(...);
    ::uint64_t b_;
    ::uint32_t a_;
    ::int32_t c_;
    ::int64_t d_;
    mutable ::google::protobuf::internal::CachedSize _cached_size_;
    PROTOBUF_TSAN_DECLARE_MEMBER
};

变量 a_, b_, c_, d_ 分别对应表格中的类型。

2. 变长编码

- 变长编码通过尽可能压缩字节数来提高效率，适合小数值的场景。
- 类型及解释：

Protobuf 类型	解释	C++ 类型
`uint32`	变长无符号整型	`uint32_t`
`uint64`	变长无符号整型	`uint64_t`
`int32`	变长有符号整型，正数编码效率更高	`int32_t`
`int64`	变长有符号整型，正数编码效率更高	`int64_t`
`sint32`	变长有符号整型，负数编码效率更高	`int32_t`
`sint64`	变长有符号整型，负数编码效率更高	`int64_t`

三、变长编码方式

编码机制：

VarInt 编码：

- - 每个字节的最高位（MSB）用于指示是否还有更多字节。
  - 剩余 7 位用于存储实际数值，按小端字节序排列。
  - 示例：数字 1023 使用 VarInt 编码为 FF 07。

ZigZag 编码：

- - ZigZag 编码将有符号整数映射到无符号整数，使得绝对值小的数字占用更少字节。

1. Varint 编码

定义
Varint 是一种变长的编码方式，其编码原理是用字节表示数字，值越小的数字使用越少的字节数表示。因此，可以通过减少表示数字的字节数进行数据压缩。
特点

- 对于 int32 类型的数字，一般需要 4 个字节表示。如果采用 Varint 编码，对于很小的 int32 数字，则可以用 1 个字节来表示。
- 虽然大的数字会需要 5 个字节来表示，但大多数情况下，消息都不会有很大的数字，所以采用 Varint 编码方式总是可以用更少的字节数来表示数字。

编码规则

- 每个字节的最高位（MSB）有特殊含义：

- - 如果是 1，表示后续的字节也是数字的一部分。
  - 如果是 0，表示本字节是最后一个字节，且剩余 7 位都用来表示数字。

- 当使用 Varint 解码时，只要读取到最高位为 0 的字节时，表示本字节是一个值经 Varint 编码后得到的字节流的最后一个字节。

负数处理

- 在计算机内，负数一般会被表示为很大的整数，因为计算机定义负数的符号位为数字的最高位。
- 如果采用 Varint 编码方式表示一个负数，那么一定需要 5 个字节（因为负数的最高位是 1，会被当做很大的整数处理）。
- Protobuf 定义了 sint32 和 sint64 类型表示负数，通过先采用 Zigzag 编码（将有符号数转换成无符号数），再采用 Varint 编码，从而用于减少编码后的字节数。

示例

- 值 300 的 Varint 编码

- - 二进制编码为：100101100（即 256 + 32 + 8 + 4）。
  - 从字节流末尾取出 7 bit 并在最高位增加 1 构成一个字节：[1]010 1100。
  - 从字节流末尾取出 7 bit 并在最高位增加 1 构成一个字节，如果是最后一个字节增加 0：[0]0000010。
  - 两字节为：[0]0000010 [1]010 1100。
  - 转换为小端模式：10101100 00000010。
  - 编码结果：1010 1100 0000 0010。
  - 十六进制：AC 02。

- 值 150 的 Varint 编码

- - 二进制编码为：1001 0110。
  - 从字节流末尾取出 7 bit 并在最高位增加 1 构成一个字节：[1]001 0110。
  - 从字节流末尾取出 7 bit 并在最高位增加 1 构成一个字节，如果是最后一个字节增加 0：[0]000 0001。
  - 两字节为：[0]000 0001 [1]001 0110。
  - 转换为小端模式：1001 0110 0000 0001。
  - 编码结果：1001 0110 0000 0001。
  - 十六进制：96 01。

代码实现

#include <iostream>  
#include <vector>  
#include <cstdint>  
#include <stdexcept>  

// Varint 编码函数  
std::vector<uint8_t> EncodeVarint(uint64_t value) {
    std::vector<uint8_t> buffer;
    while (true) {
        if ((value & ~0x7FUL) == 0) {
            // 最后一个字节，最高位为 0  
            buffer.push_back(static_cast<uint8_t>(value));
            break;
        } else {
            // 还有后续字节，最高位为 1，其余 7 位存储值  
            buffer.push_back(static_cast<uint8_t>((value & 0x7F) | 0x80));
            value >>= 7;
        }
    }
    return buffer;
}

// Varint 解码函数  
uint64_t DecodeVarint(const uint8_t*& data, size_t& size) {
    uint64_t result = 0;
    int shift = 0;
    while (true) {
        if (size == 0) {
            throw std::runtime_error("Varint decode error: truncated data");
        }
        uint8_t byte = *data++;
        size--;
        result |= (static_cast<uint64_t>(byte & 0x7F) << shift);
        if (!(byte & 0x80)) {
            // 最后一个字节，退出循环  
            break;
        }
        shift += 7;
        if (shift >= 63) {
            // 超过 64 位整数范围，抛出异常  
            throw std::runtime_error("Varint decode error: integer out of range");
        }
    }
    return result;
}

int main() {
    // 测试 Varint 编码和解码  
    uint64_t test_value = 300;
    std::vector<uint8_t> encoded = EncodeVarint(test_value);

    std::cout << "Encoded Varint: ";
    for (uint8_t byte : encoded) {
        std::cout << std::hex << "  " << static_cast<int>(byte) << " ";
    }
    std::cout << std::endl;

    // 准备解码  
    const uint8_t* data = encoded.data();
    size_t size = encoded.size();
    uint64_t decoded_value = DecodeVarint(data, size);

    std::cout << "Decoded Varint: " << decoded_value << std::endl;

    return 0;
}

与 pb

uint32 与 uint64

这两个是无符号整型，因此无需考虑负数的情况，直接存储原码。
只使用VarInt编码，不使用ZigZag编码。
例如数字1023，其原码为11 1111 1111（即10位都是1），如果使用VarInt编码，则只占用2 byte：

- 第一字节: 1 111 1111。第一个字节的最高有效位（MSB）= 1，说明这不是最后一个字节，后七位数值为111 1111。
- 第二字节: 0000 0111。第二个字节的MSB = 0，说明这是最后一个字节，后七位数值为0000 0111。

int32 与 int64

这两个类型可以用于有符号整型，但此处仅使用VarInt编码，而不使用ZigZag编码。

对于正数，它们直接存储其值，编码方式与uint32和uint64相同。

负数以补码形式存储，导致其VarInt编码看起来像是一个很大的正数。例如，int32的-1：

-1的补码表示为11111111 11111111 11111111 11111111。

因为VarInt每个字节的最高位表示是否还有更多字节，所以-1会编码成5个字节（因为每个字节的最高位都要设为1，除了最后一个）：

11111111 最高位是MSB = 1，表示未结束；

11111111 最高位是MSB = 1，表示未结束；

11111111 最高位是MSB = 1，表示未结束；

11111111 最高位是MSB = 1，表示未结束；

00000001 最高位是MSB = 0，表示结束。

因此，-1作为int32通过VarInt编码后会是11111111 11111111 11111111 11111111 00000001。

负数的编码长度变得非常长，因为它们被编码为其补码的形式，在VarInt中这看起来像一个非常大的数。

因此，虽然int32和int64能够存储负数，但是效率很低。

varint 应用场景

Protocol Buffer通信：用于减少网络传输数据量
LevelDB存储优化：键值对中的整数压缩存储
数据库索引压缩：B+树节点中的指针偏移量编码

此代码完整实现了Varint的核心编解码逻辑，输出结果验证了算法正确性。对于负数处理，需结合Zigzag编码（如(n << 1) ^ (n >> 31)）实现更优压缩

2. Zigzag 编码

定义
Zigzag 编码是一种变长的编码方式，其编码原理是使用无符号数来表示有符号数字，使得绝对值小的数字都可以采用较少字节来表示，特别适合表示负数。
原理

- 对于正整数，可以把无意义的 0 去掉，只存储从 1 开始的“有效”数据，从而压缩数据。
- 对于负数，通过移位和取反操作，将符号位移动到最后，并完成数据位的取反操作，从而实现压缩。

实现

- 对于 32 位整数，(n << 1) ^ (n >> 31) 即可实现 Zigzag 编码。
- 对于 32 位整数，(n >> 1) ^ -(n & 1) 即可实现 Zigzag 解码。

映射规则：

- 正数 n 变成 n * 2
- 负数 n 变成 (-n - 1) * 2 + 1

数值映射表举例

原始值	Zigzag编码值
0	0
-1	1
1	2
-2	3
2	4

示例

- 编码值 -1：(11111111 11111111 11111111 11111111) → (00000000 00000000 00000000 00000001)。
- 编码值 1：(00000000 00000000 00000000 00000001) → (00000000 00000000 00000000 00000010)。

代码实现

// Zigzag 编码
uint32_t zigzag_encode_32(int32_t val) {
    return (uint32_t)((val << 1) ^ (val >> 31));
}

// Zigzag 解码
int32_t zigzag_decode_32(uint32_t val) {
    return (int32_t)((val >> 1) ^ -(val & 1));
}

与 pb

sint32 与 sint64

这两个类型也可以用于有符号整型，结合了VarInt编码和ZigZag编码。

这样编码后，数值的绝对值越小，编码后所需的字节数就越少。
特别是对于负数，这样编码后即使是-1，也只需要一个字节，而不像 int32 那样需要5个字节。

四、其他类型

浮点型

Protobuf 类型	解释	C++ 类型
`float`	单精度浮点型	`float`
`double`	双精度浮点型	`double`

布尔类型

Protobuf 类型	解释	C++ 类型
`bool`	布尔类型	`bool`

字符串

Protobuf 类型	解释	C++ 类型
`string`	包含 UTF-8 和 ASCII 编码的字符串，长度不超过 `2^32`	`string`
`bytes`	字节序列，长度不超过 `2^32`，存储的是原始字节而非字符串内容	`string`

区别：

- string 存储的是编码后的字符串，如 "hello world" 或 "你好世界"。
- bytes 存储的是字节序列，解析时无法直接得到中文字符。

⭕总结

Varint 编码

- 使用动态字节数表示数字，小数值占用更少字节，大数值占用更多字节。
- 对负数不友好，需结合 Zigzag 编码优化。

Zigzag 编码

- 将有符号数映射为无符号数，使得绝对值小的数字占用更少字节。
- 特别适合负数场景。

应用场景：

uint32 和 uint64：只使用 VarInt 编码，适合正数。

int32 和 int64：只使用 VarInt 编码，但负数编码效率低。

sint32 和 sint64：结合 VarInt 和 ZigZag 编码，适合正负数混合场景。

选择策略：

定长 vs 变长：

当数值普遍小于 2^28 时，选择变长编码。

当数值大于 2^28（32 位）或 2^56（64 位）时，选择定长编码。

int vs sint：

- 如果负数出现频率低，使用 int32 或 int64。
- 如果负数出现频率高或正负数出现频率相近，使用 sint32 或 sint64。

所谓数据压缩，说白了就是将不重要的数据忽略或舍弃；由于计算机中只有0和1，本质上就是将无意义的0丢弃，而起到数据压缩的目的。数据压缩可以借助标记位实现

五. JSON 和 Protobuf 的区别 | 字段编号

JSON 的数据表示方式

JSON 使用 键值对 的形式来标识数据与变量之间的映射关系。
例如，以下 JSON 数据：

{
    "id": 1,
    "name": "张三",
    "address": "北京"
}

- "id": 1 表示变量 id 的值为 1。
- "name": "张三" 表示变量 name 的值为 "张三"。
- "address": "北京" 表示变量 address 的值为 "北京"。

在 JSON 中，键（如 "id"、"name"、"address"）是字符串形式。每个字符串需要占用多个字节存储，比如 "address" 至少需要 7 字节存储字符本身，再加上额外的格式字符。

Protobuf 的数据表示方式

Protobuf 是一种高效的二进制序列化协议，它通过字段编号来标识数据与变量之间的映射关系。
字段编号的作用：

- 在 Protobuf 中，每个成员变量都需要一个类内唯一的字段编号。
- 字段编号范围是 [1, 2^29 - 1]，其中 [19000, 19999] 是保留编号，不允许使用。
- 序列化后的数据中，字段编号以 VarInt (MSB 最高位标记）编码形式存储，用于标识对应变量及其类型。

Protobuf 的序列化过程：

- 假设有如下 message 定义：

message People {
    int32 id = 1;
    string name = 2;
    string address = 3;
};

- 序列化后，数据格式大致如下：

0000 0001 "id 的值的二进制编码"
0000 0002 "name 的值的二进制编码"
0000 0003 "address 的值的二进制编码"

- - 第一个字节 0000 0001 是字段编号，表示该数据属于 id 变量。
  - Protobuf 解析时，根据字段编号回到 message 定义中查找对应的变量和类型，然后用相应类型的解析规则解析后续数据。

流程：

例如，读取第一个字节 0000 0001，解析出字段编号为 1，回到 message 定义发现其为 id 变量，类型为 int32，最后用 int32 的解析规则解析后面的值。

JSON 和 Protobuf 的对比

效率：

- JSON：由于键是字符串形式，存储和传输效率较低。例如，"address" 至少需要 7 字节 存储字符本身，加上其他格式字符可能需要更多字节。
- Protobuf：字段编号采用 VarInt 编码，仅需 1 字节即可完成数值与变量的对应关系（字段编号在 [1, 15] 范围内时）。这使得 Protobuf 的存储和传输效率远高于 JSON。

可读性：

- JSON：数据以文本形式存储，人类可直接阅读和理解。
- Protobuf：数据以二进制形式存储，人类无法直接阅读，需要借助工具或解析代码查看内容。

扩展性：

- JSON：新增字段时无需修改已有结构，兼容性强。
- Protobuf：新增字段需要为其分配一个新的字段编号，且字段编号不可重复使用。此外，字段编号 [19000, 19999] 是保留编号，不能使用。

压缩性：

- JSON：由于包含冗长的键名，压缩效果较差。
- Protobuf：字段编号占用空间小，数据紧凑，适合高效压缩。

字段编号的设计建议

字段编号范围优化：

- 字段编号采用 VarInt 编码，一个字节只有 7 位有效位，因此：

- - 字段编号在 [1, 15] 范围内时，占用 1 字节。
  - 字段编号超过 16 时，需要占用更多字节。

- 开发时应将出现频率高的数据字段编号设置为较小值（如 [1, 15]），以提高数据压缩效率。

字段编号的唯一性：

- 每个字段编号在 message 内必须唯一，避免冲突。
- 即使字段被废弃，其编号也不应被重新使用，以免影响版本兼容性。

总结

JSON 是一种易于阅读和使用的文本格式，适合对可读性和兼容性要求较高的场景。
Protobuf 是一种高效的二进制格式，适合对性能和存储空间要求较高的场景。
Protobuf 通过字段编号实现数据与变量的映射关系，相比 JSON 的键值对方式，具有更高的存储和传输效率。

效率对比

数据类型	原始大小	Protobuf（MSB 标记位）	压缩率
int32(300)	4字节	2字节	50%
int32(-150)	4字节	3字节	25%
int64(1<<40)	8字节	6字节	25%

注意:

字段标识号应遵循[1, 2^29-1]范围
保留字段号用于未来扩展
避免频繁创建/销毁Message对象
使用repeated字段替代数组嵌套

[Protobuf] 二进制编码 | Varint & Zigzag(-) | vs json

一、Protobuf 的基本类型

1、序列化

2、反序列化

过程图

二、整型

1. 定长编码

2. 变长编码

三、变长编码方式

1. Varint 编码

与 pb

uint32 与 uint64

int32 与 int64

varint 应用场景

2. Zigzag 编码

数值映射表举例

与 pb

四、其他类型

⭕总结

所谓数据压缩，说白了就是将不重要的数据忽略或舍弃；由于计算机中只有0和1，本质上就是将无意义的0丢弃，而起到数据压缩的目的。数据压缩可以借助标记位实现

五. JSON 和 Protobuf 的区别 | 字段编号

JSON 的数据表示方式

Protobuf 的数据表示方式

JSON 和 Protobuf 的对比

字段编号的设计建议

总结

效率对比

注意:

网站公告

今日签到

热门文章

最新发布

[Protobuf] 二进制编码 | Varint & Zigzag(-) | vs json

一、Protobuf 的基本类型

1、序列化

2、反序列化

过程图

二、整型

1. 定长编码

2. 变长编码

三、变长编码方式

1. Varint 编码

与 pb

uint32 与 uint64

int32 与 int64

varint 应用场景

2. Zigzag 编码

数值映射表举例

与 pb

四、其他类型

⭕总结

所谓数据压缩，说白了就是将不重要的数据忽略或舍弃；由于计算机中只有0和1，本质上就是将无意义的0丢弃，而起到数据压缩的目的。数据压缩 可以借助 标记位 实现

五. JSON 和 Protobuf 的区别 | 字段编号

JSON 的数据表示方式

Protobuf 的数据表示方式

JSON 和 Protobuf 的对比

字段编号的设计建议

总结

效率对比

注意:

网站公告

今日签到

热门文章

最新发布

所谓数据压缩，说白了就是将不重要的数据忽略或舍弃；由于计算机中只有0和1，本质上就是将无意义的0丢弃，而起到数据压缩的目的。数据压缩可以借助标记位实现