protobuf 编码原理

protobuf 是什么？

走个流程，普及一下protobuf。

protobuf 是 google 的一种数据交换的格式，它独立于语言，独立于平台。

protobuf 可以用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式，可以用于诸如网络传输、配置文件、数据存储等诸多领域。

目前提供了多种语言的实现：java、c#、c++、go 和 python，每一种实现都包含了相应语言的编译器以及库文件。

protobuf 优势在哪里？

由于protobuf是一种二进制的格式，比使用 json、xml 进行数据交换快许多。

举个例子，对于消息（id=101,str="hello"） 用 Protobuf 序列化后的字节序列为：

08 65 12 06 48 65 6C 6C 6F 77

而如果用 XML，则类似这样：

31 30 31 3C 2F 69 64 3E 3C 6E 61 6D 65 3E 68 65 
6C 6C 6F 3C 2F 6E 61 6D 65 3E 3C 2F 68 65 6C 6C 
6F 77 6F 72 6C 64 3E ...
一共 55 个字节，这些奇怪的数字需要稍微解释一下，其含义用 ASCII 表示如下：
<helloworld>
   <id>101</id>
   <name>hello</name>
</helloworld>

首先我们来了解一下 XML 的封解包过程。XML 需要从文件中读取出字符串，再转换为 XML 文档对象结构模型。之后，再从 XML 文档对象结构模型中读取指定节点的字符串，最后再将这个字符串转换成指定类型的变量。这个过程非常复杂，其中将 XML 文件转换为文档对象结构模型的过程通常需要完成词法文法分析等大量消耗 CPU 的复杂计算。

反观 protobuf，它只需要简单地将一个二进制序列，按照指定的格式读取到对应的结构类型中就可了。

protobuf 是怎么编码的？

既然都说了protobuf那么牛逼，我们来看看它是怎么编码的吧。

先从一个简单的消息格式说起

message Test1 {
  required int32 a = 1;
}

定义一个Test1对象，然后赋值a为150，序列化后是以下结果，暂用空间很小，这得益于一种叫做Base 128 Varints的编码技术。

08 96 01

Base 128 Varints是什么？

Base 128 Varints，我们就称之为varints。

要理解protobuf的协议缓冲区编码，就要首先需要了解varints。 varints是一个使用一个或多个字节序列化整数的方法。数字越小，需要的字节数越少。

varint中的每个字节（最后一个字节除外）都设置了最高有效位（设置了最高位为1，否则为0），表示还有跟多的字节跟在后面。下文我们就称之为术语 msb 了。每个字节的低7位用于存储7位组中的数字的二进制数据，小字节序存储（不懂小字节序存储的先去问问谷哥哥或度娘）。

举个例子，数字1是单字节

#数字 1
0000 0001 (只有一个字节，后面不跟其他字节了，所以最高位不设置msb)
#数字 300
1010 1100 0000 0010 (多字节，第一个字节设置了msb，第二个字节没有设置msb)
-> 010 1100  000 0010 (去掉msb，只剩下每个字节的7位数据)

来看看varints的解码，以数字300为例

010 1100  000 0010
-> 000 0010  010 1100 (字节序反转)
-> 100101100 
(2^8 + 2^5 + 2^3 + 2^2 
= 256 + 32 + 8 + 4
= 300)

varints编码的消息结构

消息编码结果是由一系列key-value组合而成的二进制流。二进制流只是使用该字段的field-number ，而若要解析二进制流，还需要消息类型的定义（即.proto文件）来确定每个字段的名称和声明类型。

当消息被编码时，键和值被连接成一个字节流；当消息被解码时，为了不影响后面字段的解析，解析器需要支持能够跳过它不能识别的字段。所以，需要知道每个key-value对的长度。

protobuf也确实是这么做的，每个消息中的key实际上是由两个值计算而成:

1).proto文件中的field-number（每个字段的段号，显示声明，如 required int32 a = 1 中的 1就是段号）;

2). 一个mire-type类型。根据mire-type可以知道怎么计算key-value的长度。

二进制中每个key 都是varint类型（也称为tag），其值计算方法为 field-number << 3 | mire-type，即最后3bit存储mire-type，除去最后3bit存储的是 field-number。

举个例子：二进制中的第一个key，是08，去掉msb如下

000 1000

怎么来的？

field_number = 1
mire-type = 0
(1 << 3 | 0) = 08

其他类型

Signed Integers(sint32,sint64)

上一节中说到，所有与wire-type为0相关的协议缓冲区类型都被编码为varint。但是，在编码负数时，有符号的int类型（sint32和sint64）和“standard” int类型（int32和int64）之间有一个重要区别。如果使用int32或int64作为负数的类型，则生成的varint总是长度为10个字节， 实际上它被视为非常大的无符号整数。如果使用sint32或sint64代替int32或int64，则生成的varint将使用ZigZag编码，效率更高。

ZigZag编码指将有符号整形映射为无符号整形来存储，因无符号整形的特性，所以绝对值较小的数字其varint编码也会比较小。映射公式如下:

# sint32
(n << 1) ^ (n >> 31)
# sint64
(n << 1) ^ (n >> 63)

映射结果如下，是不是有”锯齿“的感觉

Non-varint Numbers

double和fixed64（mire-type=1），解析需要固定的64bits数据块；float和fixed32（mire-type=5），解析器需要固定的32bits数据块。以上也都是小字节序存储。

Strings

mire-type=2 （length-delimited）意味着varint编码长度可以指定。如下：

message Test2 {
  required string b = 2;
  (2为field_number)
}

字符串为”testing“的编码结果为

12 07 74 65 73 74 69 6e 67

因为 field_number = 2，type=2，所以tag = 2<<3 | 2 = 12，len(testing)= 07，所以第二个字节为 07，再后面的74 65 73 74 69 6e 67就是字符串的16进制值了。

消息嵌套

message Test1 {
  required int32 a = 1;
}
message Test3 {
  required Test1 c = 3;
}

如果Test1的a为150，则Test3的编码结果为：

1a 03 08 96 01
-> Test1 a: 08 96 01 
(key= (1<<3|0) = 08，150编码96 01)
-> Test3: 1a 03 
(嵌套的Test1被当做Test3的string编码，
所以 key= (3<<3|2) = 1a，len=3，
所以第二个字节为03)

可选和重复的元素

• optional

如果message中包含optional类型，表示发送方可以选择设置，接收方若解析不到，则跳过。

• repeated

如果message中包含repeated类型，可以理解为数组。在proto2版本，如果没有指定[packed=true]选项，则每个元素都要是key-value格式，但是可以和其他字段穿插排列；如果指定了[packed=true]选项），只需要写一次key就行了，后面跟着一串value，但是value不能和其他字段穿插。proto3 默认是 [packed=true]的，不需要指定。但是为了向前兼容，良好的习惯是指定[packed=true]这个字段。

message Test4 {
  repeated int32 d = 4 [packed=true];
}

给Test4 设置d的值为 3, 270 和 86942，则编码结果为

22        // tag (field number 4, wire type 2)
06        // payload size (6 bytes)
03        // first element (varint 3)
8E 02     // second element (varint 270)
9E A7 05  // third element (varint 86942)

Field顺序问题

代码中按顺序指定field-number有助于编码器做优化。