布隆过滤器（Bloom Filter）：原理、实现与分布式应用

布隆过滤器（Bloom Filter）：原理、实现与分布式应用

一、布隆过滤器是什么

布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能存在于一个集合中。

核心特性： - 说"不存在" → 一定不存在（100% 准确） - 说"存在" → 可能存在（有误判率，如 1%）

用一句话概括：宁可错杀，绝不放过——它可能把不存在的说成存在（误判），但绝不会把存在的说成不存在（不漏判）。

注：

博客：

https://blog.csdn.net/badao_liumang_qizhi

二、为什么需要布隆过滤器

问题场景

判断一个元素是否在集合中，常规方案：

方案	10亿数据占用内存	查询速度
HashSet	~40GB（每条40字节）	O(1)
数据库查询	磁盘存储	慢（IO）
布隆过滤器	~1.2GB	O(k)，极快

布隆过滤器用约1/30 的内存就能达到接近 HashSet 的查询速度，代价是有微小的误判率。

适用场景

• 能接受极小概率的误判（如 0.1%）
• 数据量巨大，HashSet 内存放不下
• 需要快速排除"一定不存在"的情况

三、工作原理

数据结构

布隆过滤器的底层就是一个位数组（bit array），初始全为 0：

位数组（假设 m=16 位）： 索引: 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 个哈希函数（假设 k=3）：

• hash1(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.2MB	7
100万	0.1%	1437万位	1.8MB	10
1000万	1%	9585万位	12MB	7
1亿	1%	9.58亿位	120MB	7
10亿	1%	95.8亿位	1.2GB	7

对比 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 实现

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>32.1.3-jre</version></dependency>import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; // 创建：预期100万元素，1%误判率 BloomFilter<String>filter = BloomFilter.create( Funnels.stringFunnel(Charset.defaultCharset()), 1_000_000, // 预期元素数 0.01 // 期望误判率 ); // 添加 filter.put("[e-mail]"); filter.put("[e-mail]"); // 查询 boolean maybeExists = filter.mightContain("[e-mail]"); // true boolean notExists = filter.mightContain("[e-mail]"); // false（大概率） // 查看误判率（随元素增加而上升） double fpp = filter.expectedFpp(); // 当前预期误判率

本地布隆过滤器的问题

实例A 的 BloomFilter: 包含 {user001, user002} 实例B 的 BloomFilter: 包含 {user003, user004} // 实例A 判断 user003 → 不存在（错误！实际存在于系统中）

每个实例只知道自己添加过的元素，无法做全局判断。

七、分布式布隆过滤器

为什么需要分布式版本

• 多实例需要共享同一个布隆过滤器
• 数据需要持久化（JVM 重启不丢失）
• 所有实例的判断结果一致

Redis 原生实现（手动 BitMap）

Redis 的 String 类型最大 512MB = 2^32 位，天然适合做位数组：

@ServicepublicclassRedisBloomFilter{@ResourceprivateStringRedisTemplateredisTemplate;privatestaticfinalStringKEY="bloom:user-emails";privatestaticfinalintBIT_SIZE=10_000_000;// 1000万位 ≈ 1.25MBprivatestaticfinalintHASH_COUNT=7;/** 添加元素. */publicvoidadd(Stringvalue){int[]offsets=getOffsets(value);for(intoffset:offsets){redisTemplate.opsForValue().setBit(KEY,offset,true);}}/** 判断是否可能存在. */publicbooleanmightContain(Stringvalue){int[]offsets=getOffsets(value);for(intoffset:offsets){Booleanbit=redisTemplate.opsForValue().getBit(KEY,offset);if(!Boolean.TRUE.equals(bit)){returnfalse;// 有一个为0，一定不存在}}returntrue;// 全部为1，可能存在}/** 计算 k 个哈希偏移量. */privateint[]getOffsets(Stringvalue){int[]offsets=newint[HASH_COUNT];inthash1=Hashing.murmur3_128().hashString(value,StandardCharsets.UTF_8).asInt();inthash2=Hashing.sipHash24().hashString(value,StandardCharsets.UTF_8).asInt();for(inti=0;i<HASH_COUNT;i++){// 双哈希模拟 k 个哈希函数offsets[i]=Math.abs((hash1+i*hash2)%BIT_SIZE);}returnoffsets;}}

Redis Modules: RedisBloom

Redis 官方模块 RedisBloom 提供原生布隆过滤器命令：

# 创建（容量100万，误判率1%）BF.RESERVE user-emails0.011000000# 添加BF.ADD user-emails"[e-mail]"BF.MADD user-emails"[e-mail]""[e-mail]"# 查询BF.EXISTS user-emails"[e-mail]"# 1（可能存在）BF.EXISTS user-emails"[e-mail]"# 0（一定不存在）# 查看信息BF.INFO user-emails

Redisson 分布式布隆过滤器

@ResourceprivateRedissonClientredissonClient;// 获取分布式布隆过滤器RBloomFilter<String>bloomFilter=redissonClient.getBloomFilter("user:registered-emails");// 初始化（只需执行一次，重复调用不会覆盖）// 预期 100万个元素，误判率 1%bloomFilter.tryInit(1_000_000,0.01);// 添加bloomFilter.add("[e-mail]");// 查询booleanmayExist=bloomFilter.contains("[e-mail]");// truebooleannotExist=bloomFilter.contains("[e-mail]");// false// 查看当前元素数量（近似值）longcount=bloomFilter.count();// 查看预期误判率doublefpp=bloomFilter.getFalseProbability();// 查看哈希函数个数inthashIterations=bloomFilter.getHashIterations();// 查看位数组大小longsize=bloomFilter.getSize();

八、实战场景详解

场景1：缓存穿透防护

问题：恶意请求大量不存在的 key，绕过缓存直达数据库。

正常请求：请求 key=123 → 缓存命中 → 返回 恶意请求：请求 key=99999999（不存在）→ 缓存未命中 → 查数据库 → 为空 → 不缓存 下一次请求同样的 key → 又查数据库 → 又为空（无限穿透）

解决：布隆过滤器前置过滤

@ServicepublicclassProductQueryService{@ResourceprivateRedissonClientredissonClient;@ResourceprivateRedisTemplate<String,String>redisTemplate;@ResourceprivateProductRepositoryproductRepository;privateRBloomFilter<String>getFilter(){returnredissonClient.getBloomFilter("product:id:bloom");}/** 系统启动时加载所有商品ID到布隆过滤器. */@PostConstructpublicvoidinitBloomFilter(){RBloomFilter<String>filter=getFilter();filter.tryInit(5_000_000,0.001);// 500万商品，0.1%误判率// 全量加载（可分批）List<String>allProductIds=productRepository.findAllIds();allProductIds.forEach(filter::add);log.info("布隆过滤器初始化完成，加载{}个商品ID",allProductIds.size());}/** 查询商品. */publicProductgetProduct(StringproductId){// 第一层：布隆过滤器（拦截一定不存在的请求）if(!getFilter().contains(productId)){returnnull;// 一定不存在，直接返回}// 第二层：Redis 缓存StringcacheKey="product:"+productId;Stringcached=redisTemplate.opsForValue().get(cacheKey);if(cached!=null){return"NULL".equals(cached)?null:JSON.parseObject(cached,Product.class);}// 第三层：数据库Productproduct=productRepository.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;privateRBloomFilter<String>getPhoneFilter(){RBloomFilter<String>filter=redissonClient.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){RBloomFilter<String>filter=redissonClient.getBloomFilter("read:"+userId);filter.tryInit(10_000,0.01);// 每用户预计看1万篇，1%误判returnfilter.contains(articleId);}/** 用户浏览文章后记录. */publicvoidmarkRead(StringuserId,StringarticleId){RBloomFilter<String>filter=redissonClient.getBloomFilter("read:"+userId);filter.tryInit(10_000,0.01);filter.add(articleId);}/** 从候选列表中过滤掉已读内容. */publicList<Article>filterUnread(StringuserId,List<Article>candidates){returncandidates.stream().filter(article->!hasRead(userId,article.getId())).collect(Collectors.toList());// 误判后果：极少数已读文章不会被推荐（可接受）}}

场景4：爬虫 URL 去重

@ServicepublicclassCrawlerUrlDedup{@ResourceprivateRedissonClientredissonClient;privateRBloomFilter<String>getFilter(){RBloomFilter<String>filter=redissonClient.getBloomFilter("crawler:visited-urls");filter.tryInit(100_000_000,0.0001);// 1亿URL，0.01%误判returnfilter;}/** 提交URL进行爬取（自动去重）. */publicbooleansubmitUrl(Stringurl){RBloomFilter<String>filter=getFilter();if(filter.contains(url)){returnfalse;// 大概率已爬过，跳过}filter.add(url);crawlerQueue.offer(url);// 加入爬取队列returntrue;}}

场景5：垃圾邮件过滤

@ServicepublicclassSpamFilter{@ResourceprivateRedissonClientredissonClient;privateRBloomFilter<String>getSpamFilter(){RBloomFilter<String>filter=redissonClient.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变1，banana不受影响

代价：内存占用增加 4 倍（每位 4bit 替代 1bit）。

2. 布谷鸟过滤器（Cuckoo Filter）

• 支持删除
• 空间效率更高（比计数布隆更省内存）
• 查询速度类似

3. 可扩展布隆过滤器（Scalable Bloom Filter）

元素超过预设容量时自动扩展，不需要预先知道精确元素数：

层级1：100万容量（满了） 层级2：200万容量（满了） 层级3：400万容量（当前使用中） 查询时：逐层查询，任一层说"可能存在"就返回 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(cron="0 0 3 * * ?")// 每天凌晨3点publicvoidrebuildBloomFilter(){RBloomFilter<String>filter=redissonClient.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.2MB

4. 不适合的场景

• 需要精确判断（误判不可接受）→ 用 HashSet 或数据库
• 需要获取元素内容 → 用 Set
• 需要删除元素 → 用计数布隆或布谷鸟过滤器
• 元素数量很少（<1万）→ 直接用 Set，布隆过滤器反而浪费

十二、总结

概念	一句话
布隆过滤器	位数组 + 多个哈希函数，空间换准确率的概率数据结构
核心特性	说不在一定不在，说在可能不在（有误判）
本质作用	快速过滤"一定不存在"的请求
适用条件	数据量大 + 能接受小概率误判
分布式版	位数组存在 Redis 中，多实例共享
最常见用途	缓存穿透防护
内存优势	10亿数据仅需 ~1.2GB（HashSet 需 ~40GB）
核心参数	预期容量 n + 期望误判率 p → 自动算出位数组大小和哈希函数数