文章目录
- 为啥需要varint编码
- 为啥需要zigzag编码
- varint
- 编码
- 解码
- zigzag
- 编码
- 解码
- 局限性
为啥需要varint编码
当我们用定长数字类型int32来表示整数时，为了传输一个整数1，我们需要传输00000000 00000000 00000000 00000001 32 个 bits，而有价值的数据只有 1 位。这就导致了大量的空间浪费，因为大部分字节并没有实际存储有效的信息
varint编码通过使用可变长度的字节序列来表示整数，根据数字的大小灵活占用的空间。这样使得小的整数可以用更少的字节表示，提高空间效率
下面是varint编码中，正数的大小和需要的字节数的关系
| 数字大小 | uvarint编码需要的字节数 |
|---|---|
| <=127 | 1 |
| <=16383 | 2 |
| <=2097151 | 3 |
| <=268435455 | 4 |
我们业务中大部分数据的size都 <= 16383，也就只用1或2个字节。相比于定长的int32，int64能节省不少空间
其设计原理为：
- 每7bit 为一组：将整数的二进制按照每7个bit划分到一个byte中
- 最高位表示是否还有下个字节：划分好的byte中，如果最高位为1，表示还有下个byte，否则当前byte是最后一个。最后一个字节的最高位为1，其他字节的最高位为0
例如：对于一个整数 500，它的二进制表示是 111110100。将其分为2组，即 11 和 1110100。然后在每组前面添加标志位，得到两个字节 10000011 和 01110100，这两个字节就是 500 的 varint 编码。相比于用 int32 的 4 字节表示，节省了 50% 的存储空间
为啥需要zigzag编码
但如果是负数，那么继续采用Varint编码就没有任何压缩效果，甚至占用更多字节。因为负数的符号位最高位为1，也就是一定会用满最大的字节
ZigZag编码解决了varint对负数编码效率低的问题，其原理为：
- 对于正数
n，会将其映射为2 * n。例如整数2，经过 zigzag 编码之后变成4。 - 对于负数
-n来说，会将其映射为2 * n-1。例如负数-3，经过 zigzag 编码之后变成了2 * 3 - 1 = 5
| n | zigzag编码后 |
|---|---|
| 0 | 0 |
| -1 | 1 |
| 1 | 2 |
| -2 | 3 |
| 2 | 4 |
| -3 | 5 |
| 3 | 6 |
| … | … |
例如：举个极端的例子-1，如果不用zigzag编码，直接用varint，那么会用10个字节。如果先zigzag变成1，再varint，只会用1个字节
接下来阅读golang标准库中如何对varint和zagzig进行编码和解码的
varint
编码
将x以varint的形式写入buf中，返回写了多少个字节
由于是每7位用一个字节存储，那么只要大于等于10000000，也就是需要超过7位，就需要先把低7位存到buf[i]中
for循环中：buf[i] = byte(x) | 10000000，这行是保留低7位，并且把buf[i]的第8位强制置为1
最后一个字节的最高位为0
func PutUvarint(buf []byte, x uint64) int {i := 0// Ox80 = 10000000for x >= 0x80 {// buf[i] = x的低8位 | 10000000buf[i] = byte(x) | 0x80// 移除低7位x >>= 7// 需要用到的字节数 + 1i++}// 最后一个字节buf[i] = byte(x)return i + 1
}
解码
传入需要解码的字节序列，返回解码后的数字，以及其占用了字节序列中前多少字节
func Uvarint(buf []byte) (uint64, int) {var x uint64var s uintfor i, b := range buf {if i == MaxVarintLen64 {return 0, -(i + 1) // overflow}// b < 10000000，也最高位为0，代表是就是最后一个字节if b < 0x80 {if i == MaxVarintLen64-1 && b > 1 {return 0, -(i + 1) // overflow}// x | 最高的7位，返回return x | uint64(b)<<s, i + 1}// 最高位为1，表示后面还有字节// 提取这个字节的前7位：b & 01111111x |= uint64(b&0x7f) << ss += 7}return 0, 0
}
注意：如果要解码成uint64，一共64位，按7位一组，最多10组，且第10组最大为1（第64位）
对应到源码中判断，如果超过10组或第10组大于1了，就返回溢出
zigzag
编码
我们知道在zigzag编码中：
-
如果x是正数，按照
2 * x的varint编码 -
如果x是负数，假设其值为
-n，就按照2 * n - 1的varint编码
对照源码看看：
func PutVarint(buf []byte, x int64) int {ux := uint64(x) << 1if x < 0 {ux = ^ux}return PutUvarint(buf, ux)
}
如果x是正数，等于x << 1的varint编码，没问题
如果x是负数，这里的操作是 x << 1，再按位取反
go中
x = ^x代表对x按位取反
这就有些难以理解了，为啥 ^（x << 1）等于 2 * n - 1？
我们先看看负数的二进制怎么表示
要计算-n的二进制表示，先计算n-1，再按位取反
那么反过来，给定一个负数的二进制x，怎么得到n是多少（也就是负多少）？就是把上面的操作反过来，先按位取反，再+1，也就是n = ^x + 1
我们目的是要得到 n * 2 - 1 ，把上面的式子带进去，得到 2 * (^x + 1) - 1 = 2 * ^x + 1
而对一个数先取反，再乘2，再加1，等于对这个数先乘2，再取反
2 * ^x + 1 = ^(2 * x)
举个例子，假设x = 10010：
为啥这个等式成立呢？因右边2 * x后，最低位变成0了，此时再取反的到的值，相比于先对x取反再*2得到的值来说，最低位多了个1。也就是后取反的话，比先取反多把末尾的0翻转成1了
于是得到n * 2 - 1 = ^(2 * x)，对应了源码中对负数的编码
解码
如果varint中存的是偶数，那么原始值就是正数，值为ux / 2
如果varint中存的是奇数，那么原始值就是负数，那么值是多少呢？
ux / 2得到的值是n-1，最终要得到-n
我们先看n怎么得到-n？n-1再按位取反
而现在已经有n-1了，直接按位取反即可
func Varint(buf []byte) (int64, int) {ux, n := Uvarint(buf) x := int64(ux >> 1)// 负数 x = n-1,要得到-n，按位取反即可if ux&1 != 0 {x = ^x}return x, n
}
局限性
注意不是所有场景都适合用varint编码：
- 当数值比较大时：例如用满了int64的64位，那么在varint中会用到10位，反而比定长编码多了用了20%的空间
- 需要随机访问时：例如一个varint数组，要随机访问下标
i的值。此时就不适合用任何变长编码的数据了。因为要随机访问的前提是每个元素的长度是定长的，这样才能根据公式i * 定长，随机访问到特定的内存空间