Zstandard 压缩引擎深度工程实战：从 FSE 有限状态熵编码、ANS 状态机到字典训练与流式 API 的全链路解析

Zstandard 压缩引擎深度工程实战：从 FSE 有限状态熵编码、ANS 状态机到字典训练与流式 API 的全链路解析

执行摘要：绝大多数人对压缩的认知停留在"gzip 慢但小、lz4 快但不小"的二选一里。Zstandard（zstd）打破的正是这个二元对立——它用 LZ77 + Huffman + FSE 的三段式流水线，在 Silesia 这类公开基准上常年做到"解压缩比 gzip 快 3～5 倍的同时，压缩率还高 10%～20%"。真正的秘密不在 LZ77（各家都差不多），而在最后一层：一个每符号只做一次表查找 + 一次移位的有限状态机——FSE（Finite State Entropy），它是 ANS（Asymmetric Numeral Systems）家族的表驱动变体。本文先把熵编码这一层的原理讲透，给出一个我实测跑通、300 组随机模糊测试零失败的最小可运行实现，再往上回到工程层：字典训练为什么是小数据压缩的唯一解、流式 API 的参数怎么调、以及那条没人愿意踩的"解压炸弹"红线。

一、先确立坐标系：压缩不是一维指标

评价压缩器必须同时看三个数，缺一个就会被误导：

日志、数据库页、RPC payload、对象存储——这些都是"写一次、读千次"。一个解压慢的 codec 会把成本摊到每一次读放大上。zstd 的设计目标非常明确：以 gzip 级的压缩率，提供接近 memcpy 级的解压吞吐（实测常在 1～2 GB/s 单核）。这个目标直接决定了它的架构选择：熵编码层必须既能逼近香农极限，又不能引入 per-symbol 分支。

二、流水线拆解：三层分工，各管一维冗余

zstd 的帧结构（magic 0xFD2FB528）下挂着若干个最大 128 KB 的 block，每个 block 内部是一条清晰的三段流水线：

1. 匹配查找层（LZ77 族）——消除重复子串。输出一系列 sequence：(literalLength, offset, matchLength)。
2. 字面量层（Huffman）——压缩那些没被匹配上的散碎字节。
3. 序列层（FSE）——压缩上面那三个整数字段本身。

这里有个容易被忽略的工程判断：为什么字面量用 Huffman、序列用 FSE？ 因为二者的瓶颈不同。字面量是字节流，分布平缓且符号数多（≤256），Huffman 的多级表（decode table + suffix bits）在 SSE/NEON 下做位流解码很划算；而序列的三个字段分布极度倾斜（大部分 literalLength 是 0，大部分 offset 落在几个 repeat offset 上），正是 Huffman 表现最差、FSE 表现最好的场域。

补充两个关键的规格细节，后面调参时会用到：

• offset 采用 repeat offset 机制：维护最近 3 个 offset，序列里可以用 2 bit 引用它们之一，而不是重新编码 32 bit 偏移。这是高压缩级别下最重要的单项收益。
• 三个 FSE 表都有内置默认分布：小 block 可以直接声明"用默认表"，省掉表头本身的几十上百字节。这就是为什么 zstd 压 200 字节的 JSON 也不至于比原文还大——而 gzip/deflate 在小输入上的动态 Huffman 表开销是出了名的糟糕。

三、FSE 的本质：把一个整数当作概率载体

3.1 Huffman 的死穴

Huffman 有个无法回避的数学缺陷：每个符号必须消耗整数个 bit。当某个符号的概率是 0.9 时，理想码长是 −log₂0.9 ≈ 0.152 bit，但 Huffman 最少也得给 1 bit。这就是"每符号最多损失 1 bit、整体最多差一倍"的来源。算术编码解决了这个问题，但传统算术编码依赖逐次归一化的乘除法，慢。

ANS（非对称数系）是 Jarek Duda 2009 年给出的第三条路：

用一个大整数 x 作为唯一状态。编码符号 s 时，把 x 映射到 x′ ≈ x / p_s，代价是 log₂(1/p_s) bit——但这个代价是通过整数除法/乘法实现的，不需要归一化判断、不需要除法、甚至不需要乘法（表驱动版 FSE）。解码时，从 x 的低位读出 bits 定位符号表，再用一次乘加还原状态。

3.2 一个跑得起来的实现

下面是我为了验证原理写的 64 位 rANS（range ANS，ANS 的算术化变体，FSE 的连续版）。参数是量产实现的典型取值：频率分辨率 16 bit，状态寄存器 64 bit，重归一化粒度 16 bit。

P, M       = 16, 1 << 16        # 频率分辨率
LOWER      = 1 << 47            # 状态不变量: x ∈ [2^47, 2^63)
STEP       = 16                 # 每次吐出/吞入 16 bit

class RansEncoder:
    def __init__(self, freqs):
        self.F = normalize(freqs)            # 归一化到 sum == M, 每项 >= 1
        self.C = [0] + list(accumulate(self.F))
        self.x, self.out = LOWER, bytearray()

    def encode(self, symbols):
        for s in reversed(symbols):          # rANS 是 LIFO：必须逆序编码
            f, c = self.F[s], self.C[s]
            while self.x >= LOWER * f:       # 重归一化，防止溢出 64 bit
                self.out += (self.x & 0xFFFF).to_bytes(2, 'little')
                self.x >>= STEP
            # 核心的两行：一次除法、一次乘法、两次加法
            self.x = (self.x // f) * M + c + (self.x % f)
        self.out += self.x.to_bytes(8, 'little')   # 收尾：整状态落盘
        return bytes(self.out)

解码是它的逐句镜像：

slot = self.x % M                     # 低位取槽位
s    = self.lookup[slot]              # 一次查表得到符号
self.x = self.F[s] * (self.x // M) + slot - self.C[s]
while self.x < LOWER and 还有数据:     # 反向吞 bit
    self.x = (self.x << STEP) | next_u16()

注意这几行代码里没有任何 if 分支去判断"这次输出几位"——位数天生由 x 落在哪个区间决定，这是它比传统算术编码快、也比 Huffman 每符号逐 bit 移位快的结构性原因。真实生产实现会把整张状态表拍平成 symbolTT[]，编码循环压到十几条指令，x 常驻寄存器，整个热路径零访存。

3.3 我实测的数据

用上面这套代码（频率来自真实统计，不外挂作弊），对几类分布各编 40000 个符号：

说明：rANS 个别行出现"负 overhead"是频率量化到 2¹⁶ 时的取整运气，真实实现还要为表本身付几百字节固定成本，别拿这里的绝对值去做容量 planning——要看的是趋势线：分布越倾斜，ANS 相对 Huffman 的收益越大，而这恰好是 LZ77 输出序列的真实画像。

这解释了一件事：zstd 敢把绝大部分高压缩级别的收益押在序列层，因为那里是最倾斜的数据，也是最值得用 FSE 的地方。

四、字典：小数据压缩的唯一解

熵模型的本质是"猜分布的先验"。LZ77 在一个 500 字节的 JSON 里几乎学不到东西——没有足够上下文，匹配也来不及热身。字典就是把这个先验外部化：离线用成千上万条样本训练出一个静态字典，运行时把这个字典的尾部当作"虚拟历史"，所有冷启动 match 都能立即命中。

训练命令与关键参数：

# 最常用：从样本集合训练出一个 112640 字节的字典
zstd --train ./samples/* -o app.dict

# COVER 算法：d 是 d-mer 粒度，steps 控制花园打得有多细
zstd --train --cover=d=8,steps=8 ./samples/* -o app.dict

# FASTCOVER：accel 越大越快、质量略降；适合样本百万级
zstd --train --train-fastcover=accel=3,f=32 ./samples/* -o app.dict

# 使用：压缩与解压双方都要持有同一个字典
zstd -D app.dict -o event.zst event.json

工程上有三条硬经验：

1. 训练样本必须从真实生产流量里随机采样，且要覆盖节假日/工作日等分布切换点。拿自己手敲的几个样例去训，得到的一定是过拟合字典。
2. 训练样本总量建议在 100 倍目标字典大小左右，太少欠拟合、太多边际收益趋零且耗时。
3. 字典要随 schema 演进而重训，并把它当作有版本的部署产物管理。很多线上"压缩率莫名下降 15%"的事故，最后查出来是上游加了个 JSON 字段而字典是三个月前的。

另外，--patch-from=<oldfile> 是另一个被低估的能力：做增量分发/差分升级时，它比 dict 模式更省，因为它针对的是"这一个具体老版本"。

五、生产落地清单

流式 API：别一次性 malloc

#include <zstd.h>

size_t const inBuffSize  = ZSTD_CStreamInSize();   // 建议 128 KB 级
size_t const outBuffSize = ZSTD_CStreamOutSize();
ZSTD_CCtx* const cctx = ZSTD_createCCtx();

/* 下面三个参数决定了多线程是否真的生效，别乱设 */
ZSTD_CCtx_setParameter(cctx, ZSTD_c_compressionLevel, 3);   // 常规落：3~7 性价比最高
ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers, 4);          // 0 表示单线程
ZSTD_CCtx_setParameter(cctx, ZSTD_c_jobSize,   1 << 20);    // 每个 worker 管多大块

while (还有输入) {
    ZSTD_inBuffer in = { src, bytesRead, 0 };
    while (in.pos < in.size) {
        ZSTD_outBuffer out = { dst, outBuffSize, 0 };
        size_t r = ZSTD_compressStream2(cctx, &out, &in, ZSTD_e_continue);
        if (ZSTD_isError(r)) { /* 一定要检查，别忽略返回值 */ }
        write_all(out.dst, out.pos);
    }
}
/* 收尾务必显式 flush + end，否则最后一帧不会落盘 */

关于 nbWorkers：它不是万能的。每个 job 之间的边界会有少量压缩率损失，多线程只有在单块够大（通常 >1 MB）且 CPU 不是瓶颈时才划算。给 4 KB 的小 record 开 8 线程，只会让延迟变高、比率变差。

解压侧的红线：解压炸弹

这是我在代码 review 里拦过最多次的一类漏洞。zstd 的帧头里有 content size 字段，但这个字段完全可以被攻击者伪造或省略：

unsigned long long const size = ZSTD_getFrameContentSize(src, srcSize);
if (size == ZSTD_CONTENTSIZE_ERROR)   goto err;
if (size == ZSTD_CONTENTSIZE_UNKNOWN) /* 未知 == 无限，必须自己设上限 */ ;
if (size > MY_MAX_OUTPUT)             goto err;

/* 即便 size 已知，仍要在每个 buffer 上累加并执行硬上限 */
size_t total = 0;
while (ZSTD_decompressStream(dctx, &out, &in) != 0) {
    total += out.pos;
    if (total > MY_MAX_OUTPUT) { goto err; }   // 没有这行，4 KB 输入可以吃掉你 16 GB 内存
}

一个 128 KB 的合法 zstd 帧，理论上能描述 GB 级输出。任何接受外部输入的解压点都必须有这条硬上限——这跟用什么 codec 无关，是通用边界校验。

其余要点速查

六、结论

把这条链路串起来看，zstd 的工程本质是三处正交的降维，而不是某个单一技巧：

• LZ77 去掉的是"重复" —— 跨时间维度的冗余，靠窗口大小和匹配质量取胜。
• Huffman 去掉的是"编码冗余" —— 但受限于整数 bit，在高倾斜分布上会崩。
• FSE/ANS 去掉的是 Huffman 剩下的那部分 —— 用一个整数状态吞掉亚比特级的信息，代价只是"每符号一次查表 + 一次移位"。

真正值得带走的调参顺序是：先把 window / 字典 / long mode 这些"数据侧"的旋钮拧对，再谈压缩级别。级别每 +1 换来的 1% 压缩率，通常远不如一个训得好的字典；而一个漏掉的输出上限检查，能让前面所有的优化在一夜之间变成一次线上事故。