最近发现 Golang 标准库竟然自带了 varint 的实现，代码位置在 encoding/binary/varint.go，这个跟protobuf里面的varint实现基本是一致的。刚好借助 golang 标准库的 varint 源码，我们来系统地学习和梳理下 varint。
熟悉 protobuf 的人肯定对 varint 不陌生，protobuf 里面除了带 fix (如 fixed32、fixed64) 之外的整数类型, 都是 varint 编码。
varint 的出现主要是为了解决两个问题：

1. 空间效率：以 uint64 类型为例，可以表示的最大值为 18446744073709551615。然而在实际业务场景中，我们通常处理的整数值远小于 uint64 的最大值。假设在我们的业务中，需要处理的整数值仅为 1，但在网络传输过程中，我们却需要使用 8 个字节来表示这个值。这就导致了大量的空间浪费，因为大部分字节并没有实际存储有效的信息。varint 编码通过使用可变长度的字节序列来表示整数，使得小的整数可以用更少的字节表示，提高空间效率。
2. 兼容性：varint 使得我们可以在不改变编码 / 解码逻辑的情况下，处理不同大小的整数。这意味着我们可以在不破坏向后兼容性的情况下，将一个字段从较小的整数类型（如 uint32）升级到较大的整数类型（如 uint64）

本文将通过分析 Golang 标准库自带的 varint 源码实现，介绍 varint 的设计原理以及Golang标准库是如何解决 varint 在编码负数时遇到的问题。

This article was first published in the Medium MPP plan. If you are a Medium user, please follow me on Medium. Thank you very much.

varint 的设计原理

varint 的设计原理非常简单：

• 7bit 为一组：将整数的二进制表示分为 7 个 bit 位一组。从低位到高位，每 7 个 bit 位作为一个单元。
• 最高位表示 “继续” 标志。在每个 7 位的单元前面添加一个标志位，形成一个 8 位的字节。如果后面还有更多的字节，这个标志位就设置为 1，否则设置为 0。
  例如：对于一个整数 uint64(300)，它的二进制表示是 100101100。我们可以将它分为两组，即 10 和 0101100。然后在每组前面添加标志位，得到两个字节 00000010 和 10101100，这两个字节就是 300 的 varint 编码。相比于用 uint64 的 4 字节表示，少了 75% 的存储空间。

1
2
3
4
5
6
7
8
9

func main() {  
    v := uint64(300)  
    bytes := make([]byte, 0)  
    bytes = binary.AppendUvarint(bytes, v)  
    fmt.Println(len(bytes))  
    for i := len(bytes); i > 0; i-- {  
       fmt.Printf("%08b ", bytes[i-1])  
    }  
}

无符号整数的 varint

在 Golang 标准库中有两套 varint 的函数: 分别用于无符号整数的 PutUvarint和 Uvarint，以及用于有符号整数的 Varint 和 PutVarint
我们先看下无符号整数的 varint 实现，代码如下：
list1: go src PutUvarint

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func PutUvarint(buf []byte, x uint64) int {
	i := 0
	for x >= 0x80 {
		buf[i] = byte(x) | 0x80
		x >>= 7
		i++
	}
	buf[i] = byte(x)
	return i + 1
}

代码里有个非常重要的常量：0x80，对应于二进制编码就是 1000 0000。这个常量对接下来的逻辑非常重要：

1. x >= 0x80。这意味着 x 的二进制表示形式至少有 8 位，我们刚才讲到 7 个 bit 位为一组，那 x 就需要被拆分了。
2. byte(x) | 0x80。将 x 的最低 8 位与 1000 0000 进行按位或操作，然后将结果存储在 buf[i] 中。这样 既可以将最高位设置为 1，同时也提取出了 x 的最低 7 位。
3. x >>= 7. 将 x 右移 7 位，处理下一个分组。
4. buf[i] = byte(x)。当 for 循环结束时，即意味着 x 的二进制表示形式最高位必然是 0。此时就不用做额外的补零操作了。

Uvarint 是 PutUvarint 的逆过程。

需要注意的是，varint 将整数划分为 7 位一组。这意味着，对于大整数 varint 将会出现负向优化。例如对于 uint64 的最大值来说，本来只需要 8 个 byte 来表示，但在 varint 中却需要 10 个字节来表示了。（64/7 ≈ 10）

负数的编码：zigzag 编码

看似 varint 编码已经完美无缺了，但以上忽略了一点：负数的存在。

我们知道，在计算机中数字是用补码来表示的，而负数的补码则是将其绝对值按位取反再加 1。这就意味着一个很小的负数，它的二进制形式对应于一个非常大的整数。
例如：对于一个 32 位的整数 -5 来说，其绝对值 5 的二进制形式是 101。 但 -5 的二进制形式却是 11111111111111111111111111111011，如果使用 varint 对其编码, 需要 5 个字节才能表示。

Golang标准库引入了 zigzag 编码来解决这个问题，zigzag 的原理非常简单：

• 对于正数 n，会将其映射为 2n。例如整数 2，经过 zigzag 编码之后变成了 4。
• 对于负数 -n 来说，会将其映射为 2n-1。例如负数 -3，经过 zigzag 编码之后变成了 5。

这样负数和正数在数值上完全不会冲突，正整数和负整数交错排列，这也是为什么叫做 zigzag 编码 (锯齿形编码）的原因。
同时，负数被转换成正数之后，二进制编码也精简了许多。
例如： 对 int32(-5) 进行 zigzag 编码后，变成了 9，对应于二进制为 00000000000000000000000000001001，使用 1 个字节即可表示 varint。
我们看下 Golang 标准库的实现，代码如下：

1
2
3
4
5
6
7

func PutVarint(buf []byte, x int64) int {
	ux := uint64(x) << 1
	if x < 0 {
		ux = ^ux
	}
	return PutUvarint(buf, ux)
}

从代码可以看出，对于有符号整数的varint实现，golang标准库这里分成了两步：

1. 先对整数进行 zigzag 编码进行转换
2. 对转换之后的数值再进行 varint 编码
   对于负数，多了一步 ux = ^ux ，这就有些难以理解了，为什么这么转换之后就等于2n - 1了？

我们可以大概推导下整个过程，假设我们有个整数 -n：

1. 对原数值先左移，再进行取反。其实可以看做：对原数值先取反，再左移，然后+1。 即 2*(~(-n))+1
2. 我们知道负数的补码=绝对值按位取反+1，那如何根据补码再推导出绝对值？这里有个公式是：|A| = ~A+1
3. 我们将这个公式带到第一步的式子里面： 2*(n-1) + 1 = 2n - 1。这就完美对应上了负数的 ZigZag 编码 (数学多么美妙)。

在 Golang 标准库里面，调用 PutUvarint 时只会使用 varint 编码，调用 PutVarint 会先进行 zigzag 编码，再进行 varint 编码。
而在 protobuf 中，如果类型是 int32、int64、uint32、uint64，只会使用 varint 编码。使用 sint32、sint64 将先进行 zigzag 编码，再进行 varint 编码

varint 不适用的情况

虽然 varint 编码设计非常精妙，但并不适用于所有的场景：

• 大整数：对于非常大的整数，varint 编码可能会比固定长度的编码更消耗空间。例如当所有的整数值域大于 2^63，那使用 varint 会用到 10 字节。相比于传统的八字节整数，反而多用了 25% 的空间
• 需要快速随机访问的数据：由于 varint 是变长编码，所以我们无法直接通过索引来访问特定的整数，必须从头开始解码，直到找到我们需要的整数。这使得 varint 编码不适合用于需要快速随机访问的数据。
• 需要频繁进行数学运算的数据：由于 varint 编码的数据需要先解码才能进行数学运算，所以如果一个应用需要频繁地对数据进行数学运算，那么使用 varint 编码可能会导致性能下降。
• 安全敏感的应用：varint 编码的数据可能会暴露出一些关于原始整数的信息，例如它的大小。在某些安全敏感的应用中，这可能是不可接受的。