算法与数据结构 / 概率型 sketch · 用固定内存换有界误差 待审核 7 页

概率型 sketch · 用固定内存换有界误差

精确统计的内存与数据量同阶：数不同的 key 要一张 Set，数频次要一张 Map，报 p99 要把样本留着排序。sketch 换一条路——放弃精确，把内存钉成一个与数据量无关的常数，再给出一个可以算出来的误差界。这一族的每个成员都是同一笔交易的不同报价：估计什么、误差是相对还是绝对、单边还是双边、能不能合并、能不能删除。

Bloom filter 是这一族里最早也最简单的一个，它只答「在不在」。本系列往后走五步：HyperLogLog 用「前导零个数」估基数，12KB 报到 0.81% 的标准误；Count-Min Sketch 用 $d$ 行计数矩阵估频次，误差单边、只高估不低估；Space-Saving 只留 $k$ 个槽位就把 heavy hitters 捞出来；t-digest 按分位密度自适应分桶，于是 p99 附近的桶比 p50 附近细；cuckoo filter 存指纹而非位，因此删得掉。

正文里的每个数字都由 sketch/core/ 的引擎跑出来，并锁进 core/*.test.ts 的断言——包括那些与常见说法不符的：HLL 在两段修正的切换点附近偏差冲到 2.23%，而 t-digest 的 p99 值误差比 p50 大一个量级。

总纲：这一族共享的那笔交易

五个结构估的东西各不相同，但形态一致：一段固定大小的状态，一个只往前推的更新函数，一个把状态折算成答案的估计函数。差别落在五个对照维度上——估计什么、误差形式、内存、可否合并、可否删除。

sketch 家族 · 五个对照维度

固定内存与有界误差

精确统计的内存与数据量同阶。概率型 sketch 把内存钉成常数，代价是一个可以算出来的误差。本页给出这一族共享的形态、五个对照维度，以及同一批数据上五种估计的实测误差。

原始论文

Flajolet, Fusy, Gandouet & Meunier · HyperLogLog (2007) algo.inria.fr 基数估计的原始论文： $\alpha_m$ 的数值解、 $1.04/\sqrt{m}$ 的方差推导，以及小基数与大基数两段修正的来历。
Heule, Nunkesser & Hall · HyperLogLog in Practice (2013) research.google.com HLL++：64 位 hash 去掉大基数修正、稀疏表示省小基数时的内存、经验偏差表修掉过渡区的偏差。
Cormode & Muthukrishnan · An Improved Data Stream Summary (2005) cs.rutgers.edu Count-Min Sketch 的原始论文： $w = \lceil e/\varepsilon \rceil$ 、 $d = \lceil \ln(1/\delta) \rceil$ 的取法与单边误差界的证明。
Metwally, Agrawal & El Abbadi · Space-Saving (2005) cse.ust.hk Stream-Summary 结构与 guaranteed top-k 的判据：固定槽位、挤掉最小者并继承其计数。
Dunning & Ertl · Computing Extremely Accurate Quantiles Using t-Digests arxiv.org t-digest 的规范描述：scale function $k_1$ 、merging 与 clustering 两种实现，以及为什么 rank 误差在两端更小。
Fan, Andersen, Kaminsky & Mitzenmacher · Cuckoo Filter (2014) cs.cmu.edu partial-key cuckoo hashing、semi-sorting 压缩，以及与 Bloom filter 的空间对照曲线。
Karnin, Lang & Liberty · Optimal Quantile Approximation in Streams (KLL, 2016) arxiv.org KLL sketch：分层采样给出最优的 $O(\varepsilon^{-1} \log\log \delta^{-1})$ 空间，是 t-digest 之外另一条分位数路线。

数数：基数与频次

「有多少个不同的 key」与「这个 key 出现了多少次」是两个问题，答法也是两套。基数走 HyperLogLog 的极值统计，频次走 Count-Min Sketch 的计数矩阵；只要 top-k 而不要全表频次时，Space-Saving 用 $k$ 个槽位就够。

前导零 · 调和平均 · 标准误 1.04/√m

HyperLogLog：12KB 数清一亿个 key

基数估计。从「hash 的前导零个数」这一个观察出发，经分桶、调和平均与偏差修正常数，得到用 12288 字节把任意规模的基数估到 0.81% 标准误的结构。含两端修正的接缝处偏差、Redis 的两种编码，以及 PFMERGE 成立的理由。

d 行计数矩阵 · 单边误差 · 界 ε·N

Count-Min Sketch：只会高估的频次表

频次估计。d 行 w 列的计数矩阵，查询取 d 个格子的最小值。误差单边——只会高估、永不低估，界为 ε·N。含参数取法、高估量随流长的实测增长，以及 conservative update 在合并上的代价。

挤掉最小者 · 继承计数 · 门槛 N/k

Space-Saving：k 个槽位捞出 heavy hitters

top-k 与 heavy hitters。固定 k 个槽位，新 key 挤掉计数最小的那个并继承它的计数，每条槽位据此给出一个误差区间。含 k 的取法、门槛 N/k 的成立理由，以及与 Count-Min 加小根堆的实测对照。

标准误不是误差上限

「HLL 用 12KB 给出 0.81% 的误差」这句话省略了它的性质：

1.04/\sqrt{m}

是标准误，即相对误差这个随机量的标准差，不是任何一次估计的上限。单次估计落在

\pm 0.81\%

内的概率约 68%，落在

\pm 2.44\%

内约 99.7%。实测 24 组独立数据、真实基数 40 万时，均方相对误差 0.788%，最大 1.647%——把区间收窄到「误差不超过 0.81%」就是错的。真要一个上限，只能引 3 倍标准误，而这条也只在 HyperLogLog §5 指出的那一段之外成立。

形状：分位数为什么更难

基数与频次都是可加的量，分位数不是——两个分片各自的 p99 不能相加得到全局 p99。t-digest 的答案是存一串按分位密度自适应的 centroid，让两端的桶比中间细。

scale function · rank 误差 · 尾部更细

t-digest：按分位密度自适应分桶

分位数估计。分位数不可加，两个分片的 p99 无法合成全局 p99。t-digest 存一串 centroid，用 scale function 让两端的桶比中间细。含 rank 误差与值误差的实测分歧，以及等权分桶的同引擎对照。

成员判定与选型

Bloom filter 删不掉，因为一个 bit 可能被多个元素共用。cuckoo filter 换成存指纹，靠 partial-key cuckoo hashing 让踢出不需要原 key，于是删除有了明确语义。末页把这几个结构映到 Redis Stack 的命令上。

选哪个结构, 先看能不能合并

分布式场景里「可合并」往往比误差率更早决定选型：每台机器各自维护一份摘要、定期汇总，要求合并后的结果等于对全量数据直接建一份。HyperLogLog 的逐桶取 max 与 Count-Min 的逐格相加都满足这一条，且合并结果逐位等于直接建的那一份，不是近似相等。 t-digest 可合并但结果不逐位相同（centroid 要重排重压）。Count-Min 启用 conservative update 后，逐格相加仍不低估，却不再等于「对合并后的流跑一遍」——实测平均高估 22.96 对 22.25，逐格不相等；而看着更紧的逐格取 max 会直接低估。这两处的实测在 Count-Min Sketch §6。

工程实现

redis/src/hyperloglog.c github.com 一手实现：稀疏编码的 ZERO / XZERO / VAL 三个 opcode、hll-sparse-max-bytes 的转换条件，以及 PFMERGE 的逐桶取 max。
Redis · Probabilistic data types redis.io PFADD / CF.* / CMS.* / TOPK.* / TDIGEST.* 各命令的参数与内存行为。
RedisBloom github.com Bloom / cuckoo / Count-Min / Top-K / t-digest 五种结构的 Redis 模块实现，含各自的容量增长策略。
tdunning/t-digest github.com t-digest 的参考实现，含 MergingDigest 与 AVLTreeDigest 两版及其精度对照的基准。
Apache DataSketches datasketches.apache.org Theta sketch、KLL、CPC 等一组带形式化误差界的生产实现，文档里有各结构的精度与内存曲线。

指纹而非位 · partial-key 踢出 · 可删除

cuckoo filter：删得掉的概率型集合

可删除的 Bloom filter 替代。存的是指纹而非位，两个候选桶由 h1 与 h1 异或 h(指纹) 给出，踢出因此不需要原 key。含与 Bloom filter 在同假阳率下的空间交叉点，以及删除的确切语义。

PF · BF · CF · CMS · TOPK · TDIGEST

Redis 的 probabilistic 命令与选型

把前六页的结构映到 Redis 的一组命令上，逐项对齐参数、内存与合并能力。含两处与本系列引擎不同的实现选择，以及一条从「要回答哪一问」出发的选型判据。