学习Protobuf，Varint是啥你真的知道么？
这篇文章，是学习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
读者每一份热爱都是笔者前进的动力！ 我是三十一，感谢各位朋友：求点赞、求评论、求转发，大家下期见！
页:
[1]