版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

1.引言

在监控系统中，海量的监控数据如何存储，一直是设计人员所必须关心的问题。OpenTSDB选择了Hbase；Open-Falcon选择了RRD(round-robin database)。Prometheus另辟蹊径，借鉴了facebook的paper(参考资料2)，设计了自己的TSDB(time series database)。本文试图简单介绍TSDB中使用的2个压缩算法

2. 简单的聊聊TSDB的文件结构

值得一提的是在prometheus中 1）数据是没有做预聚合的，所有的聚合操作都是在查询阶段进行。 据笔者观察查询的时间跨度如果超过7d，速度就会变得比较慢(3 ~ 5秒)

2）Prometheus数据都是单机存储的，数据存在丢失的可能，最近产生的数据存储在内存中，历史数据落在硬盘上，默认数据存储15天。

可以使用storage.tsdb.retention.time来修改数据存储的跨度

--storage.tsdb.retention.time=7d
  1. 文件结构
├── 01D5X2A81S8FMS16S5Q1GWNQDE
│   ├── chunks      // chunk数据
│   │   └── 000001
│   ├── index       // 索引文件
│   ├── meta.json   // 人类可读的文件
│   └── tombstones
├── 01D5X2A83TVJD7FFGKPHED5VA1
│   ├── chunks
│   │   └── 000001
│   ├── index
│   ├── meta.json
│   └── tombstones
└── wal             // wal下的全是预写日志，类似于MySQL中的binlog
    ├── 00000010
    ├── 00000011
    ├── 00000012
    ├── 00000013
    └── checkpoint.000009
        └── 00000000

如果读者仔细观察会发现，文件夹的modify时间是递增。 没错，监控数据首先按照时间维度，划分在不同的文件夹中, 然后通过索引文件index去定位不同的series, 实际的数据在chunks文件夹中 。（补充，WAL文件夹存有最近的数据。可简单的把WAL理解为最近的临时数据，chunks中的为归档数据。）

drwxr-xr-x 3 prometheus prometheus 4096 Mar  7 17:00 01D5BP4CVKS560HC8VR1TQSEAX
drwxr-xr-x 3 prometheus prometheus 4096 Mar  7 23:00 01D5CAQJK2Q0MJ04W170RZX866
drwxr-xr-x 3 prometheus prometheus 4096 Mar  8 05:00 01D5CZARBF5F2CSPCB517T2MQS
drwxr-xr-x 3 prometheus prometheus 4096 Mar  8 11:00 01D5DKXY4C9KS9NY22P56791WZ
drwxr-xr-x 3 prometheus prometheus 4096 Mar  8 17:00 01D5E8H3W57R95FABE85FWGZVM
drwxr-xr-x 3 prometheus prometheus 4096 Mar  8 23:00 01D5EX49K598YTQWWB2NH9Y2FA
drwxr-xr-x 3 prometheus prometheus 4096 Mar  9 05:00 01D5FHQFCPHB0SES21N9JN9MG6

meta.json

{
        "ulid": "01D5BP4CVKS560HC8VR1TQSEAX",
        "minTime": 1551916800000,      // 时间跨度的开始时间
        "maxTime": 1551938400000,      // 时间跨度的结束时间
        "stats": {
                "numSamples": 191160,  // 采样点的数量
                "numSeries": 531,      // `Series`的数量
                "numChunks": 1593      // `Chunk`的数量
        },
        ...
}

3. 压缩算法

时序数据库的最大特点是，每个series都是由若干二元组组成的

(T1, V1) (T2, V2) (T3, V4) ... (Tn, Vn)

T表示时间戳(int64)，V表示数值(float64)，各占8个字节 每个sample点(二元组)为16个字节。由于Prometheus采用了delta-of-delta和XOR压缩算法，据笔者测试，平均保存sample只需要2个字节，压缩率为12.5%，还是非常惊人的。

注意 delta-of-delta和XOR压缩算法利用监控数据的特定特点所实施的，在其它场合未必有效。

3.1 delta-of-delta 压缩算法

采用delta-of-delta 压缩算法针对时间戳进行压缩

    Delta1       Delta2        Delta3
T1 --------> T2 --------> T3 --------> T4

由于在Prometheus中，检查间隔往往是固定的(通常是1min)，因此 Delta2 - Delta1 或者 Delta3 - Delta2 将会是非常小的值，然后根据差值的范围，采用不等长的编码就可以达到压缩的目的

代码如下:
xor.go

func (a *xorAppender) Append(t int64, v float64) {
	var tDelta uint64
	num := binary.BigEndian.Uint16(a.b.bytes())

	if num == 0 {
		buf := make([]byte, binary.MaxVarintLen64)
		for _, b := range buf[:binary.PutVarint(buf, t)] {
			a.b.writeByte(b)
		}
		a.b.writeBits(math.Float64bits(v), 64)

	} else if num == 1 {
		tDelta = uint64(t - a.t)

		buf := make([]byte, binary.MaxVarintLen64)
		for _, b := range buf[:binary.PutUvarint(buf, tDelta)] {
			a.b.writeByte(b)
		}

		a.writeVDelta(v)

	} else {
		tDelta = uint64(t - a.t)
		dod := int64(tDelta - a.tDelta)

		// Gorilla has a max resolution of seconds, Prometheus milliseconds.
		// Thus we use higher value range steps with larger bit size.
		switch {
		case dod == 0:
			a.b.writeBit(zero)
		case bitRange(dod, 14):
			a.b.writeBits(0x02, 2) // '10'
			a.b.writeBits(uint64(dod), 14)
		case bitRange(dod, 17):
			a.b.writeBits(0x06, 3) // '110'
			a.b.writeBits(uint64(dod), 17)
		case bitRange(dod, 20):
			a.b.writeBits(0x0e, 4) // '1110'
			a.b.writeBits(uint64(dod), 20)
		default:
			a.b.writeBits(0x0f, 4) // '1111'
			a.b.writeBits(uint64(dod), 64)
		}

		a.writeVDelta(v)
	}

	a.t = t
	a.v = v
	binary.BigEndian.PutUint16(a.b.bytes(), num+1)
	a.tDelta = tDelta
}

3.2 XOR压缩算法

采用XOR 压缩算法针对值进行压缩 由于相邻的sample点的数据值差异很小，我随便挑了2个数，117.0和118.0来看看异或后的结果

package main

import (
	"fmt"
	"math"
)

func main(){
	v1 := math.Float64bits(117)
	v2 := math.Float64bits(118)
	fmt.Printf("%064b\n", v1)
	fmt.Printf("%064b\n", v2)
	fmt.Println("-----------")
	fmt.Printf("%064b\n", v1 ^ v2)
}

结果输出

0100000001011101010000000000000000000000000000000000000000000000
0100000001011101100000000000000000000000000000000000000000000000
-----------
0000000000000000110000000000000000000000000000000000000000000000

异或后，不同的bits只有2位，头部(leading)和尾部(trailing)都有大量连续的位是'0’, 根据这种情况，对leading和trailing的'0’进行压缩存储就能节约大量空间。

事实上由于IEEE 754规范所约定的Float64的内部结构，如果2个数的值接近，异或的值在头部(leading)和尾部(trailing)一定会有大量连续的位是'0’, 有兴趣的朋友可以想想为什么。

代码如下 xor.go

func (a *xorAppender) writeVDelta(v float64) {
	vDelta := math.Float64bits(v) ^ math.Float64bits(a.v)

	if vDelta == 0 {
		a.b.writeBit(zero)
		return
	}
	a.b.writeBit(one)

	leading := uint8(bits.LeadingZeros64(vDelta))
	trailing := uint8(bits.TrailingZeros64(vDelta))

	// Clamp number of leading zeros to avoid overflow when encoding.
	if leading >= 32 {
		leading = 31
	}

	if a.leading != 0xff && leading >= a.leading && trailing >= a.trailing {
		a.b.writeBit(zero)
		a.b.writeBits(vDelta>>a.trailing, 64-int(a.leading)-int(a.trailing))
	} else {
		a.leading, a.trailing = leading, trailing

		a.b.writeBit(one)
		a.b.writeBits(uint64(leading), 5)

		// Note that if leading == trailing == 0, then sigbits == 64.  But that value doesn't actually fit into the 6 bits we have.
		// Luckily, we never need to encode 0 significant bits, since that would put us in the other case (vdelta == 0).
		// So instead we write out a 0 and adjust it back to 64 on unpacking.
		sigbits := 64 - leading - trailing
		a.b.writeBits(uint64(sigbits), 6)
		a.b.writeBits(vDelta>>trailing, int(sigbits))
	}
}

3.3 总结

由于delta-of-delta 和 XOR都是不等长的压缩算法，也带来了2个缺点。 1）无法直接定位到特定时间区间的sample 2）解压必须从chunk的首部开始计算，依次解出每个sample

4. 参考资料

  1. Writing a Time Series Database from Scratch
  2. Gorilla: A Fast, Scalable, In-Memory Time Series Database
  3. prometheus-storage
  4. TSDB format
  5. IEEE 754

微信公众号