说到压缩库很多人第一反应就是 zlib 或者 zstd毕竟现成的轮子又多又稳。但我这次偏要自己写一个不是没事找事而是手头有个场景确实绕不过去嵌入式设备上跑实时日志采集既要高压缩比又要把 CPU 开销控在 5% 以内内存还不能超过 256MB。市面上的库要么太重要么压缩级别调节不够细逼得我只能动手。折腾完这个高性能压缩库回头梳理一下正好把从设计到落地的一套完整思路记录下来。这篇东西适合三类人看打算自己撸压缩算法、但是不知道该从哪里下手的已经在用现成压缩库、却总被内存或者速度卡脖子的还有纯粹想搞明白 LZ77、ANS、哈希链这些名词在真实项目里到底怎么拼装的。我尽量讲人话把每一步为什么这么选、踩过哪些坑都交代清楚让你读完能直接照着做而不是看了一堆概念还是不知道怎么写代码。先说结论高性能压缩库的本质是在三个互相打架的指标里找平衡——压缩率、压缩速度、内存占用。你不可能三个全都要但可以通过设计和调优让它们在特定场景下达到一个非常舒服的均衡点。我最后实现出来的库在默认级别下压缩速度和 zlib -6 相当压缩率只低 1% 左右但内存占用只有 zlib 的三分之一而在最高级别下比 zstd -19 还快两倍压缩率基本持平。这个结果不是靠什么黑魔法而是每一步都做对了取舍。1. 压缩库的设计目标与整体框架1.1 先搞清楚一个压缩库到底要解决什么问题动手写代码之前我花了整整三天时间梳理需求。很多人上来就开始写哈希表、写熵编码结果写到一半发现压缩率上不去或者速度达不到要求。原因很简单他们没想清楚这个压缩库服务的到底是一个什么样的数据流。我这里的数据源非常具体嵌入式设备上报的日志和传感器数据单条记录大小从几十字节到几KB不等一天产生几GB的数据。这些数据有几个明显的特点重复字段多时间戳和错误码频繁出现结构相对规整同一类事件的格式高度相似而且对实时性有要求压缩不能拖垮采集线程。针对这个场景我把核心指标定成这样压缩率要尽量逼近 gzip 的水平因为我们要长期存储省空间就是省成本压缩速度必须在单核 20MB/s 以上否则日志一多就丢数据内存占用要控制在 256MB 以内因为设备上还有其他业务在跑。这三个数字一出来选型方向就清晰了不能用纯Huffman太慢不能用纯LZMA内存太大得走一条LZ77 高性能熵编码的路。1.2 模块拆解从原始数据到压缩文件的完整链路一个完整的压缩库内部通常分成五层输入缓冲层、匹配搜索层、熵编码层、输出缓冲层和框架控制层。很多人只关心中间的算法部分忽略了外围的缓冲管理结果内存碎片化严重性能忽高忽低。输入缓冲层负责把外界传入的数据切成可控的块。我这里采用 64KB 作为一个逻辑块原因是这个尺寸既能保证 LZ77 哈希表的命中率又不会让哈希表的条目数撑破 cache。每收到一块数据先判断它是不是可以通过简单规则判定为不可压缩如果可以直接走原始块通道避免做无用功。这个预判逻辑非常关键很多压缩库在文本上表现不错一旦遇到随机数据或者已经加密过的数据性能直接崩掉就是因为没有这个快速通道。匹配搜索层就是 LZ77 算法的核心部分负责在滑动窗口里找到当前数据的最长重复片段。这里我用的不是教科书上最简单的暴力搜索而是 哈希链 懒匹配 的组合后面会详细讲。熵编码层有两个候选方案Huffman 编码和 ANS。我最终选了 rANSranged ANS理由后面细说。但不管选哪种这层都需要维护符号频率表、生成编码表、然后逐符号地输出比特流。更关键的是解码端必须能精确地复现编码端的每一步状态这个一致性是整个压缩库最容易被搞砸的地方。输出缓冲层接受熵编码器产生的比特按字节边界打包成块。这里有几个细节比特缓冲区要支持跨字节写入和读取块头要记录未压缩大小、压缩标志、校验和这样解码器才能正确切分和校验。框架控制层则负责对外提供一个简单好用的 API内部处理多线程分发、内存池复用和异常传播。2. 算法选型为什么不能只看压缩率2.1 主流压缩算法横向对比先把我实际考虑过的方案摆出来对比一下顺便说说为什么最后没有选它们。Deflate 是 gzip 和 zlib 的底层算法LZ77 加固定 Huffman 或动态 Huffman。它的优点是生态极其成熟几乎每个平台都有实现而且压缩率相当能打在通用数据上通常能压到 30% 到 40%。缺点是 Huffman 编码的效率上限就在那对高熵数据的压缩率天花板明显而且如果要跑到很高的压缩级别哈希链搜索非常耗时速度会掉到几个 MB/s。LZ4 是典型的极速压缩算法压缩速度能到几百 MB/s 甚至 GB/s 级别但压缩率比 Deflate 差不少通常只有 50% 左右。这个算法适合做网络传输中的即时压缩不适合做长期存储。Zstandard 是目前综合表现很优秀的算法它用了类似 FSE 的熵编码压缩率和速度都很均衡。但它的问题是代码量很大内部用到了很多复杂的启发式策略想要裁剪到嵌入式环境里非常费劲。我评估过直接移植 zstd发现光是内存池和线程同步的代码就够喝一壶。LZMA 是 7z 的看家算法压率高得吓人但压缩速度极慢内存动不动就是几百 MB 起步根本不可能用在我们的实时采集链路上。最后我选的路线是 LZ77 rANS。rANS 的理论压缩率要优于 Huffman因为 Huffman 的最小编码长度是 1 比特而 rANS 通过状态机的重整可以实现接近熵极限的编码尤其适合日志这种符号分布不均匀的数据。还有一点rANS 的解码速度非常快因为它是逐符号递推天然支持并行这个特性在解码端特别值钱。2.2 ANS 熵编码的取舍与实现要点ANS 全称是 Asymmetric Numeral Systems可以理解为一种把消息编码成单个自然数的奇特手法。它不像 Huffman 那样给每个符号分配整数位而是通过不断操作一个状态值来累积信息。编码时每来一个符号就把当前状态除以符号频率、再乘以总频率、加上符号的累计值得到一个更大的状态解码时逆着来通过模运算恢复符号再反推状态。听起来有点绕其实类比一下就好懂了想象你有一辆里程表的数字可以一直往上滚每次经过一个符号里程表的读数就按照某种规则跳一下。解码的人看到里程表的读数就能倒推出最后经过的那个符号是谁然后一步步往回走。只要状态值足够大这个编码的信息承载效率就能非常接近理论熵。rANS 的实现里有两个关键点归一化和符号频率表的构建。归一化是要把每个符号的频率整量化使得它们的和正好等于 2 的幂次比如 4096 或者 16384这样编码器和解码器才能用位运算代替除法。这一步做不好压缩率会直接劣化几个百分点。我试过用简单的比例缩放加最大余数法但在符号种类超过 200 的日志数据上误差太大最后改成了一种迭代修正的算法先按比例分配再把剩余量按误差从大到小逐个补齐。第二个关键点是状态的上下界约束。rANS 为了保证状态不溢出设置了两个阈值比如状态值必须保持在 2^16 到 2^23 之间。每次编码后如果状态超过上限就要把低字节输出到比特流中然后状态右移 8 位。这个 renorm 过程写起来容易但边界判断做错一个符号整个块就解不出来。我当时在调试这个环节时花了整整一个晚上用随机数据做单步比对才把所有边角情况磨平。2.3 LZ77 匹配搜索的代价模型LZ77 的匹配搜索是整个压缩库最耗时的地方。你可以在一个 64KB 的窗口里为每一个位置做最长匹配搜索但暴力做法的时间复杂度是 O(n * window_size)数据量一大就完蛋。所以我用了哈希链结构把窗口内每三个字节算一个哈希值相同哈希值的位置串成一条链搜索时只需要沿着链往前找若干步就行。这里有个关键的决策链长限制设为多少。链越长找到最长匹配的概率越高压缩率越好但搜索时间线性增长。我统计过我们的日志数据链长超过 32 之后压缩率提升微乎其微但耗时翻了一倍所以最终把链长限制在 24 到 32 之间。懒匹配是另一个重要优化。它的思路是当前位置找到的匹配先不急看看下一个位置有没有更长的匹配。如果下一个位置的匹配更长那就放弃当前位置的较短匹配用下一个位置的。这个策略平均能提升 3% 到 5% 的压缩率代价是 CPU 占用增加约 20%。在最高压缩级别我开懒匹配在默认级别关掉这样性能和压率都各自到位。代价模型这个东西容易被忽略。匹配搜索不仅仅是找一个最长串还要考虑这个匹配值得吗如果匹配长度只有 3 个字节而编码一个匹配需要消耗至少 1 个字节的距离和 1 个字节的长度那可能不如直接输出原始符号。所以我在搜索时设了一个最小匹配长度低于这个长度的匹配全部丢弃。这个阈值在某些实现里叫 min_match我默认设 4对于短字段较多的日志数据这个值最平衡。3. 核心实现细节从数据结构到内存布局3.1 哈希表与滑动窗口匹配搜索的心脏哈希表的设计直接决定了压缩库的查找效率和内存占用。我采用的是固定大小数组加链式节点数组大小为 2^15每个哈希值对应一个头指针节点数量等于窗口大小即 16384 个。这样哈希表总内存大约是 32KB 加节点内存非常可控。哈希函数我用的不是简单的取模而是一个乘数哈希h (hash * 2654435761) 16。这个常数叫黄金比例倒数效果是让相邻位置的哈希值在分布上尽量均匀减少冲突。实测下来在日志数据上哈希表的冲突率比直接取模低 15% 左右。滑动窗口的实现同样有讲究。传统做法是保留一个巨大的环形缓冲区每个新字节顶掉最老的数据。但环形缓冲区对哈希链的更新特别不友好因为你无法轻易判断链上记录的偏移量到底是不是还在窗口内。我采用的方案是每处理完一个逻辑块整块数据复制到窗口后半段然后哈希表全部清空重建。这样虽然会多一次内存拷贝但因为块内数据本身就连续拷贝开销几乎可以忽略而哈希表重建的简化让代码更健壮。实现匹配搜索时有一个大家都容易踩的坑匹配长度超过块边界时会越界。我最初的版本直接用memcmp比较结果在块尾疯狂崩溃。后来改成手工循环每次比较前检查剩余字节数虽然多了一个分支判断但安全性和调试便利性一下子就上来了。如果发现匹配长度快超过当前块尾就提前截断绝不越界读。3.2 符号分布统计与归一化LZ77 匹配层输出的是一串字面符号和匹配引用的混合流。为了让熵编码器工作我必须先统计出每个符号的出现频率。字面符号是原始字节匹配引用则需要拆成两个抽象符号长度和距离。每个符号的取值范围决定了频率表的大小。我用的频率表大小是 4096因为符号总量是 256 个字面值加上 64 个长度档位加上 64 个距离档位大约 384 个候选符号分摊到 4096 的表里非常充裕。统计阶段使用一个临时数组遍历整个逻辑块逐符号累加。这个过程是内存带宽瓶颈所以我在循环里做了手动展开每处理 8 个符号更新一次局部计数器最后再合并到主表里。这个微优化别看简单直接把统计阶段的速度提高了大约 30%。归一化算法前面提过我再详细说说。假设实际统计得到的频率是数组 freq[]我要把它们映射成 norm[]使得 sum(norm) 4096。第一步算出比例因子 scale total / 4096然后每个符号的初始值取 floor(freq[i] / scale)如果小于 1 则强制设为 0。第二步计算剩余量 leftover 4096 - sum(norm)然后按freq[i] - norm[i] * scale从大到小排序把 leftover 逐个分配给误差最大的符号。这个实现听起来很简单但最容易出问题的地方是保留频次为 0 的符号要不要编码如果不编码解码端就无法为它分配符号 ID。所以我在统计表初始化时把所有符号的频次置为 1这就是所谓的伪计数pseudo-count。它保证了每个符号在解码表里都有合法条目代价是压缩率会少一点点但对于 4096 的表来说这点损失完全可以接受。3.3 输出缓冲与字节对齐熵编码器的输出不是按字节对齐的它会连续地吐比特可能一个符号的编码横跨两个字节。因此输出缓冲层必须维护一个 bit_buffer 和 bit_count。每写入一个符号就把编码位左移进 buffer等 bit_count 达到 8 就输出一个字节。解码时反向操作先读取够位数再恢复符号。这里有个性能坑逐位操作非常慢一次性操作 32 位甚至 64 位会快很多。所以我采用了批量刷新策略bit_buffer 是一个 64 位变量每次编码先把新位拼进来当 bit_count 64 时把高 32 位拆成两个 16 位存入输出缓冲区然后左移 32 位并减去 32。这种策略能显著减少内存访问次数一个逻辑块编码完成后bit_count 可能只剩不到 32 位最后统一刷出。解码端也类似尽量按整字节批量加载。块头的设计也很重要。我固定使用 8 字节头前 4 字节是魔数0xCB1A防止错误的数据流被当成压缩流中间 2 字节记录原始块的长度最后 2 字节是压缩标志和块类型。这个头虽然增加了 8 字节开销但解压时能快速校验避免解析到错误的内存位置而导致崩溃。块边界对齐到 16 字节这样在部分嵌入式平台上 DMA 搬运时能对齐访问减少总线压力。4. 性能调优算得快和写得好是两回事4.1 压缩级别的分级策略很多现成库把压缩级别设成 1 到 9数字越大越慢越省空间。但实际搞过之后我发现单纯调长度阈值和链长并不能覆盖所有场景所以我设计了五档级别每一档对应一套完整的策略组合级别 0原始存储什么都不做只做校验和与块封装。用于已经压缩过的数据比如图片、视频或者加密后的日志。级别 1只开 LZ77最浅哈希链不懒匹配熵编码用固定频率表。速度能达到 80MB/s 以上适用于实时性极强的场景。级别 3默认LZ77 哈希链深度 24启用懒匹配熵编码用自适应频率表。这是最平衡的一档速度约 25MB/s压缩率接近 zlib -6。级别 5哈希链深度 32懒匹配开启块大小提升到 128KB。这一档压缩率比默认高一到两个百分点但内存占用翻倍。级别 7最高档哈希链深度 64开启最优匹配搜索的分支裁剪块大小 256KB。压缩率接近 zstd -19但压缩速度只有 3MB/s 左右。每个级别的策略都用位掩码表示比如FLAG_LAZY_MATCH、FLAG_ADAPTIVE_FREQ、FLAG_LARGE_BLOCK。这样调用方可以通过一个整数直接控制不需要传复杂的配置结构体。我个人建议业务方在对接时先拿几天真实数据在各档位下跑一遍基准不要凭感觉选最高档因为很多时候级别 3 到级别 5 的压缩率差距不到 2%CPU 开销却能差 5 倍。4.2 SIMD 与预取优化现代 CPU 上做压缩库优化少不了 SIMD。但 SIMD 不是无脑用而是要找准热点。我用性能剖析工具跑了一遍发现热点集中在这几个地方哈希值计算、memcpy 式的匹配扩展、以及熵编码末端的批量 bit pack。哈希值计算我用 SSE2 做了一次小优化一次处理 16 个字节的哈希预处理把每个 3 字节窗口的哈希结果算出来存入一个临时表。这样后续匹配搜索时不需要反复读取原始数据直接从临时表取哈希即可。别小看这个改动哈希计算在整个搜索过程中占到 20% 左右的 CPU 时间优化后这部分开销几乎可以忽略。匹配扩展的 SIMD 优化比较取巧。传统的memcmp在短匹配时很快但在高强度匹配搜索中动辄比较几十上百个字节主内存访问成了瓶颈。我改用了 SSE4.2 的pcmpistrm指令做一次性 16 字节比较命中时返回一个掩码可以直接跳过不需要比较的字节。实测在日志数据上匹配扩展速度提升了大约 40%。预取指令也值得加。哈希链遍历时下一轮要访问的内存位置往往不确定又在较远的地址。我在进入链遍历循环前用_mm_prefetch提前加载可能的下一个节点地址把内存延迟隐藏掉。这个优化让高压缩级别的性能又改善了约 15%。但注意预取并不是越多越好预取过深会导致 cache 污染我最后只预取一级链节点效果最好。4.3 内存分配与缓存友好性内存管理是高性能压缩库最容易忽略的环节。默认的 malloc/free 在高频调用时会成为性能杀手而且会让内存碎片化严重。我的方案是先用一个固定的内存池在初始化时一次性申请所有可能用到的缓冲区包括输入块、滑动窗口、哈希表、频率表和输出缓冲。线程内所有逻辑块的处理都从这个池里取处理完归还。这个设计让内存分配的开销降到了几乎为零。更重要的是因为所有缓冲区都是从同一块连续内存切出来的cache 命中率大幅提升。以前用 malloc 时滑动窗口和哈希表在物理上可能相隔很远每次交替访问都要经历两次 cache miss现在它们紧挨在一起热点数据循环时明显更快。内存对齐同样影响性能。我把所有大缓冲区都按 64 字节对齐保证 SIMD 加载不会跨越 cache line也避免了一些平台上的对齐异常。如果你的目标平台是 ARM Cortex-A 系列这个对齐尤其重要Mali GPU 和 CPU 之间的缓存一致性也会因为对齐不正确而出现性能抖动。另外我强烈建议实现一套简单的缓冲复用机制当上层应用连续多次调用压缩接口时内部不要每次创建新缓冲而是维护一个空闲缓冲链表。这个改动听起来平淡无奇但在循环内反复调用压缩 API 的场景下性能差距可以拉开 25% 以上。5. 实战中踩过的坑排查与修复记录5.1 压缩率突然劣化的排查第一次完整跑通整个库时我看到输出文件比原始数据还大直接懵了。日志数据明明有大量重复怎么可能压不进去后来一步步排查发现问题出在 不可压缩数据的快速通道 上。我原本的策略是计算整个块的最小字节熵如果熵高于 7.2 就认为不可压缩走原始通道。但日志数据虽然整体熵高中间却夹杂着很多可压缩的重复片段整体熵判定法把这些片段全都误杀了。解决办法是改成分区块估计把 64KB 逻辑块再切成 8 个 8KB 子块每个子块独立计算熵值只要超过一半子块可压缩就进入压缩流程。这样既保留了快速通道的优势又能精准捕捉混合型数据。第二个劣化原因更隐蔽哈希表的 Head 数组初始化时全部为 0但滑动窗口的有效偏移量范围是 1 到块结束。当哈希链访问到 Head[h] 0 时如果不加判断就会访问到错误位置导致匹配信息全乱。虽然我没崩溃但压缩率在特定数据模式下直接掉了 8%。修复方式是在链节点数组中用 -1 表示空指针而不是 0避免与合法偏移量冲突。5.2 流式压缩中块边界处理流式压缩比一次性压缩要麻烦得多。因为输入数据是源源不断的我不能等所有数据都收齐再开始压缩必须一边收一边处理。块边界处如果上一个块正好在某个匹配的中间结束那么解码端从下一个块开始时滑动窗口的初始状态必须和编码端保持一致。我最初偷懒在每个块的开头强制清空窗口结果压缩率下降了大约 10%因为跨块的重复数据无法被利用。后来改成在块之间保留一部分先前窗口编码端结束一个块时把最后 32KB 的原始数据复制到下一个块的窗口初始位置解码端解码新块时也从相同位置开始。这个 块间重叠 是流式压缩的标准做法但很多人第一次写都会漏掉。块与块之间还有一个烦人的问题最后一个块的数据不足 64KB但块头记录的长度字段如果写错解压器会直接越界。我给长度字段加了一个简单校验解码前检查其值是否在 0 到最大块大小之间不在就直接返回错误码。虽然没有实际修过崩溃但这个防御性检查帮我在调试多线程版本时省了大量时间。5.3 多线程并行压缩的并发控制高性能压缩库往往要支持多线程最简单的并行粒度是块级别每来一个逻辑块就扔给一个工作线程去压缩主线程只负责切分数据和收集结果。这个模型很清晰但问题在于工作线程之间不能共享哈希表因为每个块的状态是独立的。我在初始化时为每个线程预先分配一份完整的压缩上下文线程之间零共享这样就完全避免了锁竞争。不过多线程场景下有一个坑输出顺序。多个线程的压缩完成时间不一定和输入顺序一致如果直接按完成顺序写入文件解压端会得到乱序的块导致崩溃。解决办法是给每个块分配一个序号在输出阶段用序号排序主线程按序把结果写下去。这个排序我用了一个小数组记录每个序号的输出长度和偏移等所有线程都完成后一次性拼接。并行压缩的另一个问题是内存峰值。如果每个线程都独立持有 64KB 输入和 128KB 输出4 个线程就是近 1MB看起来不多但堆到 16 线程时就有点吓人了。所以我给线程池加了信号量限制最多同时允许 4 个压缩任务运行其余任务排队。实测 4 线程并行在 4 核设备上能跑到接近线性的加速比再增加线程数收益就递减了反而内存压力变大。提示如果你要做移动端或者嵌入式部署建议优先把线程数限制在 2 到 4并允许上层调用者通过配置项覆盖。固定写死 8 线程的东西在低配设备上反而会让系统整体变慢。我在实际调试中还发现把哈希表清零这个动作在多线程下很容易被忽略。每个线程开始处理新块之前都要清零自己的哈希表头数组。如果共用同一个上下文后一个块会继承前一个块的哈希链匹配结果就是一堆垃圾数据。这个问题排查起来特别诡异因为它不一定每次崩溃可能在特定数据分布下才出现。结尾一点经验之谈写这个压缩库的过程最深的体会就是压缩算法不是玄学每一点性能差异背后都有明确的结构性原因。别急着堆代码先把数据特征摸清楚把指标定住选型、分层、优化就都有据可依。我自己踩过最大的坑就是一开始太贪心想把压缩率做到极致结果写了一堆复杂逻辑速度掉到不忍直视。后来狠下心砍掉花哨的功能用最简单的 LZ77 加 rANS 跑通全链路再一步步加回优化最终反而拿到了非常顺手的指标。做高性能这行简单骨架加针对性优化永远比上来就搞复杂框架要靠谱。最后分享一个长期有效的小技巧每次改完压缩库的核心代码一定要跑一遍随机数据的循环测试确保压缩-解压的结果和原始输入完全一致。我几乎所有的诡异 bug 都是靠这种随机测试暴露出来的而人工构造的测试用例往往怎么跑都测不出来问题。把这套测试固化成 CI 的一部分后面改代码会安心很多。