为什么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，所以对应 type 取 2；
2. 又 a和 tag为 1，所以第一个字节应该是 (1<<3|2) = 0x0a。
3. 第二个字节表示数组长度，所以是 0x03，接下来三个字节代表数组的值分别是 1, 2, 3 的 VarInts 编码。

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

1. b 的类型为 Bar，所以对应的 type 也是2；
2. b的 tag 为 2，所以第一个字节应该是(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 时，就需要用两个以上的字段表示