title: 一亿条黑名单 HashSet 要 6GB 内存布隆过滤器 120MB 就够但误判率公式我算错过一次date: 2026-10-01tags: [布隆过滤器, 缓存穿透, Redis, Guava, 位图, 源码解析, Java]2024 年我们做风控系统的黑名单查询产品给的需求是亿级手机号毫秒级判定。第一版直接用 Redis 的 Set 存了一亿个手机号内存账单一出来运维就找上门光这一个 key 就占了 9GB。换成布隆过滤器之后同样一亿条数据、1% 误判率的配置下位图只要 120MB判定耗时稳定在微秒级。但这个组件的门槛不在用在算。我第一次配参数时把误判率公式里的 hash 函数个数代错了变量实际误判率比预期高了将近十倍白名单误杀客诉了一天。这篇文章把布隆过滤器的原理、参数计算、Guava 与 Redis 两套实现的差异和我的踩坑完整讲一遍。一、先说清它能干什么、不能干什么布隆过滤器本质是一个大位图 k 个独立哈希函数。写入元素时用 k 个哈希函数算出 k 个位置把位图上这 k 位全部置 1。查询时同样算 k 个位置只要有一位是 0元素必然不存在全是 1元素很可能存在。两个结论直接从原理推出来-不存在判定 100% 可靠。这一位是 0 意味着从来没有任何元素把它置 1。-存在判定会误判。不同元素的哈希位会重叠别的不相关元素恰好把你查的 k 个位全置过 1你就会被误判为存在。误判只能减少、不能消除且只增不减——布隆过滤器不支持删除因为清除一个元素的位可能连带影响别的元素。所以它的正确姿势不是存数据而是挡流量用它判定绝对没有拦截掉绝大部分无效查询。典型场景就是缓存穿透防护——恶意请求查一堆数据库里根本不存在的 ID每次都打到数据库布隆过滤器在前面直接把不存在的请求拦掉。二、参数计算我算错的那次误判率的近似公式是p ≈ (1 - e^(-k*n/m))^k其中 m 是位数组长度n 是元素个数k 是哈希函数个数。最优哈希函数个数k (m/n) * ln2 ≈ 0.693 * (m/n)给定目标误判率 p 时位数组长度m -n * ln(p) / (ln2)^2。我当年的错误计算 m 时把元素规模 n 代成了未来三年预估量 3000 万但实际数据量很快涨到了 1.2 亿。n 涨 4 倍误判率大约按 e 的指数恶化1% 的设计目标实际跑成了接近 9%。白名单场景 9% 的误判意味着一天十几万次误拦截客诉电话直接打爆。教训固化成一条规则布隆过滤器初始化前n 必须按最大容量上浮 50% 计算并提前定好重建预案——数据涨到阈值就基于全量数据重建一个更大的过滤器原子切换引用。重建期间误判率会短暂超标业务上要能容忍这个窗口否则就该上计数布隆过滤器或直接分片。用 Guava 验证一下参数guava 32.x的 BloomFilter// 预期 1.2 亿条误判率 1% BloomFilterString filter BloomFilter.create( Funnels.stringFunnel(StandardCharsets.UTF_8), 120_000_000L, // expectedInsertions: 按上限算不是当前量 0.01); // fpp: 期望误判率 // 内部会反推出最优 m 和 k写入元素 filter.put(13800001111); filter.put(13800002222); System.out.println(filter.mightContain(13800001111)); // true大概率 System.out.println(filter.mightContain(99999999999)); // false100% 可靠逐行解释-create内部按公式反推位数组长度和哈希函数个数120M 元素 1% 误判率大约需要 1.15GB 位图、7 个哈希函数。-put对元素做 7 次哈希置位。-mightContain只做位查询无 IO、无锁单次微秒级。三、原理源码Guava 里一次 put 到底做了什么看源码比背公式踏实。Guava 的BloomFilter.put最终走到BloomFilterStrategies里// BloomFilterStrategies.putguava 32.x节选 public boolean put(T object, Funnel? super T funnel, int numHashFunctions, BitArray bits) { long hash64 Hashing.murmur3_128().hashObject(object, funnel).asLong(); int hash1 (int) hash64; int hash2 (int) (hash64 32); boolean bitsChanged false; // 双重哈希第 i 个哈希 hash1 i * hash2 for (int i 1; i numHashFunctions; i) { int combinedHash hash1 (i * hash2); // hash2 可能为负翻转符号保证下标合法 if (combinedHash 0) { combinedHash ~combinedHash; } bitsChanged | bits.set(combinedHash % bits.bitSize()); } return bitsChanged; }逐行解释- murmur3 一次性产出 128 位哈希拆成两个 int 当作 h1、h2第 i 次哈希用h1 i*h2线性组合——这就是 Kirsch-Mitzenmacher 技巧k 个哈希函数的成本压成了一次哈希加 k 次加法。- 负数哈希用按位取反翻正比取绝对值多一层保险Integer.MIN_VALUE 的绝对值还是负数。-bits.set返回这一位是否从 0 变 1调用方可以借此统计过滤器的实际填充率填充率逼近设计值就该触发重建。mightContain的逻辑和 put 几乎一样只是把bits.set换成bits.get任何一位返回 false 就立刻判定不存在。这也解释了为什么不存在的判定是确定性的只要有一位从没被任何元素置过 1元素就绝不可能写入过。顺带看一眼位图的存储结构static final class BitArray { // LongArray 承载实际数据long 数组一块 64 位 private final LongArray data; private long bitCount; boolean set(long index) { if (get(index)) { return false; } long l (int) (index 6); // 定位到第几个 long除以 64 long m 1L index; // 在 long 内的偏移 data.set(l, data.get(l) | m); // 按位或置 1 bitCount; return true; } }index 6就是除以 64 取整1L index在对应 long 内造掩码一次按位或完成置位。1.2 亿位只需约 15MB 的 long 数组——这就是开头说的 120MBRedis 版含分片与持久化开销的来源。四、三种去重方案对比方案内存亿级支持删除误判适用Redis Set9GB支持无精确去重、小规模布隆过滤器120MB不支持有可调海量不存在拦截Cuckoo Filter约布隆 1.5 倍支持有需要删除的场景我们的选型结论黑名单只需要拦截不存在误判靠人工复核兜底布隆过滤器是明确的赢家像同一订单防止重复处理这种要支持删除且必须精确的场景直接用去重表或 Set不要硬套布隆。五、Guava 单机版与 Redis 分布式版的差异Guava 的过滤器活在 JVM 堆里多实例部署时各节点的数据不一致A 实例写入的黑名单B 实例看不到。风控这种集群一致场景必须用 Redis 版。Redis 官方模块 RedisBloom 提供BF.ADD/BF.EXISTS原生命令// RedisBloom 模块redisbloom 2.x的原生命令Jedis 直接可用 jedis.sendCommand(ProtocolCommand.BF_ADD, blacklist, 13800001111.getBytes(StandardCharsets.UTF_8)); // BF.ADD 首次执行时会按 ERROR 参数自动创建过滤器默认误判率 0.81% Object exists jedis.sendCommand(ProtocolCommand.BF_EXISTS, blacklist, 13800001111.getBytes(StandardCharsets.UTF_8)); // exists 1 表示很可能存在0 表示绝对不存在模块版的好处是创建、扩容、分片都由服务端托管BF.RESERVE blacklists 0.01 120000000一条命令完成参数初始化。缺点是要在 Redis 服务端装模块不少公司的托管 Redis 不允许——这正是我们当时退回位图自实现的原因。没装模块的团队也可以用 Redis 的位图SETBIT/GETBIT自实现我贴一下我们自实现的核心查询逻辑public boolean mightContain(String key) { byte[] data key.getBytes(StandardCharsets.UTF_8); boolean allSet true; for (int i 0; i numHashFunctions; i) { // 用双重哈希模拟 k 个独立哈希h(i) h1 i * h2 long hash Hashing.murmur3_128().hashBytes(data).asLong(); long h1 hash 32; long h2 (hash 32) 32; long combined Math.abs(h1 i * h2) % numBits; // 任何一位为 0 即判定不存在直接短路返回 if (!jedis.getbit(bitmapKey, combined)) { allSet false; break; } } return allSet; }逐行解释- 双重哈希Kirsch-Mitzenmacher 优化只用一次 murmur3 计算就能模拟 k 个哈希省 CPU。- 取模定位到位图的具体 bit。- 任何一位为 0 立即短路返回命中最快路径只有一次 Redis 往返。实测数据1.2 亿位图GETBIT 单次往返约 0.3ms7 次哈希短路后平均 2.1 次 GETBITP99 在 1ms 以内——相比原来 Set 的 9GB 内存和 SISMEMBER 的开销这笔账很划算。但要提醒一个集群版的坑布隆过滤器初始化必须是原子的全量灌入。我们上线时服务重启后过滤器是空的等于所有黑名单判定返回不存在恶意流量瞬间穿透到数据库。后来加了启动检查位图 key 不存在就先执行全量灌入约 4 分钟再对外服务灌入期用旧实例承接流量。六、我的取舍判断判定不存在且能容忍小概率误判的场景布隆过滤器是性价比之王需要精确去重且要支持删除换 Cuckoo Filter 或干脆用 Redis Set 分桶。预期容量必须按上限 50% 配置写进代码注释和方案文档并配套重建预案。单机用 Guava 就好别为了分布式把简单问题复杂化集群一致性要求高的场景直接 RedisBloom 或位图自实现。任何布隆过滤器上线方案里冷启动空过滤器和重建切换必须作为两个独立验收项我们两次事故一次就栽在冷启动上。七、复盘真实数字场景亿级手机号黑名单毫秒判定旧方案Redis Set 9GB 内存SISMEMBER 平均 0.5ms新方案1.15GB 位图n1.2 亿、p1%P99 1ms 以内踩坑参数按 3000 万低估计算实际 1.2 亿时误判率恶化到约 9%误杀客诉一天修复容量上限上浮 50% 全量重建预案 冷启动灌入检查八、思考题打开你项目的缓存查询链路看看穿透防护是查不到就缓存空值还是布隆过滤器。如果是前者估算一下恶意查询的 key 空间有多大、空值缓存会不会被打爆。欢迎在评论区讨论你选的方案和理由。