布隆过滤器Bloom Filter原理、实现与分布式应用一、布隆过滤器是什么布隆过滤器是一种空间效率极高的概率型数据结构用于判断一个元素是否可能存在于一个集合中。核心特性 - 说不存在 → 一定不存在100% 准确 - 说存在 → 可能存在有误判率如 1%用一句话概括宁可错杀绝不放过——它可能把不存在的说成存在误判但绝不会把存在的说成不存在不漏判。注博客https://blog.csdn.net/badao_liumang_qizhi二、为什么需要布隆过滤器问题场景判断一个元素是否在集合中常规方案方案10亿数据占用内存查询速度HashSet~40GB每条40字节O(1)数据库查询磁盘存储慢IO布隆过滤器~1.2GBO(k)极快布隆过滤器用约1/30 的内存就能达到接近 HashSet 的查询速度代价是有微小的误判率。适用场景能接受极小概率的误判如 0.1%数据量巨大HashSet 内存放不下需要快速排除一定不存在的情况三、工作原理数据结构布隆过滤器的底层就是一个位数组bit array初始全为 0位数组假设 m16 位 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0加上k 个哈希函数假设 k3hash1(x)对元素计算第一个哈希值hash2(x)对元素计算第二个哈希值hash3(x)对元素计算第三个哈希值添加元素把元素 “apple” 加入布隆过滤器hash1(apple) % 16 2 hash2(apple) % 16 7 hash3(apple) % 16 11 位数组 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 ↑ ↑ ↑再添加 “banana”hash1(banana) % 16 4 hash2(banana) % 16 7 ← 和 apple 冲突了但没关系 hash3(banana) % 16 14 位数组 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 ↑ ↑ ↑ ↑ ↑查询元素判断 “apple” 是否存在hash1(apple) % 16 2 → 位数组[2] 1 ✓ hash2(apple) % 16 7 → 位数组[7] 1 ✓ hash3(apple) % 16 11 → 位数组[11] 1 ✓ 全部为 1 → 可能存在 ✅判断 “grape” 是否存在hash1(grape) % 16 2 → 位数组[2] 1 ✓ hash2(grape) % 16 9 → 位数组[9] 0 ✗ 发现一个 0 → 一定不存在 ✅判断 “cherry” 是否存在误判场景hash1(cherry) % 16 2 → 位数组[2] 1 ✓apple 留下的 hash2(cherry) % 16 4 → 位数组[4] 1 ✓banana 留下的 hash3(cherry) % 16 14 → 位数组[14] 1 ✓banana 留下的 全部为 1 → 可能存在但实际不存在这就是误判⚠️为什么会误判多个元素的哈希位刚好凑齐了查询元素需要的所有位置。元素越多、位数组越满这种巧合概率越高。为什么不会漏判如果元素确实加入过它对应的 k 个位一定被设为 1查询时这 k 个位一定都是 1。位数组的位一旦设为 1 就不会变回 0。四、关键参数三个核心参数参数含义影响m位数组长度位数越大误判率越低内存越多k哈希函数个数太少或太多都增加误判率n预期插入元素数量元素越多误判率越高误判率公式误判率 ≈ (1 - e^(-kn/m))^k最优哈希函数个数k_optimal (m/n) × ln2 ≈ 0.693 × (m/n)实际选择参考给定预期元素数 n 和期望误判率 p计算所需位数组大小m -(n × ln(p)) / (ln2)²预期元素数误判率位数组大小约等于内存哈希函数数100万1%958万位1.2MB7100万0.1%1437万位1.8MB101000万1%9585万位12MB71亿1%9.58亿位120MB710亿1%95.8亿位1.2GB7对比 HashSet 存 10 亿条字符串 ≈ 40GB布隆过滤器只需 1.2GB。五、布隆过滤器的局限1. 不能删除元素位数组中的 1 被多个元素共享删除一个元素不能把位置0 否则会影响其他元素的判断 例apple 和 banana 都在 位7 上为1 删除 apple 把位7 设为0 → banana 就被误判为不存在了解决方案计数布隆过滤器Counting Bloom Filter——每个位置用计数器替代 0/1普通布隆 [0, 0, 1, 0, 1, 0, 0, 1, ...] 1位/格 计数布隆 [0, 0, 2, 0, 1, 0, 0, 3, ...] 4位/格支持减2. 不能获取已存储的元素布隆过滤器只能回答在不在不能列出哪些在。3. 误判率会随着元素增加而上升加入 10% 容量时误判率极低 加入 50% 容量时误判率接近设计值 加入 100% 容量时误判率等于设计值 超过设计容量时误判率快速上升4. 总结能做不能做判断一定不存在判断一定存在添加元素删除元素普通版极低内存占用获取具体元素列表极快查询 O(k)精确计数六、JDK/Guava 本地布隆过滤器Guava 实现dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion32.1.3-jre/version/dependencyimport com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; // 创建预期100万元素1%误判率 BloomFilterStringfilter BloomFilter.create( Funnels.stringFunnel(Charset.defaultCharset()), 1_000_000, // 预期元素数 0.01 // 期望误判率 ); // 添加 filter.put(user001example.com); filter.put(user002example.com); // 查询 boolean maybeExists filter.mightContain(user001example.com); // true boolean notExists filter.mightContain(unknownexample.com); // false大概率 // 查看误判率随元素增加而上升 double fpp filter.expectedFpp(); // 当前预期误判率本地布隆过滤器的问题实例A 的 BloomFilter: 包含 {user001, user002} 实例B 的 BloomFilter: 包含 {user003, user004} // 实例A 判断 user003 → 不存在错误实际存在于系统中每个实例只知道自己添加过的元素无法做全局判断。七、分布式布隆过滤器为什么需要分布式版本多实例需要共享同一个布隆过滤器数据需要持久化JVM 重启不丢失所有实例的判断结果一致Redis 原生实现手动 BitMapRedis 的 String 类型最大 512MB 2^32 位天然适合做位数组ServicepublicclassRedisBloomFilter{ResourceprivateStringRedisTemplateredisTemplate;privatestaticfinalStringKEYbloom:user-emails;privatestaticfinalintBIT_SIZE10_000_000;// 1000万位 ≈ 1.25MBprivatestaticfinalintHASH_COUNT7;/** 添加元素. */publicvoidadd(Stringvalue){int[]offsetsgetOffsets(value);for(intoffset:offsets){redisTemplate.opsForValue().setBit(KEY,offset,true);}}/** 判断是否可能存在. */publicbooleanmightContain(Stringvalue){int[]offsetsgetOffsets(value);for(intoffset:offsets){BooleanbitredisTemplate.opsForValue().getBit(KEY,offset);if(!Boolean.TRUE.equals(bit)){returnfalse;// 有一个为0一定不存在}}returntrue;// 全部为1可能存在}/** 计算 k 个哈希偏移量. */privateint[]getOffsets(Stringvalue){int[]offsetsnewint[HASH_COUNT];inthash1Hashing.murmur3_128().hashString(value,StandardCharsets.UTF_8).asInt();inthash2Hashing.sipHash24().hashString(value,StandardCharsets.UTF_8).asInt();for(inti0;iHASH_COUNT;i){// 双哈希模拟 k 个哈希函数offsets[i]Math.abs((hash1i*hash2)%BIT_SIZE);}returnoffsets;}}Redis Modules: RedisBloomRedis 官方模块 RedisBloom 提供原生布隆过滤器命令# 创建容量100万误判率1%BF.RESERVE user-emails0.011000000# 添加BF.ADD user-emailsuser001example.comBF.MADD user-emailsuser002example.comuser003example.com# 查询BF.EXISTS user-emailsuser001example.com# 1可能存在BF.EXISTS user-emailsunknownexample.com# 0一定不存在# 查看信息BF.INFO user-emailsRedisson 分布式布隆过滤器ResourceprivateRedissonClientredissonClient;// 获取分布式布隆过滤器RBloomFilterStringbloomFilterredissonClient.getBloomFilter(user:registered-emails);// 初始化只需执行一次重复调用不会覆盖// 预期 100万个元素误判率 1%bloomFilter.tryInit(1_000_000,0.01);// 添加bloomFilter.add(user001example.com);// 查询booleanmayExistbloomFilter.contains(user001example.com);// truebooleannotExistbloomFilter.contains(fakeexample.com);// false// 查看当前元素数量近似值longcountbloomFilter.count();// 查看预期误判率doublefppbloomFilter.getFalseProbability();// 查看哈希函数个数inthashIterationsbloomFilter.getHashIterations();// 查看位数组大小longsizebloomFilter.getSize();八、实战场景详解场景1缓存穿透防护问题恶意请求大量不存在的 key绕过缓存直达数据库。正常请求请求 key123 → 缓存命中 → 返回 恶意请求请求 key99999999不存在→ 缓存未命中 → 查数据库 → 为空 → 不缓存 下一次请求同样的 key → 又查数据库 → 又为空无限穿透解决布隆过滤器前置过滤ServicepublicclassProductQueryService{ResourceprivateRedissonClientredissonClient;ResourceprivateRedisTemplateString,StringredisTemplate;ResourceprivateProductRepositoryproductRepository;privateRBloomFilterStringgetFilter(){returnredissonClient.getBloomFilter(product:id:bloom);}/** 系统启动时加载所有商品ID到布隆过滤器. */PostConstructpublicvoidinitBloomFilter(){RBloomFilterStringfiltergetFilter();filter.tryInit(5_000_000,0.001);// 500万商品0.1%误判率// 全量加载可分批ListStringallProductIdsproductRepository.findAllIds();allProductIds.forEach(filter::add);log.info(布隆过滤器初始化完成加载{}个商品ID,allProductIds.size());}/** 查询商品. */publicProductgetProduct(StringproductId){// 第一层布隆过滤器拦截一定不存在的请求if(!getFilter().contains(productId)){returnnull;// 一定不存在直接返回}// 第二层Redis 缓存StringcacheKeyproduct:productId;StringcachedredisTemplate.opsForValue().get(cacheKey);if(cached!null){returnNULL.equals(cached)?null:JSON.parseObject(cached,Product.class);}// 第三层数据库ProductproductproductRepository.findById(productId).orElse(null);if(product!null){redisTemplate.opsForValue().set(cacheKey,JSON.toJSONString(product),30,TimeUnit.MINUTES);}else{// 缓存空值防止同一 key 反复穿透布隆过滤器误判的那 0.1%redisTemplate.opsForValue().set(cacheKey,NULL,5,TimeUnit.MINUTES);}returnproduct;}/** 新增商品时同步加入布隆过滤器. */publicvoidaddProduct(Productproduct){productRepository.save(product);getFilter().add(product.getId());}}流程图请求进入 │ ▼ 布隆过滤器判断 │ ├─ 不存在(0) → 直接返回 null快速拒绝 │ └─ 可能存在(1) │ ▼ 查 Redis 缓存 │ ├─ 命中 → 返回缓存数据 │ └─ 未命中 │ ▼ 查数据库 │ ├─ 有数据 → 写缓存 返回 │ └─ 无数据 → 写空缓存(短TTL) 返回null场景2用户名/手机号注册去重ServicepublicclassRegistrationService{ResourceprivateRedissonClientredissonClient;ResourceprivateUserRepositoryuserRepository;privateRBloomFilterStringgetPhoneFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(user:phone:bloom);filter.tryInit(50_000_000,0.001);// 5000万用户0.1%误判率returnfilter;}/** 快速检查手机号是否已注册. */publicbooleanisPhoneRegistered(Stringphone){// 布隆过滤器快速判断if(!getPhoneFilter().contains(phone)){returnfalse;// 一定没注册过}// 可能注册过有0.1%概率是误判查数据库确认returnuserRepository.existsByPhone(phone);}/** 注册成功后加入布隆过滤器. */publicvoidregister(Useruser){userRepository.save(user);getPhoneFilter().add(user.getPhone());}}好处绝大多数未注册的查询如99%以上的新手机号被布隆过滤器直接挡住不查数据库。场景3推荐系统去重用户已读内容过滤ServicepublicclassRecommendationService{ResourceprivateRedissonClientredissonClient;/** 判断用户是否看过某篇文章. */publicbooleanhasRead(StringuserId,StringarticleId){RBloomFilterStringfilterredissonClient.getBloomFilter(read:userId);filter.tryInit(10_000,0.01);// 每用户预计看1万篇1%误判returnfilter.contains(articleId);}/** 用户浏览文章后记录. */publicvoidmarkRead(StringuserId,StringarticleId){RBloomFilterStringfilterredissonClient.getBloomFilter(read:userId);filter.tryInit(10_000,0.01);filter.add(articleId);}/** 从候选列表中过滤掉已读内容. */publicListArticlefilterUnread(StringuserId,ListArticlecandidates){returncandidates.stream().filter(article-!hasRead(userId,article.getId())).collect(Collectors.toList());// 误判后果极少数已读文章不会被推荐可接受}}场景4爬虫 URL 去重ServicepublicclassCrawlerUrlDedup{ResourceprivateRedissonClientredissonClient;privateRBloomFilterStringgetFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(crawler:visited-urls);filter.tryInit(100_000_000,0.0001);// 1亿URL0.01%误判returnfilter;}/** 提交URL进行爬取自动去重. */publicbooleansubmitUrl(Stringurl){RBloomFilterStringfiltergetFilter();if(filter.contains(url)){returnfalse;// 大概率已爬过跳过}filter.add(url);crawlerQueue.offer(url);// 加入爬取队列returntrue;}}场景5垃圾邮件过滤ServicepublicclassSpamFilter{ResourceprivateRedissonClientredissonClient;privateRBloomFilterStringgetSpamFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(spam:known-senders);filter.tryInit(10_000_000,0.001);returnfilter;}/** 判断邮件是否来自已知垃圾发送者. */publicbooleanisSpam(StringsenderEmail){if(getSpamFilter().contains(senderEmail)){returntrue;// 可能是垃圾0.1%误判正常邮件被标为垃圾}returnfalse;// 一定不是已知垃圾发送者}/** 用户举报垃圾邮件. */publicvoidreportSpam(StringsenderEmail){getSpamFilter().add(senderEmail);}}九、布隆过滤器的扩展变体1. 计数布隆过滤器Counting Bloom Filter支持删除操作每个位置用计数器普通版 [0, 0, 1, 0, 1, 0, 0, 1] 每位 1 bit 计数版 [0, 0, 2, 0, 1, 0, 0, 3] 每位 4 bit 添加 apple: 位2 1, 位7 1, 位11 1 添加 banana: 位4 1, 位7 1, 位14 1 删除 apple: 位2 -1, 位7 -1, 位11 -1 ← 位7 从2变1banana不受影响代价内存占用增加 4 倍每位 4bit 替代 1bit。2. 布谷鸟过滤器Cuckoo Filter支持删除空间效率更高比计数布隆更省内存查询速度类似3. 可扩展布隆过滤器Scalable Bloom Filter元素超过预设容量时自动扩展不需要预先知道精确元素数层级1100万容量满了 层级2200万容量满了 层级3400万容量当前使用中 查询时逐层查询任一层说可能存在就返回 true十、误判率的实际影响分析误判率 1% 意味着什么100 次查询不存在的元素 - 99 次正确返回不存在 - 1 次错误返回可能存在后续查数据库确认是否真的存在各场景对误判的容忍度场景推荐误判率误判后果缓存穿透防护0.1%0.1%请求穿透到数据库可接受注册去重检查0.01%0.01%用户被误判已注册查库确认即可推荐去重1%1%已看内容不被推荐对体验影响极小URL 去重0.01%0.01%新页面被跳过几乎无感垃圾邮件0.1%0.1%正常邮件被误判为垃圾需人工检查关键认知布隆过滤器不是终点是快速过滤层 查询 → 布隆过滤器 → 不存在 → 结束快速路径 → 可能存在 → 查数据库/缓存确认慢速路径十一、注意事项1. 容量规划// 错误容量设太小filter.tryInit(10_000,0.01);// 实际插入 100万个元素后误判率飙升到 90%// 正确预估峰值容量留 2-3 倍余量filter.tryInit(3_000_000,0.01);// 预期100万留3倍余量2. 持久化和重建// 布隆过滤器数据丢失Redis 故障后需要重建Scheduled(cron0 0 3 * * ?)// 每天凌晨3点publicvoidrebuildBloomFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(product:bloom);filter.delete();// 删除旧的filter.tryInit(5_000_000,0.001);// 全量重新加载productRepository.findAllIds().forEach(filter::add);}3. 内存估算m位数 -n × ln(p) / (ln2)² 示例1000万元素0.1%误判 m -10,000,000 × ln(0.001) / (0.693)² m ≈ 143,775,874 位 m ≈ 17.2MB4. 不适合的场景需要精确判断误判不可接受→ 用 HashSet 或数据库需要获取元素内容 → 用 Set需要删除元素 → 用计数布隆或布谷鸟过滤器元素数量很少1万→ 直接用 Set布隆过滤器反而浪费十二、总结概念一句话布隆过滤器位数组 多个哈希函数空间换准确率的概率数据结构核心特性说不在一定不在说在可能不在有误判本质作用快速过滤一定不存在的请求适用条件数据量大 能接受小概率误判分布式版位数组存在 Redis 中多实例共享最常见用途缓存穿透防护内存优势10亿数据仅需 ~1.2GBHashSet 需 ~40GB核心参数预期容量 n 期望误判率 p → 自动算出位数组大小和哈希函数数 布隆过滤器（Bloom Filter）：原理、实现与分布式应用
布隆过滤器Bloom Filter原理、实现与分布式应用一、布隆过滤器是什么布隆过滤器是一种空间效率极高的概率型数据结构用于判断一个元素是否可能存在于一个集合中。核心特性 - 说不存在 → 一定不存在100% 准确 - 说存在 → 可能存在有误判率如 1%用一句话概括宁可错杀绝不放过——它可能把不存在的说成存在误判但绝不会把存在的说成不存在不漏判。注博客https://blog.csdn.net/badao_liumang_qizhi二、为什么需要布隆过滤器问题场景判断一个元素是否在集合中常规方案方案10亿数据占用内存查询速度HashSet~40GB每条40字节O(1)数据库查询磁盘存储慢IO布隆过滤器~1.2GBO(k)极快布隆过滤器用约1/30 的内存就能达到接近 HashSet 的查询速度代价是有微小的误判率。适用场景能接受极小概率的误判如 0.1%数据量巨大HashSet 内存放不下需要快速排除一定不存在的情况三、工作原理数据结构布隆过滤器的底层就是一个位数组bit array初始全为 0位数组假设 m16 位 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0加上k 个哈希函数假设 k3hash1(x)对元素计算第一个哈希值hash2(x)对元素计算第二个哈希值hash3(x)对元素计算第三个哈希值添加元素把元素 “apple” 加入布隆过滤器hash1(apple) % 16 2 hash2(apple) % 16 7 hash3(apple) % 16 11 位数组 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 ↑ ↑ ↑再添加 “banana”hash1(banana) % 16 4 hash2(banana) % 16 7 ← 和 apple 冲突了但没关系 hash3(banana) % 16 14 位数组 索引: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 值: 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 ↑ ↑ ↑ ↑ ↑查询元素判断 “apple” 是否存在hash1(apple) % 16 2 → 位数组[2] 1 ✓ hash2(apple) % 16 7 → 位数组[7] 1 ✓ hash3(apple) % 16 11 → 位数组[11] 1 ✓ 全部为 1 → 可能存在 ✅判断 “grape” 是否存在hash1(grape) % 16 2 → 位数组[2] 1 ✓ hash2(grape) % 16 9 → 位数组[9] 0 ✗ 发现一个 0 → 一定不存在 ✅判断 “cherry” 是否存在误判场景hash1(cherry) % 16 2 → 位数组[2] 1 ✓apple 留下的 hash2(cherry) % 16 4 → 位数组[4] 1 ✓banana 留下的 hash3(cherry) % 16 14 → 位数组[14] 1 ✓banana 留下的 全部为 1 → 可能存在但实际不存在这就是误判⚠️为什么会误判多个元素的哈希位刚好凑齐了查询元素需要的所有位置。元素越多、位数组越满这种巧合概率越高。为什么不会漏判如果元素确实加入过它对应的 k 个位一定被设为 1查询时这 k 个位一定都是 1。位数组的位一旦设为 1 就不会变回 0。四、关键参数三个核心参数参数含义影响m位数组长度位数越大误判率越低内存越多k哈希函数个数太少或太多都增加误判率n预期插入元素数量元素越多误判率越高误判率公式误判率 ≈ (1 - e^(-kn/m))^k最优哈希函数个数k_optimal (m/n) × ln2 ≈ 0.693 × (m/n)实际选择参考给定预期元素数 n 和期望误判率 p计算所需位数组大小m -(n × ln(p)) / (ln2)²预期元素数误判率位数组大小约等于内存哈希函数数100万1%958万位1.2MB7100万0.1%1437万位1.8MB101000万1%9585万位12MB71亿1%9.58亿位120MB710亿1%95.8亿位1.2GB7对比 HashSet 存 10 亿条字符串 ≈ 40GB布隆过滤器只需 1.2GB。五、布隆过滤器的局限1. 不能删除元素位数组中的 1 被多个元素共享删除一个元素不能把位置0 否则会影响其他元素的判断 例apple 和 banana 都在 位7 上为1 删除 apple 把位7 设为0 → banana 就被误判为不存在了解决方案计数布隆过滤器Counting Bloom Filter——每个位置用计数器替代 0/1普通布隆 [0, 0, 1, 0, 1, 0, 0, 1, ...] 1位/格 计数布隆 [0, 0, 2, 0, 1, 0, 0, 3, ...] 4位/格支持减2. 不能获取已存储的元素布隆过滤器只能回答在不在不能列出哪些在。3. 误判率会随着元素增加而上升加入 10% 容量时误判率极低 加入 50% 容量时误判率接近设计值 加入 100% 容量时误判率等于设计值 超过设计容量时误判率快速上升4. 总结能做不能做判断一定不存在判断一定存在添加元素删除元素普通版极低内存占用获取具体元素列表极快查询 O(k)精确计数六、JDK/Guava 本地布隆过滤器Guava 实现dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion32.1.3-jre/version/dependencyimport com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; // 创建预期100万元素1%误判率 BloomFilterStringfilter BloomFilter.create( Funnels.stringFunnel(Charset.defaultCharset()), 1_000_000, // 预期元素数 0.01 // 期望误判率 ); // 添加 filter.put(user001example.com); filter.put(user002example.com); // 查询 boolean maybeExists filter.mightContain(user001example.com); // true boolean notExists filter.mightContain(unknownexample.com); // false大概率 // 查看误判率随元素增加而上升 double fpp filter.expectedFpp(); // 当前预期误判率本地布隆过滤器的问题实例A 的 BloomFilter: 包含 {user001, user002} 实例B 的 BloomFilter: 包含 {user003, user004} // 实例A 判断 user003 → 不存在错误实际存在于系统中每个实例只知道自己添加过的元素无法做全局判断。七、分布式布隆过滤器为什么需要分布式版本多实例需要共享同一个布隆过滤器数据需要持久化JVM 重启不丢失所有实例的判断结果一致Redis 原生实现手动 BitMapRedis 的 String 类型最大 512MB 2^32 位天然适合做位数组ServicepublicclassRedisBloomFilter{ResourceprivateStringRedisTemplateredisTemplate;privatestaticfinalStringKEYbloom:user-emails;privatestaticfinalintBIT_SIZE10_000_000;// 1000万位 ≈ 1.25MBprivatestaticfinalintHASH_COUNT7;/** 添加元素. */publicvoidadd(Stringvalue){int[]offsetsgetOffsets(value);for(intoffset:offsets){redisTemplate.opsForValue().setBit(KEY,offset,true);}}/** 判断是否可能存在. */publicbooleanmightContain(Stringvalue){int[]offsetsgetOffsets(value);for(intoffset:offsets){BooleanbitredisTemplate.opsForValue().getBit(KEY,offset);if(!Boolean.TRUE.equals(bit)){returnfalse;// 有一个为0一定不存在}}returntrue;// 全部为1可能存在}/** 计算 k 个哈希偏移量. */privateint[]getOffsets(Stringvalue){int[]offsetsnewint[HASH_COUNT];inthash1Hashing.murmur3_128().hashString(value,StandardCharsets.UTF_8).asInt();inthash2Hashing.sipHash24().hashString(value,StandardCharsets.UTF_8).asInt();for(inti0;iHASH_COUNT;i){// 双哈希模拟 k 个哈希函数offsets[i]Math.abs((hash1i*hash2)%BIT_SIZE);}returnoffsets;}}Redis Modules: RedisBloomRedis 官方模块 RedisBloom 提供原生布隆过滤器命令# 创建容量100万误判率1%BF.RESERVE user-emails0.011000000# 添加BF.ADD user-emailsuser001example.comBF.MADD user-emailsuser002example.comuser003example.com# 查询BF.EXISTS user-emailsuser001example.com# 1可能存在BF.EXISTS user-emailsunknownexample.com# 0一定不存在# 查看信息BF.INFO user-emailsRedisson 分布式布隆过滤器ResourceprivateRedissonClientredissonClient;// 获取分布式布隆过滤器RBloomFilterStringbloomFilterredissonClient.getBloomFilter(user:registered-emails);// 初始化只需执行一次重复调用不会覆盖// 预期 100万个元素误判率 1%bloomFilter.tryInit(1_000_000,0.01);// 添加bloomFilter.add(user001example.com);// 查询booleanmayExistbloomFilter.contains(user001example.com);// truebooleannotExistbloomFilter.contains(fakeexample.com);// false// 查看当前元素数量近似值longcountbloomFilter.count();// 查看预期误判率doublefppbloomFilter.getFalseProbability();// 查看哈希函数个数inthashIterationsbloomFilter.getHashIterations();// 查看位数组大小longsizebloomFilter.getSize();八、实战场景详解场景1缓存穿透防护问题恶意请求大量不存在的 key绕过缓存直达数据库。正常请求请求 key123 → 缓存命中 → 返回 恶意请求请求 key99999999不存在→ 缓存未命中 → 查数据库 → 为空 → 不缓存 下一次请求同样的 key → 又查数据库 → 又为空无限穿透解决布隆过滤器前置过滤ServicepublicclassProductQueryService{ResourceprivateRedissonClientredissonClient;ResourceprivateRedisTemplateString,StringredisTemplate;ResourceprivateProductRepositoryproductRepository;privateRBloomFilterStringgetFilter(){returnredissonClient.getBloomFilter(product:id:bloom);}/** 系统启动时加载所有商品ID到布隆过滤器. */PostConstructpublicvoidinitBloomFilter(){RBloomFilterStringfiltergetFilter();filter.tryInit(5_000_000,0.001);// 500万商品0.1%误判率// 全量加载可分批ListStringallProductIdsproductRepository.findAllIds();allProductIds.forEach(filter::add);log.info(布隆过滤器初始化完成加载{}个商品ID,allProductIds.size());}/** 查询商品. */publicProductgetProduct(StringproductId){// 第一层布隆过滤器拦截一定不存在的请求if(!getFilter().contains(productId)){returnnull;// 一定不存在直接返回}// 第二层Redis 缓存StringcacheKeyproduct:productId;StringcachedredisTemplate.opsForValue().get(cacheKey);if(cached!null){returnNULL.equals(cached)?null:JSON.parseObject(cached,Product.class);}// 第三层数据库ProductproductproductRepository.findById(productId).orElse(null);if(product!null){redisTemplate.opsForValue().set(cacheKey,JSON.toJSONString(product),30,TimeUnit.MINUTES);}else{// 缓存空值防止同一 key 反复穿透布隆过滤器误判的那 0.1%redisTemplate.opsForValue().set(cacheKey,NULL,5,TimeUnit.MINUTES);}returnproduct;}/** 新增商品时同步加入布隆过滤器. */publicvoidaddProduct(Productproduct){productRepository.save(product);getFilter().add(product.getId());}}流程图请求进入 │ ▼ 布隆过滤器判断 │ ├─ 不存在(0) → 直接返回 null快速拒绝 │ └─ 可能存在(1) │ ▼ 查 Redis 缓存 │ ├─ 命中 → 返回缓存数据 │ └─ 未命中 │ ▼ 查数据库 │ ├─ 有数据 → 写缓存 返回 │ └─ 无数据 → 写空缓存(短TTL) 返回null场景2用户名/手机号注册去重ServicepublicclassRegistrationService{ResourceprivateRedissonClientredissonClient;ResourceprivateUserRepositoryuserRepository;privateRBloomFilterStringgetPhoneFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(user:phone:bloom);filter.tryInit(50_000_000,0.001);// 5000万用户0.1%误判率returnfilter;}/** 快速检查手机号是否已注册. */publicbooleanisPhoneRegistered(Stringphone){// 布隆过滤器快速判断if(!getPhoneFilter().contains(phone)){returnfalse;// 一定没注册过}// 可能注册过有0.1%概率是误判查数据库确认returnuserRepository.existsByPhone(phone);}/** 注册成功后加入布隆过滤器. */publicvoidregister(Useruser){userRepository.save(user);getPhoneFilter().add(user.getPhone());}}好处绝大多数未注册的查询如99%以上的新手机号被布隆过滤器直接挡住不查数据库。场景3推荐系统去重用户已读内容过滤ServicepublicclassRecommendationService{ResourceprivateRedissonClientredissonClient;/** 判断用户是否看过某篇文章. */publicbooleanhasRead(StringuserId,StringarticleId){RBloomFilterStringfilterredissonClient.getBloomFilter(read:userId);filter.tryInit(10_000,0.01);// 每用户预计看1万篇1%误判returnfilter.contains(articleId);}/** 用户浏览文章后记录. */publicvoidmarkRead(StringuserId,StringarticleId){RBloomFilterStringfilterredissonClient.getBloomFilter(read:userId);filter.tryInit(10_000,0.01);filter.add(articleId);}/** 从候选列表中过滤掉已读内容. */publicListArticlefilterUnread(StringuserId,ListArticlecandidates){returncandidates.stream().filter(article-!hasRead(userId,article.getId())).collect(Collectors.toList());// 误判后果极少数已读文章不会被推荐可接受}}场景4爬虫 URL 去重ServicepublicclassCrawlerUrlDedup{ResourceprivateRedissonClientredissonClient;privateRBloomFilterStringgetFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(crawler:visited-urls);filter.tryInit(100_000_000,0.0001);// 1亿URL0.01%误判returnfilter;}/** 提交URL进行爬取自动去重. */publicbooleansubmitUrl(Stringurl){RBloomFilterStringfiltergetFilter();if(filter.contains(url)){returnfalse;// 大概率已爬过跳过}filter.add(url);crawlerQueue.offer(url);// 加入爬取队列returntrue;}}场景5垃圾邮件过滤ServicepublicclassSpamFilter{ResourceprivateRedissonClientredissonClient;privateRBloomFilterStringgetSpamFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(spam:known-senders);filter.tryInit(10_000_000,0.001);returnfilter;}/** 判断邮件是否来自已知垃圾发送者. */publicbooleanisSpam(StringsenderEmail){if(getSpamFilter().contains(senderEmail)){returntrue;// 可能是垃圾0.1%误判正常邮件被标为垃圾}returnfalse;// 一定不是已知垃圾发送者}/** 用户举报垃圾邮件. */publicvoidreportSpam(StringsenderEmail){getSpamFilter().add(senderEmail);}}九、布隆过滤器的扩展变体1. 计数布隆过滤器Counting Bloom Filter支持删除操作每个位置用计数器普通版 [0, 0, 1, 0, 1, 0, 0, 1] 每位 1 bit 计数版 [0, 0, 2, 0, 1, 0, 0, 3] 每位 4 bit 添加 apple: 位2 1, 位7 1, 位11 1 添加 banana: 位4 1, 位7 1, 位14 1 删除 apple: 位2 -1, 位7 -1, 位11 -1 ← 位7 从2变1banana不受影响代价内存占用增加 4 倍每位 4bit 替代 1bit。2. 布谷鸟过滤器Cuckoo Filter支持删除空间效率更高比计数布隆更省内存查询速度类似3. 可扩展布隆过滤器Scalable Bloom Filter元素超过预设容量时自动扩展不需要预先知道精确元素数层级1100万容量满了 层级2200万容量满了 层级3400万容量当前使用中 查询时逐层查询任一层说可能存在就返回 true十、误判率的实际影响分析误判率 1% 意味着什么100 次查询不存在的元素 - 99 次正确返回不存在 - 1 次错误返回可能存在后续查数据库确认是否真的存在各场景对误判的容忍度场景推荐误判率误判后果缓存穿透防护0.1%0.1%请求穿透到数据库可接受注册去重检查0.01%0.01%用户被误判已注册查库确认即可推荐去重1%1%已看内容不被推荐对体验影响极小URL 去重0.01%0.01%新页面被跳过几乎无感垃圾邮件0.1%0.1%正常邮件被误判为垃圾需人工检查关键认知布隆过滤器不是终点是快速过滤层 查询 → 布隆过滤器 → 不存在 → 结束快速路径 → 可能存在 → 查数据库/缓存确认慢速路径十一、注意事项1. 容量规划// 错误容量设太小filter.tryInit(10_000,0.01);// 实际插入 100万个元素后误判率飙升到 90%// 正确预估峰值容量留 2-3 倍余量filter.tryInit(3_000_000,0.01);// 预期100万留3倍余量2. 持久化和重建// 布隆过滤器数据丢失Redis 故障后需要重建Scheduled(cron0 0 3 * * ?)// 每天凌晨3点publicvoidrebuildBloomFilter(){RBloomFilterStringfilterredissonClient.getBloomFilter(product:bloom);filter.delete();// 删除旧的filter.tryInit(5_000_000,0.001);// 全量重新加载productRepository.findAllIds().forEach(filter::add);}3. 内存估算m位数 -n × ln(p) / (ln2)² 示例1000万元素0.1%误判 m -10,000,000 × ln(0.001) / (0.693)² m ≈ 143,775,874 位 m ≈ 17.2MB4. 不适合的场景需要精确判断误判不可接受→ 用 HashSet 或数据库需要获取元素内容 → 用 Set需要删除元素 → 用计数布隆或布谷鸟过滤器元素数量很少1万→ 直接用 Set布隆过滤器反而浪费十二、总结概念一句话布隆过滤器位数组 多个哈希函数空间换准确率的概率数据结构核心特性说不在一定不在说在可能不在有误判本质作用快速过滤一定不存在的请求适用条件数据量大 能接受小概率误判分布式版位数组存在 Redis 中多实例共享最常见用途缓存穿透防护内存优势10亿数据仅需 ~1.2GBHashSet 需 ~40GB核心参数预期容量 n 期望误判率 p → 自动算出位数组大小和哈希函数数