Google Protocol Buffers 编码原理

Protocol buffers are a language-neutral, platform-neutral extensible mechanism for serializing structured data.

A Simple Messag
举个栗子, 定义一个proto message 把 a 的值设置为十进制的 150:

message Test1 {
  required int32 a = 1;
}

然后将该 message 序列化到 Binary 文件中, 可以看到数据为:

08 96 01

在理解这个些数前需要先了解 Varints

Base 128 Varints
varints 是一种使用一个或多个字节(byte)表示整型数据的方法。数值越小, 其所占用的字节数越少。(注:类似 varchar)

通常整数用字节表示, 每个字节占 8 位, 而在 varint 中每个字节的最高位(bit)为标志位 msb(most significant bit), 其余 7 位表示数据值, 因此单字节能表示的最大的数为 128(2的7次方)故称其为 Base 128; 其中 msb 位为 1, 则表示后续的字节也是该值的一部分; 如果 msb 为 0, 则表示该字节为该值的最后一个字节。
举个例子, 数值 1 用 varint 形式表示, 因为只有一个字节, 所以 msb 为 0 :

0000 0001

再如十进制 300 :

1010 1100 0000 0010
→ 010 1100  000 0010

因为 varints 使用小字节序(little-endian)存储, 所以在解析这两个字节时, 需要将字节对调再计算

→ 000 0010  010 1100
→ 256 + 32 + 8 + 4 = 300

Message Structure
在 Protocol Buffer 中 message 都是由一系列的 key-value 对构成的。在进行 message 编码时, key 和 value 被连接成二进制字节流。此字节流中都是使用字段的序号作为 key, 而每个字段的名字和类型均是在解码的过程中根据目标类型(反序列化后的对象类型)进行配对的。在解码时, 解析器会跳过无法识别的字段, 这样即使后续新增的字段, 原来程序依然可以正常解析旧字段, 保证了新老结构的兼容。
实际上编码时, key 是由字段序号和字段类型组合而成, 其结构为:

(field_number << 3) | wire_type

可以看出 key 第一部分是 field_number, 而后 3 个 bits 用于存储字段的类型信息(wire type)。Protocol Buffer所支持的 wire type 有:

Type Meaning Used For
0 Varint int32, int64, uint32, uint64, sint32, sint64, bool, enum
1 64-bit fixed64, sfixed64, double
2 Length-delimited string, bytes, embedded messages, packed repeated fields
3 Start group groups (deprecated)
4 End group groups (deprecated)
5 32-bit fixed32, sfixed32, float

回头再看最开始的 message 例子, 知道其中第一个字节 08 表示key 即

08 = 0000 1000
→ 000 1000

其中最低的3位表示字段类型, 即 0, 查上表 0 表示 varint。 再向右移3位( >> 3), 此时得到的结果为 1, 即为 field_number
这样 Protocol Buffer 的解码器得到其字段序号为 1, 其后所跟随数据的类型为 varint。然后按 varint 规则解析出后两个字节 96 01 值为150。

96 01 = 1001 0110  0000 0001
       → 001 0110   000 0001 (去掉 msb 位)
       → 000 0001   001 0110 (高低字节反转)
       → 10010110
       → 128 + 16 + 4 + 2 = 150

由此我们知道 protocol buffer 结构为 Key-value 结构连接成, 无需使用分隔符来分割不同的字段。所以可选的字段如果不存在也不会出现在 message 流中的, 这个特性就有助于减小 message 大小。

More Value Types

Signed Integers
从上面看到类型 0 表示 varint, 其包含 int32/int64/uint32/uint64/sint32/sint64/bool/enum。其中 sint32/sint64表示 signed int(有符号整型), 这两个类型和"标准的"有符号整型(int32/int64)在字段值为负数时进行编码存在较大的差别。
在计算机内, 因为负数的符号位为数字的最高位, 所以一个负数通常会被表示为一个很大的整数。如果采用 Varint 表示一个负数(32位), 那么一定需要 5 个 byte。为此 Protocol Buffer 定义了 sint32/sin64 类型, 采用 ZigZag 方式, 使编码更加高效。
ZigZag 编码的含义即用无符号数来表示有符号数字, 正数和负数交错, 如:

Signed Original Encoded As zig-zags
0 0
-1 1
1 2
-2 3
2147483647 4294967294
-2147483648 4294967295

它算法为

(n << 1) ^ (n >> 31)   // for sint32
(n << 1> ^ (n >> 63)   // for sint64

需要注意这里的位移都采用算术位移(arithmetic shift), 所以对第二部分的 (n >> 31) 和 (n >> 63), 如果 n 为负值则位移后的结果为 -1, 否则为 0。

Non-varint Numbers
非 varint 类型数字, double/fixed64 占 64位(8字节), float/fixed32 占 32位(4字节), 同样采用的小字节序(little-endian)存储

Strings
wire type 为 2, 解释为长度限定(length-delimited)类型, 其值为 varint 编码的长度信息, 紧跟着数据字符的数字编码信息

message Test2 {
  required string b = 2;
}

设置 b 的值为 "testing", proto buf 编码后为:

12 07 74 65 73 74 69 6e 67

其中 12 为 key 解析得到 field_number 和 wire type:

0x12 → 10010 → field_number = 2, wire type = 2

07 表示后面值的字节长度, 后面红色部分为字符 "testing" 的 UTF8 编码

Embedded Messages
这里定义一个 嵌入 message 的例子, 嵌入类型为 Test1, 并将 Test1 中 a 的值设置为十进制 150:

message Test3 {
  required Test1 c = 3;
}

其编码结果为:

1a 03 08 96 01

根据上面介绍的原理,可以看出最后的 3 个字节和 Test1 例中的值完全一致(08 96 01),只是增加了 string 方式的编码字符。1a 为 field_number 为 3, wire type 为 2, 03 为后面值的字节长度。

Optional And Repeated Elements
如果在 proto2 的 message 定义了一个 repeated 类型的字段(没有加 [packed = true] 参数), 则 message 编码后会有 0 个或者很多个拥有相同字段序号的 key-value 对。而且这些 repeated 字段的的值并不是连续出现, 它们可能交叉在其它字段之间。 当解析时,该字段的各值之间顺序会被保留下来, 但相对于其他字段的排序将会丢失。在 proto3 中,repeated 类型会被 packed encoding(参考下面 Packed Repeated Fields 的介绍)。
对于 proto3 中的非 repeated 类型字段及 proto2 的 optional 类型字段, 编码后的 message 都可能会出现有些字段没有key-value对的情况。

通常情况, 编码后的 message 对于一个非repeated类型的字段不会出现多个实例。但解析器是被设计成可以处理多个实例。
对于数字和字符串类型, 如果同一字段出现多次, 解析器只认最后一个值, 即后值覆盖前值。对于嵌入类型字段, 解析器会合并相同的字段类似 Message::MergeFrom 的方法。 根据这些规则,将两个编码后 message 连接起来解析和解析完再合并是等价的:

MyMessage message;
message.ParseFromString(str1 + str2);

等价于

MyMessage message, message2;
message.ParseFromString(str1);
message2.ParseFromString(str2);
message.MergeFrom(message2);

这个特性可能会用得到,当你不知道两个 message 中字段及类型时也能合并这两个 message

Packed Repeated Fields
从 2.1.0 版开始 Protocol Buffer 引入了 packed repeated 字段类型, 只需要在 repeated 字段后面设置 [pack = true] 的选项。 在 proto3 版本中, repeated 字段将默认为 packed 类型。 这种方式的 repeated 字段, 如果元素数量为 0 时不会被编码到 message 中。 如果不为 0 则 repeated 的所有元素会按 wire type 2 (length-delimited) 类型被编码到同一个 key-value 对中, 这样就不需要每个元素前面都要加类型和字段序号(对于 repeated 整型元素编码可以节省更多的空间), 举个栗子:

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

构造一个 Test4, 添加多个 d 值分别为, 3, 270, 86942, 编码后:

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

只数字类型的 repeated 字段(varint, 32-bit, or 64-bit wire types)才能定义为 "packed"。虽然 packed repeated 字段通常不会编码出超过一个 key-value 对。但是编码器也要准备好接收多个 key-value 对。这种情况下, 有效长度(payloads)应该被级联。每个 key-value 对都必须包含所有的元素数。当一个 repeated 字段没有被声明为 packed,却按照 packed 方式编码时,Protocol buffer 解析器也是可以解析这个字段的, 反之亦然, 这就保证了 [packed=true] 选项的前后向兼容性。

Field Order
在 .proto 文件中可以定义任意不连续的字段序号, 当 Message 进行编码时,编码器会按照字段顺序写入,解析器也会根据序号进行优化处理,建议按顺序定义以提高效率。
如果 Message 中有一个未知字段,java 和 C++ 编码器会把它们依次加已知字段后面(目前 Python 则不处理未知字段)

本文来源于 google protocol buffers 文档(更新日期:四月 14, 2016)

从此文档我们不但知道了pb的编码原理,更知道一些特性
1. 因为 key 中被类型占用了 3 位,所以能用一个字节表示的序号为前 15 个,16 ~ 2047 个就需要 2 个字节, 所以尽量把字段控制在15个以内可能会更高效
2. 不要修改已存在字段的序号
3. 可以删除不需要的字段(除了required),但序与必须保留不再使用
4. 字段名称长度并不影响存储空间
5. optional 兼容 repeated, 如果字段为 optional 却传了一个 repeated 类型, 并且 repeated 是一个原始类型(primitive type)字段将只识别最后一个元素; 如果是一个 message 类型字段,则所有元素将合并成一个解析
6. int32, uint32, int64, uint64, and bool相互兼容, 但(64-bit数字当int32来解析, 会被截断)
7. sint32 and sint64 相互兼容, 但是不能兼容其它 integer 类型
8. 有符号整型的字段,如果值存在负数则定义为 sint32/sint64 类型会更节省空间更高效
9. string and bytes 在 UTF8 编码下是兼容的
10. 如果bytes 内嵌一个编码的 message, 则内嵌 message 与 bytes 兼容
11. fixed32 兼容 sfixed32, fixed64 兼容 sfixed64
12. 数字类型 repeated 字段加 [packed = true] 更节省空间(因为都编码到一块应该会更高效一点)
13. proto 中定义了默认值并不能被编码。如果不设置而只是依靠默认值,则接收者无法知道你定义的默认值

Reference
[1] https://developers.google.com/protocol-buffers/docs/encoding
[2] https://developers.google.com/protocol-buffers/docs/proto
[3] https://en.wikipedia.org/wiki/Arithmetic_shift