RocksDB 上的布谷鸟过滤器
今天在给 Kvrocks 审一个 PR。这个 PR 新增了布谷鸟过滤器（Cuckoo Filter）数据结构。之前我并不了解它，正好趁此机会学习一下。
要了解布谷鸟过滤器，需要先了解它的底层基础：布谷鸟哈希（Cuckoo Hashing）。如果你已经了解了布谷鸟过滤器和布谷鸟哈希，可以直接跳过这两个部分
布谷鸟哈希
布谷鸟哈希是一种解决哈希冲突的算法，由 Rasmus Pagh 和 Flemming Friche Rodler 在 2001 年提出。其设计灵感来源于布谷鸟的“巢寄生”行为：雏鸟孵化后会将巢中其他的蛋挤出去。
其核心逻辑如下：
- 多存储位置 通常使用两个哈希函数。对于任意元素 x，它只能存在于位置 h1(x) 或 h2(x) 中。
- 挤占 插入新元素 x 时，如果 h1(x) 已被占用，它会强制踢走原有的元素 y。
- 重新安置 被踢走的元素 y 会去寻找自己的另一个候选位置。如果该位置也被占领，则继续踢走那里的元素，直到所有元素都找到位置，或达到最大循环次数。
布谷鸟哈希最大的优点是查询性能极佳。因为每个元素最多只有两个可能的位置，查询只需检查两次。但它也有一个致命缺点：插入可能失败。
假设：
hash1(A) = 1, hash2(A) = 2
hash1(B) = 2, hash2(B) = 3
hash1(C) = 3, hash2(C) = 1
hash1(D) = 2, hash2(D) = 1当 A、B、C 分别占据位置 1、2、3 时，插入 D 会引发如下循环：
D 占据 2，踢走 B
B 占据 3，踢走 C
C 占据 1，踢走 A
A 又回到 2，踢走 D ...这种情况通常说明哈希表已接近饱和，需要扩容或 rehash。而扩容往往需要重建整个哈希表，因为桶（bucket）数改变后，所有元素的位置都需要重新计算。
布谷鸟过滤器
布谷鸟过滤器是基于布谷鸟哈希思路改进的。它与普通哈希表有一个重要区别：布谷鸟过滤器不存储原始 Key，而是存储指纹（fingerprint）。
其流程大致为：item -> hash -> fingerprint。
此外，布谷鸟过滤器的每个桶（bucket）通常包含多个插槽（slot）。也就是说，一个 bucket 可以存放多个指纹。在经典实现中，bucket_size 常见取值为 2 或 4。
例如：bucket = [17, 91, 0, 0]（其中 0 表示空 slot）。
这样做可以有效降低哈希冲突导致插入失败的概率。即使两个元素落入同一个桶，只要还有空 slot 即可成功插入。
相比布隆过滤器（Bloom Filter），布谷鸟过滤器的一个核心优势是支持删除。布隆过滤器无法安全地删除元素，因为多个元素可能共享同一个 bit 位；而布谷鸟过滤器存储的是指纹，删除时只需在候选桶中找到对应的指纹并清除即可。
有得必有失
引入 slot 虽然降低了插入失败率，但也会提高假阳性概率，并让删除与重复插入的语义变得微妙。
- 假阳性概率上升
查询时需要在两个候选桶的所有 slot 里比对。slot 越多，指纹误撞的概率就越大。 粗略计算，假阳性概率（FPR）与 bucket_size 成正比：FPR ~= 2 * bucket_size / fingerprint_space
如果指纹是 8 bit（空间为 255）：
- bucket_size = 2 -> FPR ~= 1.6%
- bucket_size = 4 -> FPR ~= 3.1%
- bucket_size = 8 -> FPR ~= 6.3%
- 重复插入与删除的副作用
由于只存指纹，如果同一个 item 被重复插入，桶里会留下多个相同的指纹。删除时只能删掉其中一个。由于指纹可能碰撞，我们无法确定删除的是否正是当初插入的那个原始 item。
本质上，slot 的引入是用更高的假阳性概率换取了更高的空间利用率和插入成功率。
回到 Kvrocks
在 Kvrocks 中，布谷鸟过滤器会面临存储上的挑战。Kvrocks 的底层引擎是 RocksDB，复杂数据结构通常通过 metadata + subkey 的方式存储。
最初的提案计划将每个 bucket 都作为一个独立的 RocksDB Key 存储： InternalKey(ns_key, filter_index + bucket_index, version) -> bucket_data
问题在于 bucket 太小了。 提案默认 bucket_size = 4 且指纹为 1 byte，这意味着 payload 只有 4 bytes。 但在 RocksDB 中，一个 Entry 除了这 4 bytes 外，还包含 internal key 前缀、namespace、版本号，以及 RocksDB 内部的 metadata、索引和 filter block。这会导致严重的存储放大（写放大、空间放大、读放大）以及巨大的后台 Compaction 成本。
解决方案：Page 分页
更好的方法是将多个 bucket 打包成一个 Page： InternalKey(ns_key, filter_index + page_index, version) -> page_data
Page 应该设多大？
假设每个 RocksDB Entry 的固定开销粗估为 77B。若每个 Key 只存一个 bucket（4B），则有效载荷仅占约 5%，浪费极其严重。
下表对比了不同 Page 大小的表现：
Page Size | Buckets/Page | 实际占用 | 满载利用率 | 持平单 Key 模式所需 bucket 数 |
|---|---|---|---|---|
1KB | 256 | 1101B | 93.01% | 14 |
2KB | 512 | 2125B | 96.38% | 27 |
4KB | 1024 | 4173B | 98.15% | 52 |
8KB | 2048 | 8269B | 99.07% | 103 |
虽然 Page 越大满载利用率越高，但 1KB 的表现已足够优秀。Page 过大的坏处在于稀疏场景下的浪费。如果 8KB 的 Page 里只写了一个 bucket，空间放大比例会非常夸张。
综合考虑扩容步长和初始状态（在小规模数据下，2KB 以上的 Page，1 个 Page 即可容纳所有数据，性能最佳），所以我最后觉得 2KB Page 是比较好的选择。
2KB Page 的优势在于平衡性：
- 满载利用率约 96.38%。
- 仅需 5.27% 的空间占用率（约 27 个 bucket）即可在存储效率上超越“单桶单 Key”模式。
- 相比 1KB，减少了一半的 Key 数量；相比 4KB，在稀疏场景下的空间利用更加稳健。