作者：carmark
本文将在proto3语法背景下，介绍protobuf的编码原理，并结合业务场景探讨部分优化技巧。
序列化算法被广泛应用于各种通信协议中，本文对序列化算法进行狭义定义：
将某个struct或class的内存数据和通信数据链路上的字节流进行互相转化的算法。
基于这个定义序列化算法具有两个行为：
1、序列化：内存数据->通信链路字节流
2、反序列化：通信链路字节流->内存数据
常用的序列化算法有：json、xml、protobuf 等，将这些算法进行归纳不难发现这些算法主要是对三种基本类型（原子性、不可被拆分）和三种复合类型（由基本类型和其他符合类型构成）进行序列化和反序列化。
1、基本类型：定点数值类型、浮点数值类型、字符串类型
2、复合类型：结构体类型、数组类型、map类型
protobuf也是对这些类型进行序列化的，下文将在proto3语法的背景下介绍protobuf对不同类型的编码原理。
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编码的细节可以参考文档
https://protobuf.dev/programming-guides/encoding/ ，本文直接给出两种编码的性质：
varint编码：变长编码，对于小正整数有较好的压缩效果，对于大整数或负数编码后字节流长度会变大。
zigzag编码：定长编码，将小正整数和小负整数转换到小正整数再进行varint编码，对绝对值较小的整数有良好的压缩效果。
proto3语法中：float和double属于浮点数据类型，使用定长的四个字节或八个字节存储，数据直接用IEEE754标准表示。
proto3语法中：string、bytes属于字符串类型，字符串类型序列化后的字节流为其原始内容本身。这两种类型的不同之处在于string内的字节流必须是utf8编码，bytes没有这种要求。
proto3语法中使用message定义结构体类型，结构体类型有多个不同tagid构成的字段，字段可以是基本类型或复合类型，甚至可以是这个结构体类型本身。结构体每个字段底层都使用这种格式进行存储，需要注意的是typeid、length、data三部分长度会根据实际情况发生改变。
typeid length data
+--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------+
typeid用于存储结构体字段编号（tagNum）和字段类型（tagType），tagNum为字段“=”后的数字，tagNum也使用varint进行编码，因此如果“=”后的数字很大，则可能导致tagNum编码变大，tagid占用多个字节。而tagType则指明数据类型，这部分固定占用三个bit。
|tagNum |tagType|
+----------------------+
|x x x x x x x x|
+----------------------+
7 2 0
下表记录了不同字段类型对应的tagType值：
tagType类型0int32、int64、uint32、uint64、sint32、sint64、bool、enum1fixed64、sfixed64、double2string、bytes、结构体类型、数组类型、map类型3弃用4弃用5fixed32、sfixed32、float
length部分表示data部分的长度，同样使用变长varint编码，需要注意的是如果字段类型是数值类型，则length部分不会出序列化后的字节流中。
data部分为原始数据，可以是基本类型和复合类型序列化后的字节流，算法通常递归的对这些字段进行处理。
proto3语法中使用repeated为前缀的字段即为数组类型，也就是说repeated关键字是用来修饰结构体类型的字段的。
如果repeated修饰的是定点数值类型或浮点数值类型，在proto3语法下会默认按照下图方式将这些数值排列在一起，length部分记录data1~dataN所有数值的字节数之和。
typeid length data1 data2 dataN
+--------+--------+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx| |xxxxxxxx|
+--------+--------+--------+--------+~~+--------+
如果修饰的是其他类型则会按照以下方式组织这些数据（其中field1为数组类型），需要注意的是属于同一个数组的不同元素中间可能有其他字段的元素插入。
typeid1 length1 data1 typeid2 length2 data2 typeid1 length3 data3
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
| field1 || field2 || field1 |
proto3语法中map也是一种修饰符，修饰结构体类型的字段。map类型的key必须为定点数值类型或string类型，map的底层存储key-value键值对，采用和数组类型一样的存储方法，数组中每个元素是kv键值对。以下数据定义中，message A和message B有完全相同的底层存储结构。
message A{
map<int32,float> mp = 1;
}
message KV{
int32 K = 1;
float V = 2;
}
message B{
repeated KV mp = 1;
}
如果类型为默认值，则该字段tagid+length+data不会出现在序列化后的字节流中。
类型默认值int32、int64、uint32、uint64、fixed32、fixed64、sfixed32、sfixed64、float、double0enum0对应的枚举值boolfalsestring""bytes空字节流结构体类型null (对应字段的指针为空)数组类型空数组map类型空map
需要注意的是如果某个字段是结构体类型，该字段对应的结构体中的所有元素均为默认值，这种情况下该字段的data部分会被省略，只保留tagid和length部分，当然length部分值为0。如果字段的指针为空，则该字段不会有任何内容出现在序列化后的字节流中。
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;
}
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编码如下：
+----------------------+ +----------------------+
|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序列化之后低地址字节在前，高地址字节在后。
Q: protobuf既然有了int32 为什么还要用sint32 和 fixed32 ？
A: int32使用varint编码，对于小正数有较好的压缩效果，对于大整数和负数会导致额外的字节开销。因此引入fixed32，该类型不会对数值进行任何编码，对大于2^28-1的整数比int32占用更少的字节。而对于负数使用zigzag编码，这样绝对值较小的负数都能被有效压缩。
Q: 为什么数组类型每个元素都要用tagid+length+data这种格式进行存储？
A: 其实我也觉得这点设计不太合理，为什么不设计成tagid+元素个数+{length+data}...这种格式呢？
Q: map类型是不是尽量别用？
A: 如果你的业务对序列化后的字节流长度有要求，能不用就别用吧。
Q: 为什么数组类型和map类型的元素中间可能插入其他字节流？
A: 不清楚，不过这倒是解释了第二个问题。
Q: 既然通信双方都使用.proto文件约定了字段的类型，为什么tagid字段还要包含type信息？
A: 不清楚，不过可能和不同版本协议的兼容性有关。
通过分析protobuf的编码原理，可以发现如果对序列化后的字节流长度有要求，无脑地定义数据结构是很不理智的，本节将讨论部分优化技巧。
上文中多次提到过varint编码和zigzag编码，不同的数据类型使用不同的编码方法，那应该如何选择呢？首先给出正整数经过varint编码后占用字节数的算式，其中x表示待计算的正整数，y表示占用字节数。
对于zigzag编码需要明确一点：zigzag编码需要和varint编码一起使用。zigzag编码可以看作将正负交替的数值序列映射至正整数序列，之后再由varint对正整数进行编码。
原始数值: 0,-1,1,-2,2,-3,3,-4,4...
映射数值: 0,1,2,3,4,5,6,7,8...
现在考虑使用varint编码后4字节能表示的最大无符号整数，根据算式：令y=4，易得x最大值为2^28^-1。因此可以得到结论，对于小于2^28^-1的无符号整数推荐使用varint编码，对于大于2^28^-1的无符号整数使用varint编码会导致编码后字节数变长。
然后讨论使用zigzag+varint编码后4字节能表示的正负数范围，结合以上分析不难得出4字节能表示的正负数范围是[-2^14^ , 2^14^-1]。因此对于在此范围内的数值，经过zigzag+varint编号后的字节流长度小于四个字节。
基于以上分析下表给出不同数值范围的定点数值推荐类型（以下推荐类型都是基于最小字节流长度为目标，编解码过程会存在一定cpu消耗）
数据范围推荐类型[-2^63^,-2^31^)sfixed64[-2^31^,-2^28^)sfixed32[-2^28^,-2^14^)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
从对protobuf编码原理的介绍那部分可以看出，protobuf因为考虑兼容性原因，存储了很多tagid、length这些记录结构信息的字段。在实际应用场景中如果数据的结构较为紧密（这个词暂时还无较为精确的定义），多个字段都有相同的结构是否能去掉记录结构信息的字段，只保留内容信息的字段，从而减少数据长度呢？本文提供一种优化思路。
优化前：
message A{
int32 x = 1;
int32 y = 2;
}
message B{
int32 z = 1;
}
message C{
repeated A as = 1;
B b = 2 ;
}
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}
优化后：
message C{
repeated int32 xs = 1;
repeated int32 ys = 2;
int32 z = 3;
}
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
前后对比可看在传输相同的信息情况下字节流长度减半，这主要因为舍弃了很多tagID字段。当然这种优化思路是基于数据的结构较为紧密这一假设：优化前大部分message A中的X、Y字段均非默认值，这样就可以省略大量结构信息，从而减少字节流长度。实际应用中可以大量应用这种技巧，来优化编解码性能。
除了结构信息是否有其他信息可以被省略掉呢？当然，除了结构信息还有数据信息，即为data字段记录的值。根据信息论的基本观点，如果一组数据分布范围很广，每个数据点现频率几乎相同则需要用较多bit对这组数据进行编码。如果这组数据分布较为单一，某些数据点出现频率较高，这种数据分布能较好地使用变长编码表示。
推广到实际业务场景中，如果发现某组数据的某些字段满足某些分布特征，比如：时间戳、交易ID，这种分布范围较小，重复性较高的数据，最简单的方法是：使用一个int64存储这组数据的最小值，然后对于这组数据中的其他元素分别计算和这个最小值的差值。因为数据分布范围较小，因此差值也不会很大，从而减少整体编码长度。
优化前：
message A { repeated int64 timestamps = 1; }
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
优化后：
message A {
int64 base = 1;
repeated int64 timestamps = 2;
}
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表示一个差值即可，这样一个字节就可以记录两个差值的信息，从而进一步压缩序列化字节流。
基于上述分析和实践，不难发现protobuf进行序列化的过程中，需要储存结构信息和数据信息。对于结构紧密的数据，protobuf会导致大量bit用于表征结构信息。而如果数据信息中存在某些先验数据分布或规律，protobuf也会存储较多冗余信息。那么是否有算法能较好地结合待序列化数据的特性，进而防止信息冗余呢？这个可能需要进一步的研究...
