鑫牛元网站建设,什么是小手机型网站,做网站收费标准点击量,网站推广怎样做目录 前言
布隆过滤器
什么是布隆过滤器
布隆过滤器的作用
布隆过滤器原理
怎么设计布隆过滤器
布隆过滤器使用案例
安装布隆过滤器
添加依赖
添加配置
添加工具类
添加测试代码
简单测试
特别提醒
结语 前言
前面三篇#xff0c;已经把消息队列…目录 前言
布隆过滤器
什么是布隆过滤器
布隆过滤器的作用
布隆过滤器原理
怎么设计布隆过滤器
布隆过滤器使用案例
安装布隆过滤器
添加依赖
添加配置
添加工具类
添加测试代码
简单测试
特别提醒
结语 前言
前面三篇已经把消息队列和其所包含的Kafka和RabbitMQ做了说明并用案例演示了如何使用今天这一篇我们要讲解的内容是布隆过滤器布隆过滤器不同于过滤器Filter想知道布隆过滤器是什么和怎样使用布隆过滤器吗今天这篇博客将带你了解这些学完这篇你将能独立使用布隆过滤器了解其工作原理。下面就让我们一起来学习吧。
布隆过滤器
说起过滤器我们总是想起两种一种是Filter过滤器一种是布隆过滤器。Filter过滤器用于在全局捕捉请求并在请求前后做一些事情比如统一编码URL级别的权限访问控制过滤敏感词汇压缩请求信息等。那么布隆过滤器是做什么的呢这里先卖个关子我们继续往下看。
什么是布隆过滤器
布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多缺点是有一定的误识别率和删除困难。
布隆过滤器不保存元素之判断是否存在不保存所以也无法取出元素。
布隆过滤器的作用
布隆过滤器主要应用于网页URL的去重垃圾邮件的判别集合重复元素的判别查询加速比如基于key-value的存储系统、数据库防止查询击穿 使用BloomFilter来减少不存在的行或列的磁盘查找。
在Java开发 - Redis初体验一文中我们曾提到过布隆过滤器在缓存击穿的预防上面它是很好的效果的。刚好学完此篇你就可以在Redis项目中尝试添加布隆过滤器来防止缓存击穿因为在当时写那篇博客时我们采用的方法是给null值在文中也提到这是不合适的因为当时还没有讲解布隆过滤器学完此篇大家可以去做个尝试。
布隆过滤器原理
常规检查元素是否存在我们会怎么做一般是遍历集合判断元素是否相等但这种查询的方式在数据量庞大的情况下效率太低想要实现快速的查找前面学过的Java开发 - 树二叉树二叉排序树红黑树中曾经讲解过的数据结构或许会有一些帮助其Hash散列或类似算法可以保证高效判断元素是否存在但也存在消耗内存较多的问题布隆过滤器的存在正好解决了这个问题。
当要向布隆过滤器中添加一个元素时该元素会经过N个哈希函数的计算并最终产生k个哈希值布隆过滤器是个位数组假设每一位是0这些值就会根据计算出来的下标放入这个数组中为1。在查询时会判断这几个哈希值所在的位置只要有一个为0就不存在于布隆过滤器中。
下面我们通过几张图来说明布隆过滤器查询的原理
假设这是一个空的布隆过滤器 现在添加了coding单词在布隆过滤器中的状态
coding算法1加密1
coding算法2加密3
coding算法3加密5 现在添加了fire单词在布隆过滤器中的状态
fire算法1加密2
fire算法2加密4
fire算法3加密6 现在添加了codingfire单词在布隆过滤器中的状态
codingfire算法1加密1
codingfire算法2加密4
codingfire算法3加密6 问题来了我还没添加呢146的位置已经有东西了这时候布隆过滤器就会误判认为codingfire已存在于布隆过滤器中。
布隆过滤器误判特点:
布隆过滤器判断不存在的元素一定不在集合中布隆过滤器判断存在的元素有可能不存在集合中
这是因为我们做测试时布隆过滤器太短了假设就10格会导致每个位置值都是1我们就不用存东西了误判会很严重啥都存在那这就是个失败的布隆过滤器。所以合适的大小对布隆过滤器非常重要。
怎么设计布隆过滤器
布隆过滤器在启动时需要分配合适的内存大小这直接决定了它是否准确。设置的大小要满足这几个条件
可接受范围的大小既节省内存又不会有很高的误判率
关于这两个条件有一个公式用于计算误判率 这是根据误判率计算布隆过滤器长度的公式
n 是已经添加元素的数量
k 哈希的次数
m 布隆过滤器的长度(位数的大小)
最终结果结果就是误判率。
反着来也是可以的知道误判率反推布隆过滤器长度 推荐一个在线计算布隆过滤器大小的网站可以正推也可以反推Bloom filter calculator
布隆过滤器使用案例
安装布隆过滤器
布隆过滤器安装推荐这篇博客Redis 布隆过滤器命令的使用详解
不过它里面提到的布隆过滤器我个人不推荐因为官方也推出了一个结合了Redis和布隆过滤器的软件工具redis/redis-stack
网址在Docker
安装方法和推荐博客里是一样的由于比较简单博主就不带大家一步步安装了安装完请回到这里我们继续。
安装完记得启动 由于我们是教程所以密码不设置端口采用默认实际可是要改的。 我们在上一篇RabbitMQ所在的子工程stock中继续集成做一个简单的测试。
添加依赖 dependencygroupIdorg.springframework.boot/groupIdartifactIdspring-boot-starter-data-redis/artifactId
/dependency 添加配置 spring:redis:host: localhostport: 6379password: 添加工具类
在stock包下建utils包包下新建一个类代码如下
package com.codingfire.cloud.stock.utils;import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.data.redis.core.script.RedisScript;
import org.springframework.stereotype.Component;import java.util.Arrays;
import java.util.List;Component
public class RedisBloomUtils {Autowiredprivate StringRedisTemplate redisTemplate;private static RedisScriptBoolean bfreserveScript new DefaultRedisScript(return redis.call(bf.reserve, KEYS[1], ARGV[1], ARGV[2]), Boolean.class);private static RedisScriptBoolean bfaddScript new DefaultRedisScript(return redis.call(bf.add, KEYS[1], ARGV[1]), Boolean.class);private static RedisScriptBoolean bfexistsScript new DefaultRedisScript(return redis.call(bf.exists, KEYS[1], ARGV[1]), Boolean.class);private static String bfmaddScript return redis.call(bf.madd, KEYS[1], %s);private static String bfmexistsScript return redis.call(bf.mexists, KEYS[1], %s);public Boolean hasBloomFilter(String key){return redisTemplate.hasKey(key);}/*** 设置错误率和大小需要在添加元素前调用若已存在元素则会报错* 错误率越低需要的空间越大* param key* param errorRate 错误率默认0.01* param initialSize 默认100预计放入的元素数量当实际数量超出这个数值时误判率会上升尽量估计一个准确数值再加上一定的冗余空间* return*/public Boolean bfreserve(String key, double errorRate, int initialSize){return redisTemplate.execute(bfreserveScript, Arrays.asList(key), String.valueOf(errorRate), String.valueOf(initialSize));}/*** 添加元素* param key* param value* return true表示添加成功false表示添加失败存在时会返回false*/public Boolean bfadd(String key, String value){return redisTemplate.execute(bfaddScript, Arrays.asList(key), value);}/*** 查看元素是否存在判断为存在时有可能是误判不存在是一定不存在* param key* param value* return true表示存在false表示不存在*/public Boolean bfexists(String key, String value){return redisTemplate.execute(bfexistsScript, Arrays.asList(key), value);}/*** 批量添加元素* param key* param values* return 按序 1表示添加成功0表示添加失败*/public ListInteger bfmadd(String key, String... values){return (ListInteger)redisTemplate.execute(this.generateScript(bfmaddScript, values), Arrays.asList(key), values);}/*** 批量检查元素是否存在判断为存在时有可能是误判不存在是一定不存在* param key* param values* return 按序 1表示存在0表示不存在*/public ListInteger bfmexists(String key, String... values){return (ListInteger)redisTemplate.execute(this.generateScript(bfmexistsScript, values), Arrays.asList(key), values);}private RedisScriptList generateScript(String script, String[] values) {StringBuilder sb new StringBuilder();for(int i 1; i values.length; i ){if(i ! 1){sb.append(,);}sb.append(ARGV[).append(i).append(]);}return new DefaultRedisScript(String.format(script, sb.toString()), List.class);}}代码都是模版使用时直接添加此类即可。
添加测试代码
我们quartz包下有个QuartzJob类我们曾在里面测试Quartz功能和RabbitMQ现在我们来添加布隆过滤器的测试代码
package com.codingfire.cloud.stock.quartz;import com.codingfire.cloud.stock.utils.RedisBloomUtils;
import org.quartz.Job;
import org.quartz.JobExecutionContext;
import org.quartz.JobExecutionException;
import org.springframework.amqp.rabbit.core.RabbitTemplate;
import org.springframework.beans.factory.annotation.Autowired;import java.time.LocalDateTime;public class QuartzJob implements Job {// RabbitTemplate就是amqp框架提供的发送消息的对象Autowiredprivate RabbitTemplate rabbitTemplate;Autowiredprivate RedisBloomUtils redisBloomUtils;Overridepublic void execute(JobExecutionContext jobExecutionContext) throws JobExecutionException {//输出当前时间System.out.println(-------------- LocalDateTime.now() ---------------);// 先简单的发送一串文字
// rabbitTemplate.convertAndSend(RabbitMQConfig.STOCK_EX,RabbitMQConfig.STOCK_ROUT,黄河之水天上来奔流到海不复还。);// 首先确定要向布隆过滤器中保存的元素String[] numbers{zero,one,two,three,four,five,six,seven,eight,nine,ten};// 使用RedisBloomUtils类将上面的数组元素保存在Redis(布隆过滤器)中redisBloomUtils.bfmadd(numberBloom,numbers);// 下面就可以判断一个元素是否在这个布隆过滤器中了String elmsix;System.out.println(布隆过滤器判断elm是否存在: redisBloomUtils.bfexists(numberBloom,elm));}
}大阿甲不用纠结代码为什么写在这个类里随便你写在哪里写在测试类中也行只要你项目能运行我们写的测试方法随便你写在哪。
简单测试
下面我们来简单测试下布隆过滤器的使用看情况启动服务如果十一路学习过来和博主用的是相同工程的同学请启动nacosseatamysql还有最重要的redisbloom可能还要启动RabbitMQ否则会报错启动后运行项目查看控制台输出 能输出图中内容的就是测试成功了。
特别提醒 设置错误率和大小在使用前记得调用不设置默认0.01自己看哈。
QuartzJob中布隆过滤器虽然进行了测试但我们要知道QuartzJob的工作驱动还有一个类叫QuartzConfig这里面的代码相当于是注册触发条件。我这么说大家懂吗不懂得可以去看看驱动QuartzJob运行的触发器的设置Java开发 - Quartz初体验。
结语
简单来说布隆过滤器就是用来判断某个元素是否存在于某一个集中的东西而且其判断效率非常高是一个在大数据情况下常用的工具但它本身代码量并不大但要注意布隆过滤器存在误判率所以使用起来在设置重要参数时还是要注意些的。今天的布隆过滤器介绍到此结束 不知道大家对最近的博客还满意吗欢迎留言沟通交流。
