布隆过滤器
核心思路:在缓存层之前加一道”过滤网”,提前拦截不存在的 key
用户请求
布隆过滤器
invalid_001不存在beijing可能存在直接拦截
继续查询
无效请求拦截
Redis → 数据库
在上一节我们学习了使用缓存空对象来防护缓存穿透。
这个方案虽然简单有效,但也存在问题:
场景:恶意攻击者构造 10 万个不存在的 key
缓存空对象方案:
- 每个不存在的 key 都缓存一个空值
- 10 万个空值占用大量内存
- 假设每个空值 100 字节,总共需要约 10MB 内存
问题:
❌ 内存浪费严重
❌ 大量无效 key 污染缓存
❌ 可能挤占正常数据的缓存空间
有没有更高效的方案,既能拦截不存在的 key,又不占用太多内存?
这就是布隆过滤器大显身手的地方。
布隆过滤器(Bloom Filter)是一种概率型数据结构,用于快速判断一个元素是否存在于集合中。
核心特点
输入:元素 x
输出:两种可能
- "一定不存在"(100% 准确)
- "可能存在"(有小幅误判率)
形象比喻:
布隆过滤器就像一个筛子:
- 能 100% 拦住明显太大的石子(一定不存在的数据)
- 但可能会让小石子漏过去(可能存在,需要进一步检查)
与其他方案对比
| 方案 | 内存占用 | 判断准确率 | 适用场景 |
|---|---|---|---|
| 缓存空对象 | 高 | 100% | 少量非法 key |
| 布隆过滤器 | 极低 | 99%+ | 海量数据、key 空间大 |
| 数据库预检查 | 中 | 100% | 合法数据集合小 |
以下交互演示展示了布隆过滤器的核心机制,包括添加元素、查询元素以及误判的产生过程。试试添加几个城市,然后查询一个未添加的城市来观察误判现象。
布隆过滤器交互演示
体验布隆过滤器的添加、查询过程,观察误判是如何发生的
预设:
3 个哈希函数(使用简单字符串哈希)
输入元素后显示哈希计算结果
关键点:
- 布隆过滤器说”不存在” → 100% 不存在
- 布隆过滤器说”存在” → 可能误判,需要进一步检查
| 指标 | 无防护 | 缓存空对象 | 布隆过滤器 | 组合方案 |
|---|---|---|---|---|
| 非法请求拦截率 | 0% | 95% | 99.9% | 99.9% |
| 内存占用 | - | 高(10MB+) | 极低(100KB) | 低(200KB) |
| 响应时间 | 2000ms | 50ms | 10ms | 15ms |
| 误判率 | - | 0% | 0.1% | 0.05% |
用户请求
GET https://dashboard.kuaiyizhi.cn/api/v2/weather?city=北京Nginx
Public API
Admin API
Admin Dashboard
MySQL
Redis 集群
MySQL 主从
消息队列
练习 1
布隆过滤器为什么说”不存在”是 100% 准确的?
解题思路:
关键在布隆过滤器的判定方向是单向的:只要有任意一位是 0,就一定不存在;全为 1 只能说可能存在。所以「不存在」是 100% 准确的。
详细步骤:
最终答案:
布隆过滤器的判断逻辑:
- 检查元素的 k 个哈希位置
- 如果任意一个位置为 0 → 元素一定不存在
- 如果所有位置都为 1 → 元素可能存在
原因分析:
如果元素 X 真的存在:
- 添加 X 时,它的 k 个位置都被设为 1
- 查询 X 时,这 k 个位置都为 1
- 判断:可能存在(实际确实存在)如果元素 X 不存在:
- X 的 k 个哈希位置中,至少有一个从未被设置
- 查询 X 时,至少有一个位置为 0
- 判断:一定不存在(100% 准确)误判只发生在:
- 元素 X 不存在
- 但 X 的 k 个哈希位置都被其他元素设置为 1
- 这时会说”可能存在”(误判)
所以:布隆过滤器说”没有”,就一定没有!
练习 2
布隆过滤器的误判率如何影响内存占用?
解题思路:
要记住位数组长度与误判率之间是反向关系,并会用公式 估算:误判率定得越低,位数组越长、内存占用越多。
详细步骤:
最终答案:
误判率与内存占用的关系:
误判率越低 → 需要的位数组越长 → 内存占用越多
公式:
m = - (n × ln p) / (ln 2)²
其中:
- m: 位数组长度(比特)
- n: 预计元素数量
- p: 误判率
- ln: 自然对数具体示例(假设 n=10 万):
| 误判率 | 位数组大小 | 内存占用 |
|---|---|---|
| 1% (0.01) | 96 万位 | ~120KB |
| 0.1% (0.001) | 144 万位 | ~180KB |
| 0.01% (0.0001) | 192 万位 | ~240KB |
结论:
- 误判率降低 10 倍,内存增加约 50%
- 推荐设置:0.001(0.1%),平衡性能和准确率
练习 3
请设计一个使用布隆过滤器防护缓存穿透的完整流程。
解题思路:
这题要的是把布隆过滤器接进缓存读取链路的完整流程,重点在命中判定、未命中回源与异常 key 的处理顺序。
详细步骤:
最终答案:
设计流程
练习 3
- 步骤 1:写入缓存值、空值标记或热点保护状态
- 步骤 2:按命中、未命中和异常 key 处理读取与回源
- 步骤 3:按本节策略读取、写入缓存并处理过期或失效
- 步骤 4:校验身份、密钥或权限
关注点:命中率、回源压力、TTL 和异常 key 处理。
多层防护:
- 布隆过滤器:拦截一定不存在的 key
- 缓存空值:拦截之前确认不存在的 key
- 正常缓存:存储有效数据
- API 调用:最后的数据来源
发现内容有问题?
告诉我们哪里需要改进。
