学习Protobuf，Varint是啥你真的知道么？

TheLudGamer · 发表于 2023-1-30 08:20

这篇文章，是学习Protobuf过程中偶然所得，算法简洁，篇幅较短，预计阅读时间 4 分钟，如果对您有帮助，还望不吝评价，求点赞、求评论、求转发。

Varint 是什么？

早期，为了更好计算效率，我们的计算机中数值通常使用定长整型(fixed length intergers)表示。但是，微服务、RPC 架构盛行的今天，定长整型就显得冗余。
在大多数计算机系统中，以4 Bytes和8 Bytes 来表示整数(Int32、Int64)。这样，为了传输一个整数1，我们需要传输00000000 00000000 00000000 00000001 32 个 bits，而有价值的数据只有 1 位，这也太浪费了吧？
为了节约网络带宽，我们需要一种更加灵活的方式传输方式。Varint(Variable length integers)便是一种用于压缩整型数值的方法，通过它可以更加灵活的表达整型数值需要的空间大小。
十进制：1
二进制：00000000 00000000 00000000 00000001
Varint：00000001
可以看到，通过使用Varint方法，我们将传输大小从4 Bytes压缩至1 Bytes，这怎么弄的呢？
Varint 的原理

编码规则

a.将整数的二进制按7bit分组，从低位到高位依次排列
b.最后一组MSB设置0，其他组的MSB设置为1

编码演示
按7bit进行分组，对数组逆序设置MSB(Most Significant Bit)即可，具体如图：

解码规则

a.去掉MSB重新组合7bit字符列表
b.逆序存储7bit字符列表

Varint 编码实现(Python)

def varint_compress(zz):
res = []
while zz:
      if (zz >> 7) != 0:
         res.append(0x80 | (zz & 0x7F))
         zz = zz >> 7
      else:
         res.append(zz & 0x7F)
         break
return res
获取 Varint 的长度方法

def varint_code_len(vb):
res = 0
while vb:
      vb >>= 7
      res += 1
return res
Varint 解码实现(Python)

def varint_decompress(zb):
res = 0
offset, size = 0, len(zb)
for i in range(size):
      if (zb & 0x80) == 0x80:
         res |= (zb & 0x7F) << offset
      else:
         res |= zb << offset
         break
      offset += 7
return res
总结一下

在大多数情况下，通过Varint 编码整数都有好压缩效果，但遇到负数或大整数，就不具备压缩优势了，如下：
十进制：-1
二进制：10000000 00000000 00000000 00000001
Varint：10000001 10000000 10000000 10000000 00001000

十进制：2^30
二进制：01000000 00000000 00000000 00000000
Varint：10000000 10000000 10000000 10000000 00000100
由于引入了MSB，不但没有好的压缩效果，还加大了存储，这明显不是我们想要的那怎么办呢？ZigZag由此而生，那这个算法具体思想是怎么样的呢？请听我们下回分解
参考文档

https://en.wikipedia.org/wiki/Variable-length_quantity

https://developers.google.com/protocol-buffers/docs/encoding#varints

读者每一份热爱都是笔者前进的动力！我是三十一，感谢各位朋友：求点赞、求评论、求转发，大家下期见！

		自动登录	找回密码
密码			立即注册

学习Protobuf，Varint是啥你真的知道么？

本帖子中包含更多资源