【博客477】prometheus-----数值数据编码(varint与zigzag)

prometheus-----数据编码(varint与zigzag)

prometheus对数值数据进行编码时，使用到了varint与zigzag

varint与zigzag编码方法在protobuf中也被使用

prometheus encoding代码：

https://github.com/prometheus/prometheus/blob/main/tsdb/encoding/encoding.go

...
...
func (d *Decbuf) Varint64() int64 {
	if d.E != nil {
		return 0
	}
	// Decode as unsigned first, since that's what the varint library implements.
	ux, n := varint.Uvarint(d.B)
	if n < 1 {
		d.E = ErrInvalidSize
		return 0
	}
	// Now decode "ZigZag encoding" https://developers.google.com/protocol-buffers/docs/encoding#signed_integers.
	x := int64(ux >> 1)
	if ux&1 != 0 {
		x = ^x
	}
	d.B = d.B[n:]
	return x
}
...
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

varint编码

前言

传统的integer是以32位来表示的，存储在计算机中不管多大的数字都需要4个字节，而一个字节能表示256以内的数字，两个字节能表示65536以内的数字，在固定范围内只用一个或者两个字节表示岂不节省很大的空间。铛铛铛，varint就是根据这种思想来序列化整数的。从统计的角度来说，一般不会所有的消息中的数字都是大数，因此大多数情况下，采用 varint 后，可以用更少的字节数来表示数字信息,从而实现数据的压缩。

简介

简单来说varint是一种数据压缩算法，其核心思想是利用bit位来实现数据的压缩。使用一个或多个字节序列化整数的方法。较小的数字占用较少的字节数。

优点：

Varint是一种使用一个或多个字节序列化整数的方法，会把整数编码为变长字节。对于32位整型数据经过Varint编码后需要1-5个字节，小的数字使用1个byte，大的数字使用5个bytes。64位整型数据编码后占用1~10个字节。在实际场景中小数字的使用率远远多于大数字，因此通过Varint编码对于大部分场景都可以起到很好的压缩效果。

原理

除了最后一个字节外，varint编码中的每个字节都设置了最高有效位（msb），msb为1则表明后面的字节还是属于当前数据的,如果是0那么这是当前数据的最后一个字节数据。每个字节的低7位用于以7位为一组存储数字的二进制补码表示，最低有效组在前，或者叫最低有效字节在前。

除了最后一个字节外，varint编码中的每个字节都设置了最高有效位（most significant bit - msb）–msb为1则表明后面的字节还是属于当前数据的,如果是0那么这是当前数据的最后一个字节数据。每个字节的低7位用于以7位为一组存储数字的二进制补码表示，最低有效组在前，或者叫最低有效字节在前。这表明varint编码后数据的字节是按照小端序排列的。

例如：

这里是数字128，它是一个字节，因此未设置msb：01111111

这是300的表示方式1010 1100 0000 0010，它就显示稍微复杂些，您如何确定这是300？

首先取出第一个字节1010 1100最高位为1，表明接下来一个字节是一起的，然后取出紧跟着的一个字节0000 0010发现该字节最高位为0，则表明没有后续。因为varint是最低有效组在前,所以去掉第一个字节的最高位，然后去掉第二个字节的最高位放在第一个字节处理后的数值前面形成100101100 ，如下图所示：

zigzag编码

前言：

前面说到varint算法是一种紧凑的压缩数据方法，对于比较小的数值压缩效率很高，但是对于大的数据效率不但没有提升可能还会有所下降。而负数在计算机中的表示就是一个很大的数值。为了达到压缩效果就需要一个方法，把负数转换成小的正数的方法，而zigzag算法正好解决这个需求。

基础知识：原码，反码和补码

编码原理

负数的问题引入：

zigzag巧妙解决方法：

ZigZag编码将有符号整数映射为无符号整数，以便具有较小绝对值（例如-1）的数字也具有较小的编码值。这样做的方式是通过正整数和负整数来回“曲折”，以便将-1编码为1，将1编码为2，将-2编码为3，依此类推如下图所示。
result:

zigzag编码实现：

example：

package main

import "fmt"

func zigzag(n int) int {
	return (n << 1) ^ (n >> 31)
}

func main() {
	fmt.Println("result of zigzag -1:", zigzag(-1))
	fmt.Println("result of zigzag  1:", zigzag(1))
	fmt.Println("result of zigzag -2:", zigzag(-2))
	fmt.Println("result of zigzag  2:", zigzag(2))
	fmt.Println("result of zigzag -3:", zigzag(-3))
	fmt.Println("result of zigzag  3:", zigzag(3))
}

// go run main.go
result of zigzag -1: 1
result of zigzag  1: 2
result of zigzag -2: 3
result of zigzag  2: 4
result of zigzag -3: 5
result of zigzag  3: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

无符号数：

对正整数进行编码的时候可以使用varint编码来节省前缀0

有符号数：

对有符号整数进行编码的时候，可以使用zigzag来消除负数情况下数值很大的问题，通过zigzag对有符号数字进行编码后，使得正负数都变成了正数表示形式，此时再通过varint进行编码来节省前缀0