作者 | 李珲
编辑 | 尔悦
小 T 导读：家喻户晓，压缩算法的目标次要是为了缩小存储空间或传输带宽，通过把原始数据转换成比原始格局更紧凑的模式，来进步数据的传输、存储和解决效率。咱们相熟的很多压缩软件都是借助非常复杂的算法才得以实现，像一些时序数据库（Time-Series Database），比方 TDengine，也是通过内置压缩性能，能力实现对时序数据的高比例压缩。那具体来说，数据压缩的流程是怎么的？时序数据库中常见的数据编码和压缩算法又有哪些呢？本篇文章将会从具体实际登程进行教训分享。
数据压缩 / 解压缩的流程
压缩：输出原始数据，通过压缩器编码后，输入压缩后的数据。
input data —-> compressor —-> coded data
解压缩：输出压缩过的数据，通过解压缩器解码 / 重建后，输入原始数据。
coded data —-> decompressor —-> output data
如果输入数据和输出数据始终完全相同，那么这个压缩计划被称为可逆压缩，也称无损编码器。否则，它就是一个非可逆压缩，也称有损编码器。
- 可逆压缩：可能无失真地从压缩后的数据重构，精确地还原原始数据。可用于对数据准确性要求严格的场合，如可执行文件和一般文件的压缩、磁盘的压缩，也可用于多媒体数据的压缩。该办法的压缩比拟小，如差分编码、RLE、Huffman 编码、LZW 编码、算术编码。
- 非可逆压缩：有失真，不能齐全精确地复原原始数据，重构的数据只是原始数据的一个近似。可用于对数据的准确性要求不高的场合，如多媒体数据的压缩。该办法的压缩率比拟高，例如预测编码、音感编码、分形压缩、小波压缩、JPEG/MPEG。
咱们都晓得，数据在计算机外部是以二进制形式示意和存储的，因而，艰深地讲，数据压缩就是以起码的比特数示意数据对象。数据压缩的实质是用计算工夫换取存储空间，不同数据类型对应不同的数据压缩算法，不存在某个压缩算法可能压缩任意数据。数据压缩说到底是对数据趋势性、规律性的总结，这个数据规律性可分为基于内容（比方视频的帧与帧之间、图像的像素与像素之间的类似）、基于示意（比方变换编码、熵编码）和基于码流（比方差量压缩、深度压缩）等多种级别。
举一个数据压缩的简略例子：给定一个字符串”this is a example”，失常状况下，每个字符占用 8 个比特位，假如该字符串含有 17 个字符（蕴含空格），每一个字符呈现的频率别离是 a(2),e(2),h(1),i(2),m(1),p(1), t(1),s(2),x(1),l(1), 空格 (3). 当初咱们依照字母呈现的频率进行编码，用 111 示意“空格”，001 示意“a”，110 示意“e”，011 示意“i”，000 示意“s”，0101 示意“h”，1011 示意“m”，1000 示意“p”，0100 示意“t”，1010 示意“x”，1001 示意“l”。最初”this is a example”被编码成 010001010110001110110001110011101010001101110001001110，共 54 个比特。相比未压缩前的 136 比特，存储空间放大了 2.5 倍。
时序数据是如何被压缩的？
时序数据库（Time-Series Database）中常见的数据编码和压缩算法有如下几种：
- 霍夫曼编码
下面例子中提到的就是霍夫曼编码。这是一个流传最为宽泛的压缩计划，19 世纪 50 年代，David Huffman 在他的论文“一种构建极小多余编码的办法”中第一次形容了这种办法。霍夫曼编码通过失去给定字母表的最优前缀码进行工作。
要留神的是，这里的一个前缀码代表一个数值，并要保障字母表中的每个符号的前缀码不会成为另一个符号前缀码的前缀。例如，如果 0 是咱们第一个符号 A 的前缀码，那么字母表中的其余符号都不能以 0 开始。因为前缀码使比特流解码变得清晰明确，因而这种机制还是很有用的。
- 游程编码（英语：run-length encoding，缩写 RLE）
一种与数据性质无关的无损数据压缩技术，基于“应用变动长度的码来取代间断反复呈现的原始数据”来实现压缩。举例来说，一组字符串“AAAABBBCCDEEEE”，由 4 个 A、3 个 B、2 个 C、1 个 D、4 个 E 组成，通过 RLE 可将字符串压缩为 4A3B2C1D4E。其长处是简略、速度快，能将间断且重复性高的数据压缩成小单位。毛病也是很显著的，重复性低的数据压缩成果不好。
- XOR
该算法是联合遵循 IEEE754 规范浮点数存储格局的数据特色设计的特定算法，第一个值不压缩，前面的值是跟第一个值计算 XOR（异或）的后果，如果后果雷同，仅存储一个 0，如果后果不同，存储 XOR 后的后果。该算法受数据稳定影响较大，稳定越激烈，压缩成果越差。
- Delta
差分编码又称增量编码，编码时第一个数据不变，其余数据转换为上一个数据的 delta。其原理与 XOR 相似，都是计算相邻两个数据的差别。该算法利用宽泛，如须要查看文件的历史更改记录（版本控制、Git 等）。但在时序数据库中这种算法很少独自应用，个别会搭配 RLE、Simple8b 或者 Zig-zag 一起应用，压缩成果更好。
- Delta-of-Delta
又名二阶差分编码，是在 Delta 编码的根底上再一次应用 Delta 编码，比拟适宜编码枯燥递增或者递加的序列数据。例如 2,4,4,6,8 , Delta 编码后为 2,2,0,2,2，再 Delta 编码后为 2,0,-2,2,0。通常其也会搭配 RLE、Simple8b 或者 Zig-zag 一起应用。
- Zig-zag
Zig-zag 的呈现是为了解决 varint 算法对正数编码效率低的问题，它的原理非常简单，是将标记位后移至开端，并去掉编码中多余的 0，从而达到压缩的成果。对于比拟小的数值压缩效率很高，然而对于大的数据效率岂但没有晋升可能还会有所降落。因而，Zig-zag 通常和 Delta 编码搭配，Delta 能够很好地将大数值数据变为较小的数值。
- Snappy
Snappy 压缩算法借鉴了 LZ77 算法的思路，因为 LZ77 算法中模式匹配过程有较高的工夫复杂度，Google 对其做了许多优化，并于 2011 年对外开源。其原理是假如咱们有一个序列 S=[9,1,2,3,4,5,1,2,3,4]，匹配发现子序列 S~2,5~=[1,2,3,4] 与 S~7,10~=[1,2,3,4] 是雷同的，于是将该序列编码为 S=[9,1,2,3,4,5,6,(2,4)]，2 示意开始地位，4 示意位数。Snappy 的长处是速度快，压缩率正当，在泛滥开源我的项目中应用较为宽泛，比方 Cassandra、Hadoop、MongoDB、RocksDB、Spark、InfluxDB 等。
- LZ4
LZ4 数据压缩算法属于面向字节的 LZ77 压缩计划家族，压缩比并不高，它的特点是解码速度极快。据官网测试基准 lzbench 的测试后果，默认配置下其解压速度高达 4970MB/s。
- Simple8b
Simple8b 是 64 位算法，实现将多个整形数据（在 0 和 1<<60 -1 之间）压缩到一个 64 位的存储构造中。其中前 4 位示意选择器，前面 60 位用于存储数据。长处是简略高效，定长编码保障理解压效率，但对于大整数或者浮动较大的值来说压缩率较低，该算法实用于范畴较小的无符号整数。
- LZO
LZO 是块压缩算法，同样属于 LZ77 压缩计划家族，该算法的指标是疾速压缩和解压缩，并非压缩比。相比之下，LZ4 的解压速度更快。因为块中寄存的数据类型可能多种多样，整体的压缩成果远没有针对某一种数据类型进行压缩的算法好。
- DEFLATE
DEFLATE 是同时应用了 LZ77 算法与霍夫曼编码（Huffman Coding）的一个经典无损数据压缩算法。实际上 DEFLATE 只是一种压缩数据流的算法，该算法是 zip 文件压缩的默认算法，在 gzip、zlib 等算法中都有封装。
- Zstandard
Zstandard(Zstd) 的设计目标是提供一个相似于 DEFLATE 算法的压缩比，但成果要更快，特地是解压缩。它的压缩级别从负 5 级（最快）到 22 级（压缩速度最慢，然而压缩比最高）间能够调节。在文本日志压缩场景中，其压缩性能与 LZ4、Snappy 相当甚至更好。Linux 内核、HTTP 协定、Hadoop、HBase 等都曾经退出对 Zstd 的反对，能够预感，Zstd 将是将来几年里被宽泛关注的压缩算法。
- Bit-packing
Bit-packing（位压缩）压缩算法基于不是所有的整型都须要 32 位或者 64 位来存储这一前提，从咱们要压缩的数据中删除不必要的位。比方一个 32 位的整型数据，其值的范畴在【0,100】之间，则能够用 7 位示意。
最初以 TDengine Database 为例，咱们来看一下时序数据库在具体实现上会如何使用压缩算法。TDengine Database 提供了三种压缩选项：无压缩、一阶段压缩和两阶段压缩。
一阶段压缩依据数据的类型进行了相应的压缩，压缩算法包含 delta-delta 编码、simple 8B 办法、zig-zag 编码、LZ4 等算法，这些算法在上文中咱们也都简略介绍过了。二阶段压缩是在一阶段压缩的根底上，再用通用压缩算法进行了压缩，以此来保障压缩率更高。
综上，咱们能够看到压缩算法的抉择还是十分多的，具体的程序能够依据压缩成果和老本综合抉择。
想理解更多 TDengine Database 的具体细节，欢送大家在 GitHub 上查看相干源代码。