时间序列数据压缩算法简述

时间序列数据压缩算法简述

引言

时间序列数据是在许多应用程序和领域中生成的一种基本数据类型，例如金融、医疗保健、交通和智慧城市[1]。时间序列分析对于各种任务至关重要，包括异常检测、预测、分类和聚类等。然而，时间序列数据的庞大数量和复杂性可能对高效存储、检索和处理带来重大挑战[2]。

相比于传统的关系型数据库，时间序列数据库天生是为了时间序列数据处理而生。关系数据库往往采用传统的B+树存储结构以及行式存储的方式。这种存储结构的设计方案往往适合读多写少的场景，来提高数据查询性能，用以减少磁盘或者网络 I/O。

然而，在这种设计上，由于绝大部分设计和资源都是为了读取数据，在每插入一条新记录时，都要同步更新相应的存储结构。数据库往往还要先找到所要插入的数据位于B+ 树中的哪个节点，存储页面中的哪一个页，查看相应的键是不是已经存在等等，这都会大量增加插入操作的时间开销。因此，以目前时间序列数据库开源社区使用最为广泛的InfluxDB[3]为例，其采用了基于LSM树的存储结构，并对此进行了一些特异性优化开发，使得数据库写入的能力提高很多倍。

随着时间的推移，早期产生的数据所具有的价值会越来越低，对于时间序列数据库的应用场景之一监控场景来说，用户更可能仅仅关注当前时刻或近期内数据库的状态参数，而较早产生的数据会因时间积累越来越多且仅有较低概率会被查询。因此有必要对早期的数据进行一定程度的压缩，同时考虑到该类型数据查询价值较低，在提高压缩比的同时又能够尽可能保留原始数据的一些特征便成为了一个重要的问题。这样可以更好地对数据库资源合理规划、缓解数据库管理数据的压力，降本增效，更好的为数据的存储和查询赋能。

为了应对这些挑战，越来越需要专门的算法和数据结构来压缩并索引时间序列数据。数据压缩算法主要在数据压缩比、数据解压缩速度、数据压缩精度这几方面做权衡，指导了时间序列数据压缩的各种技术的发展。

数据压缩算法分类

对于时间序列数据，有几种常用的压缩算法。可以根据压缩再解压后是否丢失精度问题，将压缩算法分为两类：分别是无损压缩算法和有损压缩算法。 

无损压缩算法的特点是压缩前后数据的完整性保持不变，即压缩后的数据可以完全恢复到压缩前的原始数据。常见的无损压缩算法包括：

• 基于差分编码的算法[7，8]：差分编码算法通过计算相邻时间点之间的差异来压缩时间序列数据，减少冗余信息的存储。
• 基于霍夫曼编码的算法[9，10]：使用变长编码，高频数据用较短的代码表示，而低频数据用较长的代码表示。 

有损压缩算法通过去除一些冗余信息来达到较高的压缩率，但压缩后的数据不能完全恢复到原始数据，可能存在一定程度的误差。常见的有损压缩算法包括： 

• 基于小波变换的算法[11，12]：小波变换可以将时间序列数据分解成多个频率子带，提取时间序列数据的主要特征，然后通过编码对这些特征进行压缩。 
• 基于离散余弦变换的算法：离散余弦变换可以将时间序列数据转换为频域信号，通过保留高频分量和抑制低频分量实现压缩。

广泛应用的压缩算法简介

• Gorilla[13]是一种基于二进制元组编码的时间序列数据压缩算法。它的优点包括高压缩率、高压缩速度和较低的存储要求，但由于需要大缓冲区，可能会受到内存限制的影响。 
• LZ4[14]是一种通用数据压缩算法，也可用于时间序列数据压缩。其优点包括压缩速度快、压缩延迟低、压缩比好，但在一些特殊的时间序列数据分布中，可能会出现压缩性能不佳的情况。
• Zstandard[15]是一种基于LZ77算法的压缩算法，适用于一般的压缩解压任务， 也可以用于时间序列数据的压缩。其优点是压缩比高，解压延迟低，压缩速度可调，但压缩时间可能较长。 
• Snappy[16]是一种快速压缩算法，适用于各种类型的数据，包括时间序列数据。其优点包括压缩速度高、压缩延迟低、压缩比可靠，但压缩比相对较低。 
• LFZip[17]是一种基于分段和拟合算法的时间序列数据压缩算法，具有良好的压缩比和速度。它的缺点是不能处理异常值和噪声，需要调整一些参数以适应 同的数据分布。 
• Chimp[18]是一种基于采样的时间序列数据压缩算法，具有高压缩比和速度，可以动态适应不同的数据分布。它的缺点是需要足够的采样频率来保证压缩精度，并且处理异常值的能力较弱。 
• Sprintz[19]是一种简单有效的无损数据压缩算法。其主要优点包括压缩比高、速度快、复杂度低。但是Sprintz算法对数据相关性的依赖度很高，需要额外的一些位来存储差异，导致存储量相对较低。

在 CnosDB 中应用压缩算法

在 CnosDB 中，可以在创建数据库时对特定的属性指定压缩方法，CnosDB 中支持的压缩方法包括：

• Delta 
• Gzip 
• Bzip 
• Gorilla 
• Snappy
• Zstd 
• Zlib
• BitPack
• SDT
• DeadBand

语法结构如下：

CREATE TABLE TIMESERIES(
    column1 BIGINT CODEC(DELTA),
    name STRING CODEC(GZIP),
    age BIGINT UNSIGNED CODEC(NULL),
    marriage BOOLEAN,
    ID DOUBLE CODEC(GORILLA)
)

在创建数据库时，指定属性的类型后，附加一个CODEC（），括号内是压缩方法，来达到指定压缩方式的效果。

小结

时间序列的压缩主要还是围绕着时间序列的连续性好、相关性强的特点设计压缩算法，而由于数据规模通常较大，以一定精度损失换取极高压缩比的有损压缩算法更广泛地被应用。

本文简单介绍了时间序列压缩任务的来源，压缩算法的分类，并对常见压缩算法的优缺点进行了简介，在CnosDB中的应用也只是略有提及，感兴趣者可以查看参考文献中的内容。

参考文献

［1］ FU T-C. A review on time series data mining ［J］. Engineering Applications of Artificial Intelligence，2011，24（1）：164-181. 

［2］ WLODARCZYK T W. Overview of time series storage and processing in a cloud environment ［C］ // 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings，［S.l.］，2012：625-628.

［3］ NAQVI S N Z，YFANTIDOU S，ZIMÁNYI E. Time series databases and influxdb［J］. Studienarbeit, Université Libre de Bruxelles，2017，12

［4］ ANH V N，MOFFAT A. Index compression using 64-bit words［J］. Software: Practice and Experience，2010，40（2）：131-147. 

［5］ GOLOMB S. Run-length encodings (corresp.) ［J］. IEEE transactions on information theory，1966，12（3）：399-401. 

［6］ RICE R F. Some practical universal noiseless coding techniques［M］ // . 1979. 

［7］ CANDY J. A use of double integration in sigma delta modulation ［J］. IEEE transactions on communications，1985，33（3）：249-258. 

［8］ O’NEAL J. Differential pulse-code modulation (PCM) with entropy coding［J］. IEEE Transactions on Information Theory，1976，22（2）：169-174. 

［9］ OSWAL S，SINGH A，KUMARI K. Deflate compression algorithm ［J］. International Journal of Engineering Research and General Science，2016，4（1） ：430-436. 

［10］ GAILLY J-L，ADLER M. GNU gzip ［J］. GNU Operating System，1992. 

［11］ ZHANG Q，BENVENISTE A. Wavelet networks［J］. IEEE transactions on Neural Networks，1992，3（6）：889-898. 

［12］ KINGSBURY N. Complex wavelets for shift invariant analysis and filtering of signals［J］. Applied and computational harmonic analysis，2001，10（3）： 234-253. 

［13］ PELKONEN T，FRANKLIN S，TELLER J，et al. Gorilla: A fast, scalable, inmemory time series database ［J］. Proceedings of the VLDB Endowment，2015， 8（12）：1816-1827. 

［14］ COLLET Y，OTHERS. Lz4: Extremely fast compression algorithm［J］. code. google. com，2013. 

［15］COLLET Y. Zstandard-fast real-time compression algorithm［J］. Github repository [online]，2018. 

［16］ GUNDERSON S H. Snappy: A fast compressor/decompressor［J］. code. google. com/p/snappy，2015. 

［17］ CHANDAK S，TATWAWADI K，WEN C，et al. LFZip: Lossy compression of multivariate floating-point time series data via improved prediction ［C］ // 2020 Data Compression Conference (DCC)，［S.l.］，2020：342-351. 

［18］ LIAKOS P，PAPAKONSTANTINOPOULOU K，KOTIDIS Y. Chimp: efficient lossless floating point compression for time series databases ［J］. Proceedings of the VLDB Endowment，2022，15（11）：3058-3070. 

［19］ BLALOCK D，MADDEN S，GUTTAG J. Sprintz: Time series compression for the internet of things ［J］. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies，2018，2（3）：1-23