TSDB时序数据库时序数据压缩解压技术浅析_zstddecoder-程序员宅基地

技术标签: 人工智能  云栖号技术分享  物联网  big data  

简介: 目前,物联网、工业互联网、车联网等智能互联技术在各个行业场景下快速普及应用,导致联网传感器、智能设备数量急剧增加,随之而来的海量时序监控数据存储、处理问题,也为时序数据库高效压缩、存储数据能力提出了更高的要求。对于通量愈加庞大的物联网时序大数据存储,尽管标准压缩方法还能发挥其价值,但某些场景对时序数据压缩解压技术效率、性能提出了新的需求。本文介绍了现有的时序数据压缩解压技术,分类介绍了不同算法的特点和优劣势。

image.png

作者 | 仁威
来源 | 阿里技术公众号

摘要:目前,物联网、工业互联网、车联网等智能互联技术在各个行业场景下快速普及应用,导致联网传感器、智能设备数量急剧增加,随之而来的海量时序监控数据存储、处理问题,也为时序数据库高效压缩、存储数据能力提出了更高的要求。对于通量愈加庞大的物联网时序大数据存储,尽管标准压缩方法还能发挥其价值,但某些场景对时序数据压缩解压技术效率、性能提出了新的需求。本文介绍了现有的时序数据压缩解压技术,分类介绍了不同算法的特点和优劣势。

时序数据普遍存在于IoT物联网、工业互联网、车联网等相关场景,物联网设备已遍布各种行业场景应用,从可穿戴设备到工业生产设备,都会或将会产生大量数据。比如,新型波音787客机每次飞行传感器产生的数据量都在500GB左右。在这些场景下,通常具备高并发写和高通量数据处理特点,选择时序数据压缩算法需要全方位考虑数据采集、存储、分析的需要。特别需要注意的是业务应用对时序数据当前和历史数据分析的方式,选择压缩算法不当将可能导致关键信息丢失,从而影响分析结果。对于业务来说,更直接使用时序数据压缩技术的应用就是时序数据库,对于时序数据库压缩解压是关键数据处理步骤,压缩算法性能直接影响时序数据库建设投入的ROI。

一 时序数据压缩

对于数据压缩算法,业界存在更普遍的解释,通常是针对通用场景和业务相关场景,比如视频、音频、图像数据流压缩。本文重点介绍时序数据库中常用的面向时序数据设计或可用于时序数据处理的通用压缩算法。我们选择分析的算法具备对更普遍场景下持续产生时序数据压缩处理的能力,并对IoT物联网场景传感器数据压缩的以下特点做了特殊设计:

1、数据冗余(Redundancy):一些特定模式的时序数据经常性重复出现在一个或多个时间序列。

2、函数估算(Approximability):某些传感器产生的时序数据生成模式可以根据预定义函数估算。

3、趋势预测(Predictability):某些时序数据未来趋势可以通过算法预测,例如利用回归、深度神经网络等技术。

image.png

图 时序数据压缩算法分类

本文重点总结了时序数据库和物联网IoT传感器管理常用压缩算法,并根据技术方法(dictionary-based, functional approximation, autoencoders, sequential等)和技术属性(adaptiveness, lossless reconstruction, symmetry, tuneability)对碎片化的压缩技术进行了分类,详细参考上图,并针对主要算法性能进行了对比分析。

二 背景技术介绍

在介绍压缩算法之前,我们先对时序数据、压缩和品质指数(quality indices)几个关键的概念进行定义。

1 时序数据(Time Series)

时序数据指数据元组根据时间戳(ti)升序排列的数据集合,可以被划分为:

1、单变量时序(Univariate Time Series,UTS):每次采集的数据元组集合为单个实数变量。

2、多变量时序(Multivariate Time Series ,MTS):每次采集的数据元组集合由多个实数序列组成,每个组成部分对映时序一个特征。

比如,图2中股票价格在指定时间窗口的波动可以被定义为单变量时序数据,而每天交易信息(如:开盘、收盘价格,交易量等)则可以定义为多变量时序数据。

image.png

图 股票交易UTS时序数据样例

用数学范式表达时序可以被定义为:

image.png

2 数据压缩

数据压缩(又被称为源编码,source coding),根据David Salmon在《Data Compression: The Complete Reference》一书中的定义,可以简单描述为“将输入原始数据流转变为字符流(bit stream)或压缩流的体量更小的输出数据流的过程”。这个过程遵循J. G.Wolff提出的Simplicity Power(SP)理论,旨在尽量保持数据信息的前提下去除数据冗余。

数据解压缩(又被称为源解码,source decoding),执行与压缩相反过程重构数据流以适应更高效数据应用层对数据表述、理解的需要。

现有压缩算法根据实现原理的差异,可以被划分为以下几类:

  • 非适应/自适应(Non-adaptive/ adaptive):非适应算法不需要针对特殊数据流进行训练以提升效率,而适应算法则需要有训练过程。
  • 松散/非松散(Lossy/Lossless):松散算法不保障对原始数据压缩后的结果唯一,而非松散算法对同样原始数据的压缩结果唯一。
  • 对称/非对称(Symmetric/Asymmetric):对称算法对数据的压缩、解压缩使用相同的算法实现,通过执行不同的代码路径切换压缩解压缩过程;非对称算法则在数据压缩、解压缩过程分别使用不同的算法。

对于具体的时序数据流压缩解压缩过程,一个压缩算法实例(encoder)输入s体量的时序数据流TS,返回压缩后的体量s′的时序数据流TS′,且s>s′包含一同压缩的时间戳字段E(TS) = TS′。解压缩算法实例(decoder)的执行过程则是从压缩数据流还源原始的时序数据流D(TS′) = TS,若TS = TSs则压缩算法是非松散的,否则就是松散的。

3 品质指数(quality indices)

为了度量时序数据压缩算法的性能,通常需要考虑三点特性:压缩率、压缩速度、精确度。

1、压缩率:衡量压缩算法对原始时序数据压缩比率,可以定义为:

ρ=s's

其中,s′代表时序数据压缩后的体量,s为时序数据压缩前的原始体量。ρ的转置又被称为压缩因数,而品质指数(quality indices)则是被用来表述压缩收益的指标,其定义为:

cg=100loge1ρ

2、速度:度量压缩算法执行速度,通常用每字节压缩周期的平均执行时间(Cycles Per Byte,CPB)。

3、精确度:又被称为失真度量(Distortion Criteria,DC),衡量被压缩算法重构后的时序数据保留信息可信度。为适应不同场景度量需要,可以用多种度量指标来确定,常用的指标有:

Mean Squared Error:

image.png

Root Mean Squared Error:

image.png

Signal to Noise Ratio:

image.png

Peak Signal to Noise Ratio:

image.png

三 压缩算法

目前常用的时序数据压缩算法主要有以下几种:

1) Dictionary-Based (DB)

1.1. TRISTAN
1.2. CONRAD
1.3. A-LZSS
1.4. D-LZW

2) Functional Approximation (FA)

2.1. Piecewise Polynomial Approximation (PPA)
2.2. Chebyshev Polynomial Transform (CPT)
2.3. Discrete Wavelet Transform (DWT)

3) Autoencoders:

3.1. Recurrent Neural Network Autoencoder (RNNA)

4) Sequential Algorithms (SA)

4.1. Delta encoding, Run-length and Huffman (DRH)
4.2. Sprintz
4.3. Run-Length Binary Encoding (RLBE)
4.4. RAKE

5) Others:

5.1. Major Extrema Extractor (MEE)
5.2. Segment Merging (SM)
5.3. Continuous Hidden Markov Chain (CHMC)

1 Dictionary-Based (DB)

DB算法实现理念是通过识别时序数据都存在的相同片段,并将片段定义为原子片段并以更精简的标识标记替代,形成字典供使用时以标识作为Key恢复,这种方式能够在保证较高数据压缩比的同时,降低错误率。此技术实现的压缩可能是无损的,具体取决于实现情况。此架构的主要挑战是:

  • 最大限度地提高搜索速度,以便在字典中查找时间系列片段;
  • 使存储在 dictionary 中的时间串段尽可能一般,以最大限度地缩短压缩阶段的距离。

TRISTAN是基于DB策略实现的一种算法,TRISTAN算法把压缩划分为两个阶段处理,第一阶段适应性学习,第二阶段数据压缩。在学习阶段,TRISTAN字典表通过学习训练数据集来生成,或者结合专家经验定义特定模式的原子片段。有了字典表,在压缩阶段TRISTAN算法执行从以下公式中检索w的过程。

s=w·D w ∈ {0,1}k

其中,D是字典表,s为原子片段,K是压缩后的时序表征数据长度。TRISTAN解压过程则是通字典表D解释表征数据w得到原始时序数据的过程。

CORAD算法在TRISTAN基础之上增加了自动数据关联信息,对两两时序数据片断进行基于Pearson相关系数的度量,以相邻矩阵M存储相关性,通过M与字典表D相结合的计算方式,进一步提升压缩比和数据解压精确度。

Accelerometer LZSS(A-LZSS)算法是基于LZSS搜索匹配算法的DB策略实现,A-LZSS算法使用Huffman编码,以离线方式通过统计数据概率分布生成。

Differential LZW (D-LZW)算法核心思想是创建一个非常大的字典表,它会随着时间的推移而增长。一旦字典表被创建,如果在字典表中发现缓冲区块,它就会被相应的索引替换,否则,新方块将插入字典作为新的条目。增加新的缓存区块是在保证非松散压缩的原则下实现,并不限制增加的数量,但随之而来的问题就是字典表有可能无限膨胀,这就导致D-LZW算法只适用于特定场景,比如输入时序数据流为有限词组或可枚举字符集组成。

Zstandard(zstd)是一种基于Huffman编码Entropy coder实现的快速非松散DB压缩算法,字典表作为一个可选选项支撑参数控制开启关闭。算法实现由Facebook开源,支持压缩速度与压缩比之间的按需调整,能够通过牺牲压缩速度来换取更高压缩比,反之亦然。相比同类算法,zstd算法性能可参考下表数据。

image.png

表 zstd算法性能对比

2 Function Approximation (FA)

函数近似类时序压缩算法FA的主要设计思想是假设时间序列可以表示为时间函数。由于难以避免出现无法处理的新值,找出能够准确描述整个时间序列的函数是不可行的,因此我们可以将时间序列划分成多个片段,对每个段找到一个近似时间函数来描述。

由于找到一个能完整描述时间序列的函数 f:T → X 是不可行的,因此实现上我们需要考虑找出一个函数簇,以及其对映的参数来描述分段时序数据相对可行,但这也使得压缩算法为松散的实现。

相比之下,FA类算法优点是它不依赖于数据取值范围,因此不需要有基于样本数据集的训练阶段,如果采用回归算法,我们只需要单独考虑划分好的单个时间片段。

Piecewise Polynomial Approximation (PPA)是FA类算法的常用实现,此技术将时间序列分为固定长度或可变长度的多个段,并尝试找到接近细分的最佳多项式表述。尽管压缩是有损的,但可以先于原始数据的最大偏差进行修复,以实现给定的重建精度。PPA算法应用贪婪的方法和三种不同的在线回归算法来近似恒定的函数、直线和多项式。

Chebyshev Polynomial Transform (CPT)实现原理与PPA算法类似,只是改进了支持使用不同类型多项式的能力。Discrete Wavelet Transform (DWT)使用Wavelet小波转换对时序数据进行转换。Wavelet是描述起止值都为0,中间值在此之间波动的函数,

3 Autoencoders

Autoencoder是一种特殊的神经网络,被训练生成用来处理时序数据。算法架构由对称的两部分组成:编码器encoder和解码器decoder。在给定n维时序数据输入的前提下,Autoencoder的编码器输出m(m<n)维的输出。解码器decoder则可以将m维输出还原为n维输入。Recurrent Neural Network Autoencoder (RNNA)是Autoencoder的一种典型实现,通过RNN来实现对时序数据的压缩表述。

image.png

图 Autoencoder算法实现结构

4 序列化算法Sequential Algorithms(SA)

序列化算法SA实现原理是顺序融合多种简单压缩技术实现对时序数据压缩,常用技术有:

  • Huffman coding:编码器创建一个字典,将每个符号关联到二进制表示,并以相应的表示替换原始数据的每个符号。
  • Delta encoding:此技术对目标文件进行编码,以处理一个或多个参考文件。在时间系列的特定情况下,每个元素在 t 被编码为∆(xt,xt=1)。
  • Run-length encoding:在此技术中,每个运行(连续重复相同值的序列)都与对(vt, o)进行子图,其中vt是时间t值,o是连续发生次数。
  • Fibonacci binary encoding:此编码技术基于 Fibonacci 序列实现。

Delta encoding, Run-length and Huffman (DRH)算法是一种融合了Delta encoding、Huffman coding、Run-length encoding和Huffman coding四种技术的压缩算法,算法实现是非松散的且计算复杂度相对较小,适合在边缘短实现对数据的压缩解压,也因此适合应用在物联网、工业互联网、车联网等需要边缘短采集处理时序数据的场景。

Sprintz就是一种专门针对物联网场景设计的SA算法,在算法设计中考虑了对物联网场景中能源消耗、速度等时序指标波动规律因素,为以下需求而特别优化了算法设计:

1)对较小片段数据的快速处理

2)底计算复杂度的压缩、解压缩,以适应边缘端有限的计算资源

3)对实时采集时序数据的快速压缩、解压缩

4)非松散压缩

为了在处理IoT物联网环境时序数据上取得更好的压缩效果,Sprintz算法通过预测数据生成趋势的方式来提升算法对数据的压缩性能,其主要实现的算法过程包括以下几部分:

1)预测:基于delta encoding或FIRE算法通过统计历史时序数据,对新样本数据生成规律进行预测;

2)Bit packing:打包预测错误信息数据和包头描述用来解压数据的信息;

3)Run-length encoding:如果压缩过程中通过预测算法未发现任何错误信息,则略过bit packing过程的错误信息发送,并在下次发生错误时在打包预测错误信息的包头中记录略过的数据长度;

4)Entropy coding:用Huffman coding对big packing生成的包文件进行编码。

Run-Length Binary Encoding (RLBE)算法 也是一种为IoT物联网场景下数据压缩解压,适应物联网边缘端有限计算、存储资源环境的常用非松散SA时序数据压缩算法,RLBE算法融合了delta encoding,run-length encoding和Fibonacci coding三种技术,其执行过程如下图所示。

image.png

图 Run-Length Binary Encoding (RLBE)算法执行过程图示

RAKE算法原理是通过检测时序数据稀疏性来实现对数据的压缩。RAKE为非松散压缩,执行过程包涵预处理和压缩两个主要过程。预处理过程中,RAKE算法设计由字典表来转换原始数据。压缩过程则对预处理的输出数据进行稀疏性检测,压缩相邻的相同数据。

5 其他类型算法

Major Extrema Extractor (MEE)算法通过统计指定时间段的时序数据最大、最小值来对数据进行压缩。Segment Merging (SM)算法则把时序数据抽象为时间戳和值及偏差组成的片段,可用元组(t,y,δ)表述,其中t为开始时间,y是数值常量标识,δ是数据片段偏差。Continuous Hidden Markov Chain (CHMC)算法则利用马尔可夫链概率模型来将时序数据定义为一系列有限状态节点集合S及链接节点的状态迁移概率边集合A。

四 总结

时序数据是物联网、工业互联网、车联网等场景下生成数据总量中占比最高的数据类型,有效的压缩算法不但可以降低数据存储成本,同时可以在边缘到中心,中心到云的数据传输过程中节约网带宽资源,降低数据同步时间。对于作为时序数据核心存储中枢的时序数据库,压缩算法性能更是至关重要。阿里云多模数据库Lindorm核心数据库引擎之一时序引擎Lindorm TSDB内置的自研、高效数据压缩算法针对物联网、工业互联网、车联网等智能、互联场景针对性优化,进一步提升了时序数据存储的ROI,新一代云原生智能互联系统提供必要支撑。

原文链接
本文为阿里云原创内容,未经允许不得转载。 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yunqiinsight/article/details/120527500

智能推荐

Resnet网络介绍_renet网络-程序员宅基地

文章浏览阅读1.8w次,点赞9次,收藏57次。引言深度残差网络(Deep residual network, ResNet)的提出是CNN图像史上的一件里程碑事件,让我们先看一下ResNet在ILSVRC和COCO 2015上的战绩:图1 ResNet在ILSVRC和COCO 2015上的战绩ResNet取得了5项第一,并又一次刷新了CNN模型在ImageNet上的历史:图2 ImageNet分类Top-5误差Re..._renet网络

利用DPCM&Huffman编码实现数据压缩_C语言实现_c 数据压缩-程序员宅基地

文章浏览阅读1.6k次。一、实验原理 DPCM是差分预测编码调制的缩写,它利用过去的抽样值来预测当前的抽样值,对它们的差值进行编码。差值编码可以提高编码频率,这种技术已应用于模拟信号的数字通信之中。图像内的像素值之间并非相互独立,某一像素与周围像素之间存在一定的关系,这一关系导致整幅图像的信息熵不是很大。DPCM利用当前像素值减去前一像素值,得到差值,以减少图像之间的冗余,原理图如下。_c 数据压缩

JSF笔记 – JSF中的EL表达式语言支持_jsf 支持el表达式吗-程序员宅基地

文章浏览阅读3k次。1、EL表达式语言:JSF中的表达式语言形如:#{login.username }2、JSF中的表达式语言与JSP2中的表达式语言的不同:JSF使用#开始,JSP使用$开始。JSP只是访问并输出变量和Bean的值,JSF可以访问输出托管Bean的属性,还可以更新托管Bean的属性。JSF不支持内嵌函数JSF与JSP中的内置对象有点不同。3、J_jsf 支持el表达式吗

JS如何获取url的参数_如何获取的url的参数-程序员宅基地

文章浏览阅读181次。js获取url参数值 index.htm?参数1=数值1&参数2=数值2&参数3=数据3&参数4=数值4&...... 静态html文件js读取url参数 根据获取html的参数值控制html页面输出 一、字符串分割分析法。 这里是一个获取URL带QUESTRING参数的JAVASCRIPT客户端解决方案,相当于asp的request.querystring,PHP的$_如何获取的url的参数

跨其他浏览器,打开IE8浏览器(调用cmd打开)_shell.run打开浏览器-程序员宅基地

文章浏览阅读4.7k次,点赞2次,收藏5次。1.如果写在java程序中,当项目部署到服务器上后,其他浏览器访问系统,只会在当前服务器上打开浏览器(1)使用默认浏览器打开:Stringurl = "https://www.baidu.com/";Runtime.getRuntime().exec("rundll32 url.dll,FileProtocolHandler" + url);System.exit(0);(2)默..._shell.run打开浏览器

c# 禁止c# winform datagridview 拖动列宽_datagridview列宽不能拖动-程序员宅基地

文章浏览阅读3.5k次,点赞3次,收藏3次。//DataGridView1.AllowUserToResizeColumns = false; dataGridView1.AllowUserToResizeRows = false; // 禁止用户改变列头的高度 dataGridView1.ColumnHeadersHeightSizeMode = DataGridViewColumnHeadersHeightSizeMode.DisableResizing;_datagridview列宽不能拖动

随便推点

uploadify+jcrop实现头像上传裁剪功能_uploadify 上传图片 尺寸裁剪 demo-程序员宅基地

文章浏览阅读2.1k次。因为无法debug,断断续续几天才搞定 首先加载各个js和css,都在官网下载~uploadify.cssjcrop.cssjquery.jsjquery.uploadify.min.jsjcrop.js步骤:uploadify上传图片,得到图片路径在前台显示用户上传的图片赋给jcrop的id对象,裁剪后点击保存,将原始图片路径和各个坐标传给php,通过gd库实_uploadify 上传图片 尺寸裁剪 demo

C# Socket TCP 编程,客户端与服务端连接,发送字符串,文件_c# socketserver 发送字符串-程序员宅基地

文章浏览阅读1.3w次,点赞5次,收藏32次。C# 发送消息Socket服务端和客户端,这部分是服务端服务端创建一个socket对象第一个参数 :寻址方案,ip版本4 第二个参数:套接字类型,字节流 第三个参数:协议,TCPSock_c# socketserver 发送字符串

复选框的全选与取消全选的一个例子,很好用_th复选框全选取消全选-程序员宅基地

文章浏览阅读269次。<table border="1"> <tr> <th><input type="checkbox" οnclick="swapCheck()" /></th> <th>Month</th> <th>Savings</th> </tr> <tr>..._th复选框全选取消全选

Android Gradle 编译过程中的优化,kotlin教程-程序员宅基地

文章浏览阅读875次,点赞18次,收藏16次。其实Android开发的知识点就那么多,面试问来问去还是那么点东西。所以面试没有其他的诀窍,只看你对这些知识点准备的充分程度。so,出去面试时先看看自己复习到了哪个阶段就好。上面分享的百度、腾讯、网易、字节跳动、阿里等公司2021年的高频面试题,博主还把这些技术点整理成了视频和PDF(实际上比预期多花了不少精力),包含知识脉络 + 诸多细节,由于篇幅有限,上面只是以图片的形式给大家展示一部分。Android学习PDF+学习视频+面试文档+知识点笔记【Android思维脑图(技能树)】知识不体系?

最近word每次只要左键点击一下鼠标,总是要转一会圈圈才反应过来是为什么。-ZOL问答.html_word文档鼠标转圈-程序员宅基地

文章浏览阅读7.4k次,点赞3次,收藏2次。原贴地址:http://ask.zol.com.cn/x/4996911.html因为安装了powerdesigner的缘故。原因是PD有导出word文档的功能,所以默认给word添加了一个活动的WordToRMP的dll,并且带一个模板。如果你出现卡顿,没办法,暂时先禁用这个加载项。请打开位置:word选项-加载项,在右边找到powerDesigner的加载项,选中并点击转到..把对应的com加..._word文档鼠标转圈

Arcgis 标注换行_arcgis宗地注记换行-程序员宅基地

文章浏览阅读1.6w次,点赞6次,收藏32次。参考链接arcgis中标注样式换行怎么输arcgis文本标注换行处理arcgis标注换行表达式Arcgis标注语义换行arcgis条件标注及换行标注Function FindLabel ( [name] ) if (len([name])) >4 then FindLabel = left( [name],4) & chr(13) & ri..._arcgis宗地注记换行

推荐文章

热门文章

相关标签