前阵子给一条数据传输链路加压缩模块市面上的通用压缩库换来换去始终不太顺手有的压缩比漂亮但解压时延不稳定有的吞吐高但压完体积还不如直接传。最后干脆自己写了一个高性能压缩库把从算法骨架到编码落地、再到并行调参的整条链路都过了一遍。这篇文章就是这次实现的完整复盘会讲清楚关键设计为什么这么做、匹配查找的工程细节、位流输出怎么提速、以及哪些参数才是真正的性能胜负手。如果你已经在用现成压缩库但想搞懂底层原理或者准备从零搞一个压缩模块却不知道从哪下手这篇文章应该能帮你省掉不少弯路。文中代码都以示意为主目标是让你理解思路、能照着落进自己的项目。1. 动手之前先把“高性能”翻译成可度量指标1.1 三个指标互拉扯先想清楚要哪个很多人一提“高性能压缩”第一反应就是“压得快”。但实际定义过才知道高性能是三个指标的组合压缩吞吐、解压吞吐、压缩比。这三个指标经常互相对着干。比如压缩比要做得极致通常要更长的匹配链、更复杂的熵编码结果查找次数变多吞吐自然掉下来。反过来为了极限吞吐把所有查找都砍掉压缩比又会难看。更麻烦的是解压吞吐在多数场景里比压缩吞吐重要得多——数据通常只压缩一次却会被解压很多次。如果解压路径有瓶颈线上迟早出事。还有一个容易被忽视的指标是延迟特别是实时交互链路。压缩一个几兆的块如果耗时太高下游等数据的人会明显感觉到卡顿。延迟跟吞吐不是一回事高吞吐可以靠并行堆出来但单块的首字节产出时间必须靠热路径优化来缩短。我这次给自己定的目标是压缩吞吐优先解压吞吐不能比压缩吞吐低压缩比做到主流通用格式的中等偏上水平。有这个定位之后后续很多选型就好做决定了。1.2 测试数据集和验收基准要提前固定没有基准就调优等于瞎调。我准备了四类数据日志文本大量重复前缀、时间戳JSON 与配置类文本中等重复度、结构性强二进制结构化数据定长记录、少量重复已被压缩过的数据JPEG 图像之类用于验证“压了之后不能明显膨胀”每类数据准备几十到几百兆固定机器 CPU 频率测之前先跑几轮预热最终取中位数而不是平均值避免偶发抖动污染结论。我设的验收标准如下指标目标值文本类压缩比不低于 4.0压缩吞吐单线程不低于 400 MB/s解压吞吐单线程不低于 800 MB/s延迟1MB 块压缩不超过 3ms这个表格后面每次调参都会拿过来对比省得凭感觉判断改没改好。2. 算法骨架为什么选了“LZ77 哈夫曼”这条经典路线2.1 无损压缩解决的其实是两类冗余无损压缩的本质是把输入里的冗余去掉。冗余主要来自两个层面第一是重复子串。日志里大量相同的时间戳模板、二进制数据里重复的字段结构本质上都是“之前已经出现过的一段字节”。这类冗余适合用 LZ77 思路处理滑动窗口里找历史匹配输出“往回去多远、复制多长”。第二是符号频率不均。就算没有重复长串某些字节出现的频率也远高于别的字节。常见出现得多的符号应该用短码表示罕见的符号用长码表示整体平均码长可以逼近信息熵。这一步通常交给哈夫曼编码这类熵编码完成。所以经典的做法是两阶段先 LZ77 去重再对输出做熵编码。前者吃掉大块重复后者缩小剩余符号的统计冗余。两者配合才能同时获得较好的压缩比和较低的时间成本。2.2 熵编码选型我为什么没有一上来就上更复杂的方案熵编码有哈夫曼、算术编码、ANS非对称数字系统等选项。现代一些高性能压缩库倾向用 ANS因为它在吞吐和压缩密度之间平衡得非常好。但从自研实现的角度我的建议是先写限定码长的哈夫曼。原因很现实哈夫曼编解码都有现成理论二叉树或查表实现都能很快跑通。限定码长 15 bit 左右的哈夫曼可以用预计算表做到非常快的编解码。ANS 虽然密度好但实现细节多符号概率归一化、批量编码状态转移都不好调第一次自研容易在调试上耗掉大量时间。实际跑下来好的哈希匹配已经吃掉了大部分重复冗余哈夫曼主要提供“最后一公里”的熵压缩。对多数文本和日志数据这个组合已经能达到很不错的压缩比没有必要非上 ANS 不可。2.3 整体流程先想清楚再写代码整个压缩链路我分成了五段读入一块数据切分成若干独立块后面并行化用。对每个块做 LZ77 匹配输出字面量、长度、距离三元组序列。对匹配指令序列做哈夫曼编码生成码表和压缩码流。组装块头写入原始长度、压缩后长度、CRC 校验。按原顺序拼接输出。解码端就是精确反过程先读块头再解哈夫曼码流还原指令序列最后按指令逐个复制/填充得到原文。这个结构在工程上非常稳定因为块与块之间没有依赖后面并行化时边界条件极其干净。3. 匹配查找引擎哈希表、滑动窗口与懒惰匹配3.1 哈希键怎么选桶多大才合适LZ77 最核心的问题只有一个给定当前位置快速找到之前出现过的、尽量长的匹配串。朴素做法是拿当前字节和窗口里每个位置比一遍复杂度完全不可接受。所以第一件事就是把“候选位置”用一个哈希结构收窄。我选择用 4 字节做哈希键。4 字节对文本和结构化二进制数据来说长度适中冲突概率可控。如果只用 3 字节哈希表规模可以更小但候选位置太多匹配验证的次数会明显增加。哈希函数用乘法散列就行static inline uint32_t lz_hash4(const uint8_t *p, uint32_t hash_bits) { uint32_t h; memcpy(h, p, 4); // 非对齐读取交给编译器优化 h * 0x9E3779B1U; // 黄金比例常数 return h (32 - hash_bits); }哈希表大小我取窗口位置数量的 1 到 2 倍。比如窗口 64KB哈希表条目就设成 65536 或 131072。太小会导致每个桶塞进太多不同串匹配验证退化太大则缓存不友好反而影响吞吐。3.2 链式候选不能只记住“最近一次出现”最简单的实现是每个哈希桶只存“上次出现这个键的位置”。好处是内存少、访问快坏处是如果最近那次匹配长度不够长你可能直接错过更早更长的候选。我用的是经典链式结构一个head[]存每个哈希值的最新位置一个prev[]串起同一哈希值的历史位置链。初始化 head[hash] 0 prev[pos] head[hash] head[hash] pos每次拿到一个候选位置先算距离超出窗口上限就停止追链。匹配验证则是先看读取距离是否有效再按最大可能长度快速比较。哈希只负责给候选正确性靠逐字节比对兜底。注意这里不要为了“多几个候选”把链拉得太深。实测链深超过 4 以后收益非常有限反而每次都要访问随机内存缓存压力陡增。我最终的实现是默认最多追两层。3.3 懒惰匹配是压缩比和速度的中间项拿到一个匹配后有三种选择立刻编码它、寻找更长的匹配、或者再往后多看一个位置再找一次。前两种是普通贪心第三种叫懒惰匹配lazy match。懒惰匹配的逻辑很简单当前找到的匹配长度是L1如果L1不太长就先不急着定而是看下一个位置能不能找到更长的匹配L2。如果L2 L1就输出当前位置的字面量然后去处理下一个位置。while pos end: 在 pos 找到匹配 m1(len1, dist1) if len1 min_match: if len1 lazy_threshold pos 1 end: 在 pos1 找到匹配 m2(len2, dist2) if len2 len1: 输出字面量 data[pos] pos 1 采用 m2 作为当前匹配 输出匹配(dist, len) pos len else: 输出字面量 data[pos] pos 1这个做法的收益是压缩比能提升几个点代价是额外一次哈希查找。我发现把lazy_threshold设置在 32 左右比较划算只有当前匹配长度小于等于 32 时才做二次查找。长匹配本身已经很划算没必要再冒险去看下一个位置。4. 编码落地位累加器、查表策略与块头设计4.1 位累加器决定编码吞吐的底子哈夫曼输出的是不定长的比特序列。如果你一个一个 bit 写盘每写一 bit 都走一次函数调用和边界判断那编码吞吐一定上不去。正确做法是做一个宽的位累加器把多个变长编码攒满了再写内存。我用 64 位累加器按 LSB-first 顺序输出——也就是先写低位。实现如下struct BitWriter { uint64_t bitbuf 0; int bitcnt 0; uint8_t *ptr; void put(uint32_t val, int nbits) { bitbuf | (uint64_t)val bitcnt; bitcnt nbits; while (bitcnt 8) { *ptr (uint8_t)(bitbuf 0xFF); bitbuf 8; bitcnt - 8; } } void flush() { if (bitcnt 0) { *ptr (uint8_t)(bitbuf 0xFF); } bitbuf 0; bitcnt 0; } };这里有个容易错的地方flush()之后必须清空bitbuf不然下一个块接着写时会带上上一块的残留数据解出来全是错的。我一开始就吃过这个亏。LSB-first 不是唯一选择MSB-first 也完全可以。关键是编码端和解码端保持一致。这个细节最好写进块头的标志位里方便以后扩展新的编码版本。4.2 预计算表把“逐位决策”变成“查表决策”哈夫曼编码的实现如果每次都用一次循环去数 bit、每次都用 switch 判断走哪条分支性能会很难看因为分支预测失败代价很高。我在编码端预先建了一张映射表对每个符号记录它的码值和码长。编码时直接查表不再做任何判断struct HufEntry { uint32_t code; uint8_t len; }; HufEntry huff_table[256]; // 预计算完成解码端同理。我维护了一张按码长聚合的解码表用前缀读取加查表的方式一次性取出符号避免一个一个 bit 判断。解码表稍微大一点没关系因为解压路径本来就应该尽量用空间换时间。4.3 块头设计少写一个字段都会让后面想哭压缩流不是“纯压缩数据”就能工作的。没有块头解码端根本不知道这堆 bit 有多长、原始数据是多大、码表是怎么组织的。我的块头字段固定如下字段长度说明魔数4B识别文件格式防止解错文件版本号1B格式演进时做兼容块标志1B编码类型、字节序等信息原始长度4B解码后应得到的字节数压缩长度4B后续压缩数据长度CRC324B整块校验防数据损坏总长度 18 字节不算多。块头我统一对齐到 8 字节边界不是必须但能让读取端的内存访问更整齐顺手省一点开销。CRC 校验看起来是额外成本但对一个会落在真实传输链路上的格式来说不能省。数据损坏如果发现不了解压结果会是一堆莫名其妙的字节比直接报错可怕得多。5. 内存与CPU优化性能瓶颈往往不在算法而在数据访问5.1 哈希表的随机访问是最大的隐藏代价压缩任务的耗时分布里真正让 CPU 等的最多的往往不是计算而是内存访问。哈希表和滑动窗口都是大块内存每次查找都是一个随机的读。缓存线只有 64B而哈希桶分布得很散命中率稍差就全是 cache miss。一个很典型的坑为了压缩比把哈希表条数加到窗口的 4 倍结果压缩比确实涨了一点点但压缩吞吐掉了 30%因为表太大热点数据全都进不了 L2 缓存。我的缓解手段有两个哈希表条数控制在窗口的 1~2 倍内压满缓存收益的临界点。对匹配链上的候选位置做__builtin_prefetch提前把接下来要访问的窗口数据拉进一级缓存。__builtin_prefetch不是银弹加太密反而会占用内存带宽。我只对链上的前两个候选做预取实测效果好于对所有候选都预取。5.2 非对齐读取和批量拷贝要放心用字节流匹配时很多人会老老实实一个字节一个字节地比。改成内存拷贝方式的非对齐读取性能立刻就不一样了。static inline uint32_t read32(const uint8_t *p) { uint32_t v; memcpy(v, p, 4); return v; }memcpy在这里不是真的拷贝函数调用——编译器会把它优化成一条 32 位加载指令。这样既避免了 C/C 里的未对齐访问未定义行为又拿到硬件级别的读取效率。匹配比较时也可以用宽的整数一次性比 8 字节甚至 16 字节只有长度不够需要收尾时才回到逐字节。核心思想是减少循环次数让每一次循环处理更多数据。我试过用 SIMD 指令做更宽的批量比较收益存在但前提是编译器能自动向量化或者你对目标平台做了针对性实现。如果只想拿到 80% 的收益而不想引入平台相关代码先做好宽读取就够了。6. 并行化块级独立窗口与乱序输出6.1 独立窗口的设计让并行成为可能LZ77 的窗口匹配天然有顺序依赖后面数据的匹配要依赖前面已经编码的数据。如果整个大文件共享一个窗口压缩过程必须严格串行。我选择把输入数据切分成固定大小的块默认 256KB每一块用独立的窗口独立压缩。块内匹配只能引用块内的历史数据跨块的重复串不合并。这样做有两个好处块与块之间完全没有数据依赖天然适合并行压缩。解压时也能按块独立进行必要的时候可以做并行解压。代价是压缩比有一点损失遇到跨越块边界的超长重复匹配被截断成多次。但块大小越大边际损失越小。256KB 对我那批日志数据来说压缩比损失可以控制在 1% 以内换取到的并行能力却很可观。6.2 工作池压缩可以乱序输出必须有序并行压缩最自然的实现是一个简单的线程池主线程把待压缩块扔进任务队列工作线程从队列取块、压缩、把结果写回各自的结果槽。所有块完成后主线程按块序号顺序拼接输出。这里的关键是压缩任务可以不按顺序完成但落盘顺序必须按原块顺序。用一个std::atomicint next_to_write记录下一个需要写入的块号每个线程写完自己的块后尝试推进这个序号result_chunks[i] compressed_data; atomic 推进 next_to_write 如果自己是下一个就连续写入几个连续的块这个模式写起来不复杂却能完美利用多核。线程数一般设为核心数减一避免和主线程调度竞争太激烈。6.3 解压端的并行限制解压同样可以并行前提是格式允许按块随机访问。我的做法是在整体压缩流的头部维护一个“块索引表”记录每块压缩数据在流中的偏移。解压时先读索引表再分配给多个线程并行解压各块非常直接。需要注意的地方是内存占用并行解压时每个线程要同时持有自己的块缓冲区如果块太大或者线程数太多内存峰值会非常吓人。所以块大小不能只考虑压缩比还得考虑解压时的内存预算。默认 256KB 在这个维度也是合理的。7. 实测调优这些参数才是吞吐和比率的胜负手7.1 关键参数与效果对照经过几轮调参我最后锁定了几个核心参数参数默认值对性能的影响哈希表条数窗口的 1.5 倍大了缓存压力大小了匹配候选少最小匹配长度4 字节调成 3压缩比几乎不变但速度明显变慢懒惰匹配上限32 字节小于该长度才做二次查找窗口大小64KB加大提升压缩比但哈希表成本上升块大小256KB块越大压缩比越好但并行度变差最有意思的发现是min_match从 3 调到 4。起初觉得多 1 个字节的矮子匹配也能压缩差不了多少。实测后发现全是 3 字节匹配时编码指令数量暴涨输出指令的哈夫曼开销反而盖过了那点收益压缩比变化不到 0.5%压缩吞吐却掉了接近 12%。7.2 一组实测数据以下是我在固定单线程条件下测得的一组数据用来说明“快”和“省”之间确实有取舍数据源原始大小压缩后大小压缩比压缩吞吐解压吞吐日志文本512MB94MB5.45916 MB/s1740 MB/sJSON 混合256MB88MB2.91748 MB/s1530 MB/s结构化二进制256MB149MB1.72689 MB/s1410 MB/s调整懒惰匹配参数前后对比日志文本的压缩比从 5.21 提到 5.45压缩吞吐只掉了 4% 左右这个买卖非常划算。多线程缩放上4 核机器跑 256KB 分块压缩吞吐从单线程的大约 700 MB/s 提升到接近 2500 MB/s基本符合线性扩展预期。数据量再小的时候反而不建议并行因为线程创建和结果重组的开销可能超过压缩本身的耗时。8. 踩过的坑解码端往往是正确性问题的高发区最后专门说几个实现过程中踩得最深的坑尤其是解码端的问题。压缩端写错最多也就是压缩比难看解码端写错可是直接产出垃圾。第一个坑是位流尾部处理。一个块编码结束后剩余 bit 不足 8 位时必须补零写出来。解码端如果不知道补了几个零会把多余的 bit 也当成有效数据解后面 CRC 一校验就炸。解决方法是块头里记录原始长度解码时解到原始长度立即停止不再关心剩余补位。第二个坑是匹配距离越界。理论上一个格式良好的压缩流不会产生超过窗口大小的距离但防御性检查绝不能省。万一输入数据损坏或者编码器某条逻辑有 bug解到一个负数距离直接内存越界那可就不是解错几个字节的问题了。每次解码匹配指令之前检查距离是否小于当前已填充长度。第三个坑是哈希键读取越界。哈希匹配要读当前位置往后 4 个字节但如果匹配快到块末尾这 4 个字节可能已经越过缓冲区边界。我选择在每个块的末尾预留 8 字节的冗余空间并清零这样哈希读取和最长匹配比较都不会越界代码也干净很多。如果你也准备自研压缩库我的建议是先写一个“慢但正确”的版本把 LZ77 指令流和哈夫曼编解码全部跑通再把性能逐步加回去。跳过正确性直接上 SIMD 和多线程通常只会让你同时面对算法 bug 和并发 bug 的双重折磨。我自己做完整套实现后最大的体会是高性能压缩库的难点不在算法理论而在把一个很简单的道理真正做到极致——减少无关的工作少访问不该访问的内存让每个 CPU 周期都花在匹配和编码本身上。