Masutangu

长风破浪会有时 直挂云帆济沧海

也許我這一生 始終在追逐那顆九號球


Protobuf 编码原理

最近项目组有在用 protobuf,于是抽空读了些 protobuf 的相关资料。本文总结 protobuf 的编码原理,重点在于其如何实现版本兼容。文中样例及说明都参考了 protobuf 的官方文档

编码方法的介绍

要了解 protobuf 的编码方式,首先介绍下 Varint 和 ZigZag 这两种编码。

Varint

Varint 编码的优势在于值越小的数字,占用的字节更少。一般 int32 的数字都需要占用 4 个字节。使用 Varint 进行编码则有可能缩减到 1 个字节。反过来,如果是比较大的数字,则可能需要占用 5 个字节。 理解了 Varint 的目的(节省空间),来看看其原理:

Each byte in a varint, except the last byte, has the most significant bit (msb) set – this indicates that there are further bytes to come. The lower 7 bits of each byte are used to store the two’s complement representation of the number in groups of 7 bits, least significant group first.

即是说,Varint 中的每个字节的最高位 bit 有特殊的含义,该位为 1 表示后续的字节也是该数字的一部分,如果该位为 0 则是最后一个字节。其他的 7 个bit都用来表示数字,从最低有效字节开始。

举个例子,1 的二进制表示为 0000 0001。通过 Varint 编码后的二进制表示为 0000 0001,过程如下:

再举个例子,300 的二进制表示为 100101100,通过 Varint 编码后的二进制表示为 10101100 00000010,详细过程如下:

ZigZag

上节介绍了 Varints,我们知道 Varint 在处理小数值的数字很有效,而在处理值较大的数字则占用了多一个子节。对于负数来说,二进制最高有效位为 1,如果用 varint 来编码,无疑要占用比较多的子节。因此我们可以搭配 zigzag 来编码。

ZigZag 编码将有符整型转化成无符的整型,其原理是将最高位的符号位放到最低位(-1 除外),这样大大减少了字节占用。

举个例子,-2 的二进制表示为 1111 1110,用zigzag编码,-2 的绝对值为 2,二进制为 0000 0010,将符号位放到最低位,则变成 0000 0011。

公式如下:

  • 32 位整型:(n « 1) ^ (n » 31)
  • 64 位整型:(n « 1) ^ (n » 63)

Note that the second shift – the (n » 31) part – is an arithmetic shift. So, in other words, the result of the shift is either a number that is all zero bits (if n is positive) or all one bits (if n is negative).

注意这里的位移操作符。如果在位移运算符左边的变量是有符号数,编译产生的汇编指令是算术位移指令,如果该变量是无符号数,编译产生的汇编指令则是逻辑位移指令。对于左移,它们都一样,整个二进制右移,低位补 0;右移则有所区分,算数右移左边补最高符号位,逻辑位移左边补 0

举个例子,-2 经过 ZigZag 编码后为 3,过程如下:

Protobuf 的编码原理

版本兼容

Protobuf 支持向前向后兼容。向后兼容即升级的解码程序能够正确解析旧版本协议的数据,向前兼容则指旧版本的解码程序能够正确解析新版本协议的数据。如果新的协议新增了字段,旧版本的解析程序是如何自动跳过新字段的呢?

协议,即通信双方约定好的规则。收到数据时,可以根据约定好的规则进行解包。假设我们使用简单粗暴的编解码方法,将结构体定义的成员按类型依此打解包。如下图,我们约定好的协议包括三个字段,类型都为 int32,那解码函数将从接收到的字节流中依次取出 4 个字节并按整型解析。

如果发送方升级了协议,如下图:

很明显,如果旧的解码程序还是按照依次取出 3 个 int32 去解析的话,毫无疑问是错误的(会把结构体 old_message 的成员 d 的值解析成 0x1a )。如果有办法能跳过新增字段,就可以做到兼容,即旧的解码程序能正确解析出旧协议定义的字段,新增字段一律忽略。

Protobuf 采用的方法很简单也很实用,把 tag 和其类型一起打进去字节流,解码程序只要解析出不认识的 tag,就能知道该字段是新协议定义的,再通过其类型可以推断出该字段内容的长度,就能正确的跳过这部分 buffer,继续解析下一个字段。如下图:

当旧的解码程序解析到 tag 为 3 时,发现在旧协议里找不到该 tag,又从其类型 int 64 知道该 tag 的值占了 8 个字节,于是他跳过这 8 个字节,继续解析剩下的字节流。

实现

Protobuf 的实现中,将每个字段的 key 设为 varint 编码后的 (tag number << 3) | wire_type。即 key 的最低三位表示字段类型,将 key 右移三位后的值表示 tag number。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

如果是 Length-delimited Type,意味着长度不定,这时还需要在 key 后面多写入长度信息(用 varint 编码)。

举个例子:

message Test2 {
  required string b = 2;
}

将 b 的值设为 “testing”,protobuf 编码后的字节流为12 07 74 65 73 74 69 6e 67 key 为 0x12,可以算出 tag 值为 2(0x12 » 3), type 为 2 ( 0x12 取最低三位)。下个字节为 0x07 ,该字节表示长度,即长度为 7,因此后续的 7 个字节都为该 tag 的值。

另外 protobuf 还定义了 sint32/sint64 类型。sint32/sin64 类型专门用于编码负数。如果使用 int32/int64 来编码负数, 通过 varint 编码后的 buffer 长达 5/10 个字节。(int32 时占用5个字节,int64时占用10个字节,因为负数的最高位为1,会被当作非常大的整数处理)。

而 sint32/sint64 类型的值会先经过 zigzag 编码,转换成无符号整数,再采用 varint 编码,可以大大减少编码后占用的字节数。

If you use int32 or int64 as the type for a negative number, the resulting varint is always ten bytes long – it is, effectively, treated like a very large unsigned integer. If you use one of the signed types, the resulting varint uses ZigZag encoding, which is much more efficient.

使用建议

  • 常用消息字段(尤其是 repeated 字段)的 tag number 尽量分配在 1 ~ 15 之间。tag number 超过 16,key 的编码将占用多一个字节
  • 尽可能多的(全部)使用 optional 字段
  • 不能修改字段的 tag number
  • 不能增删任何 required 字段
最近的文章

浅读 Libco

今天花了一天时间,学习了下微信的开源协程库 libco的代码,写下来做个纪录,有部分细节代码(包括 coctx_swap.S 那段汇编)我还没读懂,以后再补充进来。协程的原理协程的概念和优点这里不再赘述。我们先介绍下实现协程的原理,再来看看相应的代码。协程的切换,其实就是由我们手动来管理指令执行的上下文。一般每一个协程有自己的 context_buff 来保存自己的运行上下文(寄存器和栈)。当需要挂起当前协程时,将当前的上下文保存到该协程的 context_buff,并把当前上下文重置为新...…

源码阅读继续阅读
更早的文章

简单异步应用框架的实现

两年前刚进公司的时候,第一次接触了异步框架,那时还处于懵懵懂懂的状态。最近换了组,接触到另外一种实现的异步框架,这次有了一定的积累后,对异步框架的设计也有了更多的理解。刚好最近自己基于 libuv 造了个简单的轮子 saf (Simple Async Framework),趁此机会和大家聊聊异步框架的设计思想和实现。异步框架设计思想服务器模型先来看看传统的服务器模型,如下图:一般来说,服务器端可以分为三层:接入层,逻辑层,数据层。接入层负责客户端的接入,逻辑层则实现业务逻辑,数据层就是数据...…

个人项目继续阅读