protobuf编解码研究

  • 时间:
  • 浏览:
  • 来源:互联网

背景


一.优势
1、json: 一般的web项目中,最流行的主要还是json。因为浏览器对于json数据支持非常好,有很多内建的函数支持。 2、xml: 在webservice中应用最为广泛,但是相比于json,它的数据更加冗余,因为需要成对的闭合标签。json使用了键值对的方式,不仅压缩了一定的数据空间,同时也具有可读性。 3、protobuf:是后起之秀,是谷歌开源的一种数据格式,适合高性能,对响应速度有要求的数据传输场景。因为profobuf是二进制数据格式,需要编码和解码。数据本身不具有可读性。因此只能反序列化之后得到真正可读的数据。

相对于其它protobuf更具有优势
1:序列化后体积相比Json和XML很小,适合网络传输
2:支持跨平台多语言
3:消息格式升级和兼容性还不错
4:序列化反序列化速度很快,快于Json的处理速度

以一个数字的序列化为例:

JSON:{“id”:42},9 bytes
xml:42,11 bytes 。一般还需要外层包裹实现。
protobuf:0x08 0x2A,2 bytes
0x08 = field 1, type :Variant
0x2A = 42 (raw) or 21 (zigzag)


二,编码结构

图一
在这里插入图片描述
配注:[length]是有些类型不用这个字段的,只有类型2需要填充一个length

由图可以知道其实protobuf的编码就是key-value结构,key就是tag,那这个tag就是由field_number和wird_type组成的。
那这个field_number和wire_type是什么呢?举个例子

图二
在这里插入图片描述
在这幅图中可以看到string对于的类型就是wireType,查protobuf表可以string的类型是2,所以这个wireType是2。
field_number就是我们自定义的那个数字。
到此明白了什么是wireType和field_number,那它们是怎样组合成tag的呢?

查看源码可以知道
在这里插入图片描述
也就是fieldNumber右移3位|wireType。那为什么只是右移动三位呢?
因为从图1可以知道,protobuf一共只有6种类型,因此右移3位给wireType足够填充在后面的3位,一个字节8个bit,去掉一个msb位,剩余4个bit给fieldNumber,这也就是很多博客说的前15个数字尽量给频繁使用的字段用,因为假如你用了16,那至少需要两个字节了。

varint算法

一,varint算法解决了什么问题?
对于存储IO和网络IO而言,数据越小,越能减少IO开销和节省网络带宽。对于常规的数据存储,固定类型的数据所占的内存大小是确定的。比如:byte占8bit,int32占32bit,float占32bit等等。也就是说,不论数值大小如何,内存都要开辟固定长度的内存区用来存放数据。绝大多数情况下这是浪费的。比如无符号型0255,有符号型-128127,本来8bit就可以搞定,而int32都分配了32bit的长度,这意味着前面的3字节长度并没有利用,是浪费的。Varint存储算法就是针对这种情况的改良。

对于Varint,每8bit的数据中,首位叫作most signficant bit,简称为msb,它不是数据位,代表特殊的含义:

0:代表该字节就是数据的结尾;1:代表该字节的下一字节依然是数据的一部分。

后面的7bit用来表示数据域。

举例说明。

1的二进制为:0000 0001,用varint编码为:0000 0001,即0x01,显然一个字节就表示出了大小。节省了3字节的空间。

666的二进制为:1010011010,用varint编码为:10011010, 0000 0101。占两字节大小。这里解释一下,varint算法采用的是逆序存储。即二进制数据从后向前开始,每7位为一个单元,开头加上msb,按从前向后排列。从后往前的第一个7bit为0011010,一个字节显然存不下666,所以msb为1,所以第一个字节为10011010;剩下的3bit为101,不足7bit补0,加上msb为1,故第二字节为0000 0101。


Varints 编码的3规则:

1、在每个字节开头的 bit 设置了 msb(most significant bit ),标识是否需要继续读取下一个字节
2、存储数字对应的二进制补码
3、补码的低位排在前面,字节旋转操作
00000101 | 00011010 经常字节旋转,得到
00011010 | 00000101

int32的编码源码为:
在这里插入图片描述


到目前为止,我们看到的都是Varint编码的优点:用尽可能少的字节表示数据。显然对于一般的小数值而言这是巨大的优势。下面我们分析一下这种编码的缺点。

(1) 不适合存储大数值

   一方面,对于int32而言,有32个bit表示数据域。Varint每字节都有一个msb,即意味着32bit中只有28bit来表示数据。对于小于2^28的数据,Varint最多需要4字节来编码。但对于2^28~ (2^32-1)范围内的数据,Varint编码4字节显然存不下,还需要额外的1字节,共5字节。所以,对于2^28~ (2^32-1)范围的数据,Varint编码性能是降低的,开销还大。但绝大多数情况下,我们用到的值大概率的都是小于2^28的,所以Varint编码还是很有优势的。

(2) 不适合存储负数

   另一方面,对于负数。我们知道存储的是补码。-1的补码为1111...,1111,共32bit。Varint要存放-1需要多少字节呢?乍一看一共32个1,所以需要5字节。

而在protocol buffer中,Varint编码需要10字节来存放负数。这是因为为了兼容,将 int32 扩展成 int64 的八个字节。所以-1的补码为1111,…, 1111,共64bit。加上10个msb,一共10字节。(64bit的数据域为:9个7bit + 1bit,故共10个msb)


ZigZag算法

显然Varint编码对于存放int32、int64的负数是低效的,开销更浪费。为解决这个问题, ZigZag 编码被推出以解决负数编码效率低的问题。ZigZag 的原理和概念简单易懂,用话概括介绍 ZigZag 编码:有符号整数映射到无符号整数,然后再使用 Varints 编码。既然Varint编码负数效率低下,那么将负数"转换、映射成"正数,针对正数进行Varint编码并传输,对方收到数据后,再进行"转换、映射"解码成对应的负数即可。


在这里插入图片描述
如上图所示,0的ZigZag编码为0;-1的ZigZag编码为1;1的ZigZag编码为2;-2的ZigZag编码为3 …。比如int32 a = -1,经过ZigZag编码得到1,对1进行Varint编码得到0000 0001,并存储传输。接收方收到数据0000 0001后进行Varint解码并得到1,将通过ZigZag解码得到-1。

编解码的源码为:
在这里插入图片描述
在这里插入图片描述
参考文章:

https://blog.csdn.net/milanac007/article/details/101540493
https://blog.csdn.net/jmw1407/article/details/107197938/
https://developers.google.cn/protocol-buffers/docs/encoding

本文链接http://fj.ngui.cc/a/11867.html