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

TheLudGamer

这篇文章，是学习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
  

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