最近几个月我一直在做一个高性能压缩库，起因挺简单：在项目里试了一圈 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、LZ77+Huffman、以及 BWT+MTF+Huffman（类似 bzip2）。BWT 路线的压缩率上限更高，但解压端需要逆变换，内存模型不友好，而且块内依赖性强，直接不符合我“解压轻量”的约束，第一轮就淘汰了。
真正纠结的是纯 LZ77 和 LZ77+Huffman。纯 LZ77 的优点是实现简单、解压极快——解压端只需要复制粘贴，没有任何熵编码的开销。缺点也明显：它对重复数据的压缩率不如熵编码组合。举个例子，一段全英文文本压缩后，纯 LZ77 可能只压缩掉 40%，加上熵编码能到 50% 以上。如果你要压缩的是大量模板代码、日志、JSON 这类高冗余数据，Huffman 带来的额外压缩率收益非常可观。
所以最终骨架定为：LZ77 变体负责找重复，Huffman 负责二阶段压缩符号流。这个架构在 DEFLATE（zlib）里已经验证过几十年，稳定性没问题，我又针对现代 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 6 | LZ4 default | 我的库默认档 |
|---|---|---|---|---|
| 英文文本 | 压缩率 | 36.1% | 55.2% | 39.4% |
| 英文文本 | 压缩速度 | 28 MB/s | 320 MB/s | 58 MB/s |
| 英文文本 | 解压速度 | 410 MB/s | 1120 MB/s | 620 MB/s |
| 系统日志 | 压缩率 | 21.5% | 48.7% | 24.2% |
| 系统日志 | 压缩速度 | 35 MB/s | 410 MB/s | 76 MB/s |
| 系统日志 | 解压速度 | 430 MB/s | 1180 MB/s | 690 MB/s |
| JSON数据 | 压缩率 | 33.7% | 51.0% | 36.8% |
| JSON数据 | 压缩速度 | 31 MB/s | 380 MB/s | 64 MB/s |
| JSON数据 | 解压速度 | 405 MB/s | 1150 MB/s | 640 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 全部是字母 A），LZ77 会生成大量距离为 1、长度为 258 的匹配。距离编码树里 1 的频次极高，其他距离码长都被挤压得很长，距离树的解码表构建很容易踩坑，出现非法码长组合。这两个极端我在单测里明确强制覆盖，避免了后期在真实数据上碰运气。
6.4 解压端内存对齐：非对齐访问在 ARM 上的代价
x86 上非对齐访问只是可能慢一点，ARM 上则是直接触发异常或性能断崖。解压端把匹配数据写入输出缓冲区时，缓冲区起始地址不可能总是 8 字节对齐的。早期我在 ARM 板子上测试，解压速度只有 x86 的 1/10，后来发现就是非对齐写导致的。
解决方法是写操作前先做字节对齐预处理：先逐字节写，直到目的地址对齐到 8 字节，再切换成宽拷贝。源地址、目的地址、距离三者之间的对齐关系都要考虑，这时copy_match里的距离阈值 8 也需要根据对齐状态动态调整。
7. 阶段性总结与调整
这个压缩库从提出需求到跑通基准测试用了大概 6 周时间，中间真正写代码的时间只占一半，剩下全是定位边界问题、调哈希参数、构造极端测试数据。如果让我重新来一遍，会有几个调整：
- 一开始就把字节序和极端数据测试的框架搭起来，而不是在原型跑通后才补。很多 bug 在早期定位成本远低于后期。
- 哈希链的“间隔哈希”会在第一版就实现，而不是在优化阶段才加。
- 块大小自适应不放在第一版做，先固定 16KB 把整条主流程跑稳，再放开自适应参数也不迟。这个功能虽然收益不小，但调试复杂度也高，过早加进去会干扰主体调优。
目前这个库已经稳定跑在几个内部数据集上，压缩率、速度、解压开销都符合最初定的目标表。后续我计划继续做的方向有两个：一是对照明 LLVM 的 LZ 代码生成手段，尝试在匹配搜索阶段引入更激进的分层索引；二是把压缩端的自适应级别选择做得更聪明，根据平台的 CPU 频率动态决定匹配链长度和块大小。
整个项目最大的收获不是压缩率数字本身，而是理解了一个通用压缩库在各种约束博弈中的取舍逻辑。速度、内存、压缩率、格式自由度，这四个维度没有免费午餐，每个选择都是在“可接受的损失清单”里做权衡。你不可能什么都拿到，能做的只是清晰列出需求的优先级，然后让每一个技术决策都对得上前面的优先级排序。
