wordpress个人博客网站,游戏开发软件工具,手机网站范例,做网站图结构文章目录 1. 布隆过滤器的应用场景2. 在SpringBoot项目利用Redission实现布隆过滤器3. 布隆过滤器误判的情况4. 与位图相关的操作5. 可能遇到的问题#xff08;Redission是如何记录布隆过滤器的配置参数的#xff09;5.1 问题产生的原因5.2 解决方案5.2.1 方案一#xff1a;… 文章目录 1. 布隆过滤器的应用场景2. 在SpringBoot项目利用Redission实现布隆过滤器3. 布隆过滤器误判的情况4. 与位图相关的操作5. 可能遇到的问题Redission是如何记录布隆过滤器的配置参数的5.1 问题产生的原因5.2 解决方案5.2.1 方案一删除Redis中与布隆过滤器相关的key5.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; // 容错率也就是误报率// 创建布隆过滤器参数分别为过滤器名称预期元素数量误差率RBloomFilterObject 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; // 容错率也就是误报率// 创建布隆过滤器参数分别为过滤器名称预期元素数量误差率RBloomFilterObject 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.CompletableFuture52a215fa[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, …] 5.1 问题产生的原因
之所以会报错是因为布隆过滤器的配置参数被篡改了 那布隆过滤器的配置参数存放在哪里呢当然是存在 Redis 里面Redis 中会有一个与布隆过滤器配置参数相关的 key这个 key 使用的是 Hash 结构 各个参数的含义
size布隆过滤器位图的大小hashIterations布隆过滤器在处理每个元素时要应用的哈希函数的数量falseProbability布隆过滤器的误报率即错误地判断一个元素存在于集合中的概率expectedInsertions预期将要插入布隆过滤器的元素数量
5.2 解决方案
5.2.1 方案一删除Redis中与布隆过滤器相关的key
直接删除 Redis 中与布隆过滤器相关的 key下次再操作布隆过滤器时会重新创建布隆过滤器 5.2.2 方案二创建一个新的布隆过滤器
直接更改布隆过滤器的名字创建一个新的布隆过滤器
