浅析 Protobuf 整形编码方式:Varint 与 Zigzag

5,659 阅读5分钟

Protocol Buffer (简称Protobuf) 是Google出品的性能优异、跨语言、跨平台的序列化库。

为了更好的硬件效率,计算机中的数字通常使用定长整形(fixed length intergers)表示。然而在遍地微服务的今天,需要一种更灵活的方式传输数字以节省带宽。Varint (Variable length integers)便是一种用于编码整形数字的方法,通过它可以灵活地调整整形数值所需要的空间大小。

Varint 编码

Protobuf 中的 Varint 根据整型大小进行不定长二进制编码,小于 128 (2^{7})的整型编码后占 1个字节,小于 16384 (2^{14})的整型编码后占 2 个,依此类推,最多可以使用 10 个字节表示大于等于 2^{63} 的整型;其实现原理见下图:

image.png

编码后的每个字节,首位标识是否为尾部,后续 7 位用于记录原始数字的二进制位,举个栗子,299 在 int32 下的二进制是

00000000 00000000 00000001 00101011

编码后的结果为 10101011 00000010,即每次传输可以节省 2 个字节。

由于 Varint 编码结果中每个字节仅有 7 个位是有效位(存储原始数据),对于小于 2^{28} 的 int32 或 int64 来说经 Varint 编码后可以起到压缩的效果。当然通常情况下小数字的使用远远大于大数字,因此 Varint 编码对于大部分场景都能起到压缩的效果。

Varint 编码实现如下:

const maxVarintBytes = 10 // maximum length of a varint

// EncodeVarint returns the varint encoding of x.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
// Not used by the package itself, but helpful to clients
// wishing to use the same encoding.
func EncodeVarint(x uint64) []byte {
	var buf [maxVarintBytes]byte
	var n int
	for n = 0; x > 127; n++ {
		// 首位记 1, 写入原始数字从低位始的 7 个 bit
		buf[n] = 0x80 | uint8(x&0x7F)
		// 移走记录过的 7 位
		x >>= 7
	}
	// 剩余不足 7 位的部分直接以 8 位形式存下来,故首位为 0
	buf[n] = uint8(x)
	n++
	return buf[0:n]
}

里边使用了 2 个魔数,看一下它们的二进制就能理解了,& 0x7f 取得 7 个 bit,| 0x80 将首位标记为 1。

0x80 => 0000000010000000
0x7f => 0000000001111111

所以 Varint 的反序列化方式便是取每个字节的后 7 位逆序拼接,如下图(以 299 的编码结果举例):

image.png

源码如下:

// DecodeVarint reads a varint-encoded integer from the slice.
// It returns the integer and the number of bytes consumed, or
// zero if there is not enough.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
func DecodeVarint(buf []byte) (x uint64, n int) {
	for shift := uint(0); shift < 64; shift += 7 {
		if n >= len(buf) {
			return 0, 0
		}
		b := uint64(buf[n])
		n++
		// 弃首位取 7 位并加回 x
		x |= (b & 0x7F) << shift
		// 首位为 0
		if (b & 0x80) == 0 {
			return x, n
		}
	}

	// The number is too large to represent in a 64-bit value.
	return 0, 0
}

这里有一个问题,EncodeVarintDecodeVarint 处理的都是 uint64 类型,如果我们需要处理负数呢?看看直接将负数作为 uint64 进行编码会得到什么:

fmt.Println(EncodeVarint(uint64(-299)))
// output:
// [213 253 255 255 255 255 255 255 255 1]

结果会得到 10 个字节的编码,因为 uint64(-299) 的值为 299 的补码,需要用 64 位表示!也就是最终会得到 varint 编码的最大长度,官方库中计算编码字节长度的源码如下:

// SizeVarint returns the varint encoding size of an integer.
func SizeVarint(x uint64) int {
	switch {
	case x < 1<<7:
		return 1
	case x < 1<<14:
		return 2
	case x < 1<<21:
		return 3
	case x < 1<<28:
		return 4
	case x < 1<<35:
		return 5
	case x < 1<<42:
		return 6
	case x < 1<<49:
		return 7
	case x < 1<<56:
		return 8
	case x < 1<<63:
		return 9
	}
	return 10
}

Zigzag

Zigzag 编码将有符号整型映射到无符号整型,如其名,编码后的值在正数与负数整型间摇摆,如下表:

Signed Original Encoded As
0 0
-1 1
1 2
-2 3
2147483647 4294967294
-2147483648 4294967295

其实现如下:

func Zigzag64(x uint64) uint64 {
	// 左移一位 XOR (-1 / 0 的 64 位补码)
	return (x << 1) ^ uint64(int64(x) >> 63)
}

这里要注意的是若 x 为负数,XOR 左边为 -x 的补码左移一位。下图以 -299 为例,先计算 299 补码,再 XOR 符号(-1 / 0)的补码,结果为 597;若为正数,Zigzag 的结果为原数的 2 倍。

image.png

小结

在写这篇文章的时候顺便复习了一波基础知识,比如 Varint 编码负数结果为什么是 10 个字节,原因就是负数是以补码的形式存储的。所以大学里看似入门的概念却是实际编程中都会遇到的东西,路漫漫其修远兮~

update: 2020.01.22 修正错误描述