InfluxDB数据压缩算法

前言


InfluxDB作为DB-Engines上排名第一的时序数据库,从设计和实现上都针对时序数据的特性进行了优化,其高性价比特性与数据压缩有着直接关系,本文将介绍InfluxDB使用的数据压缩算法

数据存储模型

首先简单介绍下时序数据在influxdb中是如何存储的。

时序数据场景中,每个数据点都包含数据值和时间戳,以及measurement和tag-set组成的series key,比如下面的例子中,第一个空格前面的部分就是series key,后面跟着的是值和时间戳:

InfluxDB数据压缩算法

InfluxDB的数据存储是基于series key来组织的,上面的数据有两个series key(对应两台主机)。

InfluxDB数据压缩算法

每个series key对应的数据根据时间戳进行排序后,以一个block进行存储;存储是列式的,即时间戳和数据是独立存储的:

InfluxDB数据压缩算法

下面讨论的压缩算法就是针对时间戳和值进行无损压缩。

压缩算法

InfluxDB中值是有类型的,当前支持整形,浮点数,布尔类型和字符串四种类型,而时间戳是64位整形,压缩算法是根据不同的数据类型来选择的。

时间戳

时间戳都是64位的无符号整数,其编码方式是自适应的:

  1. 因为时间戳是排序的,首先进行delta编码,第一个数据不变,其他数据转换为与上一个数据的delta;同时计算出10为因子的最大公约数。
  2. 如果最大值(即最后一个原始值与第一个原始值的差)过大(超过1 << 60,大约36年,基本不会出现),则不压缩,直接存储数组。否则,
  3. 如果delta都相同,就直接使用游程编码,只记录第一个值,delta值,以及数量即可。一般监控数据都是定时采集的,比如十秒一个点,那游程编码方式可以达到很高的压缩比;否则
  4. 所有的delta值都除以最大公约数(最大公约数是编码在数据中的),然后使用simple8b算法进行编码。

simple8b是一种整数编码算法,2010年由墨尔本大学的一位博士生提出的。simple8b将多个整数(0到1<<60-1 之间)打包到一个64位的整数中,其中前4位用作selector,用来标记每个值使用多少bit。

InfluxDB数据压缩算法

浮点数

浮点型的数据编码方式采用了facebook的Gorilla算法,详细描述可以参考paper或者内网的翻译,这里仅简单介绍下。

多数时序场景下相邻值变化不大,浮点数也不会有明显的变化,Gorilla也采用了delta编码原理,但是与整形的delta编码不同,Gorilla使用XOR来计算两个浮点值的差异。

首先我们看下常用的浮点数机器编码,也就是ieee754标准:

InfluxDB数据压缩算法

符号位和指数位在高位,所以相近的值高位是相同的,XOR的值会有很多高位的零。XOR的值会再进行变长编码。

整形

整数类型也是基于数据特征自适应地选择两种编码方式。

  1. 首先使用zig-zag编码数据,将有符号整数编码成无符号整形
  2. 如果所有的delta都相同,则使用游程编码,否则
  3. 如果可以使用simple8b,则使用simple8b算法编码(与时间戳编码一样),否则
  4. 不压缩直接存储

zigzag编码是一种针对有符号数的变长编码,其计算十分简单:

(n << 1) ^ (n >> 63)

也就是将符号位移动到最后面,这样绝对值小的数在变长编码中可以占用更少的位,编码效果如下:

 

InfluxDB数据压缩算法

布尔类型

布尔值使用简单的bit pack方式编码,每个值使用1位,没有使用二次压缩。

字符串

使用snappy算法进行编解码。Google snappy的设计原则不是追逐压缩比,而是更看中压缩性能。代码实现上,snappy也针对x86系统做了优化,比如使用little-endian,使用SSE指令直接操作128bit的整数,等等。influxdb使用go语言开发,snappy是实现中直接使用了x86汇编语言。