InfluxDB数据压缩算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

InfluxDB数据压缩算法

简介:

前言


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


数据存储模型


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


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


dd7c788fde1ad854c42741d88083efab.png


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


df157c22078028cd0162fddc972980d1.png


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


TSM_compression.png


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


压缩算法


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。


f73aa2e01a7b9e66fd67e2b10a67bab4.png


浮点数


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


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


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


Double-Precision-IEEE-754-Floating-Point-Standard-1024x266.jpg


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


整形


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



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

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


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

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

 

4f185bcc66d36c7aac9c3ac2c9f0c2a6.png


布尔类型


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


字符串


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


 


 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章