文章

Protobuf 编码原理及优化思路

发表于
作者 JunQiang
22 分钟阅读
Protobuf 编码原理及优化思路

Protobuf编码原理

1. 基本类型

1.1 定点数值类型

proto3语法中：$int32$ 、 $int64$ 、 $uint32$ 、 $uint64$ 、 $sint32$ 、 $sint64$ 、 $fixed32$ 、 $fixed64$ 、 $sfixed32$ 、 $sfixed64$ 、 $bool$ 、 $enum$ 属于定点数值类型。

  • $int32$、$int64$、$uint32$、$uint64$ 会直接使用varint编码
  • $bool$ 类型会直接使用一个字节存储
  • $enum$ 可以看成是一个 $int32$ 类型。
  • $sint32$、$sint64$ 类型会先进行zigzag编码，再进行varint编码
  • $fixed32$、$fixed64$、$sfixed32$、$sfixed64$ 类型会使用定长的四个或八个字节进行存储。
  • varint 编码：变长编码，对于 小正整数 有较 好 的压缩效果，对于 大整数或负数 编码后 字节流 长度会 变大。
  • zigzag 编码：定长编码，将 小正整数 和 小负整数 转换到 小正整数，结合 varint 编码，可以实现对绝对值较小的整数有良好的压缩效果。

关于 varint 编码和 zigzag 编码的细节可以参考文档 » https://protobuf.dev/programming-guides/encoding/

>> $ int32$ 与 $sint32$ 和 $fixed32$ 的对比？

  • $int32$ 使用 varint 编码，对于小正数有较好的压缩效果，对于大整数和负数会导致额外的字节开销。
  • $fixed32$ ，该类型不会对数值进行任何编码，对大于 $2^{28}-1$ 的整数比 $int32$ 占用更少的字节。
  • 而对于负数使用 zigzag 编码，这样绝对值较小的负数都能被有效压缩。

1.2 浮点数值类型

proto3语法中：$float$ 和 $double$ 属于浮点数据类型，使用定长的 四个字节 或 八个字节 存储，数据直接用IEEE754标准表示。

1.3 字符串类型

proto3语法中：string、bytes属于字符串类型，字符串类型序列化后的字节流为其原始内容本身。这两种类型的不同之处在于string内的字节流必须是utf8编码，bytes没有这种要求。

2. 复合类型

2.1 结构体类型

proto3语法中使用message定义结构体类型，结构体类型有多个不同tagid构成的字段，字段可以是基本类型或复合类型，甚至可以是这个结构体类型本身。

结构体每个字段底层都使用这种格式进行存储，需要注意的是 typeid、length、data 三部分长度会根据实际情况发生改变。 (本质还是TLV模型)

1
2
3
4

typeid    length   data
+--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------+
typeid

typeid用于存储结构体字段编号（tagNum）和字段类型（tagType）

  • tagNum为字段“=”后的数字，tagNum也使用varint进行编码，因此如果“=”后的数字很大，则可能导致tagNum编码变大
    • tagid占用多个字节
  • tagType则指明数据类型，这部分固定占用三个bit
1
2
3
4
5

|tagNum        |tagType|
+----------------------+
|x  x  x  x  x  x  x  x|
+----------------------+
 7              2     0

下表记录了不同字段类型对应的tagType值：

tagType类型
0$int32$、$int64$、$uint32$、$uint64$、$sint32$、$sint64$、$bool$、$enum$
1$fixed64$、$sfixed64$、$double$
2$string$、$bytes$、结构体类型、数组类型、map类型
3弃用
4弃用
5$fixed32$、$sfixed32$、$float$
length

length 部分表示 data 部分的长度，同样使用 变长varint编码

需要注意的是如果字段类型是 定点数值 类型或 浮点数值 类型，则 length 部分不会体现在序列化后的字节流中。

data

data部分为原始数据，可以是基本类型和复合类型序列化后的字节流

算法通常递归的对这些字段进行处理。

2.1 数组类型

proto3 语法中使用 repeated 为前缀的字段即为数组类型，也就是说 repeated 关键字是用来修饰结构体类型的字段的。

如果repeated修饰的是 定点数值 类型或 浮点数值 类型，在 proto3 语法下会默认按照下图方式将这些数值排列在一起

  • \[Length = \sum_{0}^N Data_N\]

length 部分记录 $data1 ~ dataN$ 所有数值的字节数之和。

1
2
3
4

typeid    length   data1    data2       dataN
+--------+--------+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|  |xxxxxxxx|
+--------+--------+--------+--------+~~+--------+

如果修饰的是其他类型则会按照以下方式组织这些数据（其中 field1 为数组类型），需要注意的是属于同一个数组的不同元素中间可能有其他字段的元素插入。

1
2
3
4
5

typeid1   length1  data1     typeid2  length2  data2     typeid1  length3  data3    
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
|			field1			 ||			field2			 ||			field1			 |

2.2 map 类型

实际业务中较少使用

proto3语法中 map 也是一种修饰符，修饰结构体类型的字段。

  • map 类型的 key必须为 定点数值类型 或 string类型

  • map的底层存储 key-value 键值对，采用和数组类型一样的存储方法，数组中每个元素是 kv键值对。

以下数据定义中，message A 和 message B 有完全相同的底层存储结构。

1
2
3
4
5
6
7
8
9
10
11
12

message A{
	map<int32,float> mp = 1;
}

message KV{
	int32 K = 1;
	float V = 2;
}

message B{
	repeated KV mp = 1;
}

2.3 类型默认值

如果类型为默认值，则该字段 tagid+length+data 不会出现在序列化后的字节流中。

类型默认值
$int32$、$int64$、$uint32$、$uint64$、$fixed32$、$fixed64$、$sfixed32$、$sfixed64$、$float$、$double$0
$enum$0对应的枚举值
$bool$false
$string$”“
$bytes$空字节流
结构体类型null (对应字段的指针为空)
数组类型空数组
map 类型空map

需要注意的是:

  • 如果某个字段是结构体类型，该字段对应的结构体中的所有元素均为默认值，这种情况下该字段的data部分会被省略，只保留tagid:和length部分，当然length部分值为0。
  • 如果字段的指针为空，则该字段不会有任何内容出现在序列化后的字节流中。

2.4 序列化示意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

enum C {
  C1 = 0;
  C2 = 1;
}

message B {
  int32 X = 1;
  sint32 Y = 2;
  C Z = 3;
}

message A {
  repeated float F1 = 1;
  map<string, B> F2 = 20;
}

1
2
3
4
5
6
7
8

message A 内存中的数值:
F1:1.2  F1:2.3  F2:{key:"123"  value:{X:1  Y:-1  Z:C2}}

message A 序列化后的字节流:
0XA,0X8,0X9A,0X99,0X99,0X3F,0X33,0X33,0X13,0X40,0XA2,0X1,0XD,0XA,0X3,0X31,0X32,0X33,0X12,0X6,0X8,0X1,0X10,0X1,0X18,0X1

|---------------------A.F1---------------------|-------------------------------A.F2----------------------------------|
       |-------1.2---------|---------2.3------|A.F2.tagid|+----------|----"123"----|-------------|1|------|-1|----|C2|

需要注意的是 message A 的 F2 字段的 tagNum 是 $20$，而 tagType 值是 $2$ ，按照上文讨论的编码原理 A.F2.tagid 编码如下：

1
2
3
4
5
6

+----------------------+ +----------------------+
|0  0  0  0  0  0  0  1| |1  0  1  0  0  0  1  0|
+----------------------+ +----------------------+
 15                                      2     0 
|typeNum                                |tagType|
|varint编码，编码前：00010100，值为20       |值为2  |

>> protobuf序列化之后 低地址字节在前，高地址字节在后

优化思路

1. 类型优化

根据 varint 编码和 zigzag 编码，

  • zigzag(n) = (n « 1) ^ (n » (sizeof(n)*8 - 1))

其中，n表示 有符号整数

<< 表示左移操作，>> 表示带符号右移操作，^表示按位异或操作

sizeof(n)表示整数n`的字节数。

计算 正整数 经过 varint 编码后占用字节数的算式:

  • 字节数 \(= ceil(\frac {log_2(n+1)}{7})\)

其中，n 表示正整数，ceil 表示向上取整，log2 表示以2为底的对数。

这个算式的原理是 varint 编码使用7位来表示一个数，每个字节的最高位用作标志位，表示是否还有后续字节。

所以，实际上每个字节只有7位用来表示数值。

因此，计算一个数n需要多少个字节，就是计算以2为底的对数，然后除以7，最后向上取整。

对于 zigzag编码需要明确一点：zigzag 编码需要和 varint 编码一起使用。

zigzag 编码可以看作将正负交替的数值序列映射至正整数序列，之后再由 varint 对正整数进行编码。

原始数值 ：\(0,-1,1,-2,2,-3,3,-4,4...\)

映射数值： \(0,1,2,3,4,5,6,7,8...\)

基于最小字节流长度为目标的数值对应类型

数据范围推荐类型
[ $-2^63$ , $-231$ )$sfixed64$
[ $-2^31$ , $-228$ )$sfixed32$
[ $-2^28$ , $-214$ )$sint64$
[ $-2^14$ , $2^14-1$ ]$sint32$
( $2^14-1$ , $2^28-1$ ]$uint32$ 或 $int32$
( $2^28-1$ , $2^32-1$ ]$fixed32$
( $2^32-1$ , $2^56-1$ ]$uint64$ 或 $int64$
( $2^56-1$ , $2^64-1$ ]$fixed64$

2. 结构优化

protobuf 因为考虑兼容性原因，存储了很多tagid、length 这些记录结构信息的字段。

在实际应用场景中如果数据的结构较为紧凑，多个字段都有相同的结构是否能去掉记录结构信息的字段，只保留内容信息的字段，从而减少数据长度呢？

优化示例

假设：优化前大部分message A中的X、Y字段均非默认值

优化前
1
2
3
4
5
6
7
8
9
10
11
12
13

message A{
	int32 x = 1;
	int32 y = 2;
}

message B{
	int32 z = 1;
}

message C{
	repeated A as = 1;
	B b = 2 ;
}

1
2
3
4
5

message C 序列化后字节流：
0XA,0X4,0X8,0X1,0X10,0X2,0XA,0X4,0X8,0X1,0X10,0X2,0XA,0X4,0X8,0X1,0X10,0X2,0X12,0X2,0X8,0X3

message C 内存中数值：
as:{x:1 y:2} as:{x:1 y:2} as:{x:1 y:2} b:{z:3}
优化后
1
2
3
4
5

message C{
	repeated int32 xs = 1;
	repeated int32 ys = 2;
	int32 z = 3;
}

1
2
3
4
5

message C 序列化后字节流：
0XA,0X3,0X1,0X1,0X1,0X12,0X3,0X2,0X2,0X2,0X18,0X3

message C 内存中数值：
xs:1  xs:1  xs:1  ys:2  ys:2  ys:2  z:3

3. 数据优化

由香农的信息论可知，

  • 如果一组数据分布范围很广，每个数据点现频率几乎相同则需要用较多bit对这组数据进行编码。
  • 如果这组数据分布较为单一，某些数据点出现频率较高，这种数据分布能较好地使用变长编码表示。

由此可知，对于 分布范围较小，重复性较高的数据 （例如，时间戳） ，选取一个 基准值，协议中记录 与 基准值 的差值

优化示例

优化前
1

message A { repeated int64 timestamps = 1; }

1
2
3
4
5

message A 序列化后字节流：
0XA,0X1E,0XCA,0XDE,0XA5,0XAF,0XAD,0X31,0XCE,0XDE,0XA5,0XAF,0XAD,0X31,0XD2,0XDE,0XA5,0XAF,0XAD,0X31,0XD6,0XDE,0XA5,0XAF,0XAD,0X31,0XDA,0XDE,0XA5,0XAF,0XAD,0X31,

message A 内存中数值：
timestamps:1695805960010  timestamps:1695805960014  timestamps:1695805960018  timestamps:1695805960022  timestamps:1695805960026
优化后
1
2
3
4

message A {
  int64 base = 1;
  repeated int64 timestamps = 2;
}

1
2
3
4
5

message A 序列化后字节流：
0X8,0XCA,0XDE,0XA5,0XAF,0XAD,0X31,0X12,0X5,0X0,0X4,0X8,0XC,0X10,

message A 内存中数值：
base:1695805960010 timestamps:0 timestamps:4 timestamps:8 timestamps:12 timestamps:16

由于差值通常较小，在此基础上可以继续进行bit优化，比如最大差值是15则最多用4个bit表示一个差值即可，这样一个字节就可以记录两个差值的信息，从而进一步压缩序列化字节流。

4. 案例

情景描述

  • 几千个玩家同时在一个区域内，将这个区域进行网格划分，一个网格内可能包含多个玩家

  • 服务器需要向每个玩家同步以这个玩家所在的网格为中心，周围九宫格的玩家的移动信息

特征分析

  1. 【数据差异小】同一个格子内的玩家的位置信息 差值较小

  2. 【字段多】给每个玩家同步的数据包有较多的数组类型字段，且这些数组类型字段有较多元素
  3. 【同步量大】服务器给每个玩家同步的数据较多，如果这个平台有8000人，每个网格平均8人，服务器给每个玩家每秒同步20帧，理论上每个玩家每秒需要同步数据量为9×8×20 = 1440，整个平台需要同步的数据量为：1440×8000=11520000

协议优化

优化前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

message TVector {
  float x = 1;
  float y = 2;
  float z = 3;
};

message TMovementComp {
  TVector location                 = 1;  // 坐标
  TVector rotation                 = 2;  // 朝向
  TVector Velocity                 = 3;  // 速度
  ENetworkMoveType NetworkMoveType = 4;
  int64 TimeStamp                  = 5;
  TVector Acceleration             = 6;
  int32 MoveFlags                  = 8;
  EMovementMode MovementMode       = 9;
  TVector Force                    = 10;  // 受到的力
  TVector AbsoluteVelocity         = 11;  // 绝对速度，用于处理角色站在跳台上运动的情况
  TBasedMovementInfo BasedMovement = 12;  // 角色站在哪个物体上，例如跳台，转盘
};

message TMoveSyncItemLv1 {
  int64 entity_id        = 1;  // entity_id
  TMovementComp moveComp = 2;
};

message TMoveSyncItemLv2 {
  int64 entity_id  = 1;  // entity_id
  TVector location = 2;  // 坐标
};

message TMoveSyncMsg {
  repeated TMoveSyncItemLv1 lv1Item = 1;  // 最高等级移动数据
  repeated TMoveSyncItemLv2 lv2Item = 2;  // 低等级移动数据
};
优化后
  • 由于同一个网格内的玩家位置信息分布比较紧密，所以将 TMovementComp 进行了数值优化以及bit压缩。
  • 对于 TMoveSyncItemLv1 中的 repeated TMovementComp 字段，则将 TMovementComp 中的数据进行拆分，将紧密数据字段移动到TMoveSyncItemLv1 这个层级。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

message TVector {
  sint32 x = 1;
  sint32 y = 2;
  sint32 z = 3;
};

message TMoveSyncComponent {
  ENetworkMoveType NetworkMoveType = 1;
  int32 MoveFlags                  = 2;
  EMovementMode MovementMode       = 3;
  // TVector Force                    = 7;  // 受到的力  这两个字段废弃
  // TVector AbsoluteVelocity         = 8;  // 绝对速度，用于处理角色站在跳台上运动的情况 这两个字段废弃
  TBasedMovementInfo BasedMovement = 4;  // 角色站在哪个物体上，例如跳台，转盘
}

message TListMoveSyncItemLv1 {
  repeated int64 locations                  = 1;
  repeated sint64 timestamps                = 2;
  repeated int64 entity_ids                 = 3;  // entity_id
  repeated sint32 rotation_x                = 5;
  repeated sint32 rotation_y                = 6;
  repeated sint32 rotation_z                = 7;
  repeated sint32 velocity_x                = 8;
  repeated sint32 velocity_y                = 9;
  repeated sint32 velocity_z                = 10;
  repeated sint32 acceleration_x            = 11;
  repeated sint32 acceleration_y            = 12;
  repeated sint32 acceleration_z            = 13;
  repeated TMoveSyncComponent moveSyncItems = 14;
}

message TListMoveSyncItemLv2 {
  repeated int64 entity_ids = 1;
  repeated int64 locations  = 2;
}

message TMoveSyncMsg {
  repeated int32 grid_x                 = 1;
  repeated int32 grid_y                 = 2;
  repeated int32 grid_z                 = 3;
  repeated TListMoveSyncItemLv1 lv1Item = 4;  // 最高等级移动数据
  repeated TListMoveSyncItemLv2 lv2Item = 5;  // 低等级移动数据
  int32 gridSize                        = 6;  // 格子尺寸
  int64 timestamp                       = 7;  // 时间戳
};
数据对比
玩家数量CPU - 优化前/优化后CLB出带宽 - 优化前/优化后
1000100% / 97%145 Mbps / 100 Mbps
2000160% / 150%533 Mbps / 305 Mbps
4000310% / 230%2093 Mbps / 1017 Mbps
8000525% / 470%7850 Mbps / 3140 Mbps

八进制编码文本反解码

protoc输出结果经常包含很多类似\346\210\221的文本，没有正常的中文汉字输出

utf-8编码的二进制以八进制的方式文本化了，由于utf-8以高位连接的方式编码，所以每个字节的高位(第8位)都是1，那么最小的字节是0x80，八进制表示为\200，也就是反斜杠加三个数字

文件模式

1

pbdecode data.txt

管道模式

1

echo '\342\226\240\345\220\204\343\203\251\343\203\263\343\202\257\343\201\253\344\273\230\343\201\217\343\201\256\343\201\253\345\277\205\350\246\201\343\201\252\343\203\235\343\202\244\343\203\263\343\203\210\343\201\257\351\253\230\343\201\204\343\201\273\343\201\251\345\244\232\343\201\217\343\201\252\343\202\212\343\201\276\343\201\231\343\200\202\347\217\276\345\234\250\343\201\257\343\203\251\343\203\263\343\202\257\343\201\2146\343\201\244\343\201\253\345\210\206\343\201\221\343\202\211\343\202\214\343\201\246\343\201\204\343\201\276\343\201\231\343\200\202\346\234\200\351\253\230\343\203\251\343\203\263\343\202\257\343\201\257\343\202\255\343\203\263\343\202\260\343\201\247\343\201\231\343\200\202\n\342\226\240\345\220\204\343\203\251\343\203\263\343\202\257\343\201\253\343\201\257\344\270\213\344\275\215\343\203\251\343\203\263\343\202\257\343\201\214\350\250\255\343\201\221\343\202\211\343\202\214\343\201\246\343\201\204\343\201\276\343\201\231\343\200\202\347\267\217\350\250\210\343\201\24710\343\203\251\343\203\263\343\202\257\343\201\214\343\201\202\343\202\212\343\201\276\343\201\231\343\200\202\344\270\213\344\275\215\343\203\251\343\203\263\343\202\2571\343\201\244\351\200\262\347\264\232\343\201\231\343\202\213\343\201\237\343\202\201\343\201\253\343\201\257\347\217\276\345\234\250\343\203\251\343\203\263\343\202\257\343\201\25610%\343\201\256\343\203\235\343\202\244\343\203\263\343\203\210\343\201\214\345\277\205\350\246\201\343\201\247\343\201\231\357\274\210\343\202\255\343\203\263\343\202\260\343\201\257500\343\203\235\343\202\244\343\203\263\343\203\210\357\274\211\343\200\202\n\342\226\240\343\203\251\343\203\263\343\202\257\347\242\272\345\256\232\346\210\246\343\201\247\343\200\201\343\203\251\343\203\263\343\202\257\343\201\257\343\200\214\350\254\216\343\201\256\346\243\213\345\243\253\343\200\215\343\201\214\350\241\250\347\244\272\343\201\225\343\202\214\343\201\276\343\201\231\343\200\202' | pbdecode

管道模式解码protobuf编码文件

1

$ protoc --decode_raw < Assets/Resources/DataConfig/dataconfig_arena_tips.bytes | pbdecode

Ex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// g++ -o decode_cpp decode.cpp

#include <assert.h>
#include <iostream>
#include <fstream>

void decode(const char *input, char *output, size_t length, bool newline = true)
{
    auto wCursor = output;
    
    auto rCursor = input;
    auto end = rCursor + length;
    while (rCursor < end)
    {
        *wCursor = *rCursor;
        if (*rCursor == '\\')
        {
            auto ptr = rCursor + 1;
            if (*ptr >= '0' && *ptr <= '9')
            {
                auto byte = 0;
                for (auto n = 0; n < 3; n++)
                {
                    byte = (byte << 3) | *ptr - '0';
                    ++ptr;
                }
                
                assert(byte <= 0xFF);
                *wCursor = static_cast<char>(byte);
                rCursor += 3;
            }
        }
        
        ++rCursor;
        ++wCursor;
    }
    
    *wCursor = 0;
    std::cout << output;
    if (newline) { std::cout << '\n'; }
    std::cout << std::flush;
}

void decodeFile(const char *path)
{
    std::ifstream fs(path, std::ifstream::binary);
    fs.seekg(0, std::ios_base::end);
    auto length = static_cast<size_t>(fs.tellg());
    fs.seekg(0);
    
    char buffer[length];
    fs.read(buffer, length);
    fs.close();
    
    decode(buffer, buffer, length, false);
}

int main(int argc, const char * argv[])
{
    if (argc > 1)
    {
        for (auto i = 1; i < argc; i++)
        {
            decodeFile(argv[i]);
        }
    }
    else
    {
        std::string pipe;
        while (std::getline(std::cin, pipe))
        {
            auto size = pipe.size();
            
            char buffer[size];
            decode(pipe.c_str(), buffer, size);
        }
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import sys
import os

def decode(input, newline=True):
    output = ""
    i = 0
    while i < len(input):
        if input[i] == '\\':
            if input[i+1].isdigit():
                byte = int(input[i+1:i+4], 8)
                assert byte <= 0xFF
                output += chr(byte)
                i += 3
            else:
                output += input[i]
        else:
            output += input[i]
        i += 1

    print(output, end='\n' if newline else '')

def decode_file(path):
    with open(path, 'rb') as file:
        content = file.read().decode()
        decode(content, newline=False)

def main():
    if len(sys.argv) > 1:
        for i in range(1, len(sys.argv)):
            decode_file(sys.argv[i])
    else:
        for line in sys.stdin:
            line = line.rstrip()
            decode(line)

if __name__ == "__main__":
    main()
Uncategories, 性能优化
PB 序列化
本文由作者按照 CC BY 4.0 进行授权