Google Protocol Buffer Encoding

Google Protocol Buffer的安装使用参考官网：
https://github.com/google/protobuf/tree/master/objectivec
Protocol Buffers 是一种轻便高效的结构化数据存储格式，可以用于结构化数据串行化，或者说序列化。它很适合做数据存储或 RPC 数据交换格式。可用于通讯协议、数据存储等领域的语言无关、平台无关、可扩展的序列化结构数据格式。

Language	Source
C++ (include C++ runtime and protoc)	src
Java	java
Python	python
Objective-C	objectivec
C#	csharp
JavaNano	javanano
JavaScript	js
Ruby	ruby
Go	golang/protobuf
PHP	php
Dart	dart-lang/protobuf

Protobuf 的优点

Protobuf 有如 XML，不过它更小、更快、也更简单。你可以定义自己的数据结构，然后使用代码生成器生成的代码来读写这个数据结构。你甚至可以在无需重新部署程序的情况下更新数据结构。只需使用 Protobuf 对数据结构进行一次描述，即可利用各种不同语言或从各种不同数据流中对你的结构化数据轻松读写。

它有一个非常棒的特性，即“向后”兼容性好，人们不必破坏已部署的、依靠“老”数据格式的程序就可以对数据结构进行升级。这样您的程序就可以不必担心因为消息结构的改变而造成的大规模的代码重构或者迁移的问题。因为添加新的消息中的 field 并不会引起已经发布的程序的任何改变。

Protobuf 语义更清晰，无需类似 XML 解析器的东西（因为 Protobuf 编译器会将 .proto 文件编译生成对应的数据访问类以对 Protobuf 数据进行序列化、反序列化操作）。

使用 Protobuf 无需学习复杂的文档对象模型，Protobuf 的编程模式比较友好，简单易学，同时它拥有良好的文档和示例，对于喜欢简单事物的人们而言，Protobuf 比其他的技术更加有吸引力。

Google Protocol Buffer 的 Encoding

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

考察消息结构之前，让我首先要介绍一个叫做 Varint 的术语。

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

比如对于 int32 类型的数字，一般需要 4 个 byte 来表示。但是采用 Varint，对于很小的 int32 类型的数字，则可以用 1 个 byte 来表示。当然凡事都有好的也有不好的一面，采用 Varint 表示法，大的数字则需要 5 个 byte 来表示。从统计的角度来说，一般不会所有的消息中的数字都是大数，因此大多数情况下，采用 Varint 后，可以用更少的字节数来表示数字信息。下面就详细介绍一下 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 的方式。

图 6. Varint 编码

图 6. Varint 编码

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

图 7. Message Buffer

图 7. Message Buffer

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

以代码清单 1 中的消息为例。假设我们生成如下的一个消息 Test1:

Test1.id = 10;

Test1.str = “hello”；

则最终的 Message Buffer 中有两个 Key-Value 对，一个对应消息中的 id；另一个对应 str。

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

Key 的定义如下：

(field_number << 3) | wire_type

可以看到 Key 由两部分组成。第一部分是 field_number，比如消息 lm.helloworld 中 field id 的 field_number 为 1。第二部分为 wire_type。表示 Value 的传输类型。

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

表 1. Wire Type

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

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

在计算机内，一个负数一般会被表示为一个很大的整数，因为计算机定义负数的符号位为数字的最高位。如果采用 Varint 表示一个负数，那么一定需要 5 个 byte。为此 Google Protocol Buffer 定义了 sint32 这种类型，采用 zigzag 编码。

Zigzag 编码用无符号数来表示有符号数字，正数和负数交错，这就是 zigzag 这个词的含义了。

如图所示：

图 8. ZigZag 编码

图 8. ZigZag 编码

使用 zigzag 编码，绝对值小的数字，无论正负都可以采用较少的 byte 来表示，充分利用了 Varint 这种技术。

其他的数据类型，比如字符串等则采用类似数据库中的 varchar 的表示方法，即用一个 varint 表示长度，然后将其余部分紧跟在这个长度部分之后即可。

通过以上对 protobuf Encoding 方法的介绍，想必您也已经发现 protobuf 消息的内容小，适于网络传输。假如您对那些有关技术细节的描述缺乏耐心和兴趣，那么下面这个简单而直观的比较应该能给您更加深刻的印象。

对于代码清单 1 中的消息，用 Protobuf 序列化后的字节序列为：

08 65 12 06 48 65 6C 6C 6F 77

而如果用 XML，则类似这样：

|

31 30 31 3C 2F 69 64 3E 3C 6E 61 6D 65 3E 68 65

6C 6C 6F 3C 2F 6E 61 6D 65 3E 3C 2F 68 65 6C 6C

6F 77 6F 72 6C 64 3E

一共 55 个字节，这些奇怪的数字需要稍微解释一下，其含义用 ASCII 表示如下：

<``helloworld``>

<``id``>101</``id``>

<``name``>hello</``name``>

</``helloworld``>

Base 128 Varints

Google Protobuf里面提出了“Base 128 Varints”编码，这是一种变字节长度的编码，官方描述为：varints是用一个或多个字节序列化整形的一种方法。我理解要点有三个(1)操作是序列化(2)操作对象是整形(3)变长编码。重点是最后一点，他是如何编码的呢？

（1）除了最后一个字节，varint中的每个字节的最高位设为1，表示后面还有字节出现

（2）每个字节的低7位看成是一个组（group），这个组和他相邻的下一个7位组共同存储某个整形的“组合表示”，最低有效组在前面。
(1)一个字节。下面只有一个字节，所以最高位是0，表示十进制1
0000 0001
(2)两个字节。
1010 1100 0000 0010
由于第一个字节后面还有一个字节，所以第一个字节的最高位设置为1，表示后面还有后继字节，第二个字节的最高位为0。去掉每个字节的最高位，我们对两个字节进行分组。第一个7位组：0101100，第二个7位组：0000010，组合起来就是：0101100 0000010，由于最低有效组在前面，所以两个7位组进行调换，结果为：0000010 0101100，中间的空格是为了大家区分，去掉前面的0，也就是：100101100，十进制为12^8 + 12^5 + 12^3 + 12^2 = 256 + 32 + 8 + 4 = 300。

（3）三个字节。我们换种方式，给定某个整形，要求写出他的varint表示，这里当然是落在需要3个字节表示的整形。16380可以吗？不可以！因为16380 < 2^14，所以2个字节足以，我们就以27491为例，27491的二进制表示为：
0110 1011 0110 0011
注意这里是高字节之前，低字节在后，和varint的编码规则相反，首先按照7位一组划分为：0000001 1010110 1100011，然后反转为：1100011 1010110 0000001，最后将末尾的7位组前面补0组成一个字节，两个7位组都补1分别组成一个字节：
11100011 11010110 00000001

(4)更多字节。聪明的你可能发现，varint编码中4个字节最大表示的数为228,非常正确，同时说明了天下没有免费的午餐，有得有失。Protobuf引入了fixed32解决这个问题的，如果某个字段经常大于228,应当优选fixed32，他是固定长度为32位的。