布隆过滤器 (Bloom Filter)

背景与动机

在软件系统中，我们经常需要判断一个元素是否在某个集合里：用户名是否已注册、URL 是否已经爬取过、商品 ID 是否在黑名单里。最直接的方案是用 HashSet 或数据库，这些方案在小规模数据下完全够用，但当数据量上升到数千万甚至数十亿时，内存开销会急剧膨胀。

以一个简单的计算为例：假设要存储 1000 万个 64 位整数，Java HashSet<Long> 每个元素大约需要 80 字节（对象头 + 引用 + HashMap 内部结构），总计约 760 MB。如果换成 Redis SET，同样规模的数据需要 GB 级别内存。这对于内存资源敏感的场景是不可接受的——尤其是在做缓存穿透防护时，我们可能只关心一个 key “绝对不存在”，此时用 Set 性价比极低。

布隆过滤器（Bloom Filter）正是为了解决这种”空间换时间 vs 精确性权衡”问题而设计的概率性数据结构。由 Burton Howard Bloom 在 1970 年提出，它用极少的内存就能回答：

• “这个元素一定不在集合里” —— 100% 确定
• “这个元素可能在集合里” —— 存在一定误判率

核心思想：牺牲少量精确性（可控的误判率），换取巨大的空间节省。

方案	1000万元素内存	误判率	是否支持删除
HashSet	~760 MB	0%	是
布隆过滤器 (1%误判)	~12 MB	1%	否
布隆过滤器 (0.01%误判)	~24 MB	0.01%	否

原理

数据结构

布隆过滤器由两个核心组件构成：

1. 位数组（Bit Array）：一个长度为 m 的二进制数组，所有位初始值为 0
2. K 个独立的哈希函数：每个哈希函数将输入映射到 [0, m-1] 范围内的整数

初始状态 (m=18, 所有位为 0):
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17

插入过程

当插入一个元素 x 时：

1. 用 K 个哈希函数分别计算 x 的哈希值：h1(x), h2(x), …, hk(x)
2. 将哈希值取模得到 K 个位置：h1(x) % m, h2(x) % m, …, hk(x) % m
3. 将这 K 个位置的二进制值设置为 1

插入 "hello" → K=3 个哈希分别映射到位置 2, 7, 14:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17

再插入 “world” → 映射到 3, 9, 14:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 1 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
(位置 14 被两次插入共享——这是后续”误判”的来源)

查询过程

当查询元素 x 是否存在时：

1. 用同样的 K 个哈希函数计算 x 的哈希值，得到 K 个位置
2. 检查位数组中这 K 个位置：

K 个位置的状态	结论	原因
所有位都是 1	可能存在	这些位可能由其他元素设置
任意一位是 0	一定不存在	如果插入过 x，该位应该是 1

为什么可能误判？ 元素 x 映射的 K 个位置可能恰好被其他插入过的元素共同覆盖，导致虽然 x 从未被插入，但所有位都已经是 1。

为什么不会漏判？ 如果 x 被插入过，这 K 个位置一定都是 1——布隆过滤器永远不会删除已经置为 1 的位。

不能删除的原因

布隆过滤器不支持删除操作的根本原因在于：一个位可能被多个元素共享。如上例中位置 14 同时被 "hello" 和 "world" 共享。如果把位置 14 从 1 改为 0（代表删除了 "hello"），那么查询 "world" 时会发现位置 14 是 0，于是错误地判定 "world" 不在集合中——造成漏判。

数学推导

符号定义

符号	含义
m	位数组长度（bit 数）
n	预期插入元素个数
k	哈希函数个数
p	误判率（false positive rate）

误判率公式推导

步骤 1：插入一个元素后，某一位仍为 0 的概率

插入一个元素时，某次哈希命中的概率是 1/m，未命中的概率是 1 - 1/m。K 次哈希过后，特定的某一位仍然为 0 的概率：

[
P_0 = \left(1 - \frac{1}{m}\right)^k
]

步骤 2：插入 n 个元素后，某一位仍为 0 的概率

n 个元素共有 n * k 次哈希操作，某一位从未被设为 1 的概率：

[
P_0(n) = \left(1 - \frac{1}{m}\right)^{kn}
]

利用极限公式：当 m 较大时，(1 - 1/m)^m ≈ 1/e，可得：

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

步骤 3：某一位为 1 的概率

[
P_1 = 1 - e^{-kn/m}
]

步骤 4：误判发生的概率

误判发生意味着查询一个不在集合中的元素时，它对应的 K 个位置恰好全部为 1：

[
P = \left(1 - e^{-kn/m}\right)^k
]

这就是经典的布隆过滤器误判率公式：

[
\boxed{P = \left(1 - e^{-kn/m}\right)^k}
]

最优哈希函数个数 k

为了使误判率最小，我们对 p 取对数后对 k 求导：

[
f(k) = \ln P = k \cdot \ln\left(1 - e^{-kn/m}\right)
]

令导数为 0：

[
\frac{df}{dk} = \ln\left(1 - e^{-kn/m}\right) + k \cdot \frac{1}{1 - e^{-kn/m}} \cdot \left(-e^{-kn/m} \cdot \frac{-n}{m}\right) \cdot \ln e = 0
]

设 p = e^{-kn/m}，简化后得到：

[
\boxed{k = \frac{m}{n} \cdot \ln 2 ≈ 0.693 \cdot \frac{m}{n}}
]

当 k 取此值时的最优误判率（此时位数组中被置为 1 的比例恰好为 50%）：

[
P_{min} = \left(\frac{1}{2}\right)^k \approx \left(0.6185\right)^{m/n}
]

位数组大小 m 的确定

在实际设计中，我们通常已知 n（预期数据量）和 p（目标误判率），进而反推 m 和 k：

由 k = (m/n) * ln2 和 P = (1/2)^k 得：

[
\boxed{m = -\frac{n \cdot \ln P}{(\ln 2)^2}}
]

[
\boxed{k = \frac{m}{n} \cdot \ln 2}
]

重要观察： m 与 n 成线性关系，与 log(1/P) 成正比。这意味着即使要求极低的误判率（如 0.0001%），m 的增长也只是对数级别。

实际计算示例

问题： 预期存储 n = 1,000 万条记录，要求误判率 P ≤ 0.01%（即 1/10000 的误判率）。

计算 m：

m = -10,000,000 * ln(0.0001) / (ln 2)^²
  = -10,000,000 * (-9.21) / 0.4805
  ≈ 191,700,000 bits
  ≈ 22.85 MB

计算 k：

k = 0.693 * 191,700,000 / 10,000,000 ≈ 13.3 → 取 13

验证： P = (1 - e^(-13*10M/192M))^13 ≈ 0.0001 = 0.01%

结论： 只需要约 23 MB 内存即可存储 1000 万条数据，且误判率仅为万分之一。

常见参数对照表

预期元素数 n	误判率 P	m (bit)	k	内存占用
10 万	1%	958,506	7	~117 KB
10 万	0.1%	1,437,759	10	~175 KB
100 万	1%	9,585,059	7	~1.14 MB
100 万	0.1%	14,377,590	10	~1.71 MB
1000 万	0.01%	191,701,168	13	~22.85 MB
1 亿	0.001%	2,875,518,004	20	~342.92 MB

实现

Guava BloomFilter 源码分析

Google Guava 提供了生产级布隆过滤器实现 com.google.common.hash.BloomFilter：

// 创建示例
BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8),
    10_000_000,  // 预期插入量
    0.0001       // 误判率 0.01%
);

filter.put("key-12345");
boolean mayExist = filter.mightContain("key-12345");  // true

核心源码（简化版），put 方法：

public <T> boolean put(T object, Funnel<? super T> funnel,
                       int numHashFunctions, LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    // 通过 MurmurHash3 计算 128-bit hash，然后拆分为两个 64-bit
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).asBytes();
    long hash1 = lowerEight(bytes);  // 低 64 位
    long hash2 = upperEight(bytes);  // 高 64 位

    boolean bitsChanged = false;
    // 使用 Double Hashing 技巧：计算 g_i = hash1 + i * hash2
    for (int i = 0; i < numHashFunctions; i++) {
        long combinedHash = hash1 + (long) i * hash2;
        if (combinedHash < 0) {
            combinedHash = ~combinedHash;  // 处理溢出
        }
        bitsChanged |= bits.set(combinedHash % bitSize);
    }
    return bitsChanged;
}

mightContain 方法：

public <T> boolean mightContain(T object, Funnel<? super T> funnel,
                                int numHashFunctions, LockFreeBitArray bits) {
    long bitSize = bits.bitSize();
    byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).asBytes();
    long hash1 = lowerEight(bytes);
    long hash2 = upperEight(bytes);

    for (int i = 0; i < numHashFunctions; i++) {
        long combinedHash = hash1 + (long) i * hash2;
        if (combinedHash < 0) {
            combinedHash = ~combinedHash;
        }
        if (!bits.get(combinedHash % bitSize)) {
            return false;  // 任一位为 0 则一定不存在
        }
    }
    return true;  // 所有位都是 1，可能存在
}

关键设计：

• Double Hashing（Kirsch-Mitzenmacher 技巧）：只计算两次哈希值 h1 和 h2，然后 g_i(x) = h1(x) + i * h2(x) 来生成 K 个哈希值。数学上已证明这不会显著增加误判率，但大幅降低了哈希计算代价。
• Guava 使用 MurmurHash3_128 生成 128-bit 哈希，天然拆解出 h1 和 h2。

Redis 布隆过滤器

方案一：RedisBloom 模块（推荐）

# 安装 RedisBloom 模块
redis-server --loadmodule /path/to/redisbloom.so

# 使用
BF.RESERVE myfilter 0.0001 10000000     # 误判率 0.01%, 预期 1000 万
BF.ADD myfilter "item1"
BF.EXISTS myfilter "item1"              # 返回 1
BF.EXISTS myfilter "item2"              # 返回 0

方案二：Bitmap + 自定义哈希（适用于无 RedisBloom 模块）

// Lua 脚本实现简易版布隆过滤器
public class RedisBloomFilter {
    private final Jedis jedis;
    private final String key;
    private final int[] seeds;  // 哈希种子

    public void add(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            jedis.setbit(key, hash, true);
        }
    }

    public boolean contains(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            if (!jedis.getbit(key, hash)) return false;
        }
        return true;
    }

    private int hash(String value, int seed) {
        // 类似 Guava 的轮子
        return Hashing.murmur3_32(seed).hashString(value, UTF_8).asInt() & 0x7FFFFFFF;
    }
}

手写完整 Java 实现

import java.util.BitSet;
import java.util.Random;

public class BloomFilter<T> {
    private final BitSet bitSet;
    private final int bitSize;
    private final int expectedInsertions;
    private final HashFunction[] hashFunctions;

    public BloomFilter(int expectedInsertions, double fpp) {
        this.expectedInsertions = expectedInsertions;
        this.bitSize = (int) (-expectedInsertions * Math.log(fpp) / (Math.log(2) * Math.log(2)));
        int numHashFunctions = (int) (Math.ceil((bitSize / (double) expectedInsertions) * Math.log(2)));
        this.bitSet = new BitSet(bitSize);
        this.hashFunctions = new HashFunction[numHashFunctions];
        Random random = new Random(0xcafebabe);  // 固定种子保证可复现
        for (int i = 0; i < numHashFunctions; i++) {
            hashFunctions[i] = new HashFunction(random.nextInt(), random.nextInt());
        }
    }

    public void put(T value) {
        for (HashFunction f : hashFunctions) {
            int hash = f.hash(value);
            bitSet.set(Math.abs(hash % bitSize));
        }
    }

    public boolean mightContain(T value) {
        for (HashFunction f : hashFunctions) {
            int hash = f.hash(value);
            if (!bitSet.get(Math.abs(hash % bitSize))) {
                return false;
            }
        }
        return true;
    }

    // 组合式哈希：h(x) = seed1 * hash(x) + seed2
    private static class HashFunction {
        private final int seed1;
        private final int seed2;

        HashFunction(int seed1, int seed2) {
            this.seed1 = seed1;
            this.seed2 = seed2;
        }

        int hash(Object obj) {
            int h = obj.hashCode();
            return seed1 * h + seed2;
        }
    }
}

使用示例：

BloomFilter<String> filter = new BloomFilter<>(10_000_000, 0.0001);
filter.put("user_123");
filter.put("user_456");
System.out.println(filter.mightContain("user_123"));  // true
System.out.println(filter.mightContain("user_789"));  // false (大概率)

生产建议： 手写实现适合理解原理，生产环境请使用 Guava BloomFilter 或 RedisBloom。生产级实现需要考虑线程安全、序列化、哈希函数均匀性（MurmurHash3）、BitSet 内存布局优化等问题。

变种

Counting Bloom Filter（计数布隆过滤器）

解决的问题： 标准布隆过滤器不支持删除。

原理： 将位数组中的每一位替换为一个 n-bit 计数器（通常 4 bit）。插入时计数器加 1，删除时计数器减 1。

插入 → 对应 K 个计数器各 +1
删除 → 对应 K 个计数器各 -1
查询 → 所有 K 个计数器 > 0 → 可能存在

溢出处理： 使用 4-bit 计数器（最大 15），当计数器达到最大值时不再递增，牺牲少量准确性换取空间。实际情况中溢出的概率极低——当 m/n 配置合理时，每个计数器的期望值远小于 15。

空间代价： 是标准布隆过滤器的 4 倍（4-bit 计数器 vs 1-bit）。

Cuckoo Filter（布谷鸟过滤器）

2014 年由 CMU 提出，核心改进：

• 支持删除
• 空间效率更高 —— 同等误判率下比 Counting Bloom Filter 节省约 30%-40% 空间
• 使用 Cuckoo Hashing + 指纹（fingerprint）：每个元素计算一个 f 位指纹，存储在两个候选桶（bucket）的任意一个中

特点：

特性	Bloom Filter	Counting BF	Cuckoo Filter
支持删除	否	是	是
空间效率	最优	4x	优于 CBF
查询性能	O(k)	O(k)	O(1)，只需检查两个桶
插入性能	O(k)	O(k)	最坏 O(∞) 需要 rehash
误报控制	精确	精确	精确

Redis Cuckoo Filter 指令：CF.RESERVE, CF.ADD, CF.EXISTS, CF.DEL

Scalable Bloom Filter（可扩展布隆过滤器）

标准布隆过滤器有个致命弱点：容量必须在初始化时确定。一旦实际数据量远超预期 n，误判率会急剧上升（公式中的 n 是实际插入数而非预期数）。

Scalable Bloom Filter 通过动态添加新的布隆过滤器层来解决：

• 当当前过滤器”饱和”时，创建一个新的布隆过滤器
• 新过滤器的误判率设置得更严格（通常等比递减）
• 查询时只需检查所有层

Layer 1 (n=100 万, P=0.01) → 满后创建
Layer 2 (n=200 万, P=0.001) → 满后创建
Layer 3 (n=400 万, P=0.0001) → ...
Layer N (n 加倍, P 递减)

时间开销为对数级，因为层数增加缓慢且早期的层误判率更高（更容易直接”否定”）。

Burst Filter（爆发过滤器）

一种混合结构：由一个”当前活跃”的小布隆过滤器 + 一个持久化的大布隆过滤器构成。数据首先写入活跃过滤器，达到阈值后合并入持久化过滤器。适合写入密集型场景（如高频日志去重），减少了每次写入都要操作大过滤器的开销。

应用场景

缓存穿透防护

缓存穿透是指查询一个数据库和缓存中都不存在的 key，请求直接穿透到数据库。恶意用户可以通过构造大量不存在的 key 造成 DB 压力。

标准方案：

请求 → 布隆过滤器(mightContain?) → 否 → 直接拒绝（不查缓存/DB）
                                  → 是 → 查缓存 → 未命中 → 查 DB

实现要点：

• 布隆过滤器初始使用数据库中所有有效 key 初始化
• 新增 key 时同步 add 到过滤器
• 布隆过滤器定期从 DB 全量重建（避免长期运行积累误差）
• 布隆过滤器本身也可放在 Redis 中做分布式共享

典型案例： 某电商商品详情页缓存穿透防护，使用 50 MB Redis Bloom Filter 过滤掉 >99% 的无效商品 ID 查询，将穿透请求从数万 QPS 降低到个位数。

大集合去重（爬虫 URL 去重）

网络爬虫需要维护”已访问 URL”集合来避免重复抓取：

1. 候选 URL 进入队列前 → 查询布隆过滤器
2. 可能存在 → 略过（允许少数漏抓）
3. 一定不存在 → 加入队列 + 插入布隆过滤器

数据量估算： 假设要抓取 100 亿个 URL，每个 URL 平均 80 字符，HashSet 存储需要 ~8 TB 内存，而使用布隆过滤器（误判率 0.001%）仅需约 20 GB。

黑名单校验

在应用层的黑名单场景中，通常不需要保证 100% 的召回率，但需要极致的内存效率和查询速度：

• 垃圾邮件过滤：邮件服务器用布隆过滤器存储已知的垃圾邮件哈希，快速筛掉
• IP/用户封禁：网关层对黑名单 IP 做布隆过滤器快速放行
• 弱密码字典：注册时用布隆过滤器快速检查密码是否在已知弱密码列表中

注意：对于需要”精确匹配”的黑名单（如支付风控），布隆过滤器只能做第一层粗筛，命中后仍需查询精确集合。

数据库与存储引擎

LevelDB / RocksDB： SSTable 底层使用布隆过滤器判断一个 key 是否可能在某 SSTable 中。如果布隆过滤器说”不在”，直接跳过该 SSTable 的磁盘查找。这是 LSM-Tree 读放大的关键优化。

配置：

RocksDB: ColumnFamilyOptions::optimize_filters_for_hits
Cassandra: 每个 SSTable 自带一个布隆过滤器，默认误判率 0.01

Apache Cassandra： Cassandra 的每个 SSTable 维护一个布隆过滤器。读请求到达时，先通过布隆过滤器判断 key 是否可能在该 SSTable 中，从而避免扫描全部 SSTable。这是 Cassandra 读性能的核心保证之一，配合 LSM-Tree 的 Compaction 策略使用。

Google Bigtable： Bigtable 的 SSTable 格式中内置了布隆过滤器，用于加快”点查（point lookup）”——快速跳过不包含目标 key 的 SSTable 文件。

Apache HBase： HBase 继承了 Bigtable 的设计，在 HFile 格式中支持多种布隆过滤器类型：

• ROW 级别：按 row key 过滤
• ROWCOL 级别：按 row key + column family + qualifier 过滤
• HBase 允许在建表时通过 BLOOMFILTER => 'ROW' 显式指定

实践案例：

一个生产级的 12 节点 Cassandra 集群，数据总量约 2 TB/节点。
在启用布隆过滤器后，点查询延迟从 15ms 降低到 2ms 以下（P99），
因为超过 90% 的 SSTable 查找被布隆过滤器直接跳过。

网络过滤器

• Squid Cache：使用布隆过滤器做 Web 缓存摘要，在以 Cache Digest 协议共享缓存摘要时大幅降低带宽开销
• CDN：节点间同步缓存摘要，用布隆过滤器描述”我缓存了哪些资源”，比传输完整 URL 列表节省 10x 以上带宽
• 路由器：分布式路由表中使用布隆过滤器做快速前缀匹配

面试常见问题

问题	关键要点
布隆过滤器的原理	位数组 + K 个哈希，绝对不在 vs 可能存在
为什么不会漏判	插入过的元素对应位一定是 1
为什么有误判	多个元素可能恰好覆盖了 K 个位置
误判率公式	P = (1 - e^(-kn/m))^k
最优 K 值	k = (m/n) * ln2
为什么不支持删除	一个位可能被多个元素共享，重置会漏判
如何支持删除	Counting Bloom Filter / Cuckoo Filter
实际系统怎么用	缓存穿透、爬虫去重、LSM-Tree SSTable 加速
容量超了怎么办	误判率会上升 → 使用 Scalable Bloom Filter
Guava 实现用了什么技巧	Double Hashing + MurmurHash3_128
和 Bitmap 的区别	Bitmap 是精确的，需要 1:1 映射；布隆过滤器是多对多映射
Redis 中怎么用	BF.ADD / BF.EXISTS（RedisBloom 模块）或 Bitmap + Lua

总结

布隆过滤器用极小的空间代价换取了可控的误判率，是”概率换空间”思想的典范应用。在实际工程中，它已经被反复证明是处理大规模集合成员查询问题的最优方案之一：

• 缓存层： 用几十 MB 内存挡掉数百万无效请求
• 存储引擎层： 作为 “快速否定器” 避免昂贵的磁盘 I/O
• 网络层： 以极低的带宽开销完成分布式集合摘要交换

理解布隆过滤器，不仅仅是掌握一个数据结构，更是理解一种工程权衡的哲学——在合适的场景下，允许可控的”错误”往往能带来数量级的性能/空间提升。