缓存穿透与布隆过滤器

微信扫一扫,分享到朋友圈

缓存穿透与布隆过滤器

1. 什么是缓存穿透

正常来说,我们使用缓存,是为了减少数据库的连接,降低数据库的连接、计算压力。同时给应用更快的响应速度与并发数量。因为数据库中的数据是存放在硬盘中的,而缓存数据则是存放在内存中的,其读取速度差距非常大。

为了实现缓存目的,通常应用在请求数据的时候,会先尝试在缓存数据中寻找,如果缓存数据中不存在,那么就会到数据库中查询,然后将查询结果写入缓存。

因为应用在请求的时候,第一步是先从整个缓存中查找,所以,要求缓存框架的查询性能要非常好。一般都是KV结构的,其查找复杂度恒定的结构。

  • 当应用第一次来请求数据的时候,缓存中当然没有,此时,就需要去数据库中查找,然后将查找结果写入缓存中。

  • 当应用第二次来请求数据的时候,因为第一次我们已经将这个数据(假设和第一次请求的数据相同)写入了缓存中,就不需要去数据库中查找了。

    缓存失效的策略,也是影响缓存命中率的一个很重要的因素。redis的缓存失效策略:LRU,LRU-K,LRU-Two,Multi Queue.失效时间TTL

  • 缓存命中率低其实不可怕,如果应用请求的数据是一个不存在的数据,那么不管是应用第几次请求,每次都需要去数据库中查询,那么,如果这操作是一个比较高并发的操作,每一次都需要去数据库查询,很快就会将数据库资源耗尽。

这就发生了一次缓存穿透。

2. 持续性的缓存穿透

因为应用查询数据库中不存在的数据时,会发生缓存穿透。

为了避免这种情况,就需要我们的缓存需要将不存在的数据也在缓存中存储。

其存储的值是一个非常特殊的值,正常情况下应用无法存储的值。这样我们才能区分,这个是数据库中有还是没有的。

但是这种机制,仍然有问题。

==如何保证缓存一致性==

我们将一个不存在的条件,在缓存中存储了一个特殊的值,那么当数据库中写入了这个条件的值的时候,如何保证缓存与数据中数据的一致性呢?

也就是如何保证缓存的可靠性,缓存是正确的缓存的值,缓存是数据中数据的真实副本呢?

  1. 设置失效时间,一般来说,在某个时间段内,查询某个数据是一个小时间片的事件,所以设置一个失效时间,在一定程度上既可以防止缓存穿透,也可以防止缓存不一致。
  2. 写入数据,也需要更新缓存数据。这里有一个思想:刚创建的数据,在接下来的一小段时间内是最活跃的,也是请求最频繁的。所以,在往数据库中写入的时候,也写入缓存中。

==缓存穿透==

有时候,我们创建的数据都有一定的规律,如果被恶意程序找到规律,每次缓存穿透查询的条件都是不同的,那,我们上面的方式就不行了。

每次应用请求,在缓存中每次都找不到,每次都需要去数据库中查询,此时,缓存就相当于不存在了。就发生了持续的缓存穿透。

一次,或者少量的缓存穿透,是很正常的。但是,持续性的缓存穿透,那就是一个很严重的问题。

3. 如何解决持续性的缓存穿透

缓存的存在,就是为了保护数据库,所以,持续性的缓存穿透,我们应该在缓存这里就去解决,而不应该简单的抛给数据库。

为了要在缓存中去查找是否存在指定条件的数据,就需要将数据库中全部数据完全加载到缓存中。

简化存储

很明显,缓存是根本存放不下这么多的数据的。怎么办?

将数据进行简化,我们将数据库中全部的数据加载到缓存中,就是为了查找,这个数据在数据库中存在。只要这个数据在数据库中存在,那么就不会发生持续性的缓存穿透。

而且,对于数据库中的数据来说,不存在的数据是无限的,而数据库中的数据是有限的。

所以,我们需要将数据库中的全部数据,做一个简化,在缓存中记录,这个数据有还是没有,对于没有的数据,我们可以快速拒绝,或者快速返回。

==而记录有还是没有,使用一个二进制位就可以记录。==

BitMap(位图),在Java中是BitSet

我们解决了二进制位的值的存储,还有键呢?也就是条件。

对于条件,输入是不固定长度的,我们需要实现:

  1. 不固定长度的输入 => 固定长度的输出
  2. 分布均匀 => 冲突小(hash,md5,sha-1)

避免hash冲突

使用了hash进行计算键,那么就有可能发生hash冲突。

  • 扩容可以避免hash冲突
  • 多个hash计算规则

注意点:

  • 无法无限扩容(空间占用增加,空间使用率低)
  • 无法无限增加hash计算(计算资源的消耗增加,时间耗费增加,时间复杂度增加)

需要找一个平衡点。

4. 布隆过滤器

==如何在海量数据中,快速判断一个元素是否存在?==

布隆,1970年

布隆过滤器–Bloom Filter

布隆过滤器本质:

  • 位数组(二进制)
  • 随机映射函数(多个)

随机映射函数的个数和hash冲突的概率有关。随机映射函数增加,hash冲突降低。

我们放入一个a元素,需要经过3个随机映射函数的映射。在写入的时候,需要将这三个随机映射函数的位的值进行设置;在查询的时候,需要这三个随机映射函数的位的值都是有,最终==不一定是有==。因为存在hash冲突。(图中d)

但是当三个随机映射函数的位,只要有一个没有,那么,最终==一定没有==。(图中e)

布隆过滤器,对于存在是不一定的,但是对于不存在是一定的。

False Positive Porbability FPP

==假阳性。==

类似于新冠肺炎的检测假阳性。

guava

字符串

集合

限流RateLimitter

二维码

布隆过滤器

……

5. 布隆过滤器使用

6. 缓存雪崩

缓存数据都有一定的有效时间TTL,在缓存失效的一瞬间,所有查询这个失效缓存数据的连接,都去查询数据库,导致数据库连接资源耗尽,从而导致整个系统不可用。

如何解决?

  • 失效时间均匀分布,避免缓存数据集中失效。
  • 控制数据库并发数量(计数器锁等,分布式锁等)
  • 双检测(获取到锁的线程将数据重新放到缓存中,其他等待锁的线程得到锁后,此时,数据可能已经被放到缓存中了)

亲属卡被当成诈骗工具 微信详解:这三点要注意

上一篇

三星Galaxy S20 Lite又名S20粉丝版 电池容量信息在3C认证数据库曝光

下一篇

你也可能喜欢

缓存穿透与布隆过滤器

长按储存图像,分享给朋友