网站是怎么搭建的,怎么查看小程序的开发公司,wordpress 目录关键词,中国航发网上采购平台一、场景
缓存穿透问题
一般情况下#xff0c;先查询Redis缓存#xff0c;如果Redis中没有#xff0c;再查询MySQL。当某一时刻访问redis的大量key都在redis中不存在时#xff0c;所有查询都要访问数据库#xff0c;造成数据库压力顿时上升#xff0c;这就是缓存穿透。…一、场景
缓存穿透问题
一般情况下先查询Redis缓存如果Redis中没有再查询MySQL。当某一时刻访问redis的大量key都在redis中不存在时所有查询都要访问数据库造成数据库压力顿时上升这就是缓存穿透。八股文背多了都知道在Redis前面添加一层布隆过滤器请求先在布隆过滤器中判断如果布隆过滤器不存在时直接返回不再访问Redis和MySQL。如果布隆过滤器中存在时再访问Redis再访问数据库。完美解决缓存穿透问题。说白了布隆过滤器就是redis的缓存 除此之外还有以下场景 黑名单 如果黑名单非常大上千万了存放起来很耗费空间在布隆过滤器中实现黑名单功能是一个很好的选择。网页爬虫对URL的去重避免爬取相同的URL地址 二、布隆过滤器
布隆过滤器BloomFilter是什么
布隆过滤器BloomFilter是一种专门用来解决去重问题的高级数据结果。实质就是一个大型位数组和几个不同的无偏hash函数无偏表示分布均匀。由一个初值为零的bit数组和多个哈希函数组成用来判断某个数据是否存在它和HyperLogLog一样不是那么的精准存在一定的误判概率。
布隆过滤器BloomFilter能干嘛 高效地插入和查询占用空间少返回的结果是不确定的一个元素如果判断结果为存在它不一定存在不存在时一定不存在。 查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了。如果这些点 有任何一个为零则被查询变量一定不在 如果都是 1则被查询变量很 可能存在。 为什么说是可能存在而不是一定存在呢 那是因为映射函数本身就是散列函数散列函数是会有碰撞的。 布隆过滤器BloomFilter只能添加元素不能删除元素。这和上面提到的hashcode判定原理是一样的相同hashcode的字符串会存储在一个index删除时是将某个index移除此时就可能移除拥有相同hashcode的不同字符串
三、实现原理和数据结构
初始化
布隆过滤器 本质上 是由长度为 m 的位向量或位列表仅包含 0 或 1 位值的列表组成最初所有的值均设置为 添加
当我们向布隆过滤器中添加数据时为了尽量地址不冲突 会使用多个 hash 函数对 key 进行运算 算得一个下标索引值然后对位数组长度进行取模运算得到一个位置每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。 例如我们添加一个字符串wmyskxz: 判断是否存在
向布隆过滤器查询某个key是否存在时先把这个 key 通过相同的多个 hash 函数进行运算 查看对应的位置是否都为 1 只要有一个位为 0那么说明布隆过滤器中这个 key 不存在 如果这几个位置全都是 1那么说明极有可能存在 因为这些位置的 1 可能是因为其他的 key 存在导致的也就是前面说过的hash冲突。
例子我们在 add 了字符串wmyskxz数据之后很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的 此时我们查询一个没添加过的不存在的字符串inexistent-key它有可能计算后坑位也是1/3/5 这就是误判了。
误判率为什么不能删除元素
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了这样就无法判断究竟是哪个输入产生的 因此误判的根源在于相同的 bit 位被多次映射且置 1。 这种情况也造成了布隆过滤器的删除问题因为布隆过滤器的每一个 bit 并不是独占的很有可能多个元素 共享了某一位 。 如果我们直接删除这一位的话会影响其他的元素。
如何解决不能删除
布谷鸟过滤器
为了解决布隆过滤器不能删除元素的问题 布谷鸟过滤器横空出世。论文《Cuckoo FilterBetter Than Bloom》 作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足 查询性能弱、空间利用效率低、不支持反向操作删除以及不支持计数
常用命令
在Redis中布隆过滤器有两个基本命令分别是 bf.add添加元素到布隆过滤器中类似于集合的sadd命令不过bf.add命令只能一次添加一个元素如果想一次添加多个元素可以使用bf.madd命令。bf.exists判断某个元素是否在过滤器中类似于集合的sismember命令不过bf.exists命令只能一次查询一个元素如果想一次查询多个元素可以使用bf.mexists命令。 四、Redis使用布隆过滤器
redis版本推荐版本6.x最低4.x版本下载布隆过滤器插件版本自选
wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz解压编译得到.so tar -zxvf v2.2.6.tar.gzcd RedisBloom-2.2.6/make Redis配置文件修改
在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址
loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址
添加完成后需要重启redis集成布隆过滤器的redis项目Rebloom插件布隆过滤器有原生镜像可以直接使用
五、代码层面调用java
基于redisson实现
package com.ruoyi.demo;import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RBucket;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.StringCodec;
import org.redisson.config.Config;import java.util.concurrent.TimeUnit;public class RedissonBloomFilterDemo {public static final int _1W 10000;//布隆过滤器里预计要插入多少数据public static int size 100 * _1W;//误判率,它越小误判的个数也就越少public static double fpp 0.03;static RedissonClient redissonClient null;//jedisstatic RBloomFilter rBloomFilter null;//redis版内置的布隆过滤器static {Config config new Config();config.useSingleServer().setAddress(redis://192.168.1.8:6379).setPassword(cxm199610133914).setDatabase(2);//构造redissonredissonClient Redisson.create(config);//通过redisson构造rBloomFilterrBloomFilter redissonClient.getBloomFilter(phoneListBloomFilter,new StringCodec());rBloomFilter.tryInit(size,fpp);// 1测试 布隆过滤器有redis有rBloomFilter.add(10086);redissonClient.getBucket(10086,new StringCodec()).set(chinamobile10086);// 2测试 布隆过滤器有redis无rBloomFilter.add(10087);//3 测试 布隆过滤器无redis无}private static String getPhoneListById(String IDNumber) {String result null;if (IDNumber null) {return null;}//1 先去布隆过滤器里面查询if (rBloomFilter.contains(IDNumber)) {//2 布隆过滤器里有再去redis里面查询RBucketString rBucket redissonClient.getBucket(IDNumber, new StringCodec());result rBucket.get();if(result ! null) {return i come from redis: result;}else{result getPhoneListByMySQL(IDNumber);if (result null) {return null;}// 重新将数据更新回redisredissonClient.getBucket(IDNumber, new StringCodec()).set(result);}return i come from mysql: result;}return result;}private static String getPhoneListByMySQL(String IDNumber) {return chinamobileIDNumber;}public static void main(String[] args) {//String phoneListById getPhoneListById(10086);//String phoneListById getPhoneListById(10087); //请测试执行2次String phoneListById getPhoneListById(10088);System.out.println(------查询出来的结果 phoneListById);//暂停几秒钟线程try {TimeUnit.SECONDS.sleep(1);}catch (InterruptedException e) {e.printStackTrace();}redissonClient.shutdown();}
}
参考文章 参考文章
