protobuffer 编解码原理

作者: 袁浩

protobuffer 编码原理

protobuffer(以下简称为PB)两个重要的优势在于高效的序列化/反序列化和低空间占用,而这两大优势是以其高效的编码方式为基础的。PB底层以二进制形式存储,比binary struct方式更加紧凑,一般来讲空间利用率也比binary struct更高,是以Key-Value的形式存储【图1】。

PB示例结构如下:

//示例protobuf结构
message Layer1
{
    optional uint32 layer1_varint  = 1;
    optional Layer2 layer1_message = 2;
}

message Layer2
{
    optional uint32 layer2_varint  = 1;
    optional Layer3 layer2_message = 2;
}

message Layer3
{
    optional uint32 layer3_varint   = 1;
    optional bytes  layer3_bytes    = 2;
    optional float  layer3_float    = 3;
    optional sint32 layer3_sint32   = 4;
}

图 1 示例PB结构内存布局

PB将常用类型按存储特性分为数种Wire Type【图 2】, Wire Type不同,编码方式不同。根据Wire Type(占3bits)和field number生成Key。

Key计算方式如下,并以Varint编码方式序列化【参考下面Varint编码】,所以理论上[1, 15]范围内的field, Key编码后占用一个字节, [16,)的Key编码后会占用一个字节以上,所以尽量避免在一个结构里面定义过多的field。如果碰到需要定义这么多field的情况,可以采用嵌套方式定义。

//Key的计算方式
Key = field_number << 3 | Wire_Type

Type

Value

Meaning

Contain

Varint

0

varint

int32,int64,sint32,sint64,uint32,uint64,bool,enum

Fixed64

1

64-bit

fixed64,sfixed64,double,float

LengthDelimited

2

length-delimi

string,message,bytes,repeated

StartGroup

3

start group

groups(deprecated)

EndGroup

4

end group

groups(deprecated)

Fixed32

5

32-bit

fixed32,float

图 2.Wire Type表

1. Varint编码

inline uint8* WriteVarint32ToArray(uint32 value, uint8* target) {
  while (value >= 0x80) {
    *target = static_cast<uint8>(value | 0x80);
    value >>= 7;
    ++target;
  }
  *target = static_cast<uint8>(value);
  return target + 1; 
}
Layer1 obj;
obj.set_layer1_varint(12345);

Varint编码只用每个字节的低7bit存储数据,最高位0x80用做标识,清空:最后一个字节,置位:还有数据。以上述操作为例,设uint32类型为12345,其序列化过程如下:

该字段的field_number = 1, wire_type = 0, 则key = 1 << 3 | 0 = 0x20。那么在内存中, 其序列为应该为0x20B960,占3Bytes。对比直接用struct存储会占4Bytes;如果struct是用 uint64呢,将占8Bytes,而PB占用内存仍是3Bytes。

下表是PB数值范围与其字节数对应关系。实际应用中,我们用到的数大概率是比较小的,而且可能 动态范围比较大(有时需要用64位存储),对比struct的内存占用,PB优势很明显。

数值范围

占用字节数

0-127

2

128-16383

3

16384-2097151

4

2097152-268435455

5

2. ZigZag编码

ZigZag编码是对Varint编码的补充与优化。负数在内存中以前补码形式存在,但不管是负数的原码还是补码,最高位都是1;那么问题来了,如果以上述Varint编码方式,所有负数序列化以后都会以最大化占用内存(32位占用6Bytes, 64位占用11Btyes)。所以,细心的同学会发现,对于有符号数的表示有两种类型,int32和sint32。对,sint32就是对这种负数序列化优化的变种。

inline uint32 WireFormatLite::ZigZagEncode32(int32 n) {
  // Note:  the right-shift must be arithmetic
  return (static_cast<uint32>(n) << 1) ^ (n >> 31);
}

sint32

uint32

0

0

-1

1

1

2

-2

3

2147483647

4294967294

-2147483648

4294967295

图 3 zigzag编码映射表

对于sint32类型的数据,在varint编码之前,会先进行zigzag编码,上图是其映射关系。编码后,较小的负数,可以映射为较小的正数,从而实现根据其信息量决定其序列化后占用的内存大小。

所以聪明的同学们已经知道该如何选择了,对于有符合数尽量选择sint32,而不是int32,不管从空间和时间上,都是更优的选择

3. length-delimi编码

length-delimi编码方式比较简单,是建立在varint编码基础上的,主要是针对message、bytes、repeated等类型,与TLV格式类似。先以varint编码写入tag即Key,再以varint编码写入长度,最后把内容memcpy到内存中。

inline uint8* WriteBytesToArray(int field_number,
                                                const string& value,
                                                uint8* target) {
  target = WriteTagToArray(field_number, WIRETYPE_LENGTH_DELIMITED, target);
  return io::CodedOutputStream::WriteStringWithSizeToArray(value, target);
}
uint8* WriteStringWithSizeToArray(const string& str,
                                                     uint8* target) {
  GOOGLE_DCHECK_LE(str.size(), kuint32max);
  target = WriteVarint32ToArray(str.size(), target);
  return WriteStringToArray(str, target);
}

4. fixed编码

fixed编码很简单,主要针对类型有fixed32、fixed64、double、float。由于长度固定,只需要Key + Value即可。对于浮点型会先强制转换成相对应的整形,反序列化时则反之。

inline uint32 EncodeFloat(float value) {
  union {float f; uint32 i;};
  f = value;
  return i;
}

inline uint64 EncodeDouble(double value) {
  union {double f; uint64 i;};
  f = value;
  return i;
}

inline void WireFormatLite::WriteFloatNoTag(float value,
                                            io::CodedOutputStream* output) {
  output->WriteLittleEndian32(EncodeFloat(value));
}

inline void WireFormatLite::WriteDoubleNoTag(double value,
                                             io::CodedOutputStream* output) {
  output->WriteLittleEndian64(EncodeDouble(value));
}

5. 整个编码流程

protobuf解码过程

上面已经介绍了编码原理,那么解码的流程也就很简单了。解码是一个递归的过程,先通过Varint解码过程读出Key, 取出field_number字段,如果不存在于message中,就放到UnKnownField中。如果是认识的field_number,则根据wire_type做具体的解析。对于普通类型(如整形,bytes, fixed类型等)就直接写入Field中,如果是嵌套类型(一般特指嵌套的Message),则递归调用整个解析过程。解析完一个继续解析下一个,直到buffer结束。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python技术的魅力

更好的编写Python代码的方式

这段代码本身没有任何问题,但是写的时候需要记住Tuple里每个元素都是什么,才能打印出对的描述。为了让代码更容易看懂:

3319
来自专栏racaljk

探索C++对象模型

只说C++对象模型在内存中如何分配这是不现实的,所以这里选择VS 2013作为调试环境具体探讨object在内存中分配情况.目录给出了具体要探讨的所有模型,正...

723
来自专栏淡定的专栏

正则表达式 : 检索匹配的利器

正则表达式是开发中一个不可多得的利器,本文旨在帮助大家入门正则并学会解决常见的正则问题,希望能帮到大家。

1170
来自专栏我爱编程

Day18内建模块collections&base64collectionsbase64

collections collections是Python内建的一个集合模块,提供了许多有用的集合类。 namedtuple >>> from collect...

4148
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第10章 数据聚合与分组运算10.1 GroupBy机制10.2 数据聚合10.3 apply:一般性的“拆分-应用-合并”10.4 透视表和交叉表10.5 总

对数据集进行分组并对各组应用一个函数(无论是聚合还是转换),通常是数据分析工作中的重要环节。在将数据集加载、融合、准备好之后,通常就是计算分组统计或生成透视表。...

3849
来自专栏Python小屋

Python花式编程案例集锦(9):sorted()函数中消失的cmp参数

明天开启全国巡讲Python模式,连续8场20天讲课,外加路上来回大约16天,这个假期有的忙了。所以接下来的一段时间里不一定能像以前更新的那么频繁,我尽量。

703
来自专栏和蔼的张星的图像处理专栏

627. 最长回文串

给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。 数据是大小写敏感的,也就是说,"Aa" 并不会被认为是一个回文串。 样例 ...

652
来自专栏tkokof 的技术,小趣及杂念

再谈谈列表元素的删除

之前(以及更早之前)都提到了列表元素的删除,也提到过几种方法,有兴趣的朋友可以去看看,其中一种个人比较倾向的写法大概是这个样子(C++):

551
来自专栏Python攻城狮

Python数据科学(七)- 资料清理(Ⅱ)1.资料转换2.处理时间格式资料3.重塑资料4.学习正则表达式5.实例处理

注意:这里的时间转换后的格式可以根据需要设定,eg:dt.strftime('%Y/%m/%d')

923
来自专栏WebHub

0.30000000000000004

0.30000000000000004问题是计算机科学领域的经典BUG, 由比尔盖茨那一代人标准化的浮点数表示法造福了一代人也祸害了一代人, 由...

502

扫码关注云+社区