3、LZ4算法原理：LZ77变体、哈希链、匹配查找、快速解压设计

LZ4 是目前工业界应用最广泛的超高速压缩算法之一，其核心设计目标并非追求极限压缩比，而是在压缩速度与解压速度之间取得极致的平衡。理解 LZ4 的原理，需要从 LZ77 的经典范式出发，剖析其在哈希链构建、匹配查找策略以及解压端简化设计上的独特取舍。本章将深入拆解 LZ4 的算法内核，帮助你在面对压缩选型时，能够准确判断其适用边界。

LZ4 的设计哲学可以概括为“以空间换时间，以简化换速度”。它继承了 LZ77 的滑动窗口思想，但摒弃了复杂的熵编码（如 Huffman 或 Arithmetic Coding），转而采用一种高度简化的 格式。这种设计使得压缩端能够以极快的速度完成匹配查找，而解压端则几乎不需要任何计算开销，仅通过内存拷贝即可完成数据还原。下面我们从三个层面拆解其核心机制。

3.1 LZ77 变体：从滑动窗口到有限状态机

LZ4 本质上是一个 LZ77 的变体实现。经典的 LZ77 算法维护一个滑动窗口，在窗口中查找最长匹配字符串，并输出 <偏移量, 匹配长度> 对。LZ4 在此基础上做了两个关键简化：固定最小匹配长度和有限偏移范围。

• 最小匹配长度（Min Match）：LZ4 规定匹配长度至少为 4 字节。这是因为一个 需要至少 2 字节存储偏移量，加上长度信息，如果匹配长度小于 4，压缩后的数据反而比原始数据更大。这个阈值是经过大量数据统计得出的经验值。
• 偏移量范围：LZ4 使用 16 位（2 字节）存储偏移量，因此最大可回溯距离为 65535 字节（64KB）。这构成了 LZ4 的滑动窗口大小。超过这个距离的重复数据将无法被引用。
• 无熵编码：与 LZMA、zlib 等算法不同，LZ4 不对 序列进行二次压缩。 直接以字节形式输出，这避免了熵编码带来的 CPU 开销，但也意味着压缩比相对较低。

这种设计使得 LZ4 的压缩过程可以看作一个确定性有限状态机：读取字节、计算哈希、查找候选、决定是否输出 。每一步都是固定开销的 O(1) 操作，没有复杂的动态规划或概率模型。

3.2 哈希链与匹配查找：速度与压缩率的平衡点

LZ4 的匹配查找机制是其性能的关键。它使用一个哈希表（Hash Table）来加速查找过程，而不是像朴素 LZ77 那样遍历整个滑动窗口。

3.2.1 哈希表结构与插入策略

LZ4 的哈希表是一个大小为 4096（2^12）的数组，每个元素存储一个 32 位的整数，表示输入流中的位置偏移。哈希函数将当前 4 字节序列映射到表中的一个槽位。当新数据到来时，LZ4 执行以下操作：

1. 读取当前位置的 4 字节，计算哈希值 hash = (sequence * 2654435761) >> 20（实际实现中采用乘法散列）。
2. 将哈希值对应的槽位中的旧位置取出，作为候选匹配位置。
3. 将当前的位置写入该槽位，覆盖旧值。

这种策略被称为“无链哈希”或“单槽哈希”。与 LZ77 中常见的哈希链（Hash Chain）不同，LZ4 的每个槽位只保存一个位置。这意味着如果多个不同的 4 字节序列映射到同一个槽位，后写入的会覆盖先前的。这种设计牺牲了部分匹配查找的准确性，但避免了链式遍历的开销。

3.2.2 匹配确认与扩展

当获得候选位置后，LZ4 会进行匹配确认：比较当前位置与候选位置的 4 字节是否完全一致。如果一致，则继续向后扩展匹配长度，直到遇到不匹配的字节或达到最大匹配长度（255 字节）。如果 4 字节不一致，则放弃该候选，直接输出字面量（Literal）。

值得注意的是，LZ4 在匹配扩展时采用“快速路径”优化：它使用 64 位或 128 位的宽比较指令（如 x86 的 rep cmpsb 或 ARM 的 ldp），一次比较 8 或 16 个字节，从而大幅减少循环次数。

参数	LZ4 默认值	对性能的影响	对压缩率的影响
哈希表大小	4096 槽位	表越小，缓存命中率越高，速度越快	表越小，冲突越多，匹配率下降
最小匹配长度	4 字节	减少无效 输出	过小则压缩率下降，过大则匹配率下降
最大匹配长度	255 字节	限制 长度字段为 1 字节	超过 255 的匹配需拆分为多个
搜索深度	1（无链）	固定 O(1) 查找时间	可能错过更长的匹配

3.3 快速解压设计：零查找、零分支的极致优化

LZ4 的解压器设计比压缩器更为精简，这也是其解压速度能达到数 GB/s 的关键。解压过程完全不需要哈希表、不需要查找匹配，只需要顺序读取 并执行内存拷贝。

3.3.1 格式解析

LZ4 的压缩数据流由一系列 组成，每个 的格式如下：

 (1字节) | 字面量长度扩展 (可选) | 字面量数据 | 匹配偏移量 (2字节) | 匹配长度扩展 (可选)

的高 4 位存储字面量长度（0-15），低 4 位存储匹配长度（0-15）。如果长度值等于 15，则后续会追加额外的字节来扩展长度（每字节最多增加 255）。这种设计使得短匹配和短字面量只需 1 字节开销，而长匹配则通过扩展字节处理。

3.4.2 解压流程

解压器的核心循环如下：

1. 读取 1 字节 ，解析出字面量长度 litLen 和匹配长度 matchLen。
2. 如果 litLen 为 15，则继续读取扩展字节，累加得到实际字面量长度。
3. 从输入缓冲区直接拷贝 litLen 字节到输出缓冲区（使用 memcpy）。
4. 如果 matchLen 为 15，则继续读取扩展字节，累加得到实际匹配长度（需加上最小匹配 4）。
5. 读取 2 字节偏移量 offset，从输出缓冲区当前位置向前偏移 offset 字节处，拷贝 matchLen 字节到当前位置。
6. 重复上述步骤，直到输入流结束。

这个流程中，没有任何条件分支依赖数据内容（除了判断长度是否为 15），也没有任何查找操作。所有的内存访问都是顺序的，CPU 的分支预测器可以完美预测循环路径。此外，LZ4 解压器还利用了 memcpy 的宽位拷贝优化，在支持 SIMD 的平台上，单次可拷贝 16 或 32 字节。

3.4 案例拆解：日志压缩场景的 LZ4 选型与调优

我们以一个实际的后端日志采集系统为例，说明 LZ4 原理在工程中的应用。该系统每天产生约 200GB 的文本日志，需要实时压缩后存储到对象存储中。

初始目标：在保证压缩速度不低于 500MB/s 的前提下，尽可能降低存储成本。

关键输入数据：日志行平均长度 512 字节，重复模式较多（如时间戳前缀、日志级别、常见错误信息），但行与行之间也存在大量随机参数。

分析判断过程：

• 如果使用 gzip（LZ77 + Huffman），压缩率可达 10:1，但压缩速度仅 50MB/s，无法满足实时性要求。
• 如果使用 LZ4，压缩率约为 4:1，但压缩速度可达 800MB/s，解压速度可达 4GB/s。
• 考虑到日志数据需要被后续分析任务频繁读取，解压速度同样重要。LZ4 的解压速度是 gzip 的 10 倍以上。

实际操作步骤：

1. 采用 LZ4 默认压缩级别（HC 级别不适用，因为其压缩速度仅 100MB/s）。
2. 将日志按 1MB 块大小进行独立压缩，便于并行处理和随机读取。
3. 在压缩前对日志行进行简单的预过滤：去除多余空格、统一时间戳格式，以提高重复模式的密度。

结果对比：

指标	gzip -1	LZ4	LZ4 HC
压缩速度	45 MB/s	780 MB/s	120 MB/s
解压速度	350 MB/s	4200 MB/s	4100 MB/s
压缩率	11.2:1	4.3:1	5.1:1
CPU 占用	2.5 核	0.4 核	1.2 核

风险与代价：LZ4 的压缩率较低，导致存储成本比 gzip 高约 2.6 倍。但考虑到节省的 CPU 资源可以用于更多日志处理任务，且对象存储成本远低于计算成本，最终选择了 LZ4。

复盘经验：LZ4 最适合“写多读少”且对实时性要求高的场景。如果日志需要长期归档且很少读取，可以先用 LZ4 实时压缩，再在后台用 xz 进行二次压缩以降低存储成本。这种分层压缩策略在大型系统中非常常见。

3.5 常见误区与总结

在实际使用 LZ4 时，开发者常陷入以下几个误区：

• 误区一：认为 LZ4 压缩率低就一无是处。实际上，LZ4 在文本、JSON、日志等“半结构化”数据上通常能达到 3-5 倍的压缩率，对于已经压缩过的数据（如 JPEG、ZIP），任何算法都难以再压缩，此时 LZ4 的“快速失败”特性反而是一种优势。
• 误区二：盲目使用 LZ4 HC（High Compression）。HC 版本通过增加搜索深度（默认 12 次）来提升压缩率，但压缩速度会下降 5-8 倍。只有在压缩速度不是瓶颈，且存储成本极高时才应考虑。
• 误区三：忽略解压速度的对称性。某些场景（如数据库备份）压缩一次、解压多次，此时应优先选择解压速度快的算法。LZ4 的解压速度是 zlib 的 5-10 倍，这是其核心优势。
• 误区四：自定义实现时未处理重叠拷贝。如前所述，这是最常见的 bug 来源。务必参考官方实现中的 LZ4_copy8 或 LZ4_wildCopy 函数。