为什么Protocol Buffers这样编码


为什么Protocol Buffers这样编码

来源

Protocol Buffers 编码原理

代码里的对象基本分两类,一类的长度是固定的,比如 int32 占用 32 比特,double 占用 64 比特;另一类的长度是变化的,比如字符串.

所以,在设计编码的时候,首先就得区分这两种情况.

定长数据变长数据的表示问题

最简单的办法就是用一个字节表示类型,紧接着传输数据.

定长类型

对于定长类型,解码的时候先读出第一个字节,根据不同的类型再读取对应长度的数据

变长类型

解码的时候先读出第一个字节,根据不同的类型再读取对应长度的数据

type type length Date
string 3 abc

要解决几个问题:

  1. 确认数据的长度
  2. 如何传输这个长度

以 string 为例。先传一个字节表示长度,再传真正的字符串.

一个字节8位,能表示的无符号数最大值是 255,所以字符串的长度不能超过 255 字节。

如果使用两个字节,则最大能表示的长度就会扩展到 65535 字节。

这又引进新的问题

  1. 如果要传输更长的字符串呢?
  2. 再加字节吗?

因为长度是变化的,所以使用固定长度字节表示很不灵活:太短则表示范围太小;太长则传输效率太低。

websockt 协议

websockt 协议划定了一个 7 比特的字段表示长度,最大能表示的长度是 127,肯定不够用。所以 websocket 协议还规定,当长度取值为 126 时,紧接着会再传输两个字节表示真正的长度;当取值为 127 时,则紧接着会传再传输八个字节表示真正的长度。

The length of the “Payload data”, in bytes:

if 0-125, that is thepayload length.

If 126, the following 2 bytes interpreted as a 16-bit unsigned integer are the payload length.

If 127, the following 8 bytes interpreted as a 64-bit unsigned integer (the most significant bit MUST be 0) are the payload length.

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

因此如果要支持 64 位整数范围,则 VarInts 最多需要 10 个字节。从最大字节占用数来看,VarInts 比 websocket 要差一点。但对于小数字,VarInts 则比 websocket 更加紧凑。

字段映射问题

对于字段映射问题,json 和 xml 都是在编码的时候直接加上字段名

{
  "foo":1,
  "bar": "hello"
}
优点 缺点
最大的好处就是易读,编码和解码逻辑互不依赖 传输效率低。每次都得重复传输字段名,有点浪费

Protocol Buffers 采用了另一种策略,给字段加编号

每个字段等号后面的数字。这个数字也叫 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 (利用最后的三bit)的方式传输的

字段映射举例

message Foo {
  int32  foo = 1;
  string bar = 2;
}

如果前面的 Foo 的 foo 字段取值为 1 的话,则对应的编码是:0x08 0x01。

  1. foo 的类型是 int32,对应的 type 取 0。
  2. 而它的 tag 又是 1,所以第一个字节是 (1<<3)|0 = 0x08,
  3. 第二个字节是数字 1 的 VarInts 编码,即 0x01。

如果 Foo 的 bar 字段取值为 吕 的话,则对应的编码是:0x12 0x03 0xe5 0x90 0x95。

  1. bar 的类型是 string,对应的 type 取 2。
  2. 而它的 tag 又是 2,所以第一个字节是 (2<<3)|2 = 0x12,
  3. 第二个字节表示字符串的长度为 3,
  4. 再后面 3 个字节是汉字吕 UTF-8 编码。
优点 缺点
使用 tag 的优点是不用重复传输字段名 因为没有字段名,所以编码和解码的代码必须持有一份字段名和 tag 的映射关系

支持自定义消息字段和 repeated 字段

Protocol Buffers 还支持自定义消息字段和 repeated 字段。这两种自段在编码上跟 string 是等价的

message Baz {
  int32 b = 1;
}
message Bar {
  repeated int32 a = 1;
             Baz b = 2;
}

Bar类型中有代表数组的repeated字段和有Baz类型

当 字段a[1,2,3],代表长度为3的int32数组

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

当自定义字段b字段取{b:4}

  1. b 的类型为 Bar,所以对应的 type 也是2
  2. btag2,所以第一个字节应该是(2<<3|2) = 0x12
  3. 第二个字节表示 message 的长度,所以是 0x02,接下来两个字节表示 Baz 的编码。

单从数据来看,我们无法区分 string,自定义消息字段和 repeated 字段。要想解析这类数据,必须依赖 proto 定义。

负数编码优化

VarInts 不太适合表示负数。因为负数在计算机使用补码表示,转成 unit64 是一个很大的数。当你使用 VarInts 表示的时候,-1 居然要占用 10 个字节

0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0x01

为此,Protocol Buffers 引入了 sint32 和 sint64 两种类型,在编码的时候先将数字转化成 ZigZag 编码。ZigZag 思想也很简单,就是用正数来表示负数,映射规则如下

ZigZag(n) = (n>>7) ^ (n<<1)

-11的处理过程如下:

11110101 >> 7           =>  11111111
11110101 << 1           =>  11101010
11111111^11101010 =>    00010101

tag 的取值范围

Protocol Buffers 还有一个问题需要注意,那就是 tag 的取值范围。

因为使用了 VarInts,所以单字节的最高位是零,而最低三位表示类型,所以只剩下 4 位可用了。也就是说,当你的字段数量超过 16 时,就需要用两个以上的字段表示


Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: