Google Protocol Buffer的编解码原理

发表于 分类于

Google Protocol Buffer（简称protbuf）是一种紧凑的可扩展的二进制消息格式，并且如上一篇文章《解析Google Protocol Buffer消息类型的自动反射原理》中介绍的那样，它还自带消息类型反射的功能。从Google公布的benchmark来看，protobuf的效率还是很高的，这主要依赖于它的高效编解码方式。

先来看一个简单的例子：

message Test1
{
    required int32 id = 1;
}

在一个应用中，我们将一个Test1的Message中的id设为150，将这个Message进行编码序列化以后以16进制输出到stdout中，会看到这样的3个字节：
08 96 01

也就是说只用了3个字节就表示了数据类型和数据的值。

Base 128 Varints

Varints是protobuf的序列化整型数据的一种编码方式，它的优点是整型数据的值越小，编码后所用的字节数越小。

经过Varints编码后的数据，它的每一个字节8bit的高位代表一个标记位。如果标记位是1，则代表下一个字节仍然是当前整型数据的组成；如果标记位是0，则代表下一个字节就是下一个整型数据了。

先看最简单的数值1，一个字节足以表示它，所以它的标记位置0：

0000 0001

再看数值300，经过Varints编码后的序列：
1010 1100 0000 0010

从左到右，依次将每个字节的高位（标志位）去掉，若标志位为1，则下一个字节仍是当前数据的组成，若标志位为0，则下一个字节是下一个数据的组成。
1010 1100 0000 0010
→ 010 1100  000 0010

因为protobuf是以little endian来编码字节序的，所以将两个字节交换、拼接，即可得到原始数据的二进制表示：
000 0010  010 1100
→  000 0010 ++ 010 1100
→  100101100
→  256 + 32 + 8 + 4 = 300

消息结构

我们知道，protobuf的消息是经过编码序列化的一系列key-value对，一个类型的数据对应一个key-value。value就是原始数据经过编码后的数据，而key由field number和wire type组成。其中field number是指.proto文件中定义的数据变量的field值。

message Test
{
    required int32 id = 1; // (1为field number)
}

Test类型中的数据id的field number就为1。

wire type是指的是.proto文件中定义的数据变量的类型的序号，protobuf中可以定义的所有数据类型的序号如下表：

Type Meaning Used For
0 Varint int32, int64, uint32, uint64, sint32, sint64, bool, enum
1 64 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

所以，数据id的wire type就为0，代表它是用varint进行编码的。

对于key-value中的key的值，是通过移位再相或的方法将field number和wire type用一个字节来存储的：

(field_number << 3) | wire_type

即低三位表示wire type，其他的位表示field number。

再回到本文开头的例子，先看第一个字节08

0000 1000

wire type为0，field name为1。符合id的类型是int32，编码方式是Varints，field是1的这一情况。

而后两个字节应该是150经过Varints编码后的序列：

96 01 = 1001 0110  0000 0001
       → 000 0001  ++  001 0110 (drop the msb and reverse the groups of 7 bits)
       → 10010110
       → 2 + 4 + 16 + 128 = 150

有符号整型

上文中提到例子都是wire type为0，也就是Varints编码。然而，对于protobuf来说，编码「标准」的整型（int32，int64）和编码「有符号」的整型（sint32，sint64）的时候，对于负数的处理方式是不同的。如果用int32或者int64来编码一个负数的话，通常需要耗费10个字节来表示，因为负数在计算机中是以补码表示的，相当于一个数值很大的无符号数。

所以这个时候就需要用「有符号」的整型（sint32，sint64）来表示负数了，它们先使用ZigZag编码方式将负数转换为绝对值较小正数，再进行Varints编码。

ZigZag将会这样编码，-1编码为1，1编码为2，-2编码为3……

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

sint32的ZigZag编码公式为

(n << 1) ^ (n >> 31)

相应的，sint64的ZigZag编码公式为
(n << 1) ^ (n >> 63)

有一点需要注意，(n >> 31)和(n >> 64)使用的是算术移位（也就是用符号位扩展移位）。

Non-varint Numbers

wire type为1和5的整型数据都是非Varints编码的。fixed64, sfixed64, double固定用64bit也就是8个字节来表示，fixed32, sfixed32, float固定的用32bit也就是4个字节来表示。

需要注意的是他们都使用little endian来编码字节序的。

字符串

wire type为2代表着该类型的数据长度是指定的。也就是用在key-value的中间加上一个经过Varints编码的表示value长度字段，即key-len-value。

message Test2
{
    required string str = 2;
}

将str设置为「testing」，然后把经过protobuf编码序列化后的数据以16进制的方式输出到stdout
12 07 74 65 73 74 69 6e 67

第一个字节0x12表示field name为2，wire type为2。第二个字节0x07表示数据长度为7，所以后面7个字节就是使用UTF8编码的字符数据，即「testing」。

嵌套消息

下面这个例子中，嵌套使用了上文的Test1类型

message Test3
{
    required Test1 c = 3;
}

同样的，Test1中c的值设为150，编码后得到的16进制序列如下
1a 03 08 96 01

第一个字节0x1a表示field number为3，wire type为2。我们发现后三个字节（08 96 01）和第一个例子中的序列一样，所以第二个字节0x03的意义就和string中的一样，代表数据的长度。

Optional And Repeated Elements

如果数据类型定义为repeated（没有选项packed=true）的话，将存在一个或多个具有相同field number值的key-value对。由于历史遗留的原因，如果repeated数据没有加上[packed=true]选项的话，repeated的系列数据并不一定是连续的。由于可能有多个key-value对的存在，导致效率会略有降低。

如果数据类型定义为optional的话，将存在0个或1个包含field number值的key-value对。

正常情况下，required和optional类型的最多只能出现一次，但是protobuf在做parse的时候，得考虑到所有的情况。所以对数值类型和字符串，如果出现多次，那么将只接受最后出现那个数据。对于嵌套类型，将有相同field值数据像Message::MergeFrom一样进行合并，即

all singular scalar fields in the latter instance replace those in the former, singular embedded messages are merged, and repeated fields are concatenated

这个规则带来的好处就是，parse两个连续的已编码好的Message的结果与分别单独parse两个Message后再合并得到的结果是一致的。所以，下面两种是情况是相等的。

// 情况一
MyMessage message;
message.ParseFromString(str1 + str2);

// 情况二
MyMessage message, message2;
message.ParseFromString(str1);
message2.ParseFromString(str2);
message.MergeFrom(message2);

Packed Repeated Fields

protobuf从2.1版本开始，对于repeated类型数据可以加上[packed=true]选项。加上这个选项后，每个repeated类型的数据连续排列，并且所有的repeated类型数据和field number、wrie type、len组成一个大的key-value（相当于key-value, value, value…）。

例如，下面一个例子：

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

建立一个Test4类型的Message对象，添加3个d类型变量，值分别为3, 270, 86492。得到编码后的16进制数据为：
22        // tag (field number 4, wire type 2)
06        // len (6 bytes)
03        // first element (varint 3)
8E 02     // second element (varint 270)
9E A7 05  // third element (varint 86942)

需要注意的是只有repeated类型的数据才能设置[packed=true]选项。

Field Order

尽管我们在编写.proto文件的Message时，可以按任意顺序设置变量类型的field number，但是protobuf在进行编码序列化的时候，会按field number的大小顺序存储数据类型，这样有利于parse时候的一些优化。但由于不是所有的消息都是由一个经过编码序列化的Message对象组成的，所以protobuf也可以parse按任意field number顺序存放的数据。在某些场合下，单纯的将2个Message对象合并（连接）起来也是有用的。

在C++实现中，如果一个Message对象中的数据含有无效的field number值，那么protobuf会把这个对象的数据按任意顺序存放。

参考文献

  1. Protocol Buffers. Encoding
  2. Wikipedia. Zigzag
  3. Google Project Hosting. Benchmarking