布隆过滤器

解决方案概述

核心思路：在缓存层之前加一道”过滤网”，提前拦截不存在的 key

问题引入

在上一节我们学习了使用缓存空对象来防护缓存穿透。

这个方案虽然简单有效，但也存在问题：

场景：恶意攻击者构造 10 万个不存在的 key

缓存空对象方案：
- 每个不存在的 key 都缓存一个空值
- 10 万个空值占用大量内存
- 假设每个空值 100 字节，总共需要约 10MB 内存

问题：
❌ 内存浪费严重
❌ 大量无效 key 污染缓存
❌ 可能挤占正常数据的缓存空间

有没有更高效的方案，既能拦截不存在的 key，又不占用太多内存？

这就是布隆过滤器大显身手的地方。

什么是布隆过滤器？

布隆过滤器（Bloom Filter）是一种概率型数据结构，用于快速判断一个元素是否存在于集合中。

核心特点

输入：元素 x
输出：两种可能
- "一定不存在"（100% 准确）
- "可能存在"（有小幅误判率）

形象比喻：

布隆过滤器就像一个筛子：

• 能 100% 拦住明显太大的石子（一定不存在的数据）
• 但可能会让小石子漏过去（可能存在，需要进一步检查）

与其他方案对比

工作原理

以下交互演示展示了布隆过滤器的核心机制，包括添加元素、查询元素以及误判的产生过程。试试添加几个城市，然后查询一个未添加的城市来观察误判现象。

关键点：

• 布隆过滤器说”不存在” → 100% 不存在
• 布隆过滤器说”存在” → 可能误判，需要进一步检查

效果对比

当前技术架构

练习

练习 1

布隆过滤器为什么说”不存在”是 100% 准确的？

如果元素 X 真的存在：
- 添加 X 时，它的 k 个位置都被设为 1
- 查询 X 时，这 k 个位置都为 1
- 判断：可能存在（实际确实存在）

如果元素 X 不存在：
- X 的 k 个哈希位置中，至少有一个从未被设置
- 查询 X 时，至少有一个位置为 0
- 判断：一定不存在（100% 准确）

练习 2

布隆过滤器的误判率如何影响内存占用？

误判率越低 → 需要的位数组越长 → 内存占用越多

公式：
m = - (n × ln p) / (ln 2)²

其中：
- m: 位数组长度（比特）
- n: 预计元素数量
- p: 误判率
- ln: 自然对数

练习 3

请设计一个使用布隆过滤器防护缓存穿透的完整流程。