为啥需要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 = 10000000
	for x >= 0x80 {
        // buf[i] = x的低8位 | 10000000
		buf[i] = byte(x) | 0x80
        // 移除低7位
		x >>= 7
        // 需要用到的字节数 + 1
		i++
	}

    // 最后一个字节
	buf[i] = byte(x)
	return i + 1
}

解码

传入需要解码的字节序列，返回解码后的数字，以及其占用了字节序列中前多少字节

func Uvarint(buf []byte) (uint64, int) {
	var x uint64
	var s uint
	for 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 & 01111111
		x |= uint64(b&0x7f) << s
		s += 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) << 1
	if 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编码：

1. 当数值比较大时：例如用满了int64的64位，那么在varint中会用到10位，反而比定长编码多了用了20%的空间
2. 需要随机访问时：例如一个varint数组，要随机访问下标i的值。此时就不适合用任何变长编码的数据了。因为要随机访问的前提是每个元素的长度是定长的，这样才能根据公式 i * 定长，随机访问到特定的内存空间