Google Protocol Buffer 的 Encoding
您目前处于:编程  2016-06-18

Protobuf 序列化后所生成的二进制消息非常紧凑,这得益于 Protobuf 采用的非常巧妙的 Encoding 方法。

Varint

Varint 是一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字,值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。

比如对于 int32 类型的数字,一般需要 4 个 byte 来表示。但是采用 Varint,对于很小的 int32 类型的数字,则可以用 1 个 byte 来表示。当然凡事都有好的也有不好的一面,采用 Varint 表示法,大的数字则需要 5 个 byte 来表示。从统计的角度来说,一般不会所有的消息中的数字都是大数,因此大多数情况下,采用 Varint 后,可以用更少的字节数来表示数字信息。

Varint 中的每个 byte 的最高位 bit 有特殊的含义,如果该位为 1,表示后续的 byte 也是该数字的一部分,如果该位为 0,则结束。其他的 7 个 bit 都用来表示数字。因此小于 128 的数字都可以用一个 byte 表示。大于 128 的数字,比如 300,会用两个字节来表示:1010 1100 0000 0010

下图演示了 Google Protocol Buffer 如何解析两个 bytes。注意到最终计算前将两个 byte 的位置相互交换过一次,这是因为 Google Protocol Buffer 字节序采用 little-endian 的方式。

消息经过序列化后会成为一个二进制数据流,该流中的数据为一系列的 Key-Value 对。如下图所示:

采用这种 Key-Pair 结构无需使用分隔符来分割不同的 Field。对于可选的 Field,如果消息中不存在该 field,那么在最终的 Message Buffer 中就没有该 field,这些特性都有助于节约消息本身的大小。

proto 文件

message Test1 {
  required int32 a = 1;
}

以上面的的消息 proto 为例,假设我们生成如下的一个消息 Test1:

Test1.id = 150;

则最终的 Message Buffer 中有一个 Key-Value 对,对应消息中的 id。

Key 用来标识具体的 field,在解包的时候,Protocol Buffer 根据 Key 就可以知道相应的 Value 应该对应于消息中的哪一个 field。

Key 的定义如下:

(field_number << 3) | wire_type

可以看到 Key 由两部分组成。第一部分是 field_number,第二部分为 wire_type。表示 Value 的传输类型。也就是说,key中的后三位,是值得传输类型。

Wire Type 可能的类型如下表所示:

在例子中,写入 message 后,我们看到最终输出文件中包含三个数字:08 96 01,这是如何得来的?

至此我们知道数字标签是1,值类型为varint。我们来解码96 01,即为150:

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

注意:数值部分,低位在前,高位在后。

有符号整数

在例子当中,field id 所采用的数据类型为 int32,因此对应的 wire type 为 0。在 Type 0 所能表示的数据类型中有 int32 和 sint32 这两个非常类似的数据类型。Google Protocol Buffer 区别它们的主要意图也是为了减少 encoding 后的字节数。

在计算机内,一个负数一般会被表示为一个很大的整数,因为计算机定义负数的符号位为数字的最高位。如果采用 Varint 表示一个负数,那么一定需要 5 个 byte。为此 Google Protocol Buffer 定义了 sint32 这种类型,采用 zigzag 编码。将所有整数映射成无符号整数,然后再采用varint编码方式编码,这样,绝对值小的整数,编码后也会有一个较小的varint编码值。

Zigzag映射函数为

Zigzag(n) = (n << 1) ^ (n >> 31), n为sint32时
Zigzag(n) = (n << 1) ^ (n >> 63), n为sint64时

按照这种方法,-1将会被编码成1,1将会被编码成2,-2会被编码成3,如下表所示:

String

类型为2的数据,是一种指定长度的编码方式:key+length+content,key 的编码方式是统一的,length 采用 varints编码方式,content 就是由 length 指定长度的 Bytes。定义如下的 message 格式:

message Test2 {
  required string b = 2;
}

设置该值为"testing",二进制格式查看:

12 07 74 65 73 74 69 6e 67

此处,key是16进制表示的,所以展开是:

12 -> 0001 0010

后三位 010 为 wire type = 2,0001 0010 右移三位为 0000 0010,即 tag=2。length 此处为7,后边跟着7个 bytes,即我们的字符创 "testing"。

嵌套 message

定义如下嵌套消息:

message Test3 {
  required Test1 c = 3;
}

同第二部分一样,设置字段为整数150,编码后的字节为:

1a 03 08 96 01

我们发现,后三个字节跟我们第一个例子中的一摸一样 (08 96 01),他们前边有一个长度限制03, 嵌套消息跟 string 是一摸一样的,其 wire type 也为 2。


Reference:

https://www.ibm.com/developerworks/cn/linux/l-cn-gpb/

http://www.cnblogs.com/shitouer/archive/2013/04/12/3017381.html


转载请并标注: “本文转载自 linkedkeeper.com ”  ©著作权归作者所有