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

开发者社区> Foo> 正文

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汇编语言。


 


 

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

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
829 0
图的单源最短路径,Floyd算法(数据结构c++)
这个算法结构很是简单,但是理解还是有一定的困难,一开始做的时候想不明白,跟着算法自己动手画画就知道这个算法具体是怎么回事了。 时间复杂度是O(N*3) 算法有点动态规划的意思,有两个数组,一个(dis[])是记录俩顶点之间的最短路径的长度的,一个[path]数组是记录俩结点的中间结点的。
787 0
再不懂时序就 OUT 啦!,DBengine 排名第一时序数据库,阿里云数据库 InfluxDB 正式商业化!
阿里云数据库 InfluxDB® 版已于近日正式启动商业化 。 InfluxDB 是 DBengine 网站时序数据库类目排名第一的数据库产品,广泛应用于互联网基础资源监控,容器监控,业务运营监控分析,物联网设备远程实时监控,工业安全生产监控,生产质量评估和故障回溯。
3108 0
MongoDB数据存储-深入了解
https://www.cnblogs.com/kevingrace/p/7909947.html
561 0
一站式数据采集存储的利器:阿里云InfluxDB®️数据采集服务
随着时序数据的飞速增长,时序数据库不仅需要解决系统的稳定性和性能问题,还需实现数据从采集到分析的链路打通,才能让时序数据真正产生价值。
1704 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
559 0
+关注
Foo
5
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载