Protocol Buffers 编码

2019-07-14

当今云时代 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

其中 3 和 4 表示的类型已经废弃,不多讨论。因为类型比较少,所以 Protocol Buffers 在编码的时候只用了 3 比特,实际传输的时候是以 (tag<<3)|type 的方式传输的。

举个例子。如果前面的 Foofoo 字段取值为 1 的话,则对应的编码是:0x08 0x01foo 的类型是 int32,对应的 type0。而它的 tag 又是 1,所以第一个字节是 (1<<3)|0 = 0x08,第二个字节是数字 1 的 VarInts 编码,即 0x01

 7       0 7      0
+-----+---+--------+
|00001|000|00000001|
+-----+---+--------+
  tag type   data

再举个字符串的例子。如果 Foobar 字段取值为 的话,则对应的编码是:0x12 0x03 0xe5 0x90 0x95bar 的类型是 string,对应的 type2。而它的 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;
}

如果我们让 Bara 字段取 [1,2,3],让 b 字段取 {b:4},则对应的编码为 0x0a 0x03 0x01 0x02 0x03 0x12 0x02 0x08 0x04。这段数据可以拆成两部分:

  1. 0x0a 0x03 0x01 0x02 0x03
  2. 0x12 0x02 0x08 0x04

先说第一部分。因为 a 的类型为 repeated int32,所以对应 type2;又 atag1,所以第一个字节应该是 (1<<3|2) = 0x0a。第二个字节表示数组长度,所以是 0x03,接下来三个字节分别是 1, 2, 3 的 VarInts 编码。

再说第二部分。因为 b 的类型为 Bar,所以对应的 type 也是 2;又 btag2,所以第一个字节应该是(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 引入了 sint32sint64 两种类型,在编码的时候先将数字转化成 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 需要注意的事项:

  1. 不要修改字段 tag
  2. 字段尽量不要超过 16 个
  3. 尽量使用小整数
  4. 如果需要传输负数,请使用 sint32sin64

参考文献:

  1. https://developers.google.com/protocol-buffers/docs/encoding
  2. https://www.deadalnix.me/2017/01/08/variable-size-integer-encoding/
  3. https://carlmastrangelo.com/blog/lets-make-a-varint
  4. https://en.wikipedia.org/wiki/LEB128
  5. https://tools.ietf.org/html/rfc6455#section-5.2