protobuf序列化/反序列化原理分析

Posted on Edited on

用冗长的标签为每个字节戴上姓名牌（XML），用花括号给值配上解说员（JSON），或是教会它们用紧凑的二进制手语流畅对话（protobuf）。

序列化/反序列化

Protobuf 是由 Google 开发的一种语言无关，平台无关，可扩展的序列化结构数据的方法，可用于通信和数据存储。

提到 Protobuf 就不得不提到序列化和反序列化的概念，同样，为了构建一个轻量级但功能相对的rpc框架，序列化和反序列化工作也必不可少。

序列化和反序列化属于通信协议的一部分，它们位于 TCP/IP 四层模型中的应用层和 OSI 七层模型中的表示层。序列化的目的是将应用层的对象转换为二进制串，而反序列化则是把二进制串转化成应用层的对象。

对于Protobuf 和 JSON，XML等序列化/反序列化方法的相似点和不同点，从数据结构化和数据序列化两个维度去进行比较可能会更直观一些。数据结构化主要面向开发和业务层面，数据序列化主要面向通信和存储层面。当然数据序列化也需要结构和格式，所以这两者的区别主要在于应用领域和场景不同，因此要求和侧重点也会有所不同。

其中，数据结构化更加侧重于人类的可读性，强调语义表达能力，而数据序列化侧重效率和压缩。XML、JSON、Protobuf 都具有数据结构化和序列化的能力，但是XML、JSON 更注重数据结构化，关注人类可读性和语义表达能力，Protobuf 更注重数据序列化，关注效率，空间，速度。

因此，Protobuf 的应用场景更为明确，一般是在传输数据量较大，RPC 服务数据数据传输，XML、JSON 的应用场景更为丰富，传输数据量较小，在 MongoDB 中采用 JSON 作为查询语句，也是在发挥其数据结构化的能力。

Protobuf序列化原理

protobuf 数据存储采用 Tag-Length-Value 即标识 - 长度 - 字段值存储方式，以标识 - 长度 - 字段值表示单个字段，最终将数据拼接成一个字节流，从而实现数据存储的功能。采用 T - L - V 的存储结构时不需要分隔符就能分隔开字段，因此各字段存储地非常紧凑，存储空间利用率非常高。此外如果某字段没有被设置字段值，那么该字段在序列化时是完全不存在的，即不需要编码，这个字段在解码时才会被设置默认值。

其中，Tag 由 field_number 和wire_type两部分组成，field_number 是字段的标识号，wire_type 是一个数值，根据它的数值可以确定该字段的字段值需要采用的编码类型。

接下来分析一下各种编码类型：

  • Varint编码

    Varint 编码是一种变长的编码方式，用字节表示数字，值越小的数字，使用越少的字节数表示。它通过减少表示数字的字节数从而进行数据压缩。Varint 编码中每个字节的最高位都有特殊的含义：如果是 1，表示后续的字节也是该数字的一部分，需要继续读取；如果是 0，表示这是最后一个字节，且剩余 7 位都用来表示数字。此外需要注意的是，varint使用小端模式进行编码，因此补码的低位排在前面。

    接下来通过一个示例来说明一下 Varint 编码的过程：

    1
    int32 a = 8;
    • 原码：0000 … 0000 1000
    • 补码：0000 … 0000 1000
    • 根据 Varint 编码规则，从低位开始取 7 bit，000 1000
    • 当取出前 7 bit 后，前面所有的位就都是 0 了，不需要继续读取了，因此设置 msb 位为 0 即可
    • 所以最终 Varint 编码为 0000 1000

    可以看到在使用 Varint 编码后只使用一个字节就可以了，而正常的 int32 编码一般需要 4 个字节。

    仔细体会上述的 Varint 编码，我们可以发现 Varint 编码本质实际上是每个字节都牺牲了一个 bit 位，来表示是否已经结束(是否需要继续读取下一个字节)，msb 实际上就起到了 length 的作用，正因为有了这个 msb 位，所以我们可以摆脱原来那种无论数字大小都必须分配四个字节的窘境。

    通过 Varint 编码对于比较小的数字可以用很少的字节进行表示，从而减小了序列化后的体积。

    但是由于 Varint 编码每个字节都要拿出一位作为 msb 位，因此每个字节就少了一位来表示字段值。那这就意味着四个字节能表达的最大数字是为$2^{28}$而不是 $2^{32}$ 了。

    所以如果当数字大于 $2^{28}$时，采用 Varint 编码将导致分配 5 个字节，原先明明只需要 4 个字节。此时 Varint 编码的效率不仅没有提高反而是下降了。

    接下来再来看一下负数的情况：

    1
    int32 a = -1;
    • 原码：1000 … 0000 0001
    • 补码：1111 … 1111 1111
    • 根据 Varints 编码规则，从低位开始取 7 bit，111 1111，由于前面还有 1 需要读取，因此需要设置 msb 位为 1，然后将这个字节放在 Varint 编码的高位。
    • 依次类推，有 9 组(字节)都是 1，这 9 组的 msb 均为 1，最后一组只有 1 位是 1，由于已经是最后一组了不需要再继续读取了，因此这组的 msb 位应该是 0.
    • 因此最终的 Varint 编码是 1111 1111 … 0000 0001（FF FF FF FF FF FF FF FF FF 01 ）

    基于兼容性考虑，如将 int64 改为 int32 后不应该影响原来的旧程序，所以Protobuf将 int32 扩展为了int64 的八个字节。

  • Zigzag编码

    为了解决 Varint 编码负数效率低的问题，首先使用Zigzag编码通过移位的方式将有符号正数映射成无符号整数，然后再使用 Varint 编码。

    1
    2
    3
    4
    5
    6
    7
    8
    public int int_to_Zigzag(int n) {
      return (n <<1) ^ (n >>31);
    }
     
    // 解码
    public int Zigzag_to_int(int n) {
      return (n >>> 1) ^ -(n & 1);
    }

    根据上面的源码我们可以得出 Zigzag 的编码过程如下：

    • 将补码左移 1 位，低位补 0，得到 result1
    • 将补码右移 31 位，得到 result2
      • 首位是 1 的补码(有符号数)是算数右移，即右移后左边补 1
      • 首位是 0 的补码(无符号数)是逻辑右移，即右移后左边补 0
    • 将 result1 和 result2 异或

    这里简单分析一下每一个步骤起到的具体作用：

    • n <<1：移除符号位，并在结尾补0
    • n >>31：将符号位移动到末尾，并在前方补1
    • 因此异或后，最后一位二进制位便能反应原始符号位，1为负数0为正数
    • 对于解码过程也是类似，首先n >>> 1空出符号位，n & 1将最后一位符号位取出，在取负数将其变为1111···1111或者0000···0000；由于在编码的过程中，除了符号位的部分已经与1111···1111进行了异或，因此这里再与1111···1111进行异或，便可以将除了符号位的部分还原，同时首位与1/0异或也可以还原原始的符号位

    因此在定义字段时如果知道该字段的值有可能是负数的话，那么建议使用 sint32/sint64 这两种数据类型。

  • length-delimited

    采用T - L - V 的存储方式。其中，Tag 和 Length 仍然采用 Varint 编码，对于字段值根据不同的数据类型采用不同的编码方式。

    对于嵌套消息类型，嵌套消息的编码是递归进行的，其层消息完全遵循外层消息的编码规则。例如对于如下的嵌套消息类型：

    1
    2
    3
    message Test2 {
        Test1 c = 3;
    }

    那么先将字段c正常序列化成二进制数据，然后再将这个嵌套类型当做byte进行处理。这里需要注意的是，虽然嵌套类型编码方式与bytes相同，但实际上两者语义存在差别：嵌套消息会被反序列化为结构化数据，而 bytes 是原始二进制。

    对于重复字段，protobuf有两种策略来序列化重复字段，一种是普通编码，另一种是紧密编码（packed）。

    普通编码使用上没有任何限制，不管是什么类型都可以使用。而紧密编码只能用在原始类型（promitive type）的字段上。

    原始类型在protobuf里的定义就是除了string和bytes以外的所有标量类型（scalar value types），包括这些：double、float、int32、int64、uint32、uint64、sint32、sint64、fixed32、fixed64、sfixed32、sfixed64、bool。

    可以看到这些类型都有一些共同点，那就是数据的大小都很小，不会很大，且大多都使用varint编码。

    首先来说普通编码，因为每个字段都有自己的序号，按序号序列化成一个个records，那么处理重复字段的方法就很简单了，比如有这么一个消息类Test：

    1
    2
    3
    message Test {
      repeated string a = 1;
    }

    a是一个重复字段，我们给a赋值为["test", "str1"]，那么序列化后会变成：

    1
    08 04 [74 65 73 74] | 08 04 [73 74 72 31]

    可以看到字段a被序列化了2次，生成了2个records。这样当反序列化程序读取到了两个相同序号的字段时，就会把它们当做一个列表收集起来了，也就实现了重复字段的传输。

    而对于原始类型来说，protobuf为了保证效率，会使用紧密编码来存储它们。

    需要说明的是，在protobuf2里，要在字段后面手动标明[packed=true]才会开启紧密编码。但是在protobuf3中，所有原始类型默认就已经开启了紧密排列。

    普通编码时，每多出一个元素就会多序列化一个record，而record里面是包含tag部分的，虽然tag大部分情况下只有一个字节长，但是对应原始类型来说，原始类型本身大部分情况下也只有一个字节长，现在又加上了tag，长度从1个字节变成了2个字节的长度，多少有些不太划算了。

    紧密编码正好就是用来解决这个问题的，它直接把所有元素打包到一起，所有元素共用一个tag，这样存储空间的利用率也就起来了。

    对于Map类型，Map类型的处理非常简单，以下两种代码在序列化后是等价的：

    1
    2
    3
    message Test {
        map<string, int32> g = 7;
    }
    1
    2
    3
    4
    5
    6
    7
    message Test {
         message g_Entry {
             optional string key = 1;
             optional int32 value = 2;
         }
         repeated g_Entry g = 7;
     }

序列化过程

Protobuf 的性能非常优越主要体现在两点，其中一点就是序列化后的体积非常小，这一点在前面编解码的介绍中已经体现出来了。还有另外一点就是序列化速度非常快，接下来就简单地介绍一下为什么序列化的速度非常快。

Protobuf 序列化的过程简单来说主要有下面两步

  • 判断每个字段是否有设置值，有值才进行编码，
  • 根据 tag 中的 wire_type 确定该字段采用什么类型的编码方案进行编码即可。

Protobuf 反序列化过程简单来说也主要有下面两步：

  • 调用消息类的 parseFrom(input) 解析从输入流读入的二进制字节数据流
  • 将解析出来的数据按照指定的格式读取到相应语言的结构类型中

Protobuf 的序列化过程中由于编码方式简单，只需要简单的数学运算位移即可，而且采用的是 Protobuf 框架代码和编译器共同完成，因此序列化的速度非常快。

可能这样并不能很直观地展现出 Protobuf 序列化过程非常快，接下来我们简单介绍一下 XML 的反序列化过程，通过对比我们就能清晰地认识到 Protobuf 序列化的速度是非常快的。

XML 反序列化的过程大致如下：

  • 从文件中读取出字符串
  • 从字符串转换为 XML 文档对象模型
  • 从 XML 文档对象结构模型中读取指定节点的字符串
  • 将该字符串转换成指定类型的变量

从上述过程中，我们可以看到 XML 反序列化的过程比较繁琐，而且在第二步，将 XML 文件转换为文档对象模型的过程是需要词法分析的，这个过程是比较耗费时间的，因此通过对比我们就可以感受到 Protobuf 的序列化的速度是非常快的。
end☆~