个人网站开发技术要求,如何建英文网站,尚品中国多年专注于高端网站建设,怎么开网店一件代发【Redis】Redis中的布隆过滤器
前言
在实际开发中#xff0c;会遇到很多要判断一个元素是否在某个集合中的业务场景#xff0c;类似于垃圾邮件的识别#xff0c;恶意IP地址的访问#xff0c;缓存穿透等情况。类似于缓存穿透这种情况#xff0c;有许多的解决方法#xf…【Redis】Redis中的布隆过滤器
前言
在实际开发中会遇到很多要判断一个元素是否在某个集合中的业务场景类似于垃圾邮件的识别恶意IP地址的访问缓存穿透等情况。类似于缓存穿透这种情况有许多的解决方法如Redis存储Null值等而对于垃圾邮件的识别恶意IP地址的访问我们也可以直接用 HashMap 去存储恶意IP地址以及垃圾邮件然后每次访问时去检索一下对应集合中是否有相同数据。这种思路对于数据量小的项目来说是没有问题的但是对于大数据量的项目如垃圾邮件出现有几十万恶意IP地址出现有上百万那么这些大量的数据就会占据大量的空间这个时候就可以考虑一下布隆过滤器了。
布隆过滤器是什么
布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。 可以把布隆过滤器理解为一个不怎么精确的 set 结构当你使用它的 contains方法判断某个对象是否存在时它可能会误判。但是布隆过滤器也不是特别不精确只要参数设置得合理它的精确度也可以控制得相对足够精确只会有小小的误判概率。
当布隆过滤器说某个值存在时这个值可能不存在当它说某个值不存在时那就肯定不存在。打个比方当它说不认识你时肯定就是真的不认识而当它说认识你时却有可能根本没见过你只是因为你的脸跟它认识的某人的脸比较相似(某些熟脸的系数组合)所以误判以前认识你。
一句话总结由一个初始值为零的bit数组和多个哈希函数构成用来快速判断集合中是否存在某个元素。 使用bit数组的目的就是减少内存的占用数组不保存数据信息只是在内存中存储一个是否存在的表示0或1 布隆过滤器的优缺点
优点
高效插入和查询内存占用空间少
缺点
存在误判不能精确过滤不能删除元素
布隆过滤器的使用场景
黑白名单校验、识别垃圾邮件
发现存在黑名单中的就执行特定操作。比如识别垃圾邮件只要是邮箱在黑名单中的邮件就识别为垃圾邮件。假设黑名单的数量是数以亿计的存放起来就是非常耗费存储空间的布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中在收到邮件时判断邮件地址是否在布隆过滤器中即可。
解决缓存穿透的问题
把已存在数据的key存在布隆过滤器中相当于Redis前面挡着一个布隆过滤器。当有新的请求时先到布隆过滤器中查询是否存在如果布隆过滤器中不存在该条数据则直接返回如果布隆过滤器中已存在才去查询缓存Redis如果Redis里没查询到则再查询MySQL数据库
布隆过滤器的原理
每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不-样的无偏 hash函数如下图中的F、G、H就是这样的hash函数。所谓无偏就是能够把元素的 hash 值算得比较均匀让元素被 hash映射到位数组中的位置比较随机。 向布隆过滤器中添加 key 时会使用多个 hash 函数对 key 进行 hash算得一个整数索引值然后对位数组长度进行取模运算得到一个位置每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1就完成了 add 操作。
向布隆过滤器询问 key 是否存在时跟add 一样也会把 hash 的几个位置都算出来**看看位数组中这几个位置是否都为 1只要有一个位为 0那么说明布隆过滤器中这个 key 不存在。如果这几个位置都是 1并不能说明这个 key 就一定存在只是极有可能存在因为这些位被置为 1 可能是因为其他的 key 存在所致。**如果这个位数组比较稀疏判断正确的概率就会很大如果这个位数组比较拥挤判断正确的概率就会降低。具体的概率计算公式比较复杂感兴趣可以阅读相关的更深入研究的资料不过非常烧脑不建议读者细看。
参考博客Redis系列–布隆过滤器Bloom Filter_redistemplate 布隆过滤器_幼儿园里的山大王的博客-CSDN博客
基于Redisson的布隆过滤器使用实例
1.引入Redisson依赖
!--原生--
dependencygroupIdorg.redisson/groupIdartifactIdredisson/artifactIdversion3.13.4/version
/dependency!--或者另一种Spring集成starter--
dependencygroupIdorg.redisson/groupIdartifactIdredisson-spring-boot-starter/artifactIdversion3.13.6/version
/dependency2.配置Redisson
Configuration
public class RedissionConfig {Value(${spring.redis.host})private String redisHost;Value(${spring.redis.password})private String password;private int port 6379;Beanpublic RedissonClient getRedisson() {Config config new Config();config.useSingleServer().setAddress(redis:// redisHost : port).setPassword(password);config.setCodec(new JsonJacksonCodec());return Redisson.create(config);}
}3.配置布隆过滤器
Configuration
public class BloomFilterConfig {Autowiredprivate RedissonClient redissonClient;/*** 创建订单号布隆过滤器* return*/Beanpublic RBloomFilterLong orderBloomFilter() {//过滤器名称String filterName orderBloomFilter;// 预期插入数量long expectedInsertions 10000L;// 错误比率double falseProbability 0.01;RBloomFilterLong bloomFilter redissonClient.getBloomFilter(filterName);bloomFilter.tryInit(expectedInsertions, falseProbability);return bloomFilter;}
}4.创建订单表
CREATE TABLE tb_order (id bigint NOT NULL AUTO_INCREMENT COMMENT 订单Id,order_desc varchar(50) NOT NULL COMMENT 订单描述,user_id bigint NOT NULL COMMENT 用户Id,product_id bigint NOT NULL COMMENT 商品Id,product_num int NOT NULL COMMENT 商品数量,total_account decimal(10,2) NOT NULL COMMENT 订单金额,create_time datetime NOT NULL COMMENT 创建时间,PRIMARY KEY (id),KEY ik_user_id (user_id)
) ENGINEInnoDB AUTO_INCREMENT51 DEFAULT CHARSETutf8mb4 COLLATEutf8mb4_0900_ai_ci;5.编写业务处理代码
Slf4j
Service
public class OrderServiceImpl implements OrderService {Resourceprivate RBloomFilterLong orderBloomFilter;Resourceprivate TbOrderMapper tbOrderMapper;Resourceprivate RedisTemplateString,Object redisTemplate;Overridepublic void createOrder(TbOrder tbOrder) {//1、创建订单tbOrderMapper.insert(tbOrder);//2、订单id保存到布隆过滤器log.info(布隆过滤器中添加订单号{},tbOrder.getId());orderBloomFilter.add(tbOrder.getId());}Overridepublic TbOrder get(Long orderId) {TbOrder tbOrder null;//1、根据布隆过滤器判断订单号是否存在if(orderBloomFilter.contains(orderId)){log.info(布隆过滤器判断订单号{}存在,orderId);String key order:orderId;//2、先查询缓存Object object redisTemplate.opsForValue().get(key);if(object ! null){log.info(命中缓存);tbOrder (TbOrder)object;}else{//3、缓存不存在则查询数据库log.info(未命中缓存查询数据库);tbOrder tbOrderMapper.selectById(orderId);redisTemplate.opsForValue().set(key,tbOrder);}}else{log.info(判定订单号{}不存在,不进行查询,orderId);}return tbOrder;}
}6.单元测试
Test
public void testCreateOrder() {for (int i 0; i 50; i) {TbOrder tbOrder new TbOrder();tbOrder.setOrderDesc(测试订单(i1));tbOrder.setUserId(1958L);tbOrder.setProductId(102589L);tbOrder.setProductNum(5);tbOrder.setTotalAccount(new BigDecimal(300));tbOrder.setCreateTime(new Date());orderService.createOrder(tbOrder);}}
Test
public void testGetOrder() {TbOrder tbOrder orderService.get(25L);log.info(查询结果{}, tbOrder.toString());
}总结
布隆过滤器的原理其实非常简单就是bitmap 多重hash主要优势就是利用非常小的空间就可以实现在大规模数据下快速判断某一对象是否存在缺点是存在误判的可能但不会漏判也就是存在的对象一定会判断为存在而不存在的对象会有较低的概率为误判为存在且不支持对象的删除因为会增加误判的概率。最典型的使用是解决缓存穿透的问题。
