解析Go: varint 的使用与实现原理

 

最近发现 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])  
    }  
}

Figure 1: varint encoding

无符号整数的 varint

Golang 标准库中有两套 varint 的函数: 分别用于无符号整数的 PutUvarintUvarint,以及用于有符号整数的 VarintPutVarint
我们先看下无符号整数的 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 编码 (数学多么美妙)。

Figure 2: ZigZag encoding

在 Golang 标准库里面,调用 PutUvarint 时只会使用 varint 编码,调用 PutVarint 会先进行 zigzag 编码,再进行 varint 编码。
而在 protobuf 中,如果类型是 int32int64uint32uint64,只会使用 varint 编码。使用 sint32sint64 将先进行 zigzag 编码,再进行 varint 编码

varint 不适用的情况

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

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