作者 | 李珲
编辑 | 尔悦
小 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 等算法，这些算法在上文中我们也都简单介绍过了。二阶段压缩是在一阶段压缩的基础上，再用通用压缩算法进行了压缩，以此来保证压缩率更高。
综上，我们可以看到压缩算法的选择还是非常多的，具体的程序可以根据压缩效果和成本综合选择。
