存储算法 #02：Bloom Filter

Bloom Filter 是一种空间极度高效的概率型数据结构，用 O(1) 时间和远小于实际数据的空间回答"某个元素是否在集合中"。无假阴性（在集合中的元素一定能查到），有假阳性（查到不代表一定存在）。RocksDB、Cassandra、HBase、Nginx 均大量使用。

相关文章：LSM Tree · SSTable · Copy-on-Write（COW）

目录

核心思想

问题：判断一个元素是否在一个大集合中，但集合太大无法全部装入内存。

朴素方案：HashSet
  优点：精确，无误判
  缺点：每个元素需要存储完整 key + 指针
        1亿个 URL（平均 64B）= 6.4 GB 内存

Bloom Filter：
  不存储元素本身，只存储"元素存在的痕迹"
  1亿个元素，误判率 1% → 只需约 114 MB
  压缩比约 56 倍

数据结构与算法

数据结构

m 位的位数组（bit array），初始全为 0
k 个独立的哈希函数 h1, h2, ..., hk（每个输出 [0, m) 范围的整数）

插入（Insert）

插入元素 x：
  计算 h1(x), h2(x), ..., hk(x)
  将位数组中这 k 个位置的 bit 设为 1

示例（m=16, k=3）：
  插入 "apple"：h1=2, h2=7, h3=11
  bits[2]=1, bits[7]=1, bits[11]=1

  插入 "banana"：h1=4, h2=7, h3=14
  bits[4]=1, bits[7]=1（已是1）, bits[14]=1

查询（Query）

查询元素 x 是否存在：
  计算 h1(x), h2(x), ..., hk(x)
  检查这 k 个位置是否全为 1

  if 任意一位为 0：元素一定不在集合中（无假阴性）
  if 全部为 1：元素可能在集合中（有假阳性）

示例：
  查询 "apple"：bits[2]=1, bits[7]=1, bits[11]=1 → 可能存在 ✅
  查询 "cherry"：h1=3, h2=9, h3=11
                 bits[3]=0 → 一定不存在 ✅（无需检查其他位）
  查询 "mango"：h1=4, h2=7, h3=14
                bits[4]=1, bits[7]=1, bits[14]=1 → 可能存在
                但 "mango" 实际上没有插入过 → 假阳性 ⚠️

误判率分析

假阳性率公式

设：
  m = 位数组长度
  n = 已插入的元素数量
  k = 哈希函数个数

单个 bit 在插入一个元素后仍为 0 的概率：
  P(bit=0) = (1 - 1/m)^k ≈ e^(-k/m)

插入 n 个元素后，单个 bit 仍为 0 的概率：
  P(bit=0) = (1 - 1/m)^(kn) ≈ e^(-kn/m)

假阳性率（k 个位置全为 1）：
  FPR = (1 - e^(-kn/m))^k

最优哈希函数个数

对 FPR 对 k 求导，令导数为 0：
  最优 k = (m/n) × ln2 ≈ 0.693 × (m/n)

实际常用：k = 7（对应 m/n ≈ 10 时，FPR ≈ 1%）

参数选择表

1 亿元素、FPR=1%：需要 9.6 × 1亿 = 9.6 亿 bit ≈ 114 MB

异常场景

假阳性导致的额外 I/O

场景（LSM Tree 中）：
  查询 key=X 不存在于 SSTable A
  但 Bloom Filter 误判为"可能存在"
  → 不必要地读取 SSTable A（磁盘 I/O）

影响：
  FPR=1% 意味着 100 次"不存在的查询"中有 1 次额外磁盘读
  对于大量不存在 key 的查询（如缓存穿透场景）代价明显

处理：
  调低 FPR（增大 m）→ 用更多内存换更少误判
  RocksDB 默认每 SSTable 配 10 bits/key（FPR ≈ 1%），可调

位数组满载后误判率飙升

问题：插入的元素数量 n >> 设计容量，大量 bit 被置 1
     极端情况（全部为 1）→ 所有查询都返回"可能存在"→ Bloom Filter 失效

解决：
  预估数据量时留足余量（建议 × 1.5~2）
  或使用动态扩容 Bloom Filter（如 Scalable Bloom Filter）
    → 当当前 filter 快满时，新建一个更大的 filter
    → 查询时检查所有历史 filter

哈希碰撞导致误判率高于预期

问题：若哈希函数质量差（输出分布不均匀），实际 FPR 高于公式预测

解决：
  使用高质量快速哈希（MurmurHash3、xxHash、FNV）
  RocksDB 使用 MurmurHash + 双哈希技术模拟 k 个独立哈希：
    h_i(x) = h1(x) + i * h2(x)
  减少哈希计算开销，同时保持分布均匀

无法删除的问题

为什么不能删除：

删除 "apple"（h1=2, h2=7, h3=11）：
  想将 bits[2], bits[7], bits[11] 置回 0
  但 bits[7] 也被 "banana" 使用了！
  → 置 0 会误删 "banana"，导致假阴性（破坏核心保证）

Counting Bloom Filter（支持删除）

将每个 bit 替换为计数器（通常 4 bit = 0~15）

插入：对应位置计数器 +1
删除：对应位置计数器 -1
查询：检查对应位置计数器是否全 > 0

代价：空间增加 4 倍（每位 4 bit vs 1 bit）
适用：需要删除操作的场景（如动态黑名单）

工程应用

参考资料

• Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors
• RocksDB Bloom Filter: https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
• 《Designing Data-Intensive Applications》Ch.3 — Hash Indexes