布隆过滤器误判率怎么算:被追问容量与恶意刷的场景题
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 商品详情页 QPS 挺高,但库里有个别 ID 是脏数据、缓存又没命中,请求全打数据库上,你怎么处理?
- 布隆过滤器的误判率和容量怎么算?
- 空值缓存如果被人恶意刷,会有什么问题?
- 布隆过滤器不支持删除,商品下架了怎么办?
- 攻击者每秒用几万个随机 UUID 请求详情页,怎么挡?
- 空值缓存的 TTL 与数据一致性怎么平衡?
- 为什么布隆过滤器只能减少穿透,不能消灭穿透?
《参考解析》
基础方案与它的问题:空值缓存最省事——查不到就写一个 NULL 标记、TTL 短一点。但它治标不治本:攻击者每次换随机 ID,每个 key 都是新的,缓存十万个空值也拦不住,反而把 Redis 内存吃掉一块,还可能把有用数据挤出去。另一个问题是数据一致性:后来真建出来的商品,在 TTL 内会让用户看到「商品不存在」,下单链路里这种误判会出事。所以空值缓存只能兜底,前面必须有布隆过滤器做第一道闸。
误判率与容量:布隆过滤器是位数组加 k 个哈希函数,查询时 k 个位置全为 1 才「可能存在」,只要有一个 0 就「一定不存在」。误判率约 (1 - e^(-kn/m))^k,最优哈希数 k = (m/n)·ln2 ≈ 0.69·m/n。经验值:每元素分配 10 bit 时误判率约 1%,14 bit 左右能压到千分之一以下。工程含义是要提前估好 n:商品 ID 千万级、按每元素 10 bit 算,位数组约十几 MB,单机内存放得下,但多实例部署各存各的,一致性要靠定时重建。
不支持删除的应对:商品下架后 ID 还在位数组里,请求会穿过去查一次 DB,可以接受并用空值缓存兜底;如果必须支持删除,就上计数布隆或布谷鸟过滤器。帖主项目里用 Redis bitmap 自己维护,配合每天凌晨从 DB 全量重建,重建期间用双 buffer 切换,避免闸门失效。
随机 UUID 攻击:布隆能挡掉几乎全部,但按 1% 误判率算,每秒几万请求仍有一两百个穿到 DB;这类请求往往伴随大 key 查询或复杂 SQL,压力仍然可观。分层做法是:参数校验前置(自增数字接口直接打回 UUID、负数、超长字符串)、布隆挡主要流量、空值缓存兜误判漏下来的、接口层按用户维度做滑动窗口限流(例如 Sentinel 配在网关)、给空值 key 加影子前缀便于监控与批量清理。
教训:这题真正暴露的不是公式没背,而是对缓存的认知停在「本地缓存 → Redis → DB 加过期时间」的表面。真在生产里被穿透打过的人,会记得布隆重建时的抖动、空值 TTL 是拍过脑子的、限流阈值调高后 DB 就报警。背下来的东西一追问就露馅,自己踩过的坑怎么问都在。