常用压缩算法

gzip

gzip是基于DEFLATE的算法，它是LZ77和Huffman编码 的结合。DEFLATE的目的是为了取代LZW和其他受专利保护的数据压缩算法，因为这些算法在当时限制了压缩和其他流行的存档器的可用性（Wikipedia）。我们通常使用tar -czf命令来进行打包并且压缩的操作，z参数正是使用gzip的方式来进行压缩。DEFLATE标准（RFC1951）是一个被广泛使用的无损数据压缩标准。它的压缩数据格式由一系列块构成，对应输入数据的块，每一块通过LZ77 （基于字典压缩，就是将最高概率出现的字母以最短的编码表示）算法和Huffman编码进行压缩，LZ77算法通过查找并替换重复的字符串来减小数据体积。

文件格式如下：

• 一个10字节的报头，包含一个魔数(1f 8b)，压缩方法 （比如08用于DEFLATE），1字节的header flags，4字节的时间戳，compression flags和操作系统ID。
• 可选的额外headers，包括原始文件名、注释字段、“extra” 字段和header的CRC-32校验码lower half 。
• DEFLATE压缩主体。
• 8字节的footer，包含CRC-32校验以及原始未压缩的数据。

我们可以看到gzip是主要基于CRC和Huffman LZ77的DEFLATE算法，这也是后面ISA-L库的优化目标。

Brotli

Alakuijala和Szabadka在2013-2016年完成了Brotli规范，该数据格式旨在进一步提高压缩比，它在优化网站速度上有大量应用。Brotli规范的正式验证是由Mark Adler独立实现的。Brotli是一个用于数据流压缩的数据格式规范，它使用了通用的LZ77无损压缩算法、Huffman编码和二阶上下文建模（2nd order context modelling）的特定组合。大家可以参考这篇论文 ​ 查看其实现原理。

因为语言本身的特性，基于上下文的建模方法 （Context Modeling）可以得到更好的压缩比，但由于它的性能问题很难普及。当前比较流行的突破算法有两种：

• ANS：Zstd, lzfse
• Context Modeling：Brotli, bz2

Zstd

Zstd全称叫Zstandard，是一个提供高压缩比的快速压缩算法，主要实现的编程语言为C，是Facebook的Yann Collet于2016年发布的，Zstd采用了有限状态熵（Finite State Entropy，缩写为FSE）编码器。该编码器是由Jarek Duda基于ANS理论开发的一种新型熵编码器，提供了非常强大的压缩速度/压缩率的折中方案（事实上也的确做到了“鱼”和“熊掌”兼得）。Zstd在其最大压缩级别上提供的压缩比接近lzma、lzham和ppmx，并且性能优于lza或bzip2。Zstandard达到了Pareto frontier（资源分配最佳的理想状态），因为它解压缩速度快于任何其他当前可用的算法，但压缩比类似或更好。

对于小数据，它还特别提供一个载入预置词典的方法优化速度，词典可以通过对目标数据进行训练从而生成。

压缩级别可以通过 –fast指定，提供更快的压缩和解压缩速度，相比级别1会导致压缩比率的一些损失，如上表所示。Zstd可以用压缩速度换取更强的压缩比。它是可配置的小增量，在所有设置下，解压缩速度都保持不变，这是大多数LZ压缩算法（如zlib或lzma）共享的特性。

• 我们采用Zstd默认的参数进行了测试，压缩时间8.471s仅为原来的11.266%，提升了88.733%
• 解压时间3.211仅为原来的29.83%，提升约为70.169%。
• 同时压缩率也从2.548提升到了2.621。

LZ4

LZ4是一种无损压缩算法，每核提供大于500 MB/s的压缩速度（大于0.15 Bytes/cycle）。它的特点是解码速度极快，每核速度为多GB/s（ 约1 Bytes/cycle ）。从上面的Zstd的Benchmark对比中，我们看到了LZ4算法效果十分出众，因此我们也对LZ4进行了对比，LZ4更加侧重压缩解压速度，尤其是解压缩的速度，压缩比并不是它的强项，它默认支持1-9的压缩参数，我们分别进行了测试。

LZ4使用默认参数压缩速度十分优秀，比Zstd快很多，但是压缩比并不高，比Zstd压缩后多了206 MB，足足多了46%，这就意味着更多的数据传输时间和磁盘空间占用。即使是最大的压缩比也并不高，仅仅从1.79提升到了2.11，但是耗时却从5s提升到了51s。通过对比，LZ4的确在压缩率上并不是最优秀的方案，在2.x级别压缩率上基本上时间优势荡然无存，而且还有一点，就是LZ4目前官方并没有对多核CPU并行压缩的支持，所以在后续的对比中，LZ4丧失了压缩解压缩速度的优势。

Pigz

Pigz的作者Mark Adler，同时也是Info-ZIP的zip和unzip、GNU的gzip和zlib压缩库的共同作者，并且是PNG图像格式开发工作的参与者。Pigz是gzip的并行实现的缩写，它主要思想就是利用多个处理器和核。它将输入分成128 KB的块，每个块都被并行压缩。每个块的单个校验值也是并行计算的。它的实现直接使用了zlib和pthread库，比较易读，而且重要的是兼容gzip的格式。Pigz使用一个线程（主线程）进行解压缩，但可以创建另外三个线程进行读、写和检查计算，所以在某些情况下可以加速解压缩。

一些博客在i7 4790K这样的家用PC平台中测试Pigz的压缩性能时，并没有十分高的速度，但在我们真机验证的数据中提升要明显很多。通过测试，它的压缩时间执行速度只用了1.768s，充分发挥了我们平台物理机的性能，User时间（CPU时间之和）一共使用了1m30.569s，这和前面的使用gzip单线程的方式速度几乎是一个级别。压缩率2.5488和正常使用tar -czf几乎相差不多。

ISA-L Acceleration Version

ISA-L是一套在IA架构上加速算法执行的开源函数库，目的在于解决存储系统的计算需求。ISA-L使用的是BSD-3-Clause License ，因此在商业上同样可以使用。

使用过SPDK（Storage Performance Development Kit ）或者DPDK（Data Plane Development Kit）应该也听说过ISA-L ，前者使用了ISA-L的CRC部分，后者使用了它的压缩优化。ISA-L通过使用高效的SIMD （Single Instruction, Multiple Data）指令和专用指令，最大化的利用CPU的微架构来加速存储算法的计算过程。ISA-L底层函数都是使用手工汇编代码编写，并在很多细节上做了调优（现在经常要考虑ARM平台，本文中所提及的部分指令在该平台支持度不高甚至是不支持）。

ISA-L对压缩算法主要做了CRC、DEFLATE和Huffman编码的优化实现，官方的数据指出ISA-L相比zlib-1有5倍的速度提升。举例来说，不少底层的存储开源软件实现的CRC都使用了查表法，代码中存储或者生成了一个CRC value的表格，然后计算过程中查询值，ISA-L的汇编代码中包含了无进位乘法指令PCLMULQDQ对两个64位数做无进位乘法，最大化intel PCLMULQDQ指令的吞吐量来优化CRC的性能。更好的情况是CPU支持AVX-512，就可以使用VPCLMULQDQ（PCLMULQDQ在EVEX编码的512 bit版本实现）等其它优化指令集（查看是否支持的方式见“附录”）。

Pzstd

通过Pigz的测试，我们就在想，是否Zstd这样优秀的算法也可以支持并行呢，在官方的Repo中，我们十分惊喜地发现了一个“宝藏”。Pzstd是C++11实现的并行版本的Zstandard （Zstd也在这之后加入了多线程的支持），类似于Pigz的工具。它提供了与Zstandard格式兼容的压缩和解压缩功能，可以利用多个CPU核心。它将输入分成相等大小的块，并将每个块独立压缩为Zstandard帧。然后将这些帧连接在一起以产生最终的压缩输出。Pzstd同样支持文件的并行解压缩。解压缩使用Zstandard压缩的文件时，PZstandard在一个线程中执行IO，而在另一个线程中进行解压缩。

下图是和Pigz的压缩和解压缩速度对比，来自官方Github仓库（机器配置为：Intel Core i7 @ 3.1 GHz, 4 threads），效果比Pigz还要出色，具体对比数据见下文：