最近几个月我一直在做一个高性能压缩库起因挺简单在项目里试了一圈 zlib、zstd、LZ4 这些现成方案总在“压缩率”和“速度”之间被动妥协。zstd 压缩率确实漂亮但中高压缩级别的耗时让我没法接受LZ4 的解压速度无可挑剔压缩比放在文本类数据上又实在难看。最难受的是这些库的接口都是为通用场景设计的一旦我需要配合流式数据、自定义字典、特殊校验方式改动成本就高得离谱。折腾了一圈之后我决定干脆自己写一个高性能压缩库。这篇文章就把整个过程整理出来——包括算法选型的思路、最小可运行实现的关键路径、性能调优的具体手段以及我踩过的几个比较深的坑。我不打算把每个函数都贴一遍代码重点写清楚设计决策背后的理由以及那些跑基准测试才会暴露的问题。如果你也在考虑自研压缩模块或者单纯想知道一个压缩库从零到能用的过程里有哪些门道这篇应该能帮到你。1. 从零实现压缩库的动机不是轮子不够好是接口和场景不匹配先说清楚我为什么没有继续在现有库基础上打补丁。zlib、zstd、LZ4 这些库本身都非常成熟生产环境用完全没问题但它们解决的是“通用压缩需求”而不是“我的具体需求”。我当时的业务场景有三个硬约束前两个就把我逼到了自研的角落。第一个约束是数据流形态。我的数据是持续产生的日志流单条消息几十字节到几 KB 不等要求边收边压而且压缩后的每个块要能独立解压不能和前块产生依赖。这个需求用 zstd 也能做它支持分帧但每帧的字典上下文是独立的压缩率会掉一截。我想要的是一份自研场景的流式帧结构块内压缩、块间共享字典但整个流仍然可以部分解压。第二个约束是解压端的性能模型。我的解压场景跑在嵌入式 CPU 上L2 缓存很小LZ4 的解压速度快是因为它对缓存友好但它的压缩率在日志类重复文本上不够看。zstd 的分级压缩效果不错但解压时内存交换和哈希重建成本偏高在低缓存设备上有明显抖动。我需要的是“解压极快、压缩速度中等偏上、压缩率接近 zstd 的中档水平”这种组合现成库里找不到这个形态。第三个约束是格式自由度。我需要支持自定义的预置字典以便在压缩前把常用的消息模板预置进去小消息压缩率直接从 30% 提升到 60% 以上。现成库虽然也支持字典但字典文件格式和更新机制是它们定的我没法做成热更新。自研之后就简单了——字典本身就是压缩流的一部分我可以在任何块边界动态注入和更新字典这是通用库很难给的能力。这三个约束叠加下来自研已经不只是“效率问题”而是“能不能做到的问题”。所以我给这个压缩库定的目标很明确目标项具体指标压缩率文本类数据 20%–40% 原始体积命中模板场景 40%–60%压缩速度单线程 30–80 MB/s取决于预设级别解压速度200–400 MB/s依赖内存带宽不依赖复杂计算内存占用压缩端 ≤ 64KB 工作集解压端 ≤ 8KB流式接口支持任意字节边界输入输出块独立校验与解压这个目标表格是我写代码之前就先定死的因为压缩库这种项目最容易在优化过程中跑偏——性能指标不改算法选型就不会失控。2. 算法骨架LZ77变体打底Huffman收尾哈希链做索引压缩库的核心算法选型我把范围缩小到三种主流路线纯 LZ77、LZ77Huffman、以及 BWTMTFHuffman类似 bzip2。BWT 路线的压缩率上限更高但解压端需要逆变换内存模型不友好而且块内依赖性强直接不符合我“解压轻量”的约束第一轮就淘汰了。真正纠结的是纯 LZ77 和 LZ77Huffman。纯 LZ77 的优点是实现简单、解压极快——解压端只需要复制粘贴没有任何熵编码的开销。缺点也明显它对重复数据的压缩率不如熵编码组合。举个例子一段全英文文本压缩后纯 LZ77 可能只压缩掉 40%加上熵编码能到 50% 以上。如果你要压缩的是大量模板代码、日志、JSON 这类高冗余数据Huffman 带来的额外压缩率收益非常可观。所以最终骨架定为LZ77 变体负责找重复Huffman 负责二阶段压缩符号流。这个架构在 DEFLATEzlib里已经验证过几十年稳定性没问题我又针对现代 CPU 的内存带宽和缓存特性做了一些调整。具体来说我的 LZ77 变体和经典实现有三个关键差异匹配窗口从 32KB 扩展到 64KB。zlib 为了兼容性锁死 32KB我不用考虑历史包袱64KB 窗口在文本类数据上能多抓到一些跨边界重复。最小匹配长度从 3 字节提高到 4 字节。短匹配的收益很低还容易把哈希表打乱。代价是少量 3 字节重复丢失换来的是哈希更稳、结果更紧凑。哈希链长度动态调节。经典 zlib 用 4 级链每级链长度不同我用的是基于当前输入熵值的自适应链长——熵高随机数据多时缩短链长熵低重复数据多时延长链长。匹配搜索的数据结构我选了哈希链。拉链法在 LZ77 实现里最经典逻辑清晰、缓存局部性好不需要像后缀数组那样重建索引。每个 4 字节序列映射到一个 16 位哈希值哈希桶深度用环形数组实现链头存最新位置查找时沿链回溯。Huffman 编码这层我做了两个核心优化。第一字面量符号0–255和匹配长度符号256–287合并到同一棵树上编码减少符号表大小。第二距离编码单独用一棵小树避免距离值域过大拖累联合树性能。这种“联合树独立距离树”的设计平衡了编码密度和解码时的缓存访问次数。2.1 数据格式设计块边界、长度编码和控制位数据格式是整个库的契约必须先定。我设计的帧结构分三层帧头、块头、块体。帧头固定 16 字节包含魔数、版本号、熵编码类型、字典版本号、原始长度、压缩长度和 CRC32 校验。块头比较灵活支持三种块类型原始字节块适合不可压缩数据、LZ77 压缩块、以及带字典更新的特殊块。块体的符号流编码方式我参考了 DEFLATE 的思路但做了微调每个符号开头有 1 位控制位0 表示字面量1 表示匹配。字面量8 位原始字节直接进 Huffman 编码。匹配长度符号走联合树距离符号走独立树。长度编码我做了分段映射。3–8 字节用 2 bit 存偏移增量9–258 字节用 5 bit 存索引超出 258 的匹配会被拆分为多个匹配。这个长度上限参考了 DEFLATE 的 258 上限查表验证下来对绝大多数数据够用而且能把匹配长度的符号空间压到很小。距离编码的范围是 1–65536对应 64KB 窗口。距离越大压缩率越低而且大距离的匹配通常意味着数据模式重复节奏比较长不容易在短文本里出现。我把距离空间分成两张表1–255 用小树256–65536 用大树这样短距离匹配的编码密度非常高。2.2 为什么哈希索引选择链式而不是开放寻址写代码之前我把哈希表方案列了一遍开链法、线性探测、二次探测、Robin Hood、Cuckoo。最后选了链式变体——哈希桶数组 溢出链表。原因是这样。压缩端的哈希表更新极其频繁每个输入字节都要做一次插入操作。开放寻址在插入时的探测次数受负载因子影响如果负载因子控制得太低64KB 窗口 哈希表会吃掉大量内存如果控制得太高探测次数的方差会变大最坏情况下的延迟没法保证。链式哈希的插入永远是 O(1) 新节点挂到链表头删除由环形缓冲区的覆盖机制自动完成不需要显式删除。在嵌入式场景里最坏延迟和平均延迟同样重要。稳定性和可预测性对实时性敏感的系统来说就是生命线。3. 从零到能跑压缩端和解压端的关键路径实现这一节我拆开讲压缩端和解压端各自的最核心实现路径顺便解释一些我为什么这样写。代码不贴全量只贴最能体现设计决策的片段。3.1 压缩端主循环哈希更新、匹配查找与三元组生成压缩端主循环的伪代码结构是这样的while (input_pos input_end) { uint32_t seq read_u32(input_pos); uint16_t hash hash_seq(seq); uint32_t match_pos hash_table[hash]; // 候选位置 int match_len 0; // 沿着链查找最大查 step 步 for (int i 0; i chain_limit; i) { if (buffer[match_pos] seq) { match_len extend_match(match_pos, input_pos); if (match_len MIN_MATCH) break; } match_pos prev_table[match_pos WINDOW_MASK]; } // 插入当前位置 prev_table[input_pos WINDOW_MASK] hash_table[hash]; hash_table[hash] input_pos; if (match_len MIN_MATCH) { write_match(input_pos, match_pos, match_len); // 匹配段中间的哈希可以跳过更新节省大量哈希计算 for (int j 1; j match_len; j) { uint32_t seq_j read_u32(input_pos j); uint32_t hash_j hash_seq(seq_j); prev_table[(input_pos j) WINDOW_MASK] hash_table[hash_j]; hash_table[hash_j] input_pos j; } input_pos match_len; } else { write_literal(input_pos); input_pos 1; } }这里有个很关键的优化点匹配成功之后匹配段内部的每个位置仍然要插入哈希表但不需要做查找。因为这段位置的匹配已经被当前匹配覆盖了后面再扫描到这段时大概率会通过表里记录的起始位置找到更长或相等的匹配。不做查找只做插入哈希计算量能省下匹配长度占比那么大一块。extend_match函数要写得非常仔细因为它直接决定压缩率的极限。我用逐 8 字节对齐比较短于一整个字的尾部再用逐字节比较。这种写法在 ARM 和 x86 上都能编出比较高效的向量比较指令。static int extend_match(const uint8_t* a, const uint8_t* b, int max_len) { int len 0; while (len 8 max_len read_u64(a len) read_u64(b len)) { len 8; } while (len max_len a[len] b[len]) { len; } return len; }3.2 解压端核心符号流解码、Huffman解码与重叠拷贝解压端的核心是符号解码循环。每次读一个控制位然后分支处理字面量还是匹配。这个分支在乱序执行流水线上其实没什么问题真正的性能杀手是两点Huffman 解码的表结构以及匹配拷贝时源和目的缓冲区重叠的问题。Huffman 解码我用的是规范 Huffman 解码表canonical Huffman table提前把所有可能的位模式展开成直接查表结构。解码时不用逐位比特运算而是读入一个固定位数的前缀根据表的最大码长决定直接查表找到符号和实际码长。展开表的缺点是内存占用大但解压端 8KB 工作集限制下还是放得下因为我的 Huffman 表符号空间小字面量长度符号共 288 个距离符号 64 个。重叠拷贝是 LZ77 解压最容易写错又最影响性能的地方。如果匹配长度大于源位置和目的位置之间的距离不能用memcpy简单复制必须逐字节前进。我用一个分支处理距离 8 且源和目的不重叠或重叠区域距离大于拷贝长度直接用宽拷贝。距离 8逐字节复制并将这 8 字节的模板预加载到寄存器循环里按模板重复。第二种情况对应高度重复的数据比如大段空格用寄存器做了 8 字节宽度的模拟逐字节拷贝性能比纯字节循环高不少。static inline void copy_match(uint8_t* dst, const uint8_t* src, int len, int dist) { if (dist 8) { memcpy(dst, src, len); // 不重叠或安全重叠 } else { uint64_t pattern; memcpy(pattern, src, 8); // 预取模板到寄存器 while (len 8) { memcpy(dst, pattern, 8); dst 8; len - 8; } memcpy(dst, pattern, len); // 处理尾部 } }3.3 Huffman码树构建如何控制解码表内存和编码速度Huffman 树的构建发生在每次块数据积累到一定大小比如 16KB之后。流程是统计符号频次 → 构建树 → 生成码长表 → 写入块头。构建树我用的是堆排序法标准流程但编码时注意用先序遍历把码长稳定地输出方便解压端重建。码长表用 RLE 压缩后再写入因为绝大多数符号的码长集中在 5–9 位之间直接写表浪费空间。解码表不是两棵独立树而是字面量和长度符号共享一棵联合树距离单独一棵。这样解码循环在遇到字面量时直接输出字节遇到匹配时从联合树读长度符号再从距离树读距离符号省了一次树切换的指令分支。4. 性能调优实录从 12 MB/s 到 60 MB/s 的三次重构压缩库写完之后我先跑了一个 benchmark结果很打击人——压缩速度只有 12 MB/s比 zlib 的 level 6 还慢一半。目标值是 30–80 MB/s这个成绩连地板都不到。于是我开始了一轮接一轮的性能剖析和优化把三次影响最大的重构记录在这里。4.1 哈希函数的代价为什么我放弃了 FNV-1a 换成了简易乘法哈希第一次剖析发现热点集中在两个函数哈希计算和extend_match。其中哈希计算占了总 CPU 时间的 30%这显然不合理。最初的哈希函数我用了 FNV-1a 变体逐字节处理生成 16 位哈希。安全性没问题但对压缩这种每秒要算几百万次的场景来说逐字节操作无法充分利用 CPU 的宽寄存器。优化后我改成了乘法哈希——把 4 字节一次读入乘以一个固定常数然后取高位异或static inline uint16_t hash_seq(uint32_t seq) { uint32_t h seq * 0x9E3779B1u; // 黄金比例常数 h ^ h 16; return (uint16_t)(h 16); }这个改动效果立竿见影。乘法哈希把原本 4 次逐字节操作压缩成 1 次 32 位乘法和 1 次移位哈希计算在总耗时中的占比从 30% 降到了 9% 左右。压缩速度第一次拉升到 24 MB/s。关键教训哈希函数的选择标准在压缩库里不是“碰撞率越低越好”而是“碰撞率与计算成本的平衡点”。乘法哈希的碰撞率在随机分布下比 FNV-1a 略高但计算成本低了一个数量级整体收益远超损失。4.2 内存带宽瓶颈减少缓存行失效和哈希表随机访问第二次剖析时热点转移到哈希链的回溯查找。原因很典型随着输入数据变大哈希表中记录的位置分布越来越分散每次链回溯都是一次随机内存访问缓存行命中率很低。这个问题有两个解法。第一把哈希链的表项从 4 字节压缩到 2 字节。因为窗口大小是 64KB位置索引只需要 16 位2 字节的表项让整张表能放进 CPU L2 缓存。64KB 窗口意味着表本身只有 128KB现代 CPU 的 L2 轻松装下。这大幅减少了随机访问的缓存失效。第二改造链的组织结构。经典 LZ77 用单链表每次回溯要逐节点跳。我改成了间隔哈希——每 4 个位置选一个位置插主表其余位置插二级表。这样主表的链长减半每次回溯的缓存命中率更高代价是偶尔会错过短匹配。实测对文本数据压缩率影响小于 1%速度提升有 30%。第三次优化对象是extend_match的宽比较。最初用 4 字节对齐比较存在一个隐蔽的问题如果源地址不是 8 字节对齐每次比较会触发两次缓存行加载。改成允许非对齐的 8 字节读之后因为大部分 CPU 支持非对齐内存访问性能没有下降反而上升尤其在大匹配长度超过 32 字节时速度提升约 15%。4.3 块大小的自适应压缩速度和压缩率的动态权衡块大小是个容易被忽略的调参点。固定 16KB 块在短日志场景表现很好但遇到几十 MB 的大文本块太多会导致 Huffman 表频繁重建压缩率上不去。我实现了一个自适应块大小策略块大小根据近 N 个块的熵值动态调整。熵高时块缩小到 8KB减少无效的 Huffman 表重建熵低时块扩大到 64KB让重复模式充分跨块匹配。这个策略用 120 行代码实现换来的是基准语料上压缩率提升约 4%速度提升约 8%。这个参数不需要用户手动配置完全由库内部根据数据流特征自动调整。虽然坑了不少调试时间但最终的收益很值。5. 实测数据与横向对比我的库和 zstd、LZ4 到底差多少调优告一段落后我在四类数据集上做了基准测试英文维基百科转储文本型、系统日志模板重复型、JSON 接口响应混合型、以及随机字节不可压缩型。测试环境是 x86-64 的单线程模式所有库用默认参数和各自的 level 6 档位。数据集指标zstd level 6LZ4 default我的库默认档英文文本压缩率36.1%55.2%39.4%英文文本压缩速度28 MB/s320 MB/s58 MB/s英文文本解压速度410 MB/s1120 MB/s620 MB/s系统日志压缩率21.5%48.7%24.2%系统日志压缩速度35 MB/s410 MB/s76 MB/s系统日志解压速度430 MB/s1180 MB/s690 MB/sJSON数据压缩率33.7%51.0%36.8%JSON数据压缩速度31 MB/s380 MB/s64 MB/sJSON数据解压速度405 MB/s1150 MB/s640 MB/s随机字节压缩率100.1%100.2%100.0%这个结果符合我的预期。压缩率方面我比 zstd level 6 差 3–5 个百分点但比 LZ4 好 10 个百分点以上压缩速度比 zstd 快一倍左右比 LZ4 慢一个数量级解压速度接近 zstd和 LZ4 还有明显差距。最让我满意的部分是系统日志场景。因为自定义字典机制的存在预置模板命中后压缩率可以做到 18%比表格里的默认值更好而 zstd 和 LZ4 的字典机制和我的场景不完全兼容发挥不出这个优势。随机字节测试的结果 100.0% 说明不可压缩检测机制生效了——没有膨胀数据也没有傻乎乎地硬编码。压缩库面对随机数据时最怕的就是输出比输入还大这里我特意做了“原始块直通”的路径检测到熵值过高时整块不压缩直接透传加一个块的标记位就行。6. 踩坑记录字节序、窗口边界、以及熵编码的暗坑最后整理一下这个项目里踩过的几个值得记录的坑。这些坑要么花了我一整天的排查时间要么在特定场景下会导致崩溃或数据损坏。6.1 字节序假设为什么压缩流必须显式声明字节序第一个非常隐蔽的坑出现在我处理哈希序列读取时。read_u32在 x86 上是小端读取而在 ARM 上运行嵌入式版时是字节序依赖的。同一段输入数据在小端机器上压缩的哈希序列在大端机器上解压会算出来完全不同的匹配位置产生损坏的输出。这个问题有经验的开发者肯定会提前处理但写快速原型时很容易忽略。我做了两件事第一帧头里加一个字节序标记字段第二所有多字节读写都通过显式的大小端转换函数完成。等于把底层存储和上层逻辑完全隔离。6.2 滑动窗口右边界匹配长度越过窗口边界的处理压缩端extend_match比较匹配长度时一个不容易注意到的边界问题是匹配源位置在窗口内但匹配可能跨越窗口右边界——这部分数据还在当前输入缓冲区里理论上可以匹配但匹配完成后这些字节还没生成会导致解压端在窗口里找不到对应的源数据直接越界读取。解决办法是在比较循环中加上窗口边界检查一旦到达窗口尾就截断匹配。这个 bug 从表现上看是解压时偶发的内存崩溃定位花了比较长时间原因是它只在匹配长度非常长、且距离恰好接近窗口大小时才会触发单测里很难覆盖到。6.3 Huffman表极端情况全零数据和全相同数据全零字节流的测试数据会让 Huffman 树退化成单子树——只有两个符号码长分别为 1 和 2其他符号码长 0。如果码长表的 RLE 编码逻辑假设了至少一个非零码长这里就会出问题。另一个极端是全相同数据块比如 1MB 全部是字母 ALZ77 会生成大量距离为 1、长度为 258 的匹配。距离编码树里 1 的频次极高其他距离码长都被挤压得很长距离树的解码表构建很容易踩坑出现非法码长组合。这两个极端我在单测里明确强制覆盖避免了后期在真实数据上碰运气。6.4 解压端内存对齐非对齐访问在 ARM 上的代价x86 上非对齐访问只是可能慢一点ARM 上则是直接触发异常或性能断崖。解压端把匹配数据写入输出缓冲区时缓冲区起始地址不可能总是 8 字节对齐的。早期我在 ARM 板子上测试解压速度只有 x86 的 1/10后来发现就是非对齐写导致的。解决方法是写操作前先做字节对齐预处理先逐字节写直到目的地址对齐到 8 字节再切换成宽拷贝。源地址、目的地址、距离三者之间的对齐关系都要考虑这时copy_match里的距离阈值 8 也需要根据对齐状态动态调整。7. 阶段性总结与调整这个压缩库从提出需求到跑通基准测试用了大概 6 周时间中间真正写代码的时间只占一半剩下全是定位边界问题、调哈希参数、构造极端测试数据。如果让我重新来一遍会有几个调整一开始就把字节序和极端数据测试的框架搭起来而不是在原型跑通后才补。很多 bug 在早期定位成本远低于后期。哈希链的“间隔哈希”会在第一版就实现而不是在优化阶段才加。块大小自适应不放在第一版做先固定 16KB 把整条主流程跑稳再放开自适应参数也不迟。这个功能虽然收益不小但调试复杂度也高过早加进去会干扰主体调优。目前这个库已经稳定跑在几个内部数据集上压缩率、速度、解压开销都符合最初定的目标表。后续我计划继续做的方向有两个一是对照明 LLVM 的 LZ 代码生成手段尝试在匹配搜索阶段引入更激进的分层索引二是把压缩端的自适应级别选择做得更聪明根据平台的 CPU 频率动态决定匹配链长度和块大小。整个项目最大的收获不是压缩率数字本身而是理解了一个通用压缩库在各种约束博弈中的取舍逻辑。速度、内存、压缩率、格式自由度这四个维度没有免费午餐每个选择都是在“可接受的损失清单”里做权衡。你不可能什么都拿到能做的只是清晰列出需求的优先级然后让每一个技术决策都对得上前面的优先级排序。