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_TypeType | 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结束。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。