TSDB 时序数据库时序数据压缩解压技能浅析
https://p6.toutiaoimg.com/large/pgc-image/4b0cb611c7e64f248d905b5c785b90f8摘要：目前，物联网、工业互联网、车联网等智能互联技术在各个行业场景下快速普及应用，导致联网传感器、智能设备数量急剧增加，随之而来的海量时序监控数据存储、处理问题，也为时序数据库高效压缩、存储数据本领提出了更高的要求。对于通量愈加庞大的物联网时序大数据存储，尽管标准压缩方法还能发挥其价值，但某些场景对时序数据压缩解压技术效率、性能提出了新的需求。本文介绍了现有的时序数据压缩解压技术，分类介绍了不同算法的特点和优劣势。
时序数据普遍存在于IoT物联网、工业互联网、车联网等相干场景，物联网设备已遍布各种行业场景应用，从可穿戴设备到工业生产设备，都会或将会产生大量数据。好比，新型波音787客机每次飞行传感器产生的数据量都在500GB左右。在这些场景下，通常具备高并发写和高通量数据处理特点，选择时序数据压缩算法需要全方位考虑数据采集、存储、分析的需要。特别需要留意的是业务应用对时序数据当前和历史数据分析的方式，选择压缩算法不当将大概导致关键信息丢失，从而影响分析效果。对于业务来说，更直接使用时序数据压缩技术的应用就是时序数据库，对于时序数据库压缩解压是关键数据处理步骤，压缩算法性能直接影响时序数据库创建投入的ROI。
一 时序数据压缩
对于数据压缩算法，业界存在更普遍的解释，通常是针对通用场景和业务相干场景，好比视频、音频、图像数据流压缩。本文重点介绍时序数据库中常用的面向时序数据计划或可用于时序数据处理的通用压缩算法。我们选择分析的算法具备对更普遍场景下持续产生时序数据压缩处理的本领，并对IoT物联网场景传感器数据压缩的以下特点做了特殊计划：
1、数据冗余（Redundancy）：一些特定模式的时序数据经常性重复出现在一个或多个时间序列。
2、函数估算（Approximability）：某些传感器产生的时序数据生成模式可以根据预界说函数估算。
3、趋势预测（Predictability）：某些时序数据将来趋势可以通过算法预测，例如使用回归、深度神经网络等技术。
https://p9.toutiaoimg.com/large/pgc-image/f2ba94700ed44636a1e972047f9c125d图 时序数据压缩算法分类
本文重点总结了时序数据库和物联网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中股票价格在指定时间窗口的波动可以被界说为单变量时序数据，而每天交易信息（如：开盘、收盘价格，交易量等）则可以界说为多变量时序数据。
https://p3.toutiaoimg.com/large/pgc-image/5a205533c01d4da5a62ff8f369f753f9图 股票交易UTS时序数据样例
用数学范式表达时序可以被界说为：
https://p6.toutiaoimg.com/large/pgc-image/7f217eef68824f71a4095ee7495a2785
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：
https://p9.toutiaoimg.com/large/pgc-image/b0a1c85dd44a477fbf99123d5b08d9ee
Root Mean Squared Error:
https://p26.toutiaoimg.com/large/pgc-image/21ca903cc31b4fd6ba8c57ed503b7edd
Signal to Noise Ratio:
https://p26.toutiaoimg.com/large/pgc-image/9d6c7193db2945578dc33d5762c91c10
Peak Signal to Noise Ratio:
https://p6.toutiaoimg.com/large/pgc-image/1e5f0707cd7f4ba0bd62626fab1a685a
三 压缩算法
目前常用的时序数据压缩算法重要有以下几种：
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算法性能可参考下表数据。
https://p9.toutiaoimg.com/large/pgc-image/5fafb99d711248e2bcbeb5dbf78ed70d表 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
<span style="font-size: 0.882em;"><span style="color: #24292E; --tt-darkmode-color: #9DA4AB;">Autoencoder是一种特殊的神经网络，被训练生成用来处理时序数据。算法架构由对称的两部分组成：编码器encoder和解码器decoder。在给定n维时序数据输入的前提下，Autoencoder的编码器输出m（m 转发了
页:
[1]