写点什么

protocol buffer 的高效编码方式

发布于: 4 小时前

简介

protocol buffer 这种优秀的编码方式,究竟底层是怎么工作的呢?为什么它可以实现高效快速的数据传输呢?这一切都要从它的编码方式说起。

定义一个简单的 message

我们知道 protocol buffer 的主体就是 message,接下来我们从一个简单的 message 出发,详细讲解 protobuf 中的编码方式。

比如下面的一个非常简单的消息对象:

message Student {  optional int32 age = 1;}
复制代码

在上面的例子中,我们定义了一个 Student 消息对象,并给他定义了一个名叫 age 的字段,并给它设置一个值叫做 22。然后使用 protobuf 将其进行序列化,这么大的一个对象,对其序列化之后的字节如下所示:

08 96 00
复制代码

很简单,使用三个字节就可以表示一个 messag 对象,数据量非常小。

那么这三个字节到底表示什么意思呢?一起来看看吧 。

Base 128 Varints

在解释上面的三个字节的含义之前,我们需要了解一个 varints 的概念。

什么叫 Varints 呢?就是序列化整数的时候,占用的空间大小是不一样的,小的整数占用的空间小,大的整数占用的空间大,这样不用固定一个具体的长度,可以减少数据的长度,但是会带来解析的复杂度。

那么怎么知道这个数据到底需要几个 byte 呢?在 protobuf 中,每个 byte 的最高位是一个判断位,如果这个位被置位 1,则表示后面一个 byte 和该 byte 是一起的,表示同一个数,如果这个位被置位 0,则表示后面一个 byte 和该 byte 没有关系,数据到这个 byte 就结束了。

举个例子,一个 byte 是 8 位,如果表示的是整数 1,那么可以用下面的 byte 来表示:

0000 0001
复制代码

如果一个 byte 装不下的整数,那么就需要使用多个 byte 来进行连接操作,比如下面的数据表示的是 300:

1010 1100 0000 0010
复制代码

为什么是 300 呢?首先看第一个 byte,它的首位是 1,表示后面还有一个 byte。再看第二个 byte,它的首位是 0,表示到此就结束了。我们把判断位去掉,变成下面的数字:

010 1100 000 0010
复制代码

这时候还不能计算数据的值,因为在 protobuf 中,byte 的位数是反过来的,所以我们需要把上面的两个 byte 交换一下位置:

000 0010 010 1100 
复制代码

也就是:

10 010 1100 
复制代码

=256 + 32 + 8 + 4 = 300

消息体的结构

从 message 的定义可以知道,protobuf 中的消息体的结构是 key=value 的形式,其中的 key 就是 message 中定义的字段的整数值 1,2,3,4 等。而 value 就是真正对其设置的值。

当一个消息被编码之后,这些 key 和 value 会被连接在一起,组成一个 byte stream。当要对其进行解析的时候,需要定位到 key 和 value 的具体长度,所以在 key 中需要包含两部分,第一个部分就是字段在 proto 文件中的值,第二个部分就是 value 部分占用的长度大小。

只有通过这两个部分的值结合起来,解析器才能够正确的对字段进行解析。

key 的这种格式,被称为 wire types,有哪些 wire types 呢?我们看一下:

可以看到除了 3,4 两种类型之外,其他的类型可以分为三类,一类是固定长度的类型,如 1,5,他们分别是 64 位和 32 位的数字。

第二类是 0,表示 Varint,这是一种可变类型,用来表示通用的数字类型,bool 类型和枚举类型。第三类 2,表示长度区分的类型,这种类型通常用来表示字符串,字节数字等。

所有的 key 都是一个 varint 类型,它的值是:(field_number << 3) | wire_type,也就是说 key 的最后三个位,用来存储 wire 类型。

上面我们例子中的 key 的值是 08,用二进制表示:

000 1000
复制代码

最后三位是 0,表示是一个 Varint 类型,将 08 右移三位,得到 1,表示 key 表示的字段是 1 这个字段,也就是 age。

然后我们看下剩下的部分 96 00,换成二进制是:

96 00 = 1001 0110  0000 0000
复制代码

根据 Varint 的定义,第一位表示的是连接位,表示第二个字节的内容和第一个字节的内容是一起的。对于 Varint 来说,需要将低位的字节和高位的字节进行交换,如下:

1001 0110  0000 0000 去掉最高位的1 :001 0110  0000 0000  交换低位字节和高位字节:0000 0000  001 0110 
复制代码

上面的值是16 + 4 + 2 = 22

这样我们就得到了值为 1 的 key,对应的 value 是 22。

符号整数

我们知道有两种表示符号整数的方式,一种是标准的 int 类型:int32 和 int64,一种是带符号的 int 类型:sint32 和 sint64。

这两种类型的区别在于对应负整数的表示上。对于 int32 和 int64 来说,所有的负整数都是以十个字节来表示的,所以占用的空间会比较大,不适合用来表示负整数。

如果使用 sint32 和 sint64,那么使用的编码方式是 ZigZag,对于负整数来说更加有效。

ZigZag 将带符号的整数和无符号的整数进行映射,对于每个 n 来说,将会使用下面的公式来编码:

(n << 1) ^ (n >> 31)
复制代码

对于 sint64 来说就是:

(n << 1) ^ (n >> 64)
复制代码

举个例子:

# 字符串

字符串的 wire 类型是 2,说明它的值是一个 varint 编码的长度。举个例子:

 message Student {  optional string name = 2;}

复制代码

上我们给 Student 定义了第二个属性 name,假如给 name 赋值 “testing” ,那么得到的编码是:

12 07 [74 65 73 74 69 6e 67]
复制代码

中括号的编码就是”testing”的 UTF8 表示。

0x12 可以这样解析:

 0x12→ 0001 0010  (binary representation)→ 00010 010  (regroup bits)→ field_number = 2, wire_type = 2
复制代码

0x12 表示字段 2 的类型是 2,后面跟着的 07 就表示后续 byte 字节的长度了。

嵌套的消息

消息中可以嵌套消息,我们看一个例子:

message Teacher {  optional Student s = 3;}
复制代码

假如我们把 s 的 age 字段设置为 22,就和第一个例子一样,那么上面的编码就是:

 1a 03 08 96 00
复制代码

可以看到后面的三个字节和第一个例子是一样的。前面两个字节的判断方式和字符串是一值的,这样就不再多讲。

总结

好了,protobuf 的基本编码规则和实现已经讲完了。听起来是不是很奇妙?

本文已收录于 http://www.flydean.com/03-protobuf-encoding/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

发布于: 4 小时前阅读数: 6
用户头像

关注公众号:程序那些事,更多精彩等着你! 2020.06.07 加入

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧,尽在公众号:程序那些事!

评论

发布
暂无评论
protocol buffer的高效编码方式