title: 布隆过滤器误判率从 1% 飙到 30%用户漏收了 1/3 的推送容量按日常设大促当天就爆了tags: [布隆过滤器, RedisBloom, 误判率, 去重, 缓存]category: 后端大促当天客诉说「通知没收到」我们的消息中心给每个用户推送前会先查布隆过滤器判断「这条消息 id 是不是已经推过」推过就跳过避免重复骚扰。平时稳得一笔误判率我们按公式算的是 1%。大促当天客诉暴涨「明明有优惠券到账却没收到任何推送」。抽样发现大量真实未推送的消息 id被过滤器判定成了「已推送」直接被丢了。根因一句话布隆过滤器的容量预计元素数我们按日常 100 万/天设的大促实际 1200 万/天塞爆之后误判率从 1% 一路涨到 30%。事故现场一行 exist 决定了推不推推送前的去重逻辑很简洁问题就藏在「判断」这一步的信任上// 推送前置去重 public void pushIfNotSent(String msgId, User user) { // 1. 查布隆过滤器返回 true 表示「大概率已推送」 boolean maybeSent bloomFilter.mightContain(msgId); if (maybeSent) { return; // 2. 误判时真实未推送的消息在这里被错误丢弃 } doPush(user, msgId); // 3. 放过才真正推送 bloomFilter.put(msgId); // 4. 推送成功再标记 }第 2 行是致命点布隆过滤器说true只能表示「可能存在」不是「一定存在」。日常误判率 1% 时千分之一的消息被漏推我们勉强能忍但当元素数量远超初始容量误判率飙升这个比例就变成了三成。参数怎么算误判率和容量是绑死的布隆过滤器的两个核心参数——位数组大小m和哈希函数个数k——都由「预计元素数n」和「目标误判率p」决定// 估算参数标准公式 public static long optimalBits(long n, double p) { // 1. m -n * ln(p) / (ln2)^2元素越多或误判率要求越低位数组越大 return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))); } public static int optimalHashes(long n, long m) { // 2. k m/n * ln2哈希个数过多会增加写入成本、过少则误判率上升 return Math.max(1, (int) Math.round((double) m / n * Math.log(2))); }按我们设的n 1_000_000、p 0.01算m ≈ 9585058位约 1.14 MBk 7。关键在这个m是固定的。布隆过滤器一旦创建位数组大小不可变。当实际元素数涨到n 12_000_00012 倍而m不变真实误判率近似p ≈ (1 - e^(-k * n / m))^k (1 - e^(-7 * 12_000_000 / 9_585_058))^7 ≈ (1 - e^(-8.76))^7 ≈ (1 - 0.000157)^7 ≈ 0.30 // 实际约 30%公式告诉我们误判率只和「实际元素数 / 位数组大小」有关容量设小了元素一多误判率就指数级上升。我们当初拍脑袋按日常量设没留大促余量等于给过滤器埋了个定时炸弹。RedisBloom 的正确姿势容量、误判率、扩容我们用的是 RedisBloom 模块命令层面要显式声明容量和误判率// 用 Lettuce 调用 RedisBloomBF.RESERVE 只需建一次 // BF.RESERVE key error_rate capacity [EXPANSION n] [NONSCALING] redisCommands.execute(BF.RESERVE, msg:pushed, // 过滤器名 0.01, // 目标误判率 1% 20000000); // 容量按大促峰值的 ~1.6 倍预留而非日常 100 万 // 推送时用 BF.ADD / BF.EXISTS Boolean exists (Boolean) redisCommands.execute(BF.EXISTS, msg:pushed, msgId); if (Boolean.FALSE.equals(exists)) { doPush(user, msgId); redisCommands.execute(BF.ADD, msg:pushed, msgId); }第 3 行capacity我们后来改成 2000 万按大促峰值 1200 万再留 60% 余量。RedisBloom 默认还带EXPANSION容量满时按倍数新建子过滤器扩容但子过滤器越多查询要扫越多段且扩容后的新段误判率仍是目标值——只是整体内存和查询成本上升。我的做法是不依赖自动扩容直接把初始容量设足扩容只当安全网。也可以选NONSCALING容量写死不扩容塞满后再BF.ADD会报错等于用「写入失败」强制你正视容量规划比默默误判更可控。替代品对比什么时候不该用布隆过滤器方案能否删除误判适合场景代价布隆过滤器否标准版有海量去重、空间极敏感容量固定超量误判飙升布谷鸟过滤器是更低且可控需要删除元素的去重实现复杂内存略高Redis Set是无精确量小、要精确内存随元素线性增长Redis 位图是无用户已读标记偏移即 id适合 id 连续的场景我们这场景「消息去重」如果要精确、且量可控其实用 Redis Set 存「已推送消息 id」也能做代价是内存大。我们保留布隆过滤器是因为消息量上亿、内存敏感但前提是容量必须按峰值预留并配合「关键消息走精确去重兜底」如交易类通知不依赖布隆直接用数据库唯一约束防重。复盘数字大促当天误判导致漏推约 31% 的营销类消息约 370 万条客诉 2100 起无直接资损但品牌影响大。修复把容量提到 2000 万后当天剩余时段漏推率回到 0.9%。事后我们加了一条容量巡检每个布隆过滤器按「近 7 天峰值 × 1.5」自动预警容量是否够用。我的取舍判断我不建议把布隆过滤器当「精确去重」用。它天生有假阳性设计上就该只用在「误判代价低、能容忍偶尔漏/重」的地方比如缓存穿透防护误判顶多多查一次库、爬虫 URL 去重。一旦业务要求「不能漏推、不能误删」就得上精确结构Set、数据库唯一索引或者至少给布隆过滤器配一层精确兜底。还有一点容量一定要按峰值设不是按平均值。布隆过滤器的位数组是创建时就定死的超量即误判飙升没有「慢慢涨」的缓冲期。我们这次就是吃了按日常量设容量的亏。误判率随元素数上涨到底涨多快把不同实际元素数代入p ≈ (1 - e^(-k·n/m))^k位数组m固定为设计 100 万时的值我们离线算了一组实际元素数相对设计容量真实误判率100 万1×~1%300 万3×~6%600 万6×~15%1200 万12×~30%这条曲线说明布隆过滤器的误判率不是线性增长而是逼近 1 的速度越来越快。大促当天我们的元素数正好落在 12× 附近误判撞上 30% 并不意外。我们环境是 Redis 7.2 RedisBloom 2.6.0Java 客户端redis.clients:jedis:5.1.0BF.RESERVE在容量写死后塞满会直接报错反而比「默默误判」安全——至少你能立刻知道容量不够而不是等客诉。监控上怎么早发现容量不够我们给每个过滤器加了写入量巡检用INCR记已写入元素数超过设计容量七成就告警给扩容留提前量public void markAdded(String key, String id) { long used redisCommands.incr(bf:used: key); // 1. 记录已写入元素数 long cap Long.parseLong(redisCommands.get(bf:cap: key)); // 2. 设计容量 if (used cap * 0.7) { alertService.warn(布隆过滤器 key 用量 used / cap); // 3. 超 70% 告警 } redisCommands.execute(BF.ADD, key, id); }第 1 行用INCR维护写入计数第 3 行在超过七成设计容量时报警。比起等误判率飙起来再救火提前按峰值留余量我们按近 7 天峰值 ×1.5 设capacity成本低得多。如果场景要删元素考虑布谷鸟过滤器布隆过滤器标准版不支持删除要删只能重建。需要删除的去重场景可以看布谷鸟过滤器Cuckoo Filter它用桶 指纹存元素支持delete且在相同误判率下内存通常比布隆更小只是实现更复杂、对哈希分布更敏感。我们消息去重不需要删所以没换但如果你做的是「用户已读标记」这类要随时清除的状态布谷鸟过滤器比布隆更合适。我们最终的容量公式线上每个过滤器都按capacity 近 7 天日均峰值 × 1.5申请且BF.RESERVE一律带NONSCALING塞满即报错而不是默默误判把消息丢掉。运营大促前会提前报备预估峰值我们据此把容量再乘 2 预扩。举例说若日常日均 100 万、大促预估 1200 万我们直接按 2000 万建过滤器大促当天实际只到设计容量的 0.6 倍误判率稳稳压在 1% 出头。把容量规划做成「按峰值 × 余量」而不是「按平均值」是这次事故给我们最贵的教训——布隆过滤器一旦建好位数组大小就焊死了超量没有缓冲期只有误判率一路向上。另外RedisBloom 在NONSCALING模式下容量写死后继续BF.ADD会直接报错我们把这个错误接成实时告警而不是吞掉容量问题第一时间就被人看到比等客诉回查快了至少一个量级。我们甚至把写入失败写成降级逻辑超出容量就回退到数据库唯一约束兜底去重宁可多一次查库也不让消息因过滤器报错而丢失。思考题你项目里的布隆过滤器BF.RESERVE的 capacity 是按什么设的把它和实际峰值元素数除一下——如果比值小于 3误判率大概率已经远超你当初算的那个「1%」了。