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

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

Bloom filter 有一条硬限制：删不掉。一个 bit 可能被多个元素共用，清零时无从知道还有没有别人在用。计数型变体把每一位换成一个计数器，代价是内存翻几倍，且计数器会溢出。

cuckoo filter 换掉了「存位」这个前提。它为每个元素存一段 $f$ 位的 fingerprint，放进两个候选桶之一。删除因此有了明确语义：拿走一份指纹。

1 · 指纹与两个候选桶

结构是 $\text{numBuckets}$ 个桶，每桶 $b$ 个位置，每个位置存一段 $f$ 位指纹（0 留作空位标记）。候选桶由这两个式子给出：

i_1 = h(x) \bmod \text{numBuckets}, \qquad i_2 = i_1 \oplus \big( h(\text{fp}(x)) \bmod \text{numBuckets} \big)

桶数取 2 的幂时取模退化为按位与，上式的异或是对合的： $(i_1 \oplus t) \oplus t = i_1$ 。从 $i_2$ 出发同样算得回 $i_1$ 。

定义 1.1（partial-key cuckoo hashing） 元素的第二处候选由它的指纹而非它本身决定，故任何持有指纹的一方都能算出另一处候选，无须原 key。

这一条正是踢出能进行下去的全部依据。cuckoo hashing 的踢出链上，被换出来的是完整的 key，随时能重算它的两个候选；filter 里只留了指纹，原 key 早已丢掉。partial-key 的构造把「另一处候选」这个信息编码进了指纹本身。

图 1-1 · 16 个桶、每桶 4 个位置、指纹 8 位的 cuckoo filter 逐个装入。黄框是最近一次插入的踢出路径，蓝框是被查 key 的两个候选桶。可单步插入，可选一个 key 查看它的指纹与两处候选，以及从第二处反算回第一处。

代价写在同一行式子里： $i_2$ 由指纹决定，而指纹只有 $f$ 位，桶的选择空间随之被压到 $2^f$ 。 $f$ 太短时同一指纹的元素会挤在同一对桶里，装填率塌掉。

2 · 每桶 b 个位置

每桶只放一个指纹时，负载因子上不去。实测总位置数固定 65536、 $f = 12$ ：

$b$	桶数	装入	负载因子
1	65536	33671	0.514
2	32768	46383	0.708
4	16384	63126	0.963
8	8192	64860	0.990

$b = 1$ 那一行的 0.514 与 cuckoo hashing 的相变点 0.5 对得上，这不是巧合：两处是同一个随机图论结果。加大 $b$ 把相变点推高， $b = 4$ 时 0.963，而查找仍是两次访存，只是每次带回一整个 cache line。这条路的性价比最高，论文与 RedisBloom 都取 $b = 4$ 。

3 · 假阳率

查询检查两个桶共 $2b$ 个位置，任何一个与被查 key 的指纹相同就报「可能在」。单个位置误撞的概率是 $2^{-f}$ ，故假阳率约

\varepsilon \approx 1 - (1 - 2^{-f})^{2b} \approx \frac{2b}{2^f}

$b = 4$ 、 $f = 8$ 时理论值 3.125%，实测 2.96%； $f = 12$ 时理论 0.195%，实测 0.184%。 $f$ 每加一位假阳率大致减半。

4 · 删除的确切语义

删除是「从两个候选桶里找到一份匹配的指纹，清掉它」。这句话里的每一处限定都有后果。

正面：剩下的元素一律不受影响。指纹是一份份独立存放的，每次插入对应一份，拿走一份不会动到别人。实测 1024 桶 × 4 位置、装入 3946 个后删掉前 1973 个，剩下的 1973 个全部仍能查到，零假阴性。

反面：删掉的元素可能仍报「在」。若另一个仍在表里的 key 与它同指纹、同候选桶，清掉的那一份可能本属于对方，而对方的那一份留了下来。实测 1024 桶 × 4 位置、装入 3946 个后删掉前 1973 个，其中只有 1 个仍报存在，占 0.05%。

更硬的一条：只能删确实加过的元素。若对一个从未加过、但恰好指纹冲突的 key 调用删除，它会清掉别人的指纹，制造出一个真的假阴性。这一条在 Bloom filter 那边不存在（因为那边根本不提供删除），是 cuckoo filter 独有的使用约束。

图 4-1 · cuckoo filter 的删除与 Bloom filter 清位式删除的并列对照，下方给出一个被连坐的具体元素及它与被删元素共用的那一位。可调装入量与删除量观察两侧的假阴性数。

对照组是同规模的 Bloom filter： $m = 4096$ 、 $k = 7$ 装入 300 个，清掉第一个元素的 7 个 bit 后，另有 6 个从未被删的元素随之查不到。每一个都与被删元素共用了至少一位。

5 · 与 Bloom filter 的空间对照

「cuckoo filter 比 Bloom filter 省」这句话需要限定假阳率区间，否则它是错的。实测 $\text{numBuckets} = 16384$ 、 $b = 4$ ，逐档改 $f$ ，Bloom 一侧取理论最优的 $m/n = \log_2(1/\varepsilon)/\ln 2$ ：

$f$	实测假阳率	cuckoo bit / 元素	Bloom bit / 元素	比值
8	2.9647%	8.32	7.32	1.137
10	0.7340%	10.40	10.23	1.017
11	0.3632%	11.43	11.69	0.978
12	0.1840%	12.46	13.11	0.950
16	0.0138%	16.66	18.51	0.900

交叉点落在 $\varepsilon \approx 0.4\%$ 。宽松的假阳率下 cuckoo filter 反而更费—— $f = 8$ 时多花 13.7%。

成因在两个式子的形状。cuckoo 每元素要 $f/\alpha$ 位（ $\alpha$ 是装填率， $b = 4$ 时约 0.96），Bloom 要 $1.44 \log_2(1/\varepsilon)$ 位。前者是「 $\log_2(1/\varepsilon)$ 加一个常数再除以 0.96」，后者是「1.44 倍的 $\log_2(1/\varepsilon)$ 」。斜率小的那条终究会赢，但要等 $\log$ 足够大才补得回那个常数。

图 5-1 · 两种结构每元素比特数随目标假阳率的变化，竖线标出交叉点。可拖动指纹位数

f

定位到具体一档，下方另有每桶位置数对最高负载的影响。

警示 · 上表与论文给出的交叉点不同：Fan 等人报告的是约 3%，本页实测约 0.4%。差别有两处来源。一是本页的 Bloom 一侧取了理论最优值，而实际实现受 $k$ 取整与位数取整影响会更费；二是论文的 cuckoo 一侧带 semi-sorting 压缩，它把每元素省下约 1 位，本页的引擎没有实现。把这两项算进去，两条曲线的交叉点会明显右移。

6 · 插入失败与回滚

踢出预算耗尽时，手上还捏着最后一枚被换出的指纹。第一版引擎在这一步直接返回失败，测试立刻红了：那一枚被丢掉了，某个此前加进去的 key 从此查不到——「无假阴性」这条不变量在插入失败的那一刻破掉。

修法是记录踢出路径上每一步换出的槽号与原值，失败时逆序回滚。core/cfilter.test.ts 里有一条专门验它：装到装不下为止，随后每一次失败的插入前后逐格比对，矩阵必须一字不差。

生产实现的做法不太一样。论文与 RedisBloom 都留一个「victim」槽存下那枚指纹，查询时额外看一眼；这样既不丢元素，也省下回滚的开销，代价是查询多一次比较。本页的引擎选回滚，因为它让「无假阴性」成为一条无例外的不变量，写测试时不必给失败路径开特例。

7 · 参考文献

Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014). Cuckoo filter: practically better than Bloom. CoNEXT 2014, 75–88.
Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144.
Fan, B., Andersen, D. G., & Kaminsky, M. (2013). MemC3: compact and concurrent MemCache with dumber caching and smarter hashing. NSDI 2013, 371–384.
Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422–426.
Graf, T. M., & Lemire, D. (2020). Xor filters: faster and smaller than Bloom and cuckoo filters. ACM Journal of Experimental Algorithmics, 25, 1–16.