曾经我以为压缩库就是调个参数的事直到线上服务的 CPU 给压缩打满我才决定老老实实动手把一个高性能压缩库实现从头写了一遍。这篇帖子就是记录那几周里做的算法选型、工程取舍和踩坑过程。如果你也遇到过通用压缩库性能不够、压缩率调不上去、或者想理解 zstd / LZ4 这类库背后到底在忙什么这篇文章应该能帮上忙。这不是一篇泛泛的综述而是我实际从空文件写到能跑压测的完整复盘包含可参考的 C 代码片段、性能测试方法和一堆文档里不会写的细节。1. 一场真实的压缩性能瓶颈我为什么决定自己写压缩库1.1 那个 CPU 被打满的下午故事背景是这样一个系统大量日志和结构化数据实时写入存储层每条记录在落盘前都要压缩。最初用的通用压缩库默认配置压测时发现压缩这一个环节就吃掉了将近 30% 的 CPU 时间。数据量一上去服务整体吞吐就上不去了。当时团队里有人提议换更强的算法但结果是压缩率上去了CPU 开销更高换更快的算法CPU 下来了磁盘空间却涨得飞快。这就像买东西只看价格不看质量两头都不讨好。我后来仔细看了性能剖析数据发现真正的问题不是压缩算法选错了而是通用库必须兼容各种输入、各种配置内部做了太多通用性牺牲。它要考虑老 CPU、小内存、流式输入、文本二进制混合……这些兼容性全都要花 CPU 和内存。而我们场景里的数据模式其实非常固定完全可以通过更针对性的实现拿到好几个百分点的性能提升。就在那一刻我决定与其继续在通用库的参数空间里打转不如直接写一个贴合自己场景的高性能压缩库实现。1.2 压缩库设计里的黄金三角速度、压缩率、内存动手之前我先梳理了一下压缩库设计时绕不开的三角约束压缩速度、压缩率和内存占用。这三者永远在互相拉扯你想压缩率高就得更仔细地找重复、建更复杂的统计模型计算量必然上去你想速度快就得牺牲搜索深度、用更简单的编码压缩率自然下滑。设计维度想要提升时通常牺牲的压缩速度减少匹配搜索范围、用 SIMD、加并行压缩率压缩率加大窗口、加深匹配链、用 ANS内存与速度内存占用限制窗口、固定哈希桶压缩率对于我现在的场景我明确排序解压速度第一压缩率第二内存占用第三。为什么解压速度优先因为数据是写多读少但读的时候要大批量回溯历史解压慢会直接拖垮查询链路。这个排序直接决定了后面所有选型。因此我建议你在开始之前也先把这个三角排序想清楚不然中途容易反复改架构。2. 算法选型的第一步LZ77、Huffman 与 ANS 怎么选2.1 一切从 LZ77 滑动窗口开始几乎所有现代压缩库的地基都是 LZ77zlib、gzip、zstd、LZ4 全是它的变体。LZ77 的基本思想很简单维护一个已经处理过的历史窗口尝试从窗口里找到当前数据的最长匹配如果能找到足够长的重复片段就输出一个“距离 长度”的引用找不到就直接输出原始字节。这个消息的表述可以类比成你在校对一本翻印稿看见一句“从前有座山山里有座庙”发现前面三页刚出现过一模一样的句子就没必要再抄一遍写个“翻到第三页、重复 12 个字”就行了。这就是匹配器在做的事。理解这一点以后再去看任意一款压缩库的核心代码你就不会迷路因为它们的骨架基本都是 LZ77 匹配引擎加后续编码。2.2 LZ77 之上为什么要再接一层熵编码如果只做 LZ77输出流里会有大量距离、长度和字面量这些数值的出现频率差异很大。比如距离值通常集中在很小的范围内长度值也有偏向性。这时候用统计编码再压一遍能把高频值用更短的 bit 表示低频值用更长的 bit。常用的有 Huffman 和 ANS非对称数字系统。Huffman 是 deflate 的老搭档实现简单、解压快ANS 是 zstd 里 FSE 的基础压缩率更高但编解码状态机更复杂。2.3 我的选择LZ77 匹配引擎 轻量熵编码起步我并不建议第一次写压缩库就直接上 ANS。ANS 的状态转移逻辑很容易写错而且一旦写错压缩出来的数据解不开排查成本非常高。我当时采用的分阶段策略是先把 LZ77 匹配引擎写出来输出“字面量 距离 长度”的中间格式这个阶段先不做熵编码保证链路能跑通。用 Huffman 对中间格式做一次熵编码先获得一个能压缩的版本。等整个框架稳定之后再把 Huffman 替换成 ANS按需优化压缩率。这个路线最核心的好处是每一步都有可验证的中间产物出问题容易定位。我自己见过好几个朋友一上来就照着 zstd 抄 ANS结果前两周全部耗在熵编码上匹配引擎反而没写明白。记住匹配引擎才是 LZ 类压缩库性能的主战场熵编码是锦上添花。3. 核心实现哈希表、滑动窗口与匹配链的工程取舍3.1 为什么匹配引擎决定整体性能下限压缩库的整体性能基本上在上限上由匹配引擎决定。CPU 每秒能扫描多少数据、能找到多好的匹配直接决定压缩吞吐和压缩率。而匹配器的本质是快速回答“当前字节串之前在窗口里出现过吗最长出现在哪”这个问题。快速是关键因为你每处理一个字节都要问一遍窗口大小可能是 64KB、256KB 甚至更高全扫一遍不现实必须用索引结构把查找变成近似 O(1)。3.2 哈希表设计4 字节滑窗与桶大小标准做法是对输入做哈希。常见策略是每次取当前四个字节4-byte stride计算哈希用哈希值做下标查哈希表。为什么取四个字节三个字节区分度不够高冲突会很严重五个字节以上计算量和内存都涨收益不大。四个字节在性价比上正好。我实现时用的是直接索引匹配哈希函数选择了一个简单的乘法哈希代码是这样static inline uint32_t hash4(const uint8_t *p) { uint32_t v (uint32_t)p[0] | ((uint32_t)p[1] 8) | ((uint32_t)p[2] 16) | ((uint32_t)p[3] 24); v * 0x9E3779B1u; // 黄金比例哈希常数 return v (32 - HASH_BITS); }HASH_BITS决定了哈希表大小我选了 16即 65536 个桶。每个桶里存的是“最近一个进入窗口且哈希值为 h 的位置”。这个数字不是随便定的它和窗口大小有直接关系窗口 64KB每个位置都会在某个桶里占一个坑桶太少则会频繁碰撞。3.3 用链表还是用数组内存布局的取舍教科书会告诉你哈希表后面挂链表每个桶里一串位置。但真正写高性能实现时我不会用指针链表。内存分配散落各处每一次链指针跳转都可能触发缓存未命中对性能是致命的。我给每个哈希桶只保存一个“头的索引”然后在窗口上维护一个数组prev[]记录“从我这个位置往前数上一个哈希值相同的位置”。这本质上是在数组上模拟链表代码长这样// head: 哈希桶存最近位置索引 // prev: 记录同一哈希链的前驱 uint32_t head[1 HASH_BITS]; uint32_t prev[WINDOW_SIZE]; void insert(uint32_t pos, const uint8_t *p) { uint32_t h hash4(p); prev[pos WINDOW_MASK] head[h]; head[h] pos; }这样整个索引结构就是三个连续数组内存紧凑访问一个位置时大概率周围的prev也刚好在缓存里性能好很多。3.4 一次完整的匹配查找流程有了索引查找匹配的过程就清晰了对当前四个字节算哈希取到桶里的链头然后沿着prev往前回溯若干个候选位置逐一对候选位置做实际字节比对找到最长的那一段。完整代码见下static int find_match(const uint8_t *src, const uint8_t *win_start, uint32_t cur_pos, uint32_t max_len, int depth, uint32_t *best_dist) { uint32_t h hash4(src); uint32_t cand head[h]; int best_len 0; *best_dist 0; while (cand ! INVALID_POS depth-- 0) { uint32_t dist cur_pos - cand; if (dist 0 || dist WINDOW_SIZE) break; const uint8_t *p src; const uint8_t *q win_start cand; while (p src max_len *p *q) { p; q; } int len (int)(p - src); if (len best_len) { best_len len; *best_dist dist; if (len MAX_LEN_LIMIT) break; } cand prev[cand WINDOW_MASK]; } return best_len; }这里面有几个细节值得展开。第一max_len不能太大因为输出编码里的长度字段是有限制的超过了就得断开重来。第二depth是搜索深度控制最少回溯多少候选depth 越小速度越快、压缩率越差zlib 里对应的是最大匹配链长度。第三prev的下标必须用窗口掩码规约否则索引会一直涨导致数组越界。这类代码的关键考量是候选不一定要最多而是要足够好。我的经验是把 depth 控制在 32~64 之间够用又不慢具体值按你的数据集微调。4. SIMD 与缓存之道高性能压缩库的底层加速手段4.1 缓存友好块大小与内存连续的底层逻辑写完上面的匹配器压缩已经能跑了但性能距离理想状态差得远。我开始用工具看热点最后发现大部分时间不在哈希计算而在寻找匹配时的逐字节比较。逐字节比较的问题在于每比较一个字节都要加载一次内存等到发现匹配长度很长时CPU 已经浪费了大量周期。优化的第一步是简化候选位置的管理第二步就是用 SIMD 一次比较更多字节。先说块大小。我把输入切成 64KB 一个块每个块有一个独立的哈希表和窗口让所有热数据尽量压在 L2 缓存里。64KB 不是拍脑袋定的我的测试平台 L2 是 512KB窗口 哈希表 中间缓冲加起来刚好能放进缓存再大就会出现缓存颠簸吞吐反而掉。4.2 用 SIMD 把 16 字节的比对变成一条指令逐字节循环里最核心的代码是*p *q然后p, q编译器一般会尝试自动向量化但那种向量化效果不稳定。我改成显式 SIMD 后单次可以并排比较 16 或 32 字节。以 SSE2 为例#include immintrin.h static inline int match_len_simd(const uint8_t *a, const uint8_t *b, int limit) { int len 0; while (len 16 limit) { __m128i va _mm_loadu_si128((const __m128i *)(a len)); __m128i vb _mm_loadu_si128((const __m128i *)(b len)); __m128i eq _mm_cmpeq_epi8(va, vb); int mask _mm_movemask_epi8(eq); if (mask ! 0xFFFF) { int bits (int)__builtin_ctz(~mask); // 第一个不同的位置 return len bits; } len 16; } while (len limit a[len] b[len]) len; return len; }原理并不复杂_mm_cmpeq_epi8把对应位置的字节比较结果放进一个 16 字节的向量里每个字节要么是0xFF相等要么是0x00不等_mm_movemask_epi8把每个字节的最高位抽出来组成一个 16 位整数这样一次就能判断 16 个字节是否全部相等以及第一个不相等的位置在哪里。实测效果非常明显匹配长度在 16 字节以下时SIMD 版本和逐字节版本差不多一旦匹配超过 32 字节SIMD 版本能快接近一个数量级。4.3 内存对齐、编译选项与指令集分派写这类代码时我习惯做三件事对热循环里的关键数组做对齐给哈希表和窗口数组加alignas(64)避免跨缓存行访问带来的额外负载。编译期开启目标指令集-O3 -marchnative或者针对目标服务器明确启用-msse4.2、-mavx2不要用默认的-O2这个差别在压缩这种计算密集型代码里经常能达到两位数百分比。在运行时检测指令集做分派如果程序要部署在多代 CPU 上不能直接用-marchnative编译出来的版本否则老 CPU 会崩溃。我认为更好的做法是用__builtin_cpu_supports(avx2)之类接口做运行时判断提供 SSE2 / AVX2 / 纯标量三个实现。内存对齐还有一个容易忽略的点SIMD 加载最好不要真的对齐到 16 字节边界因为数据流的位置是任意的。所以我上面用的是_mm_loadu_si128非对齐加载它在绝大多数现代 CPU 上性能已经接近对齐加载不值得为了对齐去复制数据。5. 基准测试与瓶颈定位数据会告诉你优化方向5.1 建立一套可信的测试基准优化如果没有可信的基准基本等于盲人摸象。我最开始犯的错就是只用一个大文件测试结果优化方向全被偏差带着跑了。后来我用了一组固定的混合数据集数据集特征用途程序日志纯文本大量重复行、时间戳考察匹配器对重复数据的敏感度JSON 结构数据短键长值、重复字段接近真实业务二进制序列化对象高低熵混合考察最坏情况随机字节完全不可压缩考察压缩失败时的开销每组数据我都固定大小比如 256MB冷启动跑三次取中位数。为什么取中位数而不是平均值因为平均值容易被偶发抖动拉高中位数更稳定。压缩库这种紧贴硬件的性能很小的系统扰动都会带来百分之几的噪声只跑一次的结果根本不可信。5.2 三个关键指标与测试方法我用的指标是压缩吞吐、解压吞吐、压缩率。压缩吞吐指每秒处理多少 MB 输入解压吞吐指每秒解出多少 MB 原始数据。压缩率则是输出大小除以输入大小。这三者在测试时不能混在一起看尤其是压缩吞吐要包含哈希计算和匹配查找的全部时间不能只测压缩核心函数。测试解压吞吐时有个细节解压往往比压缩简单但它的瓶颈可能是分支预测失败和内存随机读。我在测试时特意用了压缩率差异很大的多组数据观察解压速度是否稳定。如果数据一换解压速度剧烈波动说明实现里存在大量依赖数据的条件分支这是需要重点优化的问题。5.3 一次 perf 采样找到的隐形瓶颈我自己的实现优化到一定程度后吞吐一直卡在某个数值上不去。用perf record抓热点发现热点既不在哈希表也不在最内层的字节比较而在我没注意到的函数。具体是怎么发现的perf结果里五个热点函数中有一个是哈希计算函数本身占用比例高得出奇。问题在于我每次查找都重复做了一次哈希而插入时已经算过一次了完全可以复用。把哈希计算改成“当前块的哈希值缓存”每次滑动窗口只需要增量更新热点立刻降下来。那次改动给我一个很深的印象性能瓶颈往往藏在“你没有意识到的重复劳动”里。因此我用两个建议概括这部分经验一是周期性用perf看热点不要靠猜二是把所有“每次循环都重复计算的值”列出来逐个问是否真的需要重复算。6. 踩坑记录哈希退化、边界处理与内存分配器的隐形代价6.1 哈希桶退化当输入全是相同字符时第一个真正让我崩溃的问题是处理特殊输入时性能突然暴跌。用连续相同的字节比如 1MB 的全0做测试压缩吞吐掉到正常水平的十分之一。原因很清楚所有位置算出来的哈希值都相同所有位置都挤在同一个哈希桶里prev链变成一条超长的顺序链表查找匹配时深度失控。解决方案不是在哈希函数上做文章而是在匹配查找循环里加上主动退出条件如果当前候选和当前位置的距离已经超过窗口限制或者已经找到了长度足够长的匹配就立刻停止继续回溯。此外我还加了一个“最小匹配长度”阈值长度小于阈值就拒绝输出引用避免为 3 个字节的重复付出大量哈希查找成本。经过处理后这种极端输入的性能平稳了很多。6.2 最后一公里的边界压缩块末尾的数据怎么处理LZ77 匹配到压缩块末尾时很容易遇到“当前字节还能匹配上但剩下的数据不够编码一个长度字段”的情况。我最初的处理是偷懒直接拷贝剩余数据结果压缩率在短块场景下比预期差不少。后来改成在临近块末尾时如果匹配长度不足以完全覆盖剩余数据就拆成“部分匹配 部分字面量”并对长度字段做范围判断。这里尤其注意编码和解码的边界必须完全一致否则解压端会收到一个越界的长度引用直接产生毁坏性错误。我在调试时专门写了一个模糊测试生成器不断生成随机长度、随机内容的短块做压缩解压回环测试才把这些边角问题一个不落地揪出来。6.3 内存分配器的隐形代价一次分配还是多次分配我最早版本的实现里每压缩一块就分配一次哈希表和临时缓冲结果perf显示malloc相关开销占了总时间的一大部分。小块内存反复申请释放不仅慢还会造成内存碎片。后来改成初始化压缩器时一次性申请所有需要的缓冲空间整个压缩过程不再发生任何动态内存分配效果立竿见影耗时下降了约 15%。对压缩库这种频率很高的场景我认为一条设计原则是运行时分配器尽量只在初始化或者批量边界出现热路径里严禁出现malloc/free。这也是很多工业级压缩库采用的模式比如 zstd 提供ZSTD_compressCCtx就是为了复用上下文而不重新分配。6.4 并行压缩的边界条件与收益曲线最后提一下并行。多线程压缩看似简单每个线程压缩一个块然后拼接结果即可但直接拼接是不行的因为压缩块与块之间可能存在引用关系如果你不共享窗口随便拼接会导致解压方无法定位。工业实现里要么维护独立的块上下文要么在块的头部保存每次压缩的元信息解压时按元信息解每个块。我在实测中发现并行收益并不是线性增长的。核数从 1 加到 8 时收益明显但超过 8 之后受内存带宽限制吞吐基本不再提升。所以我最后的建议是不要盲目把线程数拉满先测出你机器上的收益拐点再用那个数做上限。最后分享一点个人体会经过这次从零实现我最大的感受是高性能压缩库的“高性能”往往不是某一个惊天动地的技巧而是每个环节都不拖后腿。匹配引擎的索引结构要紧凑字节比对要 SIMD内存分配要提前规划哈希退化要主动防御边界条件要反复测试。任何一个环节掉了链子整体性能都会被打回原形。如果看完这篇你也想自己动手我会建议你从 LZ77 加 Huffman 的组合开始先跑通完整链路再去碰 ANS 和并行。碰到性能瓶颈时先测再做判断千万别靠感觉调参。毕竟压缩这种贴近硬件的活儿数据会告诉你答案只是你得先去听。