Protocol Buffers 编码
涛叔当今云时代 gRPC 大行其道，gRPC 默认的序列化编码 Protocol Buffers 也跟着流行开来。都说 Protocol Buffers 效率很高，那到底高在哪里呢？今天就跟大家讨论一下 Protocol Buffers 的编码规则。
代码里的对象基本分两类，一类的长度是固定的，比如 int32 占用 32 比特，double 占用 64 比特；另一类的长度是变化的，比如字符串。所以，在设计编码的时候，首先就得区分这两种情况。最简单的办法就是用一个字节表示类型，紧接着传输数据，如下图所示：
type data
+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx| |xxxxxxxx|
+--------+--------+~~+--------+
7 0 7 0 7 0一个字节有 256 种取值。我们可以为每一种类型分配一个编号。解码的时候先读出第一个字节，根据不同的类型再读取对应长度的数据。对于定长类型的数据，解码到此就完成了。对于变长类型数据，我们还需要确认数据的长度。如何传输这个长度呢？以 string 为例。先传一个字节表示长度，再传真正的字符串，如下图所示：
type=string length data
+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx| |xxxxxxxx|
+--------+--------+~~+--------+
7 0 7 0 7 0一个字节能表示的最大值是 255，所以字符串的长度不能超过 255 字节。这肯定是不行的。怎么办？如果我们使用两个字节，则最大能表示的长度就会扩展到 65535 字节。这对于一般的使用场景也就够用了。但如果要传输更长的字符串呢？再加字节吗？
因为长度是变化的，所以使用固定长度字节表示很不灵活：太短则表示范围太小；太长则传输效率太低。如果我们用 4 个字节表示长度 1，则为 0x00 0x00 0x00 0x01，高 31 位都是零，没有传递任何信息。
如果能去掉这些零效率不就提上来吗？比如，对于长度 1 只传 0x01，对于长度 4112 只传 0x1010。但就，这样做会导致另外一个问题：如何确定表示长度所需要的字节数量。我们好像以回到了原点。为了表示字符串的长度，我们引入了长度字段，现在长度字段的长度也是不确定的了。
对于这个问题，不同的协议采用了不同的方法。
比如 websockt 协议划定了一个 7bit 的字段表示长度，最大能表示的长度是 127，肯定不够用。所以 websocket 协议还规定，当长度取值为 126 时，紧接着会再传输两个字节表示真正的长度；当取值为 127 时，则紧接着会传再传输八个字节表示真正的长度。这是 RFC6455 的定义消息格式片段：
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-------+-+-------------+-------------------------------+
|F|R|R|R| opcode|M| Payload len | Extended payload length |
|I|S|S|S| (4) |A| (7) | (16/64) |
|N|V|V|V| |S| | (if payload len==126/127) |
| |1|2|3| |K| | |
+-+-+-+-+-------+-+-------------+ - - - - - - - - - - - - - - - +
| Extended payload length continued, if payload len == 127 |
+ - - - - - - - - - - - - - - - +-------------------------------+
~ ~在 websocket 中，长度为 0~126 占用一个字节；128~65534 占用两个字节、大于 65535 则占用八个字节。websockt 的做法与简单设置固定长度字节相比确实进步了不少。但它只把长度分成三个区间，有点太粗了。比如，长度在 128 到 256 之间话需要占用两个字节；长度一旦超过 65534，则对不住了，八字节走起。
显然，我们需要一个分段粒度更细的方案。这就用到 VarInts 了。
websoket 协议中征用了 126 和 127 这两个数字表示长度字段总共占几个字节，以达到动态扩展的效果。VarInts 则是征用了每个字节的最高位(MSB)。具体表示方式如下表：
0 ~ 2^07 - 1 0xxxxxxx
2^07 ~ 2^14 - 1 1xxxxxxx 0xxxxxxx
2^14 ~ 2^21 - 1 1xxxxxxx 1xxxxxxx 0xxxxxxx
2^21 ~ 2^28 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
2^28 ~ 2^35 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx简单来说，在解码的时候，如果读到的字节的 MSB 是 1 话，则表示还有后序字节，一直读到 MSB 为 0 的字节为止。举个例子，长度 624485 可以作如下编码：
MSB ------------------ LSB
10011000011101100101 <1> 二进制 20bit
0100110 0001110 1100101 <2> 从 LSB 到 MSB 每七位分一组，不足七位高位补零
00100110 10001110 11100101 <3> 最右边一组高位补零，其他组高位补一
0x26 0x8E 0xE5 <4> 转换成十六进制
→ 0xE5 0x8E 0x26 <5> 从 LSB 到 MSB 输出结果如果要支持 64 位整数范围，则 VarInts 最多需要 10 个字节。从最大字节占用数来看，VarInts 比 websocket 要差一点。但对于小数字，VarInts 则比 websocket 更加紧凑。大家可以把 websocket 的方法看成是三档变速，把 VarInts 的看成是无级变速。
有了 VarInts，我们就把定长数据和变长数据的表示问题给解决了。那是不是编码设计到此就完成了呢？不然。我们还要解决字段映射的问题。
对于字段映射问题，json 和 xml 都是在编码的时候直接加上字段名，比如：
{
"foo":1,
"bar": "hello"
}这样做最大的好处就是易读，编码和解码逻辑互不依赖。但缺点也很明显，传输效率低。每次都得重复传输字段名，有点浪费。Protocol Buffers 采用了另一种策略，给字段加编号。举个例子：
message Foo {
int32 foo = 1;
string bar = 2;
}请大家留意每个字段等号后面的数字。这个数字也叫 tag，不能重复，跟字段一一对应。Protocol Buffers 每个字段编码后从逻辑上分为三个部分：
<tag> <type> [<length>] <data>tag, type, 和 length 都用 VarInts 表示。
Protocol Buffers 在 3 版本中定义了 4 种类型 type：
- 0
VarInt表示int32, int64, uint32, uint64, sint32, sint64, bool, enum - 1
64-bit表示fixed64, sfixed64, double - 2
Length-delimited表示string, bytes, embedded messages, repeated 字段 - 5
32-bit表示fixed32, sfixed32, float
其中 3 和 4 表示的类型已经废弃，不多讨论。因为类型比较少，所以 Protocol Buffers 在编码的时候只用了 3 比特，实际传输的时候是以 (tag<<3)|type 的方式传输的。
举个例子。如果前面的 Foo 的 foo 字段取值为 1 的话，则对应的编码是：0x08 0x01。foo 的类型是 int32，对应的 type 取 0。而它的 tag 又是 1，所以第一个字节是 (1<<3)|0 = 0x08，第二个字节是数字 1 的 VarInts 编码，即 0x01。
7 0 7 0
+-----+---+--------+
|00001|000|00000001|
+-----+---+--------+
tag type data再举个字符串的例子。如果 Foo 的 bar 字段取值为 吕 的话，则对应的编码是：0x12 0x03 0xe5 0x90 0x95。bar 的类型是 string，对应的 type 取 2。而它的 tag 又是 2，所以第一个字节是 (2<<3)|2 = 0x12，第二个字节表示字符串的长度为 3，再后面 3 个字节是汉字吕 UTF-8 编码。
7 0 7 0 25 0
+-----+---+--------+===========+
|00010|010|00000011|0xe50x90x95|
+-----+---+--------+===========+
tag type length utf-8使用 tag 的优点是不用重复传输字段名，但也是它的缺点。因为没有字段名，所以编码和解码的代码必须持有一份字段名和 tag 的映射关系，这是在生成代码的时候自动完成的。也就是说，没有 proto 文件，你是没法对 Protocol Buffers 数据进行解码的。
Protocol Buffers 还支持自定义消息字段和 repeated 字段。这两种自段在编码上跟 string 是等价的。先举个 repeated 字段的例子。
message Baz {
int32 b = 1;
}
message Bar {
repeated int32 a = 1;
Baz b = 2;
}如果我们让 Bar 的 a 字段取 [1,2,3]，让 b 字段取 {b:4}，则对应的编码为 0x0a 0x03 0x01 0x02 0x03 0x12 0x02 0x08 0x04。这段数据可以拆成两部分：
0x0a 0x03 0x01 0x02 0x030x12 0x02 0x08 0x04
先说第一部分。因为 a 的类型为 repeated int32，所以对应 type 取 2；又 a 的 tag 为 1，所以第一个字节应该是 (1<<3|2) = 0x0a。第二个字节表示数组长度，所以是 0x03，接下来三个字节分别是 1, 2, 3 的 VarInts 编码。
再说第二部分。因为 b 的类型为 Bar，所以对应的 type 也是 2；又 b 的 tag 为 2，所以第一个字节应该是(2<<3|2) = 0x12。第二个字节表示 message 的长度，所以是 0x02，接下来两个字节表示 Baz 的编码。
7 0 7 0 25 0 7 0 7 0 7 0 7 0
+-----+---+--------+===========+-----+---+--------+=====+===+========+
|00001|010|00000011|0x010x02x03|00010|010|00000010|00001|000|00000100|
+-----+---+--------+===========+-----+---+--------+=====+===+========+
tag type length utf-8 tag type length tag type data
|<----- baz.b ---->|
|<---------- foo.a ----------->|<-------------- foo.b -------------->|单从数据来看，我们无法区分 string，repeated 和 message。要想解析这类数据，必须依赖 proto 定义。
VarInts 不太适合表示负数。因为负数在计算机使用补码表示，转成 unit64 是一个很大的数。当你使用 VarInts 表示的时候，-1 居然要占用 10 个字节！是可忍，孰不可忍！为此，Protocol Buffers 引入了 sint32 和 sint64 两种类型，在编码的时候先将数字转化成 ZigZag 编码。ZigZag 思想也很简单，就是用正数来表示负数，映射规则如下：
+-- 0 -1 1 -2 2 -3 3...
| +--+--+--+--+--+--+---->
+-> 0 1 2 3 4 5 6...同样的，单从数据来看，我们也没法区分整数是不是用了 ZigZag 编码处理，这些信息只能从 proto 文件获取。
Protocol Buffers 还有一个问题需要注意，那就是 tag 的取值范围。因为使用了 VarInts，所以单字节的最高位是零，而最低三位表示类型，所以只剩下 4 位可用了。也就是说，当你的字段数量超过 16 时，就需要用两个以上的字节表示了。
写到这里，Protocol Buffers 的编码也就说得差不多了。总结几条使用 Protocol Buffers 需要注意的事项：
- 不要修改字段 tag
- 字段尽量不要超过 16 个
- 尽量使用小整数
- 如果需要传输负数，请使用
sint32或sint64
参考文献：