在SpringBoot项目中利用Redission实现布隆过滤器（布隆过滤器的应用场景、布隆过滤器误判的情况、与位图相关的操作）

文章目录

1. 布隆过滤器的应用场景
2. 在SpringBoot项目利用Redission实现布隆过滤器
3. 布隆过滤器误判的情况
4. 与位图相关的操作
5. 可能遇到的问题（Redission是如何记录布隆过滤器的配置参数的）
- 5.1 问题产生的原因
- 5.2 解决方案
- - 5.2.1 方案一：删除Redis中与布隆过滤器相关的key
  - 5.2.2 方案二：创建一个新的布隆过滤器

对 Redission 不了解的同学，可以参考我的另一篇博文：在SpringBoot项目中使用Redission实现分布式锁（什么是Redission、为什么要使用分布式锁、分布式锁的应用场景、Redission的读锁和写锁、可重入锁的原理

至于什么是布隆过滤器，可以参考我的另一篇博文：Redis缓存面试三兄弟：缓存穿透、缓存雪崩、缓存击穿的 1.3.3 方案三：使用布隆过滤器 部分

1. 布隆过滤器的应用场景

布隆过滤器（Bloom Filter）是一种空间效率极高的概率数据结构，用于测试一个元素是否属于集合

布隆过滤器可能会产生误报（一个元素不属于集合，但布隆过滤器判断元素属于该集合），但绝不会漏报（一个元素属于集合，但布隆过滤器判断元素不属于该集合）

布隆过滤器适用于以下一些应用场景：

网络爬虫：避免爬取已经访问过的URL，减少重复工作
防止缓存穿透：在缓存系统中，使用布隆过滤器检查请求的数据是否可能存在，以避免对不存在的数据进行数据库查询
数据库索引：用于快速判断一个记录是否存在于数据库中，减少不必要的磁盘I/O操作
邮件系统：过滤垃圾邮件，通过布隆过滤器快速判断一个邮件地址是否在垃圾邮件发送者列表中
网络安全：用于检测和防御DDoS攻击，通过布隆过滤器识别和过滤恶意流量
分布式系统：在分布式环境中，布隆过滤器可以用来检查数据是否已经被处理，以避免重复处理
文件系统：在文件检索系统中，快速判断一个文件是否存在于文件系统中，减少文件系统的访问次数
大数据集去重：在处理大规模数据集时，使用布隆过滤器进行高效去重
网络服务：检查客户端请求的内容是否已经被服务器处理过，从而避免重复处理

布隆过滤器的优点在于它的空间效率和查询速度，布隆过滤器在处理大量数据时非常有用

2. 在SpringBoot项目利用Redission实现布隆过滤器

如果不知道如何在 SpringBoot 项目项目中接入 Redission，可以参考我的另一篇博文：在SpringBoot项目中使用Redission实现分布式锁（什么是Redission、为什么要使用分布式锁、分布式锁的应用场景、Redission的读锁和写锁、可重入锁的原理）

编写一个测试类，测试布隆过滤器的过滤效果

import org.junit.jupiter.api.Test;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;@SpringBootTest
public class BloomFilterTests {@Autowiredprivate RedissonClient redissionClient;@Testpublic void testBooleanFilter() {try {String filterName = "myBloomFilter";long expectedInsertions = 100000L; // 预期元素数量double falseProbability = 0.01; // 容错率，也就是误报率// 创建布隆过滤器，参数分别为：过滤器名称，预期元素数量，误差率RBloomFilter<Object> bloomFilter = redissionClient.getBloomFilter(filterName);bloomFilter.tryInit(expectedInsertions, falseProbability);// 添加元素for (int i = 1; i <= 50; i++) {bloomFilter.add(String.format("element%02d", i));}// 检查元素是否存在System.out.println("bloomFilter.contains(\"element01\") = " + bloomFilter.contains("element01"));System.out.println("bloomFilter.contains(\"element51\") = " + bloomFilter.contains("element51"));} finally {// 关闭 Redission 客户端redissionClient.shutdown();}}}

输出结果如下

在这里插入图片描述

3. 布隆过滤器误判的情况

我们将预期元素数量改为 5 个，再次对布隆过滤器进行测试

import org.junit.jupiter.api.Test;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;@SpringBootTest
public class BloomFilterTests {@Autowiredprivate RedissonClient redissionClient;@Testpublic void testBooleanFilter() {try {String filterName = "myBloomFilter";long expectedInsertions = 5L; // 预期元素数量double falseProbability = 0.01; // 容错率，也就是误报率// 创建布隆过滤器，参数分别为：过滤器名称，预期元素数量，误差率RBloomFilter<Object> bloomFilter = redissionClient.getBloomFilter(filterName);bloomFilter.tryInit(expectedInsertions, falseProbability);// 添加元素for (int i = 1; i <= 50; i++) {bloomFilter.add(String.format("element%02d", i));}// 检查元素是否存在System.out.println("bloomFilter.contains(\"element01\") = " + bloomFilter.contains("element01"));System.out.println("bloomFilter.contains(\"element51\") = " + bloomFilter.contains("element51"));} finally {// 关闭 Redission 客户端redissionClient.shutdown();}}}

运行结果如下

在这里插入图片描述

可以看到，布隆过滤器出现了误判的情况（element51 不在集合中，但布隆过滤器判断 element51 在集合中）

我们查看布隆过滤器的配置（布隆过滤器中各个参数的含义可参考本文的布隆过滤器中各个参数的含义章节）

在这里插入图片描述

可以发现，布隆过滤器底层的位图的大小为 47，布隆过滤器在处理每个元素时要应用的哈希函数的数量为 7，也就是说，每个元素会映射到位图的 7 个位置上

我们往布隆过滤器中插入了 50 个元素，每个元素映射到位图的 7 个位置上，非常容易发生哈希冲突的情况，从而导致布隆过滤器误判

我们删除布隆过滤器后，重写运行测试代码，查看位图中 1 的数量

在这里插入图片描述

redissionClient.getBitSet(filterName).cardinality()

在这里插入图片描述

可以发现，位图的大小为 47，位图中 1 的数量也是 47，也就是说，位图中所有位置都是 1，也就意味着此时布隆过滤器已经完全失去了过滤作用

所以说，在初始化布隆过滤器时，我们需要十分注意 预期元素数量 和 误判率 参数，否则布隆过滤器的过滤效果将会大打折扣，甚至失效

4. 与位图相关的操作

Redission 提供的 RBloomFilter 类用于布隆过滤，而 RBitSet类用于常规的位图操作

使用 RBitSet 类可以对各种位图进行各种操作，如设置位、清除位、检查位的状态等

在这里插入图片描述

@Test
public void testBitmap() {try {String filterName = "myBloomFilter";RBitSet bitSet = redissionClient.getBitSet(filterName);bitSet.set(0, true); // 设置第0位为1bitSet.set(1, false); // 设置第1位为0bitSet.clear(0); // 清除第0位boolean isSet = bitSet.get(0); // 检查第0位是否为1System.out.println("isSet = " + isSet);long count = bitSet.cardinality(); // 返回位图中1的数量System.out.println("count = " + count);} finally {// 关闭 Redission 客户端redissionClient.shutdown();}
}

5. 可能遇到的问题（Redission是如何记录布隆过滤器的配置参数的）

在这里插入图片描述

org.redisson.client.RedisException: ERR Error running script (call to f_a7ac8cff901d5cafb8de37987dfbe1fc11f00eb4): @user_script:1: user_script:1: Bloom filter config has been changed . channel: [id: 0xe1fd1f6a, L:/127.0.0.1:3098 - R:127.0.0.1/127.0.0.1:6379] command: (EVAL), promise: java.util.concurrent.CompletableFuture@52a215fa[Not completed, 1 dependents], params: [local size = redis.call(‘hget’, KEYS[1], ‘size’);local hashIterations = redis.call(‘hget’, KEYS[1], ‘hashIterations’);assert(size == ARGV[1] and hashIterations == ARGV[2], ‘Bloom filter config has been changed’)local k = 0;local c = 0;for i = 4, #ARGV, 1 do local r = redis.call(‘setbit’, KEYS[2], ARGV[i], 1); if r == 0 then k = k + 1;end; if ((i - 4) + 1) % ARGV[3] == 0 then if k > 0 then c = c + 1;end; k = 0; end; end; return c;, 2, {myBloomFilter}:config, myBloomFilter, 47, 7, 7, 6, 14, 20, …]