Bloom Filter 家族：从位数组到 Ribbon，每键位数离下界还差多少

关于 Bloom filter 家族，流传最广的说法有三条：“误判率就是 \((1-e^{-kn/m})^k\)”；“cuckoo filter 比 Bloom filter 省空间，还能删除”；“RocksDB 默认给每个 SST 配 10 bits/key 的 Bloom filter，后来又换成了更省的 Ribbon”。三条都要打折扣。那个公式是近似，而且对 \(k \ge 2\) 是严格偏低的；cuckoo filter 只有在误判率低于约 3%（带 semi-sorting）时才比 Bloom 省；RocksDB 9.10 的 filter_policy 默认是 nullptr，不配置就没有 filter，Ribbon 也要显式打开。

本文用一个问题串起整个家族：给定误判率 \(\varepsilon\)，每个键至少要多少位，每种结构离这个下界差多少、差在哪里、换来了什么。 顺序是”下界 → Bloom 及其变体 → 存指纹的哈希表 → 解线性方程的静态过滤器 → 生产实现 → 争论”。所有每键位数与误判率都来自同目录的 reproduce/filters.c 和 reproduce/exact_fpr.py（环境见第二节）；RocksDB 与 LevelDB 的行为以 9.10.0 与 1.23 的源码为准。Cuckoo Hashing 一文已经讲过 cuckoo filter 的桶结构和部分键哈希，这里只做家族视角的比较。

一、问题：近似成员查询与空间下界

近似成员查询

给定全集 \(U\) 中的一个 \(n\) 元集合 \(S\)，近似成员查询（approximate membership query，AMQ）结构回答”\(x \in S\) 吗”，要求：

• \(x \in S\) 时一定回答”是”，没有假阴性（false negative）；
• \(x \notin S\) 时回答”是”的概率不超过 \(\varepsilon\)，这就是误判率，也叫假阳性率（false positive rate，FPR）。

它的典型用途是挡在一次昂贵的查找前面。LSM-tree 查一个不存在的键时，每个 SST 文件的 filter 若回答”否”，就可以跳过这个文件的索引块和数据块读取；只有回答”是”时才去读，其中比例为 \(\varepsilon\) 的读取是白读。

下界：每键 \(\log_2(1/\varepsilon)\) 位

Carter、Floyd、Gill、Markowsky、Wegman（STOC 1978）给出了这个问题的空间下界。论证是计数：设结构用 \(M\) 位，共有 \(2^M\) 种状态。每种状态对应一个”回答为是”的集合 \(A\)，它必须包含 \(S\)，并且至多含 \(n + \varepsilon(u-n)\) 个元素（\(u = |U|\)）。一种状态最多能服务 \(\binom{|A|}{n}\) 个不同的 \(S\)，而所有 \(\binom{u}{n}\) 个 \(n\) 元集合都必须被某个状态服务，所以

\[ 2^M \binom{n + \varepsilon(u-n)}{n} \ge \binom{u}{n} \quad\Longrightarrow\quad M \ge \log_2 \frac{\binom{u}{n}}{\binom{n+\varepsilon(u-n)}{n}} \approx n \log_2 \frac{1}{\varepsilon} \quad (u \gg n). \]

最后一步用了 \(\binom{u}{n} / \binom{\varepsilon u}{n} \approx \varepsilon^{-n}\)。下界与键本身多长无关：过滤器存的是哈希后的信息，不是键。

表中 1.44 是 \(1/\ln 2 \approx 1.4427\)，来历见第二节。

谱系

今天的过滤器从三条路线分叉：

• 位数组，AND 探测：Bloom（CACM 1970）→ Fan 等人的 counting Bloom filter（SIGCOMM 1998；IEEE/ACM ToN 2000）→ Kirsch 与 Mitzenmacher 的双重哈希（ESA 2006）→ Putze、Sanders、Singler 的分块 Bloom（WEA 2007；JEA 2009）→ RocksDB 的 FastLocalBloom（6.6.0 起）。
• 存指纹的哈希表，OR 探测：quotient filter（Bender 等，PVLDB 2012）、cuckoo filter（Fan 等，CoNEXT 2014）、counting quotient filter（Pandey 等，SIGMOD 2017）。
• 解线性方程，XOR 探测，只支持静态集合：Bloomier filter（Chazelle 等，SODA 2004）与 Dietzfelbinger–Pagh 的检索结构（ICALP 2008）→ xor filter（Graf 与 Lemire，JEA 2020）→ binary fuse filter（Graf 与 Lemire，JEA 2022）；另一支从 Dietzfelbinger 与 Walzer 的带状矩阵高斯消元（ESA 2019）到 Ribbon filter（Dillinger 与 Walzer，arXiv 2021；期刊版 Dietzfelbinger 等，JACM 2026）→ RocksDB 的 NewRibbonFilterPolicy（6.15.0 起）。

“AND / OR / XOR 探测”是 Ribbon 论文第 1 节的分类：查询时要求所有探测位都是 1、任一探测位置的指纹匹配、或所有探测位置异或后与指纹相等。

二、Standard Bloom filter：公式、最优 \(k\) 与公式的误差

结构

一个 \(m\) 位的位数组，初始全 0；\(k\) 个哈希函数，每个把键映射到 \(\{0, \ldots, m-1\}\)。插入把 \(k\) 个位置置 1；查询检查这 \(k\) 位，全为 1 回答”可能在”，有一位为 0 就回答”一定不在”。

图里的 q1 从未插入，它的三个位置分别是 y、x、y 置的，这就是假阳性的全部机制：不同键的位在数组里混在一起，没有任何一位”属于”某个键。同一个事实也决定了 Bloom filter 不能删除，把第 13 位清零会同时抹掉 x 和 y。

近似公式与最优 \(k\)

假设每个哈希值独立均匀。插入 \(n\) 个键共做 \(kn\) 次置位，某一位仍为 0 的概率是

\[ p_0 = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}. \]

若再假设查询的 \(k\) 个位置”是否为 1”彼此独立，误判率就是

\[ \varepsilon \approx \left(1 - e^{-kn/m}\right)^k . \]

记 \(b = m/n\) 为每键位数。对 \(k\) 求最小值，得到 \(k^* = b \ln 2\)，此时 \(p_0 = 1/2\)、\(\varepsilon = 2^{-k^*}\)。反解出

\[ b = \frac{\log_2(1/\varepsilon)}{\ln 2} \approx 1.44 \log_2 \frac{1}{\varepsilon}. \]

这 44% 的额外开销有一个直观解释：最优时一半的位是 1，每次探测只能排除一半的非成员，所以要 \(\log_2(1/\varepsilon)\) 次探测；而每次插入要写 \(k\) 位，让一半的位变成 1 需要 \(m \ln 2 = nk\) 次置位，于是 \(m = nk/\ln 2\)。位数组里的 1 位是被多个键”碰撞”共享的，这部分冲突就是和下界之间的差。

\(k\) 必须是整数，所以实际误判率比 \(2^{-b\ln 2}\) 略高。取 \(b = 10\)：\(k=7\) 时公式给出 0.819%；LevelDB 按 \(\lfloor 0.69 b \rfloor\) 取 \(k=6\)，公式给出 0.843%。

这个公式偏低

Bose、Guo、Kranakis、Maheshwari、Morin、Morrison、Smid、Tang（Information Processing Letters 2008）指出，推导里”各探测位是否为 1 彼此独立”的假设不成立：知道前几位是 1，会提高后面的位也是 1 的概率（位数组里 1 的总数是随机的）。他们的反例是 \(n=1\)、\(k=2\)、\(m=2\)：枚举 16 种情况可得误判率为 \(5/8\)，而公式 \((1-(1-1/m)^{kn})^k\) 给出 \(9/16\)。他们证明对任意 \(k \ge 2\) 这个公式都是严格下界。Christensen、Roginsky、Jimeno（IPL 2010）随后指出 Bose 等人给出的精确式里 Stirling 数那一项写错了，还指出通常归到 Bloom 名下的”经典公式”其实不是 Bloom 原文的推导：Bloom 1970 年论文里的 Method 2 把某位仍为 0 的比例写成 \((1-k/m)^n\)。他们给出的精确式可以写成

\[ \varepsilon_{\text{exact}} = \frac{1}{m^{k(n+1)}} \sum_{i=1}^{m} i^k \, i! \binom{m}{i} S(kn, i), \]

其中 \(S(kn, i)\) 是第二类 Stirling 数，即把 \(kn\) 次置位分成 \(i\) 个非空组的方式数；乘上 \(i!\binom{m}{i}\) 就是这些置位恰好覆盖 \(i\) 个不同位的方式数。reproduce/exact_fpr.py 先在 5 个小参数上用暴力枚举核对这个式子（全部一致，其中包括 \(5/8\)），再与两种近似比较（python3 exact_fpr.py，结果见 reproduce/exact_fpr_results.txt）：

偏差随 \(m\) 增大而缩小：1024 位时只剩 0.4%。所以争论的实际结论是，对几十位、几百位的小过滤器，经典公式会低估误判率；对数据库里动辄百万位的过滤器，它足够准。 下面的实测也支持这一点。

实验环境与口径

• CPU：Intel Core i9-12900K（WSL2 报告 24 个逻辑 CPU），内核 6.6.87.2-microsoft-standard-WSL2，GCC 16.1.1 20260430，Python 3.14.5。
• 编译运行：gcc -O2 -Wall -Wextra -o filters filters.c -lm && ./filters，可用 ./filters e1 到 e7 单跑一个实验。完整运行约 45 秒（taskset -c 2 绑核，只用于减少干扰，文中没有计时数据）。
• 规模：\(n = 2^{20}\) 个成员键，\(2^{25}\) 个非成员查询键。键由 splitmix64 的终结器从两个不相交的整数区间生成，因为它是双射，成员与非成员不会重合。每种过滤器再用带种子的同一函数对键做一次哈希。
• 指标：每键位数、实测误判率、负载、构建成功率、消元步数、每次查询触及的 64 字节缓存行数，全部与时钟无关。种子固定，三次完整运行输出逐字节一致，结果保存在 reproduce/results.txt。每个实验都检查了所有成员键的查询结果，没有假阴性。
• 另用 -fsanitize=address,undefined 编译逐个跑过 e1 到 e7，无报错。

双重哈希：两个哈希值就够

实现不需要 \(k\) 个独立哈希函数。Kirsch 与 Mitzenmacher（ESA 2006；Random Structures & Algorithms 2008）证明，用 \(g_i(x) = h_1(x) + i\,h_2(x) \bmod m\) 模拟 \(k\) 个哈希函数，渐近误判率不变。./filters e1 在同一组键上对比两种做法：

三列的差别在统计噪声以内（10 bits/key 那一行约 27 万次假阳性，相对标准误约 0.2%）。LevelDB 1.23 就是这样做的，而且只用一个 32 位哈希值，把它循环右移 17 位作为增量：

// LevelDB 1.23, util/bloom.cc, BloomFilterPolicy::CreateFilter()（有删减）
    size_t bits = n * bits_per_key_;
    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;
    ...
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }

构造函数里 k_ = bits_per_key * 0.69 向下取整并限制在 1 到 30，注释说明是”intentionally round down to reduce probing cost”；\(k\) 写在 filter 的最后一个字节里，读取端按它探测。最少 64 位的限制对应上一小节的结论：过滤器太小时，误判率既高又偏离公式。

三、Counting Bloom filter：删除的代价

把位换成计数器

Fan、Cao、Almeida、Broder 在 Summary Cache 论文（SIGCOMM 1998；IEEE/ACM ToN 2000）中需要让代理缓存的摘要随缓存内容增删，于是把每一位换成一个小计数器：插入给 \(k\) 个计数器加 1，删除减 1，查询检查它们是否都非零。

第三行说明了一条使用约束：只能删除确实插入过的键。删除一个假阳性键会把别的键的计数器减到 0，制造出 Bloom filter 本来保证不会有的假阴性。cuckoo filter 和 quotient filter 有同样的约束。

4 位够不够

计数器要多宽？在最优 \(k = b\ln 2\) 下，某个计数器至少为 \(i\) 的概率不超过 \(\binom{nk}{i} m^{-i} \le \left(\frac{e\,nk}{i\,m}\right)^i = \left(\frac{e \ln 2}{i}\right)^i\)，对所有 \(m\) 个计数器取并：

\[ \Pr[\text{某个计数器} \ge 16] \le m \left(\frac{e \ln 2}{16}\right)^{16} \approx 1.37 \times 10^{-15}\, m . \]

所以 4 位计数器（Fan 等人的选择）在任何实际规模下几乎不会溢出。./filters e3 用 \(m = 10n\) 个计数器、\(k=7\)，在 \(2^{20}\) 个键上跑 5 个种子：最大计数器分别是 8、9、9、8、8；值为 8 的计数器占 \(7.8 \times 10^{-7}\)，值为 9 的占 \(5.7 \times 10^{-8}\)。离 16 还远。如果要防御溢出，可以让计数器饱和：到 15 后不再加，也不再减。这不会产生假阴性，只是那个位置永远不能回到 0。

代价是空间直接乘 4：1% 误判率要约 \(4 \times 9.59 \approx 38\) bits/key。cuckoo filter 论文 Table 1 把 counting Bloom 的空间列为标准 Bloom 的 3 到 4 倍，quotient filter 论文也说”BFs incur a 4× space blow-up to support deletion”。正因为这个代价，后来支持删除的过滤器都改走存指纹的路线（第五节）。

四、分块 Bloom filter：一次查询只碰一条缓存行

为什么要分块

标准 Bloom filter 的 \(k\) 个位置在整个数组里均匀分布。数组比缓存大时，一次命中查询要碰 \(k\) 条缓存行；非成员查询遇到第一个 0 就停，但也要碰约 2 条。./filters e2 统计了每次查询触及的不同 64 字节缓存行数：非成员查询平均 1.81 到 2.07 条，成员查询几乎恰好是 \(k\) 条（\(k = 17\) 时平均 16.998 条）。

Putze、Sanders、Singler（WEA 2007；JEA 2009）的分块 Bloom filter（blocked Bloom filter）先用一个哈希值选出一个缓存行大小的块，再把这个键的 \(k\) 位全部放进块里，任何查询都只碰一条缓存行。RocksDB 从 6.6.0 起的新 Bloom 实现（format_version=5）就是这种结构，源码里叫 FastLocalBloom：

// RocksDB 9.10.0, util/bloom_impl.h, class FastLocalBloomImpl
  static inline void AddHash(uint32_t h1, uint32_t h2, uint32_t len_bytes,
                             int num_probes, char *data) {
    uint32_t bytes_to_cache_line = FastRange32(h1, len_bytes >> 6) << 6;
    AddHashPrepared(h2, num_probes, data + bytes_to_cache_line);
  }

  static inline void AddHashPrepared(uint32_t h2, int num_probes,
                                     char *data_at_cache_line) {
    uint32_t h = h2;
    for (int i = 0; i < num_probes; ++i, h *= uint32_t{0x9e3779b9}) {
      // 9-bit address within 512 bit cache line
      int bitpos = h >> (32 - 9);
      data_at_cache_line[bitpos >> 3] |= (uint8_t{1} << (bitpos & 7));
    }
  }

块就是一条 64 字节、512 位的缓存行。一个 64 位哈希值拆成两半：低 32 位 \(h_1\) 用 FastRange32（乘法取高位）选缓存行，高 32 位 \(h_2\) 每次乘以 32 位黄金比例常数，取最高 9 位作为行内位地址。启用 AVX2 时，HashMayMatchPrepared() 用一次 _mm256_mullo_epi32 同时算出 8 个探测位置，这也是 ChooseNumProbes() 注释里说”can (with AVX2) make up to 8 probes for the same cost”的原因。

图中的 6 个位地址是 reproduce/draw_diagrams.py 按上面的源码公式从图上标注的 \(h_1\)、\(h_2\) 算出来的。

代价：同样的位数，误判率更高

reproduce/filters.c 按上面的公式移植了 FastLocalBloom（包括 ChooseNumProbes() 的 \(k\) 表），哈希函数换成本文统一的 splitmix64，与 RocksDB 用的 XXH3 不同。与同样位数、最优整数 \(k\) 的标准 Bloom 比较（./filters e2）：

10 bits/key 时实测 0.967%。bloom_impl.h 的注释写的是：10 bits/key、6 次探测、512 位块时理论最优为 0.9535%，“This implementation yields about 0.957%”；本文的移植换了哈希函数，结果与之接近。差距随位数增加迅速拉大，原因有两个：

1. 块间负载不均。 每块平均装 \(512/b\) 个键，实际个数近似服从 Poisson 分布。误判率是块内负载的凸函数（大致按指数变化），装得多的块误判率上升的幅度大于装得少的块下降的幅度，平均下来比均匀负载高；目标误判率越低，这种凸性的影响越大。
2. 探测数被压低。 同一块里的 \(k\) 位本身也会互相碰撞，块越”满”越不划算。RocksDB 的注释写明，“the best choice for cache-local Bloom can be notably smaller than standard bloom, e.g. 9 instead of 11 @ 16 b/k”，表中 16 bits/key 一行正是这两个值。

换算成空间：24 bits/key 的分块 Bloom 只达到 \(\log_2(1/\varepsilon) = 14.2\) 位对应的误判率，比下界多 69%，而标准 Bloom 始终是 44%。Ribbon 论文第 1 节也说分块 Bloom 在小 \(\varepsilon\) 时空间开销可以超过 50%。它换来的是查询只有一次随机访存。Ribbon 论文对静态过滤器的比较（Figure 1，见第十节）显示，只要这个空间开销可以接受，分块 Bloom 仍是最快的。

五、存指纹的哈希表：quotient filter 与 cuckoo filter

另一条路线不用位数组，而是把每个键的 \(p\) 位指纹存进一个紧凑的哈希表。查询时检查几个候选位置里是否有相同的指纹，只要有一个匹配就回答”是”（OR 探测）。指纹是逐键存放的，所以可以删除、可以动态插入。Ribbon 论文第 1 节总结过这类结构的共性：已知的实例每键都要 \((1+\epsilon)\lambda + \mu\) 位，其中 \(\lambda = \log_2(1/\varepsilon)\)，附加项 \(\mu > 1.44\)，为了速度常取 \(\mu = 3\)。\(\mu\) 是一个常数，所以误判率越低，它相对 \(\lambda\) 越不显眼，这类结构越划算。

Quotient filter

Bender、Farach-Colton、Johnson、Kraner、Kuszmaul、Medjedovic 等人的 quotient filter（“Don’t Thrash: How to Cache Your Hash on Flash”，PVLDB 5(11), 2012）把 \(p\) 位指纹拆成高 \(q\) 位的商（quotient）和低 \(r = p - q\) 位的余数（remainder）。表有 \(2^q\) 个槽，商就是指纹的”本来位置”（canonical slot），槽里只存余数，再加 3 个元数据位：

• is_occupied：有某个指纹的商等于这个槽号；
• is_continuation：这个槽里的余数不是它所在 run 的第一个；
• is_shifted：这个槽里的余数不在它的本来位置。

同一个商的余数排成一个连续的 run，run 按商有序排列；位置被占时整体向后挪，就像线性探测。

注意 is_occupied 描述的是”槽号”，不是”槽里的内容”：槽 2 的 is_occupied 为 1，因为 C 的商是 2，可 C 实际存在槽 3。查询商为 2 的指纹时，先看槽 2 的 is_occupied，为 0 就直接回答”否”；为 1 就向左扫到 cluster 的起点（is_shifted 为 0 的槽 1），数出商 2 前面有几个 run，再向右跳过这么多个 run，找到商 2 的 run 逐个比较余数。

论文第 3 节给出的误判率是两个元素指纹完全相同的概率

\[ 1 - \left(1 - 2^{-p}\right)^n \approx 1 - e^{-n/2^p} \le \frac{n}{2^p} \le 2^{-r}, \]

每键空间约为 \((r+3)/\alpha\) 位，\(\alpha\) 为负载。论文建议负载不超过 75%，因为 cluster 变长后插入和查询都会变慢；在 1% 误判率这样的典型配置下，论文估计它比 Bloom filter 多用约 20% 的空间。换来的是删除、按哈希序遍历、合并两个过滤器以及扩容，这些都来自”余数按商有序存放”。Pandey、Bender、Johnson、Patro 的 counting quotient filter（SIGMOD 2017）在此基础上改了元数据编码，并支持计数。

Cuckoo filter

cuckoo filter（Fan、Andersen、Kaminsky、Mitzenmacher，CoNEXT 2014）用分桶 cuckoo hashing 存指纹：每个键有两个候选桶，每桶 \(b\) 个槽。它的关键是部分键 cuckoo hashing：

\[ i_1 = \mathrm{hash}(x), \qquad i_2 = i_1 \oplus \mathrm{hash}(f), \]

另一个桶只依赖当前桶号和指纹 \(f\)，搬动指纹时不需要知道它来自哪个键。

桶结构、踢出过程、异或对称性为什么要求桶数是 2 的幂，见 Cuckoo Hashing 第八节。空间上，论文第 5 节给出：\(f\) 位指纹、负载 \(\alpha\) 时，非成员查询检查两个桶共 \(2b\) 个指纹，误判率上界为

\[ 1 - \left(1 - 2^{-f}\right)^{2b} \approx \frac{2b}{2^f}, \]

所以 \(f \ge \lceil \log_2(1/\varepsilon) + \log_2(2b) \rceil\)，每键 \((\log_2(1/\varepsilon) + 3)/\alpha\) 位（\(b=4\)）。桶内指纹排序后用查表编码（semi-sorting）可再省 1 位，变成 \((\log_2(1/\varepsilon) + 2)/\alpha\)；\(b = 4\) 时论文取 \(\alpha = 95.5\%\)。

./filters e4 在 \(2^{18}\) 个桶（\(2^{20}\) 个槽）里用随机游走插入，最多踢 500 次，第一次失败时停下，被挤出的最后一个指纹放进一个 victim 槽（与参考实现 efficient/cuckoofilter 相同），不做 semi-sorting：

第五列用 \(2^f - 1\) 而不是 \(2^f\)，因为实现和参考代码一样把指纹 0 留作”空槽”；乘 \(\alpha\) 是因为只有被占用的槽能匹配。负载停在 95% 到 96%，与论文的 95% 和 Cuckoo Hashing 第四节实测的 96.3% 一致。

什么时候比 Bloom 省？令 \(\lambda = \log_2(1/\varepsilon)\)，解 \(1.44\lambda = (\lambda + c)/0.955\)：

• 不做 semi-sorting（\(c = 3\)）：\(\lambda \approx 7.9\)，交点在 \(\varepsilon \approx 0.4\%\)。实测也是如此：\(f=10\) 时 10.39 bits/key 得到 0.751%，同样位数的最优 Bloom 按公式是 0.68%，Bloom 仍略好；\(f = 12\) 时 12.47 bits/key 得到 0.189%，Bloom 是 0.25%，cuckoo 反超。
• 做 semi-sorting（\(c = 2\)）：\(\lambda \approx 5.3\)，交点在 \(\varepsilon \approx 2.5\%\)。论文的表述是”more space efficient than Bloom filters when \(\epsilon < 3\%\)“。

所以”cuckoo filter 比 Bloom 省”这句话，前提是误判率足够低，而且在 0.4% 到 3% 之间还取决于是否实现了 semi-sorting。另外，论文的公式假设表被填到 \(\alpha\)；桶数必须是 2 的幂，\(n\) 稍多于某个 2 的幂容量的 95% 时就要把桶数翻倍，实际负载会降到一半左右，每键位数随之翻倍。

六、Xor 与 binary fuse：给静态集合解一个线性方程组

从静态函数到过滤器

如果集合在构建后不再变化，还有一条更省的路线。静态函数（static function，也叫检索结构）存储一个映射 \(S \to \{0,1\}^r\)，对 \(S\) 外的键可以返回任意值。Dietzfelbinger 与 Pagh（ICALP 2008）观察到：取一个随机指纹函数 \(\mathrm{fp}: U \to \{0,1\}^r\)，把它在 \(S\) 上的限制存成静态函数，查询时比较”存的值”和”算出的指纹”，就得到误判率 \(2^{-r}\) 的过滤器，因为非成员的指纹与存储内容无关。

xor filter（Graf、Lemire，ACM JEA 25, 2020）是这个思路最直接的实现：数组 \(B\) 分成 3 段，每个键在每段里哈希出一个位置，要求

\[ B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)] = \mathrm{fp}(x) \qquad \text{对所有 } x \in S . \]

查询就是三次读取、两次异或、一次比较：

/* reproduce/filters.c：xor filter 查询 */
static int xor_query(const Xor *x, uint64_t key)
{
    uint64_t h = mix64(key ^ x->seed);
    uint32_t s[3];
    xor_slots(x, h, s);
    return (x->B[s[0]] ^ x->B[s[1]] ^ x->B[s[2]]) == xor_fp(x, h);
}

构建：剥离

这是 \(n\) 个方程、\(|B|\) 个未知数的 GF(2) 线性方程组，每个方程只有 3 个非零系数。Graf 与 Lemire 按 Botelho、Pagh、Ziviani 构造完美哈希的做法用剥离（peeling）求解：反复找出只被一个键用到的槽，把这个键”挂”在这个槽上并从图中删掉；全部删完后按相反顺序给挂着的槽赋值，每个槽被赋值时，它所在方程的另外两个槽要么已经赋值，要么仍是 0。

图里 B1 的值依赖 B3：c 最先被剥离，所以最后赋值，这时 b 已经写好了 B3。剥离能成功的前提是方程足够稀疏。3 元随机超图的剥离阈值约为 \(0.82\)（Ribbon 论文第 2 节记作 \(c_3^\Delta\)），所以数组至少要约 \(1.22n\) 个槽。Graf 与 Lemire 取 \(|B| = \lfloor 1.23n \rfloor + 32\)，论文 Figure 1 显示单次构建成功的概率总在 0.8 以上，失败就换一个种子重来。

注意这个阈值和 Cuckoo Hashing 第四节的可定向阈值 \(c_{3,2} \approx 0.918\) 不是一回事：高斯消元只要求方程组有解，阈值是 XORSAT 的 \(0.918\)；剥离是一种贪心解法，阈值更低。Ribbon 走的就是”不剥离、直接消元”的路线（第七节）。

./filters e5 的结果：

每键位数恰好是 \(1.23f\)（\(f=8\) 时 9.84，与论文一致），误判率就是 \(2^{-f}\)，与负载无关。9 个 \(f\) 值的构建都是第一个种子就成功。另在较小的集合上统计单次构建成功率：\(n = 100\) 时 2000 次里成功 95.7%，\(n = 1000\) 时 89.6%，\(n = 10^4\) 时 500 次里成功 90.4%，\(n = 10^5\) 时 100 次全部成功，都高于论文说的 0.8。

继续压缩：xor+ 与 binary fuse

\(1.23\) 这个系数来自剥离阈值，要再省空间有两种办法：

• xor+（同一篇论文第 3 节）：\(1.23n\) 个槽里约 \(0.23n\) 个是空的。构建时用 3 个队列，先处理前两段，把空槽尽量赶到第三段（论文实测第三段平均 36% 为空），只对第三段用 Rank9 压缩掉空槽，每键 \(1.0824f + 0.5125\) 位，代价是查询多一次 rank 运算。
• binary fuse filter（Graf、Lemire，ACM JEA 27, 2022）：采用 Dietzfelbinger 与 Walzer 建议的分法，把数组切成很多同样大小、互不重叠的小段（例如几百段），每个键的 3 个位置落在 3 个连续的小段里。大集合时 3-wise 版本只要约 \(1.125n\) 个槽，4-wise 约 \(1.075n\)；论文摘要称它离存储下界在 13% 以内。本文没有实现 binary fuse，第八节图中它的曲线是论文公式。

七、Ribbon：带状矩阵上的逐行高斯消元

方程的形状

Ribbon filter 由 Dillinger（当时在 Facebook）与 Walzer 在 arXiv 预印本 “Ribbon filter: practically smaller than Bloom and Xor”（arXiv:2103.02515，2021，未经同行评审）中提出，名字是 “Rapid Incremental Boolean Banding ON the fly” 的缩写。它的方程组来自 Dietzfelbinger 与 Walzer（ESA 2019）的 sgauss 构造；后来这条线的完整分析以 Dietzfelbinger、Dillinger、Hübschle-Schneider、Sanders、Walzer 的 “Ribbon: Fast Succinct Static Retrieval and Approximate Membership” 发表在 JACM 73(1), 2026。

每个键 \(x\) 对应一个随机起点 \(s(x)\) 和一个 \(w\) 位的随机系数向量 \(c(x)\)（强制首位为 1），方程是”从第 \(s(x)\) 行开始的 \(w\) 行解向量，按 \(c(x)\) 选出来异或，等于 \(r\) 位的 \(b(x)\)“。把方程按起点排序，所有非零系数都落在一条宽为 \(w\) 的斜带（ribbon）里，高斯消元不会在带外产生填充。

逐个插入方程

Dillinger 与 Walzer 的算法（论文 Algorithm 1）不需要先排序：系统 \(M\) 有 \(m\) 行，第 \(i\) 行要么空着，要么存一个以第 \(i\) 列开头（首位为 1）的方程。插入一个方程时，若它起点所在的行已被占用，就把那一行异或进来，首位变成 0，右移到下一个 1，重复直到落进空行：

复现程序里的实现与论文 Algorithm 1 一一对应（\(w = 64\)，系数用一个 uint64_t，最低位是”首位”）：

/* reproduce/filters.c：标准 Ribbon 的插入，对应 Dillinger & Walzer Algorithm 1 */
static int rb_add(Ribbon *rb, uint64_t key)
{
    uint32_t i, b; uint64_t c;
    rb_hash(rb, key, &i, &c, &b);
    for (;;) {
        rb->steps++;
        if (!rb->C[i]) { rb->C[i] = c; rb->Bv[i] = b; return 1; }
        c ^= rb->C[i]; b ^= rb->Bv[i];
        if (!c) return b == 0;
        int j = __builtin_ctzll(c);
        i += (uint32_t)j; c >>= j;
    }
}

c 变成 0 时有两种情况：b 也是 0，说明这个方程已被之前的方程蕴含，可以丢掉；b 不是 0，说明方程组矛盾，构建失败，要换种子重来。全部插入后从最后一行向上回代，每行解出一个 \(r\) 位值。查询只读从 \(s(x)\) 开始的连续 \(w\) 行，这是它比 xor filter 局部性好的地方。

需要多少余量

每键空间是 \((1+\epsilon) r\) 位，\(m = (1+\epsilon)n\)。\(\epsilon\) 不是常数：带宽 \(w\) 固定时，\(m\) 越大，需要的余量越大。论文 Table 1 给出了”插入直到第一次失败”时的经验余量，./filters e6 用同样的方式（起点在 \([0, m-64]\) 上均匀，对应表中不做 smash 的列）跑 5 个种子取中位数：

5 个种子的波动很大，但量级与论文一致。固定 \(n = 2^{20}\)、每个比例 20 个种子：\(m/n = 1.06\) 时 0 次成功，1.08 时 6 次，1.10 时 15 次，1.12 时 20 次全成功；每个键平均 3.6 到 4.3 次消元循环。论文的办法是加宽带（\(w = 128\) 时同一列的余量约为 \(w=64\) 的一半）、在分片边界附近集中起点（smash），或者用 Homogeneous Ribbon 与实验性的 Balanced Ribbon；论文报告 \(w=64\) 的 Balanced Ribbon 每键约 \(1.005\lambda + 0.008\) 位。

./filters e7 取 \(m = \lceil 1.10n \rceil\)，失败就换种子：

最后一列按”每行 \(r\) 位、行与行紧密相接”的布局计算：一次查询读 \(64r\) 个连续的位，\(r = 8\) 时约 2 条缓存行，而 xor filter 是 3 次互不相邻的读取。RocksDB 的实际布局与此不同（见第九节），这一列只说明”连续读取”这个性质，不代表 RocksDB 的数字。

八、全家族对比：离下界差多少

把 e2、e4、e5、e7 的全部测量点画在一张图上。左图是每键位数对误判率，右图是每键位数除以 \(\log_2(1/\text{FPR})\)，即”是下界的几倍”。实线和虚线是公式，带标记的折线是实测：

图由 reproduce/plot_space_fpr.py 从 results.txt 生成。取误判率在 0.1% 附近的实测点：

四种曲线形状对应四种误差来源：

• Bloom 是常数倍 \(1/\ln 2\)：最优时每位为 1 的概率是 \(1/2\)，每次探测把误判率减半，要 \(k = \log_2(1/\varepsilon)\) 次探测；而每键 \(b\) 位最多支撑 \(k = b\ln 2\) 次探测，所以 \(b = \log_2(1/\varepsilon)/\ln 2\)。
• 分块 Bloom 的倍数随 \(\varepsilon\) 变小而增大：块间负载不均的代价按指数放大。
• 指纹表是加性常数 \(\mu\)：每键多出的 3 位左右（元数据、桶内位置信息、\(\log_2(2b)\)）不随 \(\varepsilon\) 变化，\(\varepsilon\) 越小占比越低。
• 线性方程组是常数倍 \(1+\epsilon\)：xor 的 \(\epsilon = 0.23\) 来自剥离阈值，Ribbon 的 \(\epsilon\) 取决于带宽 \(w\) 和 \(n\)，binary fuse 把 xor 的 \(\epsilon\) 降到 0.125 或 0.075。

九、生产实现：RocksDB 9.10 的 FastLocalBloom 与 Ribbon

本节以 RocksDB 9.10.0（commit ae8fb3e）为准。

默认值

// RocksDB 9.10.0, include/rocksdb/table.h, struct BlockBasedTableOptions（摘录）
  bool optimize_filters_for_memory = true;
  std::shared_ptr<const FilterPolicy> filter_policy = nullptr;
  uint32_t format_version = 6;

filter_policy 默认为空，SST 文件里不建 filter；“默认 10 bits/key”只是文档和很多配置示例里的常用值。NewBloomFilterPolicy(10) 在 format_version >= 5 时生成 FastLocalBloom，否则生成旧的 LegacyBloom（filter_policy.cc 里按 format_version < 5 分支）。optimize_filters_for_memory 按分配器实际给出的块大小（malloc_usable_size）调整 filter 的字节数，HISTORY.md 称用 jemalloc 时约省 10% 内存，6.12 作为实验选项引入，6.22.0 标为可用于生产，9.10.0 默认打开。

版本线索（均出自 HISTORY.md）：

Ribbon 的实现选择

RocksDB 的 Ribbon 是 Standard128RibbonBitsBuilder：系数行是 128 位（CoeffRow = Unsigned128），kHomogeneous = false，kUseSmash = false，解按论文第 5 节的 interleaved column-major layout（ICML）存放，论文说明，ICML 字长等于 \(w\) 时，每个结果位最多（而且几乎总是）组合两个字。按论文 Table 1，同样的 \(m\) 下 \(w=128\) 需要的余量约为 \(w=64\) 的一半。

构建失败时它不报错，而是退回 Bloom：

// RocksDB 9.10.0, table/block_based/filter_policy.cc,
// Standard128RibbonBitsBuilder::Finish()（有删减）
    bool success = banding.ResetAndFindSeedToSolve(
        num_slots, hash_entries_info_.entries.begin(),
        hash_entries_info_.entries.end(),
        /*starting seed*/ entropy & 255, /*seed mask*/ 255);
    if (!success) {
      ROCKS_LOG_WARN(
          info_log_, "Too many re-seeds (256) for Ribbon filter, %llu / %llu",
          static_cast<unsigned long long>(hash_entries_info_.entries.size()),
          static_cast<unsigned long long>(num_slots));
      SwapEntriesWith(&bloom_fallback_);
      assert(hash_entries_info_.entries.empty());
      return bloom_fallback_.Finish(buf, status);
    }

同一个函数里还有几种退回 Bloom 的情况：键数超过 kMaxRibbonEntries（950000000）、算出的槽数为 0、把消元所需内存计入 block cache 时超限（IsMemoryLimit()）。计算空间时（CalculateSpaceAndSlots()），槽数少于 1024 且同样误判率的 Bloom 更小，也直接用 Bloom，这与第二节”小过滤器另当别论”是同一个现象。

用法与代价

filter_policy.h 对 NewRibbonFilterPolicy(double bloom_equivalent_bits_per_key, int bloom_before_level = 0) 的说明是：

• 空间比 Bloom 省约 30%，查询时间相近，构建时 CPU 约为 3 到 4 倍、临时内存约 3 倍；
• 参数按”等效 Bloom 位数”给出，传 10 得到与 Bloom 相同的 0.95% 误判率，但每键只用约 7 位；
• 单个 filter 里有 1 亿个键时，构建要 3 GB 未计入统计的临时内存，Bloom 是 1 GB。

第二条可以和论文对上：0.95% 对应 \(\lambda = \log_2(1/0.0095) \approx 6.72\)，7 位是下界的 1.04 倍，与 Table 1 中 \(w=128\) 的余量量级一致。

bloom_before_level 决定哪些层用 Bloom。memtable flush 算作第 -1 层，所以默认值 0 表示”只有 flush 用 Bloom”；1 表示 L0（含 flush）用 Bloom、其余层用 Ribbon；-1 表示总用 Ribbon；INT_MAX 表示总用 Bloom。它可以通过 SetOptions() 在线修改。配置片段（不是完整程序）：

// 配置片段：L0 及 flush 用 FastLocalBloom，更深的层用 Ribbon
rocksdb::BlockBasedTableOptions t;
t.filter_policy.reset(rocksdb::NewRibbonFilterPolicy(10.0, 1));
options.table_factory.reset(rocksdb::NewBlockBasedTableFactory(t));

这样分层的理由写在同一段注释里：较深的层数据多、存活久，省下的空间值得多花的构建 CPU；L0 和 flush 频繁重建，Bloom 的构建速度更重要。每层 filter 该给多少位是另一个问题，Dayan、Athanassoulis、Idreos 的 Monkey（SIGMOD 2017）给出了按层分配误判率的方法，见 B+tree 与 LSM-tree。

Ribbon 论文的脚注给出了一个规模参照：在一些大规模 RocksDB 应用中，分块 Bloom filter 占用了约 10% 的内存和约 1% 的 CPU，filter 按大小加权的平均存活时间约 3 天。在这种条件下，拿构建 CPU 换 30% 的 filter 内存是划算的。

十、争论与开放问题

经典公式到底错在哪里。 Bose 等人（2008）指出公式对 \(k \ge 2\) 偏低，Christensen 等人（2010）又指出 Bose 等人的精确式里有一处写错，并指出通常归到 Bloom 名下的公式并不是 Bloom 原文的推导。第二节的精确计算与实测给出的结论是：偏差只对几十到几百位的过滤器有实际意义。仍然没有定论的是工程上”用哪个公式配参数”，RocksDB 的 bloom_impl.h 不用经典公式，而是按分块结构另算（CacheLocalFpRate()），再叠加 32 位或 64 位哈希本身的指纹碰撞率。

动态结构能不能逼近下界。 静态结构可以做到 \((1+o(1))\,n\log_2(1/\varepsilon)\) 位，Ribbon 与 binary fuse 是这条路上的实用结构。动态结构不行：Lovett 与 Porat（FOCS 2010；SIAM J. Comput. 2013）证明，对任意常数 \(\varepsilon\)，支持逐个插入的 AMQ 至少要 \(C(\varepsilon)\,n\log_2(1/\varepsilon)\) 位，其中 \(C(\varepsilon) > 1\) 只依赖 \(\varepsilon\)。这个下界说明差距存在，但没有说明差距有多大。Ribbon 论文把现有 OR 探测结构的附加项 \(\mu > 1.44\) 解释为它们在近似一个最小完美哈希，同时说明这是”an observation about existing structures, not necessarily a fundamental limitation”。动态过滤器到底能做到多少，以及 Even、Even、Morrison 的 prefix filter（PVLDB 2022）这类新设计离它有多远，仍是开放问题。

空间与速度。 分块 Bloom 的空间最差，查询最快；Ribbon 的空间最好，构建最慢。Ribbon 论文 Figure 1 对静态过滤器、\(n = 10^7\) 做了比较，以”构建时间加三种查询时间之和”为准，在”空间开销上限 × 误判率”平面上标出最快的结构：空间开销低到其他结构都达不到的区域只有 Ribbon；Ribbon 也在 \(f > 2^{-8}\) 的部分区域快过 xor，在 \(f > 2^{-12}\) 的部分区域快过 xor+；“Blocked Bloom filters are still the fastest whenever applicable”。这个比较不包括动态结构，也不涉及过滤器之外的 I/O。RocksDB 的分层混合配置是工程上的折中，哪一层该切换，目前只有经验值。

哈希函数的假设。 上面所有分析都假设哈希函数是完全随机的。Kirsch 与 Mitzenmacher 证明了双重哈希的渐近误判率不变，但只是渐近结论；Dillinger 与 Manolios（FMCAD 2004）讨论了有限规模下双重哈希的问题并提出 enhanced double hashing。RocksDB 的注释给出了另一个具体限制：只用 32 位哈希时，10 bits/key 的配置在约 4000 万个键处，哈希碰撞带来的误判就开始超过过滤器本身，“so 32-bit hash is a bad idea with 10s of millions of keys or more”。RocksDB 的 FastLocalBloom 构建时用一个 64 位哈希拆成两半；LevelDB 1.23 用的是 32 位哈希。

十一、工程陷阱与选型

常见陷阱：

1. 以为 RocksDB 默认有 filter。 filter_policy 默认是 nullptr，要显式配置。
2. 把块大小当成 512 字节。 FastLocalBloom 的块是 512 位（64 字节）的一条缓存行。
3. 按经典公式给分块 Bloom 配位数。 16 bits/key 时分块 Bloom 的误判率是标准 Bloom 的 1.87 倍，24 bits/key 时是 6.2 倍（第四节）。
4. 删除没插入过的键。 counting Bloom、quotient filter、cuckoo filter 都会因此出现假阴性（第三节图）。
5. cuckoo filter 反复插入同一个键。 同一个指纹最多只能在两个桶里放 \(2b\) 份，超过就失败（见 Cuckoo Hashing 第八节）。
6. 忽略 cuckoo filter 的桶数约束。 桶数必须是 2 的幂，\(n\) 不凑巧时实际负载远低于 95%，每键位数随之上升。
7. 对静态过滤器做增量更新。 xor、binary fuse、Ribbon 都要整体重建；构建可能失败，要准备换种子（RocksDB 最多 256 次）或退回其他结构。
8. 大 filter 的构建内存。 Ribbon 构建 1 亿键的单个 filter 要 3 GB 临时内存，可以用分区 filter 把它切小。
9. 版本兼容。 Ribbon filter 只有 6.15.0 及以后能读；更老的版本会当作没有 filter，性能下降直到 compaction 重建 filter。

选型：

十二、参考资料

文档与规范

• RocksDB 9.10.0，include/rocksdb/filter_policy.h：NewBloomFilterPolicy、NewRibbonFilterPolicy 与 bloom_before_level 的说明。
• RocksDB 9.10.0，include/rocksdb/table.h：BlockBasedTableOptions 的默认值。
• RocksDB 9.10.0，HISTORY.md：6.6.0、6.15.0、6.19.0、6.20.0、6.22.0、6.24.0、8.6.0 各条。

源码

• RocksDB 9.10.0（commit ae8fb3e5000e46d8d4c9dbf3a36019c0aaceebff）：util/bloom_impl.h（FastLocalBloomImpl、ChooseNumProbes()），table/block_based/filter_policy.cc（Standard128RibbonBitsBuilder、Bloom 退回逻辑），util/ribbon_impl.h（SerializableInterleavedSolution）。
• LevelDB 1.23（commit 99b3c03b3284f5886f9ef9a4ef703d57373e61be）：util/bloom.cc。

核心论文

• B. H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors”, CACM 13(7):422–426, 1970.
• L. Carter, R. Floyd, J. Gill, G. Markowsky, M. Wegman, “Exact and Approximate Membership Testers”, STOC 1978, pp. 59–65.
• P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid, Y. Tang, “On the False-Positive Rate of Bloom Filters”, IPL 108(4):210–213, 2008.
• K. Christensen, A. Roginsky, M. Jimeno, “A New Analysis of the False Positive Rate of a Bloom Filter”, IPL 110(21):944–949, 2010.
• L. Fan, P. Cao, J. Almeida, A. Z. Broder, “Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol”, SIGCOMM 1998; IEEE/ACM ToN 8(3):281–293, 2000.
• A. Kirsch, M. Mitzenmacher, “Less Hashing, Same Performance: Building a Better Bloom Filter”, ESA 2006; Random Structures & Algorithms 33(2):187–218, 2008.
• F. Putze, P. Sanders, J. Singler, “Cache-, Hash- and Space-Efficient Bloom Filters”, WEA 2007, LNCS 4525, pp. 108–121; ACM JEA 14, 2009.
• M. A. Bender, M. Farach-Colton, R. Johnson, R. Kraner, B. C. Kuszmaul, D. Medjedovic 等, “Don’t Thrash: How to Cache Your Hash on Flash”, PVLDB 5(11):1627–1637, 2012.
• B. Fan, D. G. Andersen, M. Kaminsky, M. Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom”, CoNEXT 2014, pp. 75–88.
• T. M. Graf, D. Lemire, “Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters”, ACM JEA 25, 2020.
• T. M. Graf, D. Lemire, “Binary Fuse Filters: Fast and Smaller Than Xor Filters”, ACM JEA 27, 2022.
• P. C. Dillinger, S. Walzer, “Ribbon filter: practically smaller than Bloom and Xor”, arXiv:2103.02515, 2021（预印本）。
• M. Dietzfelbinger, P. C. Dillinger, S. Hübschle-Schneider, P. Sanders, S. Walzer, “Ribbon: Fast Succinct Static Retrieval and Approximate Membership”, JACM 73(1), 2026.
• S. Lovett, E. Porat, “A Lower Bound for Dynamic Approximate Membership Data Structures”, FOCS 2010; SIAM J. Comput. 42(6):2182–2196, 2013.

其他论文

• B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal, “The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables”, SODA 2004.
• M. Dietzfelbinger, R. Pagh, “Succinct Data Structures for Retrieval and Approximate Membership”, ICALP 2008.
• M. Dietzfelbinger, S. Walzer, “Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications”, ESA 2019.
• F. C. Botelho, R. Pagh, N. Ziviani, “Simple and Space-Efficient Minimal Perfect Hash Functions”, WADS 2007.
• P. C. Dillinger, P. Manolios, “Bloom Filters in Probabilistic Verification”, FMCAD 2004.
• P. Pandey, M. A. Bender, R. Johnson, R. Patro, “A General-Purpose Counting Filter: Making Every Bit Count”, SIGMOD 2017.
• T. Even, G. Even, A. Morrison, “Prefix Filter: Practically and Theoretically Better Than Bloom”, PVLDB 15(7):1311–1323, 2022.
• N. Dayan, M. Athanassoulis, S. Idreos, “Monkey: Optimal Navigable Key-Value Store”, SIGMOD 2017.
• A. Broder, M. Mitzenmacher, “Network Applications of Bloom Filters: A Survey”, Internet Mathematics 1(4):485–509, 2004.

实验

• reproduce/filters.c：第二到第八节的全部每键位数、误判率、负载、构建成功率与缓存行统计，输出见 reproduce/results.txt。
• reproduce/exact_fpr.py：第二节小过滤器的精确误判率，输出见 reproduce/exact_fpr_results.txt。
• reproduce/plot_space_fpr.py：第八节的图；reproduce/draw_diagrams.py：各结构的布局图。

系列导航： - 上一篇：一致性哈希：从 Karger 哈希环到 Jump、Maglev 与有界负载 - 下一篇：密码学哈希与非密码学哈希：安全定义、迭代构造与哈希洪泛

相关阅读： - Cuckoo Hashing：用两个位置换取最坏情况常数查找 - 完美哈希：从 FKS 两级表到 gperf 与现代 MPHF - B+tree 与 LSM-tree：原地更新与异地更新的读、写、空间代价 - HyperLogLog：从概率计数到 Redis 实现的基数估计