526互联

Protobuf原理

发布时间 2023-12-11 19:14:43作者: 王鹏鑫

三个东西

1.原码

我们用第一个位表示符号（ 0 为非负数，1 为负数），剩下的位表示值。例如：

  • +8 → 原：00001000

  • -8 → 原: 10001000

2.反码

我们用第一位表示符号（ 0 为非负数，1 为负数），剩下的位，非负数保持不变，负数按位求反。例如：

  • +8 → 原：0000 1000 → 反：0000 1000

  • -8 → 原：1000 1000 → 反：1111 0111

3.补码

我们用第一位表示符号（ 0 为非负数，1 为负数），剩下的位非负数保持不变，负数按位求反末位加一。

  • +8 → 原：0000 1000 → 补：0000 1000

  • -8 → 原：1000 1000 → 补：1111 1000

ZigZag

为了传输一个整型 1，我们需要传输 “00000000 00000000 00000000 00000001” 32 个 bits，而有价值的数据只有 1 位，剩下的都是浪费

对于正整数来讲，如果在传输数据时，我们把多余的 0 去掉，或者尽可能的减少无意义的 0。那么我们是不是就可以将数据进行压缩？那怎样进行压缩？

答案也很简单，例如 00000000 00000000 00000000 00000001 这个数。如果我们只发送 1 位 或者 1 字节 00000001，是不是就会很大程度减少无用的数据？

当然，如果这个世界上只有正整数，那我们就可以方便的做到这一点。可惜，他居然存在负数！那负数如何表示？

例如，十进制 -1 的补码表示为 11111111 11111111 11111111 11111111。

可以看到，前面全是 1，你说怎么弄？

ZigZag 给出了一个很巧妙的方法。我们之前讲补码说过，补码的第一位是符号位，他阻碍了我们对于前导 0 的压缩，那么，我们就把这个符号位放到补码的最后，其他位整体前移一位。

补：11111111 11111111 11111111 11111111

→ 符号后移：11111111 11111111 11111111 1111111

但是即使这样，也是很难压缩的。于是，这个算法就把负数的所有数据位按位求反，符号位保持不变，得到了这样的整数，如下：

十进制：-1

→ 补：11111111 11111111 11111111 11111111

→ 符号后移：11111111 11111111 11111111 11111111

→ ZigZag：00000000 00000000 00000000 00000001

而对于非负整数，同样的将符号位移动到最后，其他位往前挪一位，数据保持不变，如下：

十进制：1

→ 补：00000000 00000000 00000000 00000001

→ 符号后移：00000000 00000000 00000000 00000010

→ ZigZag：00000000 00000000 00000000 00000010

这样一弄，正数、0、负数都有同样的表示方法了。我们就可以对小整数进行压缩了，对吧~

于是，就可以写成如下的代码：

func int32ToZigZag(n int32) int32 {
    return (n << 1) ^ (n >> 31)
}

ZigZag 还原代码如下：

func toInt32(zz int32) int32 {
    return int32(uint32(zz)>>1) ^ -(zz & 1)
}

类似的，我们还原的代码就反过来写就可以了。不过这里要注意一点，就是右移的时候，需要用不带符号的移动，否则如果第一位是 1 的时，移动时会补1。所以，使用了无符号的移位操作uint32(zz)>>1。

好了，有了该算法，就可以得到一个有前导 0 的整数。只是，该数据依然使用 4 字节存储。下来我们要考虑如何尽可能的减少字节数，并且还能还原。

例如，我们将 1 按照如上算法转化得到：00000000 00000000 00000000 00000010。

下来我们最好只需要发送 2 bits（10），或者发送 8 bits（00000010），把前面的 0 全部省掉。因为数据传输是以字节为单位，所以，我们最好保持 8 bits这样的单位。所以我们有 2 种做法：

  • 我们可以额外增加一个字节，用来表示接下来有效的字节长度，比如：00000001 00000010，前 8 位表示接下来有 1 个字节需要传输，第二个 8 位表示真正的数据。这种方式虽然能达到我们想要的效果，但是莫名的增加一个字节的额外浪费。有没有不浪费的办法呢？

  • 字节自表示方法。ZigZag 引入了一个方法，就是用字节自己表示自己。具体怎么做呢？我们来看看代码。

// zz是zigzag后的结果
func compress(zz int32) []byte {
    var res []byte
    size := binary.Size(zz)
    for i := 0; i < size; i++ {
        if (zz & ^0x7F) != 0 {
            res = append(res, byte(0x80|(zz&0x7F)))
            zz = int32(uint32(zz) >> 7)
        } else {
            res = append(res, byte(zz&0x7F))
            break
        }
    }
    return res
}

  • 举个例来讲：

    十进制：-1000

    → 补：11111111 11111111 11111100 00011000

    → ZigZag：00000000 00000000 00000111 1100111

    我们先按照七位一组的方式将上面的数字划开，0000 0000000 0000000 0001111 1001111。

    详细步骤如下：

    1. 他跟 ^0x7F 做与操作的结果，高位还有信息，所以，我们把低 7 位取出来，并在倒数第八位上补一个 1（0x80）：11001111。

    2. 将这个数右移七位，0000 0000000 0000000 0000000 0001111。

    3. 再取出最后的七位，跟 ^0x7F 做与操作，发现高位已经没有信息了（全是0），那么我们就将最后 8 位完整的取出来：00001111，并且跳出循环，终止算法。

    4. 最终，我们就得到了两个字节的数据 [11001111, 00001111]。

    通过上面几步，我们就将一个 4 字节的 ZigZag 变换后的数字变成了一个 2 字节的数据。如果我们是网络传输的话，就直接发送这 2 个字节给对方进程。对方进程收到数据后，就可以进行数据的组装还原了。具体的还原操作如下：

func decompress(zzByte []byte) int32 {
   var res int32
   for i, offset := 0, 0; i < len(zzByte); i, offset = i+1, offset+7 {
      b := zzByte[i]
      if (b & 0x80) == 0x80 {
         res |= int32(b&0x7F) << offset
      } else {
         res |= int32(b) << offset
         break
      }
   }
   return res
}

　　

Protobuf

Protobuf 在序列化数据时，将 Protobuf 数据类型总共划分为 6 大类，英文称为 “wire type”。

 
wire type proto 类型 含义
0 int32, int64, uint32, uint64, sint32, sint64, bool, enum Varint
1 fixed64, sfixed64, double 64-bit
2 string, bytes, embedded messages, packed repeated fields Length-delimited
3 groups (废弃) Start group
4 groups (废弃) End group
5 fixed32, sfixed32, float 32-bit

下来通过一个 message 信息展开说明，如下：

message HelloRequest {
  string name = 1;
  int32 num = 2;
  float height = 3;
  repeated int32 hobbies= 4;
}

1. 类型和顺序

那传输的数据中如何保存 “数据类型” 和 ”顺序“？

数据类型对应到 “wire type”，顺序对应到 “field number”。假如 int32 num = 2 对应如下：

•wire type：0，通过上面表格对应。

•field number：2，字段后的唯一编码。

将这两个信息按照如下公式组装：

(field_number << 3) | wire_type

带入得：

(2 << 3) | 0
→ 16

2. Varint

对于 num 字段保存的数据如何如何压缩？假如 num 存储的数据为 300。按照 4 字节存储如下：

00000000 00000000 00000001 00101100

从结果可以看到，真实有效的数据只有 2 字节，为了压缩，面对不同的数据大小会占用不用的字节数。

那如何记录数据长度？我们可以再增加一个字节去记录真实数据所占用的实际字节数。对于 300 数据，增加一个字节记录长度，那下来和数据一块总共需要 3 个字节。那还有什么办法再减少字节数吗？

当然会有呀，不然我就说了一堆废话，咱继续。

请出 Varint 算法，过程如下：

•将数据以 7 位为一组进行分割；

•将组的顺序颠倒，即：将 “高位 → 低位” 规则，改为 “低位 → 高位”；

•识别每一组，如果该组后还有数据，就在该组前增加一位 “1”，否则增加 “0”。

将数据 300 带入该算法，过程如下：

300: 00000000 00000000 00000001 00101100
→ 7 位分割：0000 0000000 0000000 0000010 0101100
→ 颠倒顺序：0101100 0000010 0000000 0000
→ 组前加 1/0：10101100 00000010
→ 十进制：172 2

按照这套算法下来，将数据压缩为 2 个字节存储。而接收方拿到字节数据后，只需要按照高位识别，如果为 0，说明之后没有数据了。

最终，对于 int32 num = 2 结构和数据 300，压缩后的结果为：

16 172 2

3. Length-delimited

现在说说 string name = 1 ，该类型对应的 “wire type” 为 2，“field number” 为 2。记录 “顺序” 和 “类型” 方式和上面讲的一样。

重点说说数据如何记录，相比 Varint 算法，该类型就简单多了，只需要使用 Varint 算法记录数据的字节长度。

假如，name 的值为 “miao”，最终结果为：

10 4 109 105 97 111

解释：

•10：(2 << 3) | 2 。

•4：字符串长度。

•之后：按照 “UTF-8” 编码保存。

对于 message 嵌套、repeated (数组或切片)、字节数组，也是按照该算法得到。

例如，repeated int32 hobbies= 4 ，假设 hobbies 数据为 [10, 20]，最终结果为：

34 2 10 20

4. 浮点数

针对浮点类型，就更简单了，浮点数据使用固定字节保存，记录 “顺序” 和 “类型” 依然是上面讲的。

假如，float height = 3 ，该类型对应的 "wire type" 为 5，数据假设为 52.1，最终结果为：

29 102 102 80 66

解释：

•29：(3 << 3) | 5 。

•之后：使用固定字节数 4。

如果使用了双精度，那对应的 “wire type” 为 1，数据占用字节数为 8。

5. sint32/sint64

这两个类型不知道你在写 proto 文件时有没有用到，明白这个很重要，不然有时候数据就不能起被到压缩的作用。

上面讲到的 Varint 算法中，我们知道了以 7 位一组，再增加一位 “识别位” 来起到压缩数据的作用。但存在一个问题，倘若存在负数时，那这种压缩方式就失效了。

至于为啥？如何解决的？

如果写 proto 文件时，设置的数据类型为 sint32 或 sint64 时，将采用 ZigZag 算法进行数据压缩。