布隆过滤器

1970 年，Burton Howard Bloom 在 Communications of the ACM 上发表了一篇不到 3 页的短文"Space/Time Trade-offs in Hash Coding with Allowable Errors"，提出了一种奇特的数据结构。

Bloom 的核心想法是：如果允许极小概率的误报（False Positive），可以用极少的内存表示一个巨大的集合，并在 $O(1)$ 时间内回答"元素是否在集合中"。

这个用空间换取误报率的权衡，在网络系统、数据库、分布式系统中产生了深远影响。

破除误解：什么是"允许误报"#

布隆过滤器有一个独特的保证： - 无假阴性（No False Negatives）：若元素确实在集合中，过滤器一定返回"存在" - 有假阳性（False Positives Possible）：若元素不在集合中，过滤器可能（以小概率）错误返回"存在"

这意味着： - "不存在" = 绝对确定不存在 - "存在" = 可能存在（置信度 $1 - \varepsilon$）

这种"宁可放过，不可错杀"的特性（相对于误判方向）在许多场景下非常有用——先用布隆过滤器快速排除"一定不存在"的情况，再对"可能存在"的做精确检查。

工作原理#

布隆过滤器由两部分构成： 1. 一个长度为 $m$ 的位数组（bit array），初始全为 0 2. $k$ 个独立哈希函数 $h_1, h_2, \ldots, h_k$，每个将元素映射到 $[0, m-1]$

插入元素 $x$：计算 $h_1(x), h_2(x), \ldots, h_k(x)$，将位数组中这 $k$ 个位置全部设为 1。

查询元素 $x$：检查 $h_1(x), h_2(x), \ldots, h_k(x)$ 对应的 $k$ 个位置是否全为 1。 - 若有任一为 0：$x$ 肯定不在集合中 - 若全为 1：$x$ 可能在集合中（也可能是其他元素的哈希值的"残留"）

位数组（m=10）：  0 1 0 1 0 1 0 0 1 0
                   ↑   ↑       ↑
                   h1  h2      h3（元素 "apple" 的三个哈希位置均为 1）
```

假阳性产生的原因：位数组是共享的，多个元素的哈希位置可能重叠，导致一个未插入的元素的 $k$ 个哈希位置"恰好"全被其他元素设过 1。

手算一遍：16 位向量 + 3 个哈希#

把 $m = 16$、$k = 3$ 摆出来，用三个可以徒手算的哈希函数：

$$h_1(x) = x \bmod 16,\quad h_2(x) = (3x + 7) \bmod 16,\quad h_3(x) = (5x + 11) \bmod 16$$

依次插入三个元素 4、9、13：

位数组变成：

下标  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
值    0  0  1  1  1  0  0  0  1  1  0  0  1  1  1  1
```

16 位里有 9 位被置 1。现在查三个没有插入过的数：

这张表最该看的是最后一行：8 从来没被插入过，却过了全部三道检查。 而且三个 1 分别来自不同的元素——位 8 是插入 9 时置的（$h_3(9) = 8$），位 15 和位 3 都是插入 4 时置的（$h_3(4) = 15$、$h_2(4) = 3$）。假阳性不是某一次冲突，是多个元素的痕迹在无意中拼出了另一个元素的签名。 这也解释了为什么假阳性无法通过"更好的哈希函数"消除：只要位数组是共用的，痕迹就会互相拼接。

第一行同样值得注意：查 10 只花了 1 次位检查就得出"绝对不在"。这是布隆过滤器在真实系统里最有价值的性质——否定判定通常极快，因为只要撞上一个 0 就可以立刻返回，不需要走完 $k$ 个哈希。

顺手验一下理论：$n = 3$、$m = 16$、$k = 3$，代入下一节的公式得 $\left(1 - e^{-9/16}\right)^3 \approx 0.080$。而 0 到 15 之间除三个成员外共 13 个数，逐个试下来恰好只有 8 一个假阳性，实测 $1/13 \approx 0.077$——对得上，而且对得有点巧。$m$ 只有 16 时公式只是渐近近似（它假设各位独立置 1），能撞得这么准是运气；真要评估参数，还是得用大 $m$ 或直接实测。

假阳性率的数学#

设已插入 $n$ 个元素，位数组长 $m$，哈希函数 $k$ 个。假阳性率的近似公式：

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

$k$ 太小时每个元素的签名太短、容易被撞上；$k$ 太大时位数组被填得太满、到处都是 1。中间必有一个最优值，而它的推导只有三行。

记 $p = e^{-kn/m}$，这是一个位仍为 0 的概率，于是 $\varepsilon = (1-p)^k$。由 $p$ 的定义反解出 $k = -\frac{m}{n}\ln p$，代入取对数：

$$\ln \varepsilon = k \ln(1-p) = -\frac{m}{n}\,\ln p \cdot \ln(1-p)$$

$m/n$ 是给定的，所以最小化 $\ln\varepsilon$ 等价于最大化 $\ln p \cdot \ln(1-p)$。这个乘积关于 $p \leftrightarrow 1-p$ 对称，在 $p = 1/2$ 处取到最大。于是最优条件就是让位数组恰好一半是 0、一半是 1：

$$e^{-kn/m} = \frac{1}{2} \quad\Longrightarrow\quad k^* = \frac{m}{n}\ln 2 \approx 0.693\,\frac{m}{n}$$

此时 $\varepsilon^* = (1/2)^{k^*} = 2^{-0.693\,m/n}$，等价地 $\varepsilon^* = e^{-(m/n)(\ln 2)^2}$。

"一半 0 一半 1"是这个结论最好记的形式，也顺带给了一个调参时的自检手段：把线上过滤器的位密度打出来，如果远离 0.5，参数就配错了。

数值表：每元素多少比特买多少精度#

$k$ 必须取整，所以实际用的是 $k = \text{round}(0.693\,m/n)$，再代回 $\varepsilon = (1-e^{-kn/m})^k$：

反过来问"要某个精度得付多少比特"，公式是 $m/n = \ln(1/\varepsilon)/(\ln 2)^2 \approx 1.44\log_2(1/\varepsilon)$：

• $\varepsilon = 1\%$ → 9.6 比特/元素
• $\varepsilon = 0.1\%$ → 14.4 比特/元素
• $\varepsilon = 0.01\%$ → 19.2 比特/元素

每把假阳性率降低一个数量级，固定多付 $\ln 10/(\ln 2)^2 \approx 4.8$ 比特。 这条线性关系是布隆过滤器最实用的一条工程直觉：精度不是越买越贵，它是按量匀速定价的。要从 1% 降到百万分之一，也只是 9.6 加上 4 个 4.8，约 29 比特——不到 4 字节，而你替代掉的可能是一个几十字节的字符串键。

一个参照系：信息论下界告诉我们，任何能以假阳性率 $\varepsilon$ 回答成员查询的结构，每元素至少要 $\log_2(1/\varepsilon)$ 比特。$\varepsilon = 1\%$ 时下界是 6.64 比特，布隆过滤器要 9.59 比特——$1/\ln 2 \approx 1.44$ 倍，也就是 44% 的固定浪费。这 44% 不是实现不好，是结构本身的代价，也正是后来一批"更紧"的过滤器（见下文）要抢的空间。

布隆过滤器无法做到的事#

• 删除元素：不能删！将某位置清零可能影响其他元素的记录。
• 枚举集合元素：位数组不存储元素本身，无法遍历
• 精确统计集合大小：只能估计

第一条值得看一个具体反例。回到上面那个 16 位的例子：删除元素 4 意味着把位 3、4、15 清零。但位 3 同时是 $h_2(8)$ 会检查的位——更要命的是，如果之前还插入过某个元素恰好也用到位 3，清零就会让那个确实在集合里的元素查不到了。而布隆过滤器的全部价值建立在"无假阴性"上：一旦允许假阴性，下游那个"再去磁盘精确查一遍"的兜底逻辑就失效了，因为它根本不会被触发。这不是精度下降，是保证方向的翻转，性质完全变了。

计数布隆过滤器（Counting Bloom Filter） 的解法是把每个位换成一个小计数器，插入时加一、删除时减一。Fan、Cao、Almeida 与 Broder 在 2000 年的《Summary Cache》论文里提出并给出了计数器宽度的选择：4 比特。理由是概率——在他们的参数下，任一计数器涨到 16 以上（也就是溢出）的概率约 $1.37\times10^{-15}$，实践中可以忽略。

代价很直接：内存变成 4 倍。原本 1% 假阳性率下的 9.6 比特/元素，变成 38.4 比特，接近 5 字节。如果键本身是一个 8 字节的 64 位 ID，用负载因子 0.7 的哈希集合存精确值约需 11 字节——空间优势从"十倍级"缩到了"两倍多"，而你还得接受 1% 的假阳性。这时候引入一个概率结构是否值得，就不再是显而易见的了。近年更常见的选择是直接换掉结构：布谷鸟过滤器（Cuckoo Filter）原生支持删除，空间还比计数布隆过滤器省，见下文。

现实中的应用#

网络与分布式系统#

谷歌 BigTable（2006）和 Apache HBase：每个 SSTable 文件附带一个布隆过滤器，查询某 key 是否在文件中时，先问布隆过滤器。若回答"不存在"，直接跳过该文件（磁盘 I/O 极贵）；若"可能存在"，再实际读文件。Bigtable 的 OSDI 2006 论文把布隆过滤器和"不可变 SSTable 栈"、压缩一起列为核心表示技术，并指出用一小块 tablet 服务器内存存过滤器，能大幅减少读操作所需的磁盘寻道次数。

Facebook Cassandra：同样用布隆过滤器减少读放大（Read Amplification）。

CDN 缓存穿透防护：防止大量对不存在 key 的请求打穿缓存层直达数据库——布隆过滤器记录所有已存在的 key，不存在的请求直接被过滤器拦截。

数据库与搜索#

PostgreSQL：contrib 里的 bloom 扩展提供了一种基于布隆过滤器的索引访问方法。它的定位很具体：表有很多列、查询会用任意列组合做等值匹配时，一个 bloom 索引可以顶替一大堆 B-tree 索引。默认签名长度 80 比特、每个索引列贡献 2 比特（均可配置，签名最长 4096 比特）。它只支持等值查询——因为哈希抹掉了顺序，范围查询无从下手。这是布隆过滤器的通用限制在数据库里的直接体现。

垃圾邮件过滤：SpamAssassin 等工具用布隆过滤器快速过滤已知垃圾 URL/域名。

区块链#

比特币轻节点（SPV 客户端）：BIP 37 让轻节点把一个布隆过滤器发给全节点，说明"我关心哪些交易"，全节点据此筛选，只回传可能相关的交易——本意是在隐私和带宽之间取得平衡。这个设计后来被判定失败，理由见下一节。

现场：三次"改用别的东西"#

布隆过滤器最有教育意义的地方，恰恰是那几个用过它、后来换掉的系统。三个案例，三种不同的失败原因。

一、Chrome 的安全浏览：因为不能删而换掉。 Chrome 早期确实用布隆过滤器在本地粗筛恶意 URL——先排除绝大多数干净网址，只对"可能匹配"的联网精确验证。2012 年前后，Chromium 把这套本地结构换成了排序前缀集（prefix set）：直接存恶意 URL 哈希的 32 位前缀，差值压缩后顺序存放。换掉的原因不主要是空间——恶意网址名单每天都在增删，而布隆过滤器不支持删除，只能定期整体重建；前缀结构能增量维护，还顺带消灭了假阳性带来的多余联网查询。

二、比特币 BIP 37：因为过滤器泄露了查询意图而废弃。 轻钱包为了省带宽，会把假阳性率调得很低——而假阳性本来是这个设计里唯一的隐私来源。Gervais、Čapkun、Karame 与 Gruber 在 ACSAC 2014 的论文《On the Privacy Provisions of Bloom Filters in Lightweight Bitcoin Clients》给出了结论：一个只用少量地址（比如少于 20 个）的 SPV 客户端，几乎会把自己全部地址暴露给对端节点。2019 年，Bitcoin Core 0.19 把 -peerbloomfilters 默认值改为 false，不再接受 BIP 37 过滤器（官方给出的直接理由是消除已知的拒绝服务向量，尤其对使用机械硬盘的节点）。替代方案 BIP 158 把方向整个反转：由节点为每个区块发布一个确定的紧凑过滤器，客户端下载后在本地匹配，永远不向任何人发送自己的过滤器。 泄露问题从"降低概率"变成了"结构上不存在"。

三、RocksDB：没换掉，但加了一个更紧的同类。 RocksDB 至今默认给每个键 10 比特（假阳性率略低于 1%）。真实约束是内存：很大的库会把 10% 甚至更多的 RAM 花在过滤器上——过滤器不是可选的装饰，它就是"最坏读放大很高、平均读性能却很好"这件事的来源。2020 年的 6.15 版起，RocksDB 提供了 Ribbon 过滤器（Dillinger 与 Walzer，2021）作为替代：同样 1% 的假阳性率下，NewRibbonFilterPolicy(9.9) 只用约 7 比特/键，比布隆过滤器省下约 30% 内存，代价是过滤器上的 CPU 消耗约 3–4 倍，且构造期的临时内存高得多（约 231 比特/键，布隆过滤器约 74 比特/键，大约要构造 50 个过滤器文件才能把这笔临时开销赚回来）。

回头对一下上一节的下界：1% 假阳性率的信息论下界是 6.64 比特/元素，布隆过滤器 9.6、Ribbon 约 7——Ribbon 把 44% 的浪费压到了约 5%。这也说明那 30% 的节省不是工程微调，而是逼近了理论极限，后面基本没有空间了。

三个案例合起来是同一句判断：布隆过滤器很少因为"不够快"被换掉，它被换掉的原因永远是那三条硬约束里的某一条——不能删、会泄露查询意图、以及那固定 44% 的空间浪费。 选型时该先问的不是"它多快"，而是"这三条我踩了哪条"。

变种与改进#

计数布隆过滤器（Counting Bloom Filter，Fan、Cao、Almeida、Broder 在 2000 年的 "Summary Cache" 论文中提出）：每个位置用计数器代替单比特，支持删除操作（减计数）。代价是更多内存（每位置 3-4 比特）。

可扩展布隆过滤器（Scalable Bloom Filter，Almeida et al. 2007）：动态扩展，在不知道最终集合大小时保持目标假阳性率。

Cuckoo Filter（Cuckoo 过滤器，Fan et al. 2014）：基于 Cuckoo Hashing，存的不是位而是每个元素的短指纹（fingerprint），支持删除，空间效率与布隆过滤器相当甚至更优，在某些场景下已成为首选替代。论文标题就是它的定位：《Cuckoo Filter: Practically Better Than Bloom》。

MinHash + Bloom 组合：用于判断两个大集合的相似度（Jaccard 系数），是文档去重和网络爬虫的核心技术。

近十几年的替代者：都在抢那 44%#

上文算过，布隆过滤器每元素比信息论下界多花 44%。2012 年之后出现的一批结构，攻的基本都是这一块，而且各自还捎带解决了别的毛病：

商过滤器那一行的"访问局部性好"最值得注意，因为它揭示了 2012 年之后这批工作的真正动机。布隆过滤器的 $k$ 次哈希会跳到位数组里 $k$ 个互不相关的位置——对内存来说是 $k$ 次随机访问，对 SSD 来说更是灾难。商过滤器把一个元素的信息集中在少量连续槽位里，于是一次查询只要一两次连续读。Bender 等人论文的标题正是《Don't Thrash: How to Cache Your Hash on Flash》：他们要解决的不是空间，是布隆过滤器只能待在内存里这件事。

同样值得注意的是 XOR 过滤器和 Ribbon 过滤器的共同代价：它们都要求先知道全部元素、一次性构造，不支持插入。这不是缺陷而是交换——放弃增量插入，才换来接近下界的紧凑度。放在 LSM 树的场景里这个交换非常合理：SSTable 一旦写出就不再改，过滤器本来也只需构造一次。"能不能接受静态构造"是选这一代过滤器的第一道分水岭。

布隆过滤器背后的哲学：接受不确定性#

布隆过滤器提出了一个在计算机系统设计中深刻而实用的思想：在工程系统中，有限的不确定性有时比无限的精确性更有价值。

系统不总需要 100% 精确的答案。如果 99% 的情况下能立即给出正确答案，而 1% 的情况下需要进一步检查——而这个"进一步检查"的代价完全可接受——那么布隆过滤器就是完美的工具。

这种"概率近似"思想催生了一整个研究领域：概率数据结构（Probabilistic Data Structures），包括 Count-Min Sketch（频率估计）、HyperLogLog（基数估计）等，都遵循类似哲学。

跨域连接#

• 概率论：最优哈希个数不是试出来的，而是三行推导的结果——把假阳性率写成"某位仍为零"的概率的函数，最小化等价于最大化一个关于该概率对称的乘积，极值恰在二分之一处。于是最优配置就是"位数组恰好一半为零"。这条结论顺带给出线上自检：把位密度打出来，远离一半就是参数配错了。
• 哈希：假阳性不是某一次碰撞，而是多个元素留下的痕迹在无意中拼出了另一个元素的签名。这解释了为什么换更好的哈希函数消不掉它：只要位数组共用，痕迹就会互相拼接。它与哈希表冲突的性质也不同——冲突可以靠链表或探测化解，痕迹拼接无法化解，只能靠更多比特把概率压低。
• 免疫系统：免疫识别同样是用有限的受体库去覆盖近乎无限的抗原空间，代价同样是交叉反应，也就是假阳性。系统的应对是二次确认：识别之外还需要共刺激信号，单一信号不足以触发攻击。这与"过滤器说可能存在、再去精确查一遍"是同一种架构，而自身免疫正是这条兜底失效后的后果。
• 风险与不确定性：它把误差全部压到一个方向，使下游可以对"不存在"做零成本的硬决策，这是故障安全设计的教科书形态。方向一旦翻转，性质就完全变了：允许删除会引入假阴性，而兜底逻辑本来只在"可能存在"时才被调用，此时根本不会触发。误差的分布形状比误差的大小更决定系统能不能用。
• 隐私工程：轻客户端把自己的过滤器发给对端时，假阳性本是唯一的隐私来源；为省带宽把假阳性率调低，等于把隐私一起调没。正确的修法不是继续调参数，而是反转方向——由服务端为每个区块发布确定的紧凑过滤器，客户端在本地匹配，永不外发。泄露从"概率上很小"变成"结构上不存在"。

参考文献#

• Bloom, B. H. "Space/Time Trade-offs in Hash Coding with Allowable Errors." Communications of the ACM 13(7), 422–426 (1970).
• Chang, F. et al. "Bigtable: A Distributed Storage System for Structured Data." OSDI, 2006. （SSTable 与布隆过滤器减少磁盘寻道）
• Fan, L., Cao, P., Almeida, J. & Broder, A. Z. "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol." IEEE/ACM Transactions on Networking 8(3), 281–293 (2000). （计数布隆过滤器与 4 比特计数器的选择）
• Bender, M. A. et al. "Don't Thrash: How to Cache Your Hash on Flash." Proceedings of the VLDB Endowment 5(11), 1627–1637 (2012). （商过滤器）
• Fan, B., Andersen, D. G., Kaminsky, M. & Mitzenmacher, M. "Cuckoo Filter: Practically Better Than Bloom." CoNEXT, 2014.
• Graf, T. M. & Lemire, D. "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters." ACM Journal of Experimental Algorithmics 25 (2020). DOI 10.1145/3376122.
• Dillinger, P. C. & Walzer, S. "Ribbon Filter: Practically Smaller Than Bloom and Xor." arXiv:2103.02515 (2021).
• Gervais, A., Čapkun, S., Karame, G. O. & Gruber, D. "On the Privacy Provisions of Bloom Filters in Lightweight Bitcoin Clients." ACSAC, 2014. DOI 10.1145/2664243.2664267.
• Mitzenmacher, M. & Upfal, E. Probability and Computing. 2nd ed. Cambridge University Press, 2017. （第5章）
• PostgreSQL 官方文档 F.6 bloom — bloom filter index access method（签名长度与每列比特数的默认值）。
• RocksDB 官方博客 Ribbon Filter（2021-12-29）与 RocksDB Wiki Bloom Filter（默认 10 比特/键、Ribbon 的空间与 CPU 实测）。

延伸阅读#

• Broder, A. & Mitzenmacher, M. "Network Applications of Bloom Filters: A Survey." Internet Mathematics 1(4), 2004.
• Almeida, P. S., Baquero, C., Preguiça, N. & Hutchison, D. "Scalable Bloom Filters." Information Processing Letters 101(6), 2007.
• Bitcoin BIP 158 Compact Block Filters for Light Clients（"由服务端发布、客户端本地匹配"的替代设计）。