跳到主要内容

布隆过滤器

布隆过滤器（Bloom Filter）是一种由 Burton Howard Bloom 在 1970 年提出的，空间效率极高的概率型数据结构。它专门用于判断“一个元素是否在一个集合中”。

以下是关于布隆过滤器的详细介绍：

1. 基本原理 (Basic Principle)​

布隆过滤器的核心是一个很长的二进制向量（Bit Array）和一组随机映射函数（Hash Functions）。

  • 初始化：创建一个长度为 mm 的比特数组，所有位都置为 0。
  • 添加元素：
    1. 选定 kk 个独立的哈希函数。
    2. 当一个元素被加入集合时，用这 kk 个哈希函数分别计算该元素的哈希值。
    3. 将这 kk 个哈希值对数组长度 mm 取模，得到 kk 个位置。
    4. 将比特数组中这 kk 个位置的值全部设为 1。
  • 查询元素：
    1. 用同样的 kk 个哈希函数计算该元素的哈希值。
    2. 检查比特数组中这 kk 个位置的值。
    3. 如果任意一个位置是 0，则该元素一定不在集合中。
    4. 如果所有位置都是 1，则该元素可能在集合中（存在误报风险）。

对此设计的认识​

k 个哈希函数相当于是一个空间中的点在 k 个维度上的投影的计算方法，k 个哈希的值就唯一决定了空间中的一个点。

我们可以将每一个一个点的 k 个维度的投影全部记录下来，但是这样就会导致这个记录数据随着点的数量线性增长，同时还会面临对过滤器本身检索时间的线性增加，所以布隆过滤器选择了再进行一次哈希，将数据压缩到长度为 m 的比特数组。

由于两次哈希都有碰撞可能，所以布隆过滤器的结论是集合中不存在，确定是不存在；但是如果结果是存在，那么存在与否无法确认。

2. 例子 (Example)​

假设我们有一个长度为 10 的比特数组（m=10m=10），和 2 个哈希函数（k=2k=2）。

  1. 初始状态：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  2. 插入元素 "Apple"：
    • Hash1("Apple") % 10 = 3
    • Hash2("Apple") % 10 = 7
    • 数组变为：[0, 0, 0, 1, 0, 0, 0, 1, 0, 0]（位置3和7置为1）
  3. 插入元素 "Banana"：
    • Hash1("Banana") % 10 = 1
    • Hash2("Banana") % 10 = 7
    • 数组变为：[0, 1, 0, 1, 0, 0, 0, 1, 0, 0]（位置1置为1，位置7已经是1了）
  4. 查询 "Cherry"（不在集合中）：
    • Hash1("Cherry") % 10 = 2
    • Hash2("Cherry") % 10 = 5
    • 由于位置 2 和 5 都是 0，判定 "Cherry" 一定不存在。
  5. 查询 "Peach"（不在集合中，但可能产生误报）：
    • Hash1("Peach") % 10 = 1
    • Hash2("Peach") % 10 = 3
    • 位置 1 和 3 都是 1（由 Apple 和 Banana 贡献）。布隆过滤器会返回 "可能存在"，这就是假阳性（False Positive）。

3. 数学理论 (Mathematical Theory)​

布隆过滤器的性能由三个因素决定：比特数组大小 mm、哈希函数个数 kk、插入元素个数 nn。

  • 假阳性概率（False Positive Rate, PP）： 在插入 nn 个元素后，任意一个比特位仍为 0 的概率是：(1−1m)kn≈e−kn/m(1 - \frac{1}{m})^{kn} \approx e^{-kn/m}。 因此，某个不在集合中的元素被误判为在集合中的概率约为： P≈(1−e−kn/m)kP \approx (1 - e^{-kn/m})^k

  • 最优哈希函数个数 kk： 对于给定的 mm 和 nn，使误判率最小的 kk 为： k=ln⁡2⋅mn≈0.693⋅mnk = \ln 2 \cdot \frac{m}{n} \approx 0.693 \cdot \frac{m}{n}

  • 所需存储空间 mm： 如果预期的元素个数为 nn，容忍的误判率为 PP，则需要的比特数 mm 为： m=−nln⁡P(ln⁡2)2m = - \frac{n \ln P}{(\ln 2)^2}

4. 特性 (Characteristics)​

优点：​

  1. 极高的空间效率：不存储元素本身，只存储位。比 Hash Set 等结构节省大量空间。
  2. 查询时间极快：插入和查询的时间复杂度都是 O(k)O(k)，与集合中元素的数量无关。
  3. 保密性强：由于不存储原始数据，在某些对隐私敏感的场景（如密码黑名单）非常有优势。

缺点：​

  1. 存在误报（False Positives）：它可能会告诉你某个元素在集合中，但实际上不在。
  2. 零漏报（No False Negatives）：如果它说某个元素不在，那它绝对不在。
  3. 删除困难：标准的布隆过滤器不支持删除元素。因为多个元素可能映射到同一个比特位，删除一个元素（将 1 置为 0）可能会影响其他元素的判断。
    • 注：可以使用“计数布隆过滤器（Counting Bloom Filter）”来解决删除问题，但会消耗更多空间。

5. 常见应用场景​

  • 防止缓存击穿：在访问数据库之前，先用布隆过滤器判断 Key 是否存在。如果布隆过滤器说不存在，直接返回，避免无效查询大量涌入数据库。
  • 垃圾邮件过滤：判断一个邮件地址是否在数亿个垃圾邮件黑名单中。
  • 爬虫 URL 去重：在爬取网页时，判断某个 URL 是否已经爬取过。
  • 数据库优化：Google BigTable 和 Apache Cassandra 使用布隆过滤器来减少对磁盘中不存在的行或列的访问。

总结​

布隆过滤器是一个典型的 “空间换精度” 的设计，它用极小的代价解决了大规模数据的快速过滤问题，只要你的业务逻辑能容忍极小概率的误报，它就是最优选。

Appendex​

数学公式推导​

推导布隆过滤器的假阳性概率（False Positive Rate）是一个经典的概率统计过程。我们可以将其拆解为以下四个核心步骤：

1. 变量定义​

首先明确公式中的变量含义：

  • mm：比特数组的长度（Bit Array Size）。
  • nn：已经插入到过滤器中的元素数量。
  • kk：哈希函数的个数。

2. 第一阶段：单个比特位被置为 0 的概率​

我们将推导在所有元素插入完成后，数组中某个特定的位（比如第 ii 位）仍然是 0 的概率。

  1. 单次哈希： 当一个哈希函数对一个元素进行哈希时，它选中某个特定位置的概率是 1m\frac{1}{m}。那么，没选中该位置的概率就是： 1−1m1 - \frac{1}{m}
  2. 一个元素的所有哈希： 一个元素有 kk 个哈希函数。这 kk 个函数都没选中该位置的概率是： (1−1m)k(1 - \frac{1}{m})^k
  3. 所有 nn 个元素的所有哈希： 总共进行了 n×kn \times k 次哈希操作。所有这些操作都没选中该位置的概率（即该位保持为 0）是： Pzero=(1−1m)knP_{zero} = (1 - \frac{1}{m})^{kn}

3. 第二阶段：引入自然常数 ee 的近似​

为了方便计算，我们利用高等数学中的极限公式：当 xx 很大时，(1−1x)x≈e−1(1 - \frac{1}{x})^x \approx e^{-1}。

  1. 我们将原式变形： Pzero=[(1−1m)m]knmP_{zero} = \left[ (1 - \frac{1}{m})^m \right]^{\frac{kn}{m}}
  2. 当 mm 足够大时，括号内部 (1−1m)m≈e−1≈12.718(1 - \frac{1}{m})^m \approx e^{-1} \approx \frac{1}{2.718}。
  3. 代入得： Pzero≈(e−1)knm=e−kn/mP_{zero} \approx (e^{-1})^{\frac{kn}{m}} = e^{-kn/m} 这就是你提到的第一个公式：在插入 nn 个元素后，任意一个比特位仍为 0 的概率。

4. 第三阶段：比特位被置为 1 的概率​

既然位为 0 的概率是 PzeroP_{zero}，那么位为 1 的概率（即被某个哈希函数击中的概率）就是： Pone=1−Pzero≈1−e−kn/mP_{one} = 1 - P_{zero} \approx 1 - e^{-kn/m}

5. 第四阶段：假阳性概率 PP 的推导​

假阳性定义： 当查询一个实际不存在的元素时，由于哈希冲突，恰好该元素对应的 kk 个哈希位置全都是 1。

  1. 假设这 kk 个位置是独立的（这是一个理想化的假设，但在 mm 很大时非常接近真实情况）。
  2. 第 1 个位置是 1 的概率是 PoneP_{one}。
  3. 第 2 个位置也是 1 的概率是 PoneP_{one}。
  4. ...
  5. 所有 kk 个位置同时为 1 的概率就是 PoneP_{one} 的 kk 次幂： P=(Pone)k≈(1−e−kn/m)kP = (P_{one})^k \approx (1 - e^{-kn/m})^k

总结推论直观理解：​

  • e−kn/me^{-kn/m}：数组中**空着（为0）**的部分比例。
  • 1−e−kn/m1 - e^{-kn/m}：数组中**填了（为1）**的部分比例。
  • (1−e−kn/m)k(1 - e^{-kn/m})^k：如果你随机在数组里选 kk 个点，这 kk 个点全都被填过的概率。

结论：

  • 当数组长度 mm 增大时，PP 减小（空间换精度）。
  • 当元素个数 nn 增大时，PP 增大（存得越多，越容易误报）。
  • 当哈希函数 kk 变化时，对 PP 的影响是非线性的，存在一个最优的 kk 值能使 PP 达到最小。

这两个公式的推导是布隆过滤器理论中最核心的部分，本质上是一个求极值的过程。我们将从上一步得到的假阳性概率公式 P≈(1−e−kn/m)kP \approx (1 - e^{-kn/m})^k 出发进行推导。

1. 最优哈希函数个数 kk 的推论​

我们的目标是：给定 mm（数组长度）和 nn（元素个数），找到一个 kk，使得 PP 最小。

第一步：简化表达式 为了方便计算，我们令 f=e−kn/mf = e^{-kn/m}。这里的 ff 实际上是经过 kk 个哈希函数处理 nn 个元素后，某个比特位仍然为 0 的概率。 那么公式变为： P=(1−f)kP = (1 - f)^k

第二步：利用 ff 反推 kk 根据 f=e−kn/mf = e^{-kn/m}，取对数得 ln⁡f=−kn/m\ln f = -kn/m，所以： k=−mnln⁡fk = - \frac{m}{n} \ln f

第三步：将 kk 代入 PP 的表达式中并取对数 为了求极值，我们对 PP 取自然对数： ln⁡P=kln⁡(1−f)\ln P = k \ln(1 - f) 代入第二步中的 kk： ln⁡P=−mnln⁡f⋅ln⁡(1−f)\ln P = - \frac{m}{n} \ln f \cdot \ln(1 - f) ln⁡P=−mn[ln⁡f⋅ln⁡(1−f)]\ln P = - \frac{m}{n} \left[ \ln f \cdot \ln(1 - f) \right]

第四步：求导找极值 我们要使 ln⁡P\ln P 最小。由于 −mn-\frac{m}{n} 是常数且为负数，这等价于求函数 g(f)=ln⁡f⋅ln⁡(1−f)g(f) = \ln f \cdot \ln(1 - f) 的最大值。 根据对称性（或者对 g(f)g(f) 求导并令其等于 0）： 当 f=1−ff = 1 - f 时，即 f=12=0.5f = \frac{1}{2} = 0.5 时，g(f)g(f) 取得最大值。

直观理解： 当布隆过滤器中正好有一半的比特位被置为 1，另一半为 0 时，该结构承载的信息熵最大，误判率最低。

第五步：得出结果 将 f=1/2f = 1/2 代回 f=e−kn/mf = e^{-kn/m}： e−kn/m=12e^{-kn/m} = \frac{1}{2} −kn/m=ln⁡(1/2)=−ln⁡2-kn/m = \ln(1/2) = -\ln 2 k=mnln⁡2≈0.693⋅mnk = \frac{m}{n} \ln 2 \approx 0.693 \cdot \frac{m}{n}

2. 所需存储空间 mm 的推论​

我们的目标是：已知预期的误判率 PP 和元素个数 nn，计算最少需要多少比特位 mm。

第一步：使用最优 kk 时的 PP 值 在上述推导中我们知道，当 kk 取最优值时，f=1/2f = 1/2。 代入假阳性概率公式： P=(1−f)k=(1−1/2)k=(12)kP = (1 - f)^k = (1 - 1/2)^k = (\frac{1}{2})^k P=2−kP = 2^{-k}

第二步：对 PP 取对数 ln⁡P=ln⁡(2−k)=−kln⁡2\ln P = \ln(2^{-k}) = -k \ln 2

第三步：代入最优 kk 的表达式 将 k=mnln⁡2k = \frac{m}{n} \ln 2 代入上式： ln⁡P=−(mnln⁡2)⋅ln⁡2\ln P = - (\frac{m}{n} \ln 2) \cdot \ln 2 ln⁡P=−mn(ln⁡2)2\ln P = - \frac{m}{n} (\ln 2)^2

第四步：解出 mm mln⁡P=−n(ln⁡2)2m \ln P = - n (\ln 2)^2 m=−nln⁡P(ln⁡2)2m = - \frac{n \ln P}{(\ln 2)^2}

3. 结论的实际意义​

  1. 关于 kk：

    • 如果哈希函数太少，位数组里 1 太少，容易冲突。
    • 如果哈希函数太多，位数组很快就会被填满 1，也容易冲突。
    • 最优状态是：让数组里刚好有一半是 1。

  2. 关于 mm：

    • 公式 m=−nln⁡P(ln⁡2)2m = - \frac{n \ln P}{(\ln 2)^2} 告诉我们，空间需求 mm 与元素个数 nn 成线性正比，与期望误差 PP 的对数成反比。
    • 如果你想让误判率从 1% 降到 0.1%，你需要显著增加 mm（大约增加 1.5 倍空间）。

经验法则： 在最优情况下，每个元素大约需要 9.6 个比特（bits）来维持 1% 的误判率。无论你处理的是 100 万数据还是 10 亿数据，这个比例（m/nm/n）是恒定的。

工程例子​

在工程实践中（如 RocksDB, HBase, Cassandra, Google BigTable），布隆过滤器通常被存储在内存中，用来拦截对磁盘上不存在的数据的随机读请求。

为了方便估算，我们通常设定一个最常用的误判率标准：P=1%P = 1\%（这是大多数数据库默认或推荐的平衡点）。

在 P=1%P=1\% 的情况下，推导公式告诉我们：每个元素大约需要 9.6 bits (约 1.2 字节)。

以下是针对不同量级数据量的布隆过滤器尺寸表：

1. 不同数据规模下的内存占用 (误判率 P=1%P=1\%)​

数据量 (nn)占用比特数 (mm)占用内存 (字节/MB)备注
10 万 (10^5)96 万 bits117 KB相当于一张高清图标的大小
100 万 (10^6)960 万 bits1.14 MB极小，现代手机 APP 都能轻松负载
1000 万 (10^7)9600 万 bits11.44 MB相当于一首高品质 MP3 的大小
1 亿 (10^8)9.6 亿 bits114.4 MB约等于一个轻量级浏览器的内存占用
10 亿 (10^9)96 亿 bits1.12 GB这是一个大型商业数据库分片常见的规模
100 亿 (10^10)960 亿 bits11.17 GB需要 16G 内存以上的服务器专门承载

2. 误判率对大小的影响（以 1 亿条数据为例）​

如果我们改变对“精度”的要求，内存占用会随之变化。依然以 1 亿条数据 (n=108n=10^8) 为例：

  • 追求极致性能 (P=0.1%P=0.1\%):
    • 每个元素需要约 14.4 bits。
    • 总占用：171.6 MB。
    • 适用场景：磁盘 I/O 极其昂贵，必须严防死守。
  • 工程平衡点 (P=1%P=1\%):
    • 每个元素需要约 9.6 bits。
    • 总占用：114.4 MB。
    • 适用场景：主流数据库默认配置。
  • 节省内存 (P=5%P=5\%):
    • 每个元素需要约 6.2 bits。
    • 总占用：74.3 MB。
    • 适用场景：内存资源极度紧张，能挡住 95% 的无效请求即可。

3. 工程中的真实案例：RocksDB​

在 RocksDB（被用于 TiDB, CockroachDB 等）中，布隆过滤器的配置通常如下：

  • 默认配置： bits_per_key = 10。
  • 计算： 如果你的数据库里有 1 亿个 Key。
  • 内存开销： 1 亿×10 bits=1 Gbits≈125 MB1 \text{ 亿} \times 10 \text{ bits} = 1 \text{ Gbits} \approx 125 \text{ MB}。
  • 效果： 它可以过滤掉 99% 以上原本需要读取磁盘的“不存在的 Key”查询。

4. 为什么这个数据量非常“划算”？​

我们可以对比一下：

  • 如果用 Hash Set 存储 1 亿个 UUID（每个 36 字节）： 需要 1 亿×36 Byte≈3.6 GB1 \text{ 亿} \times 36 \text{ Byte} \approx 3.6 \text{ GB} 的内存（这还没算 Hash 表的额外指针开销）。
  • 如果用布隆过滤器： 只需要 125 MB。

结论： 布隆过滤器用 1/30 的内存代价，解决了 99% 的无效查询问题。在工程上，这种用极小内存交换极大 I/O 性能提升的买卖是非常划算的。通常在千万到亿级数据量时，布隆过滤器的优势最为明显。