【protobuf源码探秘】编码、序列化

为什么要写这篇？

早就想写了，不过前面有redis源码学习的系列在，就一直拖着。
在我学protobuf的时候，在网上看到一个博客，说的挺好，但是偏偏插了这么一句：fixed 和 int 相比，fixed重时间、int重空间。所以如果对空间性能有要求的话就使用int… 吧啦吧啦的。

然后我还就真信了。然后还就把我毕设项目协议里的int32全换成fixed32了，给我一顿操作猛如虎啊。

后来，由于前面学的不全面，我又去了protobuf的官网查看官方文档，就想着看看那个人说的是不是对的。好家伙，翻来翻去，人家只是说，如果大数出现频繁的业务，考虑使用fixed，并没有说什么哪个快哪个慢。。。

然后我整个人就懵了，要知道我的毕设里可几乎都是小数啊（8位数以下），那到底他说的是对的还是错的啊？？？

想来想去，还是看源码里怎么写的吧。

---

编码

编码结构

这里的 [Length] 是可选的，含义是针对不同类型的数据编码结构可能会变成 Tag - Value 的形式，如果变成这样的形式，没有了 Length 我们该如何确定 Value 的边界？

注意其中的 Start group 和 End group 两种类型已被遗弃。

这样：

对 sint32、sint64 又会有一些特别编码（ZigTag 编码）处理，相当于 Varint 这个编码类型里又存在两种不同编码。

现在来模拟一下，我们接收到了一串序列化的二进制数据，我们先读一个 Varints 编码块，进行 Varints 解码，读取最后 3 bit 得到 wire_type（由此可知是后面的 Value 采用的哪种编码），随后获取到 field_number （由此可知是哪一个字段）。依据 wire_type 来正确读取后面的 Value。接着继续读取下一个字段 field…

---

Varints 编码

1、在每个字节开头的 bit 设置了 msb(most significant bit )，标识是否需要继续读取下一个字节
2、存储数字对应的二进制补码
3、补码的低位排在前面

看个例子：

int32 val =  1;  // 设置一个 int32 的字段的值 val = 1; 这时编码的结果如下
原码：0000 ... 0000 0001  // 1 的原码表示
补码：0000 ... 0000 0001  // 1 的补码表示
Varints 编码：0#000 0001（0x01）  // 1 的 Varints 编码，其中第一个字节的 msb = 0

编码过程：
数字 1 对应补码 0000 … 0000 0001（规则 2），从末端开始取每 7 位一组并且反转排序（规则 3），因为 0000 … 0000 0001 除了第一个取出的 7 位组（即原数列的后 7 位），剩下的均为 0。所以只需取第一个 7 位组，无需再取下一个 7 bit，那么第一个 7 位组的 msb = 0。最终得到：

0 | 000 0001（0x01） 

解码过程：
数字 1 的 Varints 编码中 msb = 0，所以只需要读完第一个字节无需再读。去掉 msb 之后，剩下的 000 0001 就是补码的逆序，但是这里只有一个字节，所以无需反转，直接解释补码 000 0001，还原即为数字 1。

---

这里编码数字 1，Varints 只使用了 1 个字节。而正常情况下 int32 将使用 4 个字节存储数字 1。

msb 实际上就起到了 Length 的作用，正因为有了 msb（Length），所以我们可以摆脱原来那种无论数字大小都必须分配四个字节的窘境。通过 Varints 我们可以让小的数字用更少的字节表示。从而提高了空间利用和效率。

---

负数的 Varints 编码情况

不多说，直接上例子：

int32 val = -1
原码：1000 ... 0001  // 注意这里是 8 个字节
补码：1111 ... 1111  // 注意这里是 8 个字节

再次复习 Varints 编码：对补码取 7 bit 一组，低位放在前面。
上述补码 8 个字节共 64 bit，可分 9 组（负数的补码和正数不一样）且这 9 组均为 1，这 9 组的 msb 均为 1，最后剩下一个 bit 的 1，用 0 补齐作为最后一组放在最后，最后得到 Varints 编码：

1#1111111 ... 0#000 0001 （FF FF FF FF FF FF FF FF FF 01）

注意，因为负数必须在最高位（符号位）置 1，这一点意味着无论如何，负数都必须占用所有字节，所以它的补码总是占满 8 个字节。你没法像正数那样去掉多余的高位（都是 0）。再加上 msb，最终 Varints 编码的结果将固定在 10 个字节。

这也就是说为什么在 protoc 里直接用 int 存储负数不好。

---

ZigZag 编码

存储负数推荐 sint 族，在使用 sint 的时候，默认采用 ZigZag 编码。

一张图其实就明白了：

这里的“映射”是以移位实现的。

---

bool

当 boolVal = false 时，其编码结果为空。
这里是 ProtoBuf 为了提高效率做的又一个小技巧：规定一个默认值机制，当读出来的字段为空的时候就设置字段的值为默认值。而 bool 类型的默认值为 false。也就是说将 false 编码然后传递（消耗一个字节），不如直接不输出任何编码结果（空），终端解析时发现该字段为空，它会按照规定设置其值为默认值（也就是 false）。如此，可进一步节省空间提高效率。

---

fixed族

Varints 编码在一定范围内是有高效的，超过某一个数字占用字节反而更多，效率更低。如果现在有场景是存在大量的大数字，那么使用 Varints 就不太合适了。具体的，如果数值比 2^56 大的话，fixed64 这个类型比 uint64 高效，如果数值比 2^28 大的话，fixed32 这个类型比 uint32 高效。

example.set_fixed64val(1)
example.set_sfixed64val(-1)
example.set_doubleval(1.2)

// 编码结果，总是 8 个字节
09 # 01 00 00 00 00 00 00 00
11 # FF FF FF FF FF FF FF FF （没有 ZigZag 编码）
19 # 33 33 33 33 33 33 F3 3F

fixed32、sfixed32、float 与 64-bit 同理

---

不定长数据类型

string、bytes、EmbeddedMessage、repeated。Length-delimited 类型的编码结构为 Tag - Length - Value：

syntax = "proto3";

// message 定义
message Example1 {
    string stringVal = 1;
    bytes bytesVal = 2;
}



Example1 example1;
example1.set_stringval("hello,world");
example1.set_bytesval("are you ok?");




0A 0B 68 65 6C 6C 6F 2C 77 6F 72 6C 64 
12 0B 61 72 65 20 79 6F 75 20 6F 6B 3F 

---

repeat

原先的 repeated 字段的编码结构为 Tag-Length-Value-Tag-Length-Value-Tag-Length-Value…，因为这些 Tag 都是相同的（同一字段），因此可以将这些字段的 Value 打包，即将编码结构变为 Tag-Length-Value-Value-Value…

syntax = "proto3";

// message 定义
message Example1 {
    repeated int32 repeatedInt32Val = 4;
    repeated string repeatedStringVal = 5;
}

example1.add_repeatedint32val(2);
example1.add_repeatedint32val(3);
example1.add_repeatedstringval("repeated1");
example1.add_repeatedstringval("repeated2");

22 02 02 03
2A 09 72 65 70 65 61 74 65 64 31 2A 09 72 65 70 65 61 74 65 64 32

repeatedInt32Val 字段的编码结果为：

22 | 02 02 03

22 即 00100010 -> wire_type = 2(Length-delimited), field_number = 4(repeatedInt32Val 字段)，02 字节长度为 2，则读取两个字节，之后按照 Varints 解码出数字 2 和 3。

---

repeated string 不进行默认 packed

1. 因为int32采用的是varints编码，省去了TLV中的 L，实际上是TV格式的，所以 repeated int32 是 TLVVV 格式的
2. string采用的是 TLV 编码，故 repeated string 采用的是TLVLVLV格式

---

嵌套字段

上文没有提及嵌套字段，因为：

依据元信息(即 .proto 文件，使用 protoc 编译时，.proto 文件会被编译成字符串保存在代码 xxx.pb.cc 中）可以区分该字段是否是嵌套字段。简单来说，你是无法直接从 pb 二进制数据直接解码出信息的，一定是需要有 .proto 文件的配合。只是在代码层面， .proto 文件早就在 protoc 的时候就已经以某种形式存在于 protobuf 生成的客户端代码中，代码可以随时拿到 .proto 文件中表达的元信息，例如一个字段是否为嵌套字段。

---

序列化与反序列化

文章标题写的是源码探秘是吧。是得放点代码出来。

SerializeToString

当某个 Message 调用 SerializeToString 时，经过一层层调用最终会调用底层的关键编码函数 WriteVarint32ToArray 或 WriteVarint64ToArray，整个过程如下图所示：

inline uint8* CodedOutputStream::WriteVarint32ToArray(uint32 value, uint8* target) {
  // 0x80 -> 1000 0000
  // 大于 1000 0000 意味这进行 Varints 编码时至少需要两个字节
  // 如果 value < 0x80，则只需要一个字节，编码结果和原值一样，则没有循环直接返回
  // 如果至少需要两个字节
  while (value >= 0x80) {
    // 如果还有后续字节，则 value | 0x80 将 value 的最后字节的最高 bit 位设置为 1，并取后七位
    *target = static_cast<uint8>(value | 0x80);
    // 处理完七位，后移，继续处理下一个七位
    value >>= 7;
    // 指针加一，（数组后移一位）   
    ++target;
  }
  // 跳出循环，则表示已无后续字节，但还有最后一个字节

  // 把最后一个字节放入数组
  *target = static_cast<uint8>(value);
  // 结束地址指向数组最后一个元素的末尾
  return target + 1;
}

// Varint64 同理
inline uint8* CodedOutputStream::WriteVarint64ToArray(uint64 value,
                                                      uint8* target) {
  while (value >= 0x80) {
    *target = static_cast<uint8>(value | 0x80);
    value >>= 7;
    ++target;
  }
  *target = static_cast<uint8>(value);
  return target + 1;
}

---

关于 fixed 族的编码

inline uint8* WireFormatLite::WriteFixed32ToArray(int field_number,
                                                  uint32 value, uint8* target) {
  // WriteTagToArray: Tag 依然是 Varint 编码，与上一节 Varint 类型是一致的
  // WriteFixed32NoTagToArray：固定写四个字节即可
  target = WriteTagToArray(field_number, WIRETYPE_FIXED32, target);
  return WriteFixed32NoTagToArray(value, target);
}

inline uint8* WireFormatLite::WriteSFixed32NoTagToArray(int32 value,
                                                        uint8* target) {
  return io::CodedOutputStream::WriteLittleEndian32ToArray(
      static_cast<uint32>(value), target);
}

inline uint8* CodedOutputStream::WriteLittleEndian32ToArray(uint32 value,
                                                            uint8* target) {
#if defined(PROTOBUF_LITTLE_ENDIAN)
  memcpy(target, &value, sizeof(value));
#else
  target[0] = static_cast<uint8>(value);
  target[1] = static_cast<uint8>(value >>  8);
  target[2] = static_cast<uint8>(value >> 16);
  target[3] = static_cast<uint8>(value >> 24);
#endif
  return target + sizeof(value);
}

这个会快？不要看上面一个while就以为人家慢了。

---

Length delimited 字段序列化

因为其编码结构为 Tag - Length - Value，所以其字段完整的序列化会稍微多出一些过程：

其序列化实现的几个关键函数为：

ByteSizeLong：计算对象序列化所需要的空间大小，在内存中开辟相应大小的空间
WriteTagToArray：将 Tag 值写入到之前开辟的内存中
WriteStringWithSizeToArray：将 Length + Value 值写入到之前开辟的内存中

---