请选择 进入手机版 | 继续访问电脑版

[Redis] Redis利用 元素删除的布隆过滤器来办理 缓存穿透题目

[复制链接]
查看34 | 回复8 | 2021-9-13 23:41:07 | 显示全部楼层 |阅读模式
目次

前言

在我们一样平常 开发 中,Redis利用 场景最多的就是作为缓存和分布式锁等功能来利用 ,而其用作缓存最大的目的 就是为了降低数据库访问。但是假如我们某些数据并不存在于Redis当中,那么哀求 还是会直接到达数据库,而一旦在同一时间大量缓存失效或者一个不存在缓存的哀求 被恶意访问,这些都会导致数据库压力骤增,这就是本文要讲述的缓存穿透,缓存击穿和缓存雪崩的标题 ,而布隆过滤器正是缓存穿透的一种办理 方案

缓存雪崩

缓存雪崩指的是Redis当中的大量缓存在同一时间全部失效,而假如碰巧 这一段时间同时又有大量哀求 被发起,那么就会造成哀求 直接访问到数据库,大概 会把数据库冲垮。

缓存雪崩一样平常 形容的是缓存中没有而数据库中有的数据,而由于 时间到期导致哀求 直达数据库。

办理 方案

办理 缓存雪崩的方法有很多:

1、加锁,保证单线程访问缓存。如许 就不会有很多哀求 同时访问到数据库。

2、失效时间不要设置成一样。典型的就是初始化预热数据的时间 ,将数据存入缓存时可以采用随机时间来确保不会咋同一时间有大量缓存失效。

3、内存答应 的环境 下,可以将缓存设置为永不失效。

缓存击穿

缓存击穿和缓存雪崩很类似 ,区别就是缓存击穿一样平常 指的是单个缓存失效,而同一时间又有很大的并发哀求 必要 访问这个key,从而造成了数据库的压力。

办理 方案

办理 缓存击穿的方法和办理 缓存雪崩的方法很类似 :

1、加锁,保证单线程访问缓存。如许 第一个哀求 到达数据库后就会重新写入缓存,后续的哀求 就可以直接读取缓存。2、内存答应 的环境 下,可以将缓存设置为永不失效。

 缓存穿透

缓存穿透和上面两种征象 的本质区别就是这时间 访问的数据其在数据库中也不存在,那么既然数据库不存在,以是 缓存内里 肯定也不会存在,如许 假如 并发过大就会造成数据源源不断的到达数据库,给数据库造成极大压力。

办理 方案

对于缓存穿透标题 ,加锁并不能起到很好地结果 ,由于 本身key就是不存在,以是 即使控制了线程的访问数,但是哀求 还是会源源不断的到达数据库。

办理 缓存穿透标题 一样平常 可以采用以下方案共同 利用 :

1、接口层举行 校验,发现非法的key直接返回。比如数据库中采用的是自增id,那么假如 来了一个非整型的id或者负数id可以直接返回,或者说假如 采用的是32位uuid,那么发现id长度不等于32位也可以直接返回。

2、将不存在的数据也举行 缓存,可以直接缓存一个空或者其他约定好的无效value。采用这种方案最好将key设置一个短期失效时间,否则大量不存在的key被存储到Redis中,也会占用大量内存。

布隆过滤器(Bloom Filter)

针对上面缓存穿透的办理 方案,我们思考 一下:假如一个key可以绕过第1种方法的校验,而此时有大量的不存在key被访问(如1亿个或者10亿个),那么这时间 全部存储到缓存,会占用非常大的空间,会浪费大量服务器内存,导致内存不足。

那么有没有一种更好的办理 方案呢?这就是我们接下来要先容 的布隆过滤器,布隆过滤器就可以最大程度的办理 key值过多的这个标题 。

什么是布隆过滤器

大概 大部分人都知道有这么一个口试 标题 :怎样 在10亿的海量的无序的数据中快速判定 一个元素是否存在?

要办理 这个标题 就必要 用到布隆过滤器,否则大部分服务器的内存是无法存储这么大的数目 级的数据的。

布隆过滤器(Bloom Filter)是由布隆在1970年提出的。它实际 上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的长处 是空间服从 和查询时间都比一样平常 的算法要好的多,缺点是有肯定 的误辨认 率而且删除困难。

位图(Bitmap)

Redis当中有一种数据布局 就是位图,布隆过滤器此中 紧张 的实现就是位图的实现,也就是位数组,并且在这个数组中每一个位置只有0和1两种状态,每个位置只占用1个比特(bit),此中 0表示没有元素存在,1表示有元素存在。如下图所示就是一个简单的布隆过滤器示例(一个key值颠末 哈希运算和位运算就可以得出应该落在哪个位置):

在这里插入图片形貌

哈希碰撞

上面我们发现,

  1. lonely
复制代码
  1. wolf
复制代码
落在了同一个位置,这种不同的key值颠末 哈希运算后得到类似 值的征象 就称之为哈希碰撞。发生哈希碰撞之后再颠末 位运算,那么末了 肯定会落在同一个位置。

假如 发生过多的哈希碰撞,就会影响到判定 的正确 性,以是 为了减少哈希碰撞,我们一样平常 会综合思量 以下2个因素:

1、增大位图数组的大小(位图数组越大,占用的内存越大)。

2、增长 哈希函数的次数(同一个key值颠末 1个函数相称 了,那么颠末 2个或者更多个哈希函数的计算,都得到相称 结果 的概率就天然 会降低了)。

上面两个方法我们必要 综合思量 :比如增大位数组,那么就必要 斲丧 更多的空间,而颠末 越多的哈希计算也会斲丧 cpu影响到终极 的计算时间,以是 位数组到底多大,哈希函数次数又到底必要 计算多少次合适必要 具体 环境 具体 分析。

布隆过滤器的2大特点

下面这个就是一个颠末 了2次哈希函数得到的布隆过滤器,根据下图我们很容易 看到,假如我们的Redis根本不存在,但是Redis颠末 2次哈希函数之后得到的两个位置已经是1了(一个是wolf通过f2得到,一个是Nosql通过f1得到)。

在这里插入图片形貌

以是 通过上面的征象 ,我们从布隆过滤器的角度可以得出布隆过滤器紧张 有2大特点:

1、假如 布隆过滤器判定 一个元素存在,那么这个元素大概 存在

2、假如 布隆过滤器判定 一个元素不存在,那么这个元素肯定 不存在

而从元素的角度也可以得出2大特点:

1、假如 元素实际 存在,那么布隆过滤器肯定 会判定 存在

2、假如 元素不存在,那么布隆过滤器大概 会判定 存在

PS:必要 注意 的是,假如 颠末 N次哈希函数,则必要 得到的N个位置都是1才能判定 存在,只要有一个是0,就可以判定 为元素不存在布隆过滤器中

fpp

由于 布隆过滤器中总是会存在误判率,由于 哈希碰撞是不大概 百分百避免的。布隆过滤器对这种误判率称之为假阳性概率,即:False Positive Probability,简称为fpp。

在实践中利用 布隆过滤器时可以本身 定义一个fpp,然后就可以根据布隆过滤器的理论计算出必要 多少个哈希函数和多大的位数组空间。必要 注意 的是这个fpp不能定义为100%,由于 无法百分保证不发生哈希碰撞。

布隆过滤器的实现(Guava)

在Guava的包中提供了布隆过滤器的实现,下面就通过Guava来了解 一下布隆过滤器的应用:
1、引入

  1. pom
复制代码
依赖

  1. <dependency>
  2. <groupId>com.google.guava</groupId>
  3. <artifactId>guava</artifactId>
  4. <version>29.0-jre</version>
  5. </dependency>
复制代码

2、新建一个布隆过滤器的测试demo:

  1. package com.lonelyWolf.redis;
  2. import com.google.common.base.Charsets;
  3. import com.google.common.hash.BloomFilter;
  4. import com.google.common.hash.Funnels;
  5. import java.text.NumberFormat;
  6. import java.util.ArrayList;
  7. import java.util.List;
  8. import java.util.UUID;
  9. public class BloomFilterDemo {
  10. private static final int expectedInsertions = 1000000;
  11. public static void main(String[] args) {
  12. BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);
  13. List<String> list = new ArrayList<>(expectedInsertions);
  14. for (int i = 0; i < expectedInsertions; i++) {
  15. String uuid = UUID.randomUUID().toString();
  16. bloomFilter.put(uuid);
  17. list.add(uuid);
  18. }
  19. int rightNum1 = 0;
  20. int wrongNum1 = 0;
  21. NumberFormat percentFormat =NumberFormat.getPercentInstance();
  22. percentFormat.setMaximumFractionDigits(2); //最大小数位数
  23. for (int i=0;i < 500;i++){
  24. String key = list.get(i);
  25. if (bloomFilter.mightContain(key)){
  26. if (list.contains(key)){
  27. rightNum1++;
  28. }else {
  29. wrongNum1++;
  30. }
  31. }
  32. }
  33. System.out.println("布隆过滤器认为存在的key值数:" + rightNum1);
  34. System.out.println("-----------------------分割线---------------------------------");
  35. int rightNum2 = 0;
  36. int wrongNum2 = 0;
  37. for (int i=0;i < 5000;i++){
  38. String key = UUID.randomUUID().toString();
  39. if (bloomFilter.mightContain(key)){
  40. if (list.contains(key)){
  41. rightNum2++;
  42. }else {
  43. wrongNum2++;
  44. }
  45. }
  46. }
  47. System.out.println("布隆过滤器认为存在的key值数:" + rightNum2);
  48. System.out.println("布隆过滤器认为不存在的key值数:" + wrongNum2);
  49. System.out.println("布隆过滤器的误判率为:" + percentFormat.format((float)wrongNum2 / 5000));
  50. }
  51. }
复制代码

运行之后,第一部分输出的值肯定 是和for循环内的值相称 ,也就是百分百匹配,即满意 了原则1:假如 元素实际 存在,那么布隆过滤器肯定 会判定 存在
第二部分的输出的误判率即fpp总是在3%左右,而且随着for循环的次数越大,越靠近 3%。即满意 了原则2:假如 元素不存在,那么布隆过滤器大概 会判定 存在

这个3%的误判率是怎样 来的呢?我们进入创建布隆过滤器的

  1. create
复制代码
方法,发现默认的fpp就是0.03:

在这里插入图片形貌

对于这个默认的3%的fpp必要 多大的位数组空间和多少次哈希函数得到的呢?在

  1. BloomFilter
复制代码
类下面有两个
  1. default
复制代码
方法可以获取到位数组空间大小和哈希函数的个数:

  • optimalNumOfHashFunctions:获取哈希函数的次数
  • optimalNumOfBits:获取位数组大小

debug进去看一下:

在这里插入图片形貌

得到的结果 是7298440 bit=0.87M,然后颠末 了5次哈希运算。可以发现这个空间占用黑白 常小的,100W的key才占用了0.87M。

PS:点击这里可以进入网站计算bit数组大小和哈希函数个数。

布隆过滤器的怎样 删除

上面的布隆过滤器我们知道,判定 一个元素存在就是判定 对应位置是否为1来确定的,但是假如 要删除掉一个元素是不能直接把1改成0的,由于 这个位置大概 存在其他元素,以是 假如 要支持删除,那我们应该怎么做呢?最简单的做法就是加一个计数器,就是说位数组的每个位假如 不存在就是0,存在几个元素就存具体 的数字,而不仅仅只是存1,那么这就有一个标题 ,本来存1就是一位就可以满意 了,但是假如 要存具体 的数字比如说2,那就必要 2位了,以是 带有计数器的布隆过滤器会占用更大的空间

带有计数器的布隆过滤器

下面就是一个带有计数器的布隆过滤器示例
1、引入依赖 :

  1. <dependency>
  2. <groupId>com.baqend</groupId>
  3. <artifactId>bloom-filter</artifactId>
  4. <version>1.0.7</version>
  5. </dependency>
复制代码

2、新建一个带有计数器的布隆过滤器demo:

  1. package com.lonelyWolf.redis.bloom;
  2. import orestes.bloomfilter.FilterBuilder;
  3. public class CountingBloomFilter {
  4. public static void main(String[] args) {
  5. orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
  6. 0.01).countingBits(8).buildCountingBloomFilter();
  7. cbf.add("zhangsan");
  8. cbf.add("lisi");
  9. cbf.add("wangwu");
  10. System.out.println("是否存在王五:" + cbf.contains("wangwu")); //true
  11. cbf.remove("wangwu");
  12. System.out.println("是否存在王五:" + cbf.contains("wangwu")); //false
  13. }
  14. }
复制代码

构建布隆过滤器前面2个参数一个就是盼望 的元素数,一个就是fpp值,后面的

  1. countingBits
复制代码
参数就是计数器占用的大小,这里传了一个8位,即最多答应 255次重复,假如 不传的话这里默认是16位大小,即答应 65535次重复。

总结

本文紧张 讲述了利用 Redis存在的三种标题 :缓存雪崩缓存击穿缓存穿透。并分别对每种标题 的办理 方案举行 了形貌 ,末了 偏重 先容 了缓存穿透的办理 方案:布隆过滤器。原生的布隆过滤器不支持删除,但是可以引入一个计数器实现带有计数器的布隆过滤器来实现删除功能,同时在末了 也提到了,带有计数器的布隆过滤器会占用更多的空间标题 。

到此这篇关于Redis利用 元素删除的布隆过滤器来办理 缓存穿透标题 的文章就先容 到这了,更多相干 Redis 缓存穿透内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 白度了一生一x | 2021-9-18 08:13:07 | 显示全部楼层
admin楼主是男的还是女的?
回复

使用道具 举报

avatar pcng417912 | 2021-9-18 19:59:39 | 显示全部楼层
内容很有深度!
回复

使用道具 举报

avatar 风云18171265739 | 2021-9-20 23:15:23 | 显示全部楼层
顶顶更健康!
回复

使用道具 举报

avatar 巴拿巴 | 2021-10-4 10:01:01 | 显示全部楼层
怎么我回帖都没人理我呢?
回复

使用道具 举报

avatar 小雨1004 | 2021-10-9 06:39:58 | 显示全部楼层
看帖不回帖都是耍流氓!
回复

使用道具 举报

avatar 123457886 | 2021-10-9 23:36:18 | 显示全部楼层
我就搞不明白了,看帖回帖能死人么,居然只有我这么认真的在回帖!
回复

使用道具 举报

精华帖的节奏啊!
回复

使用道具 举报

支持一下,下面的保持队形!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则