缓存穿透和布隆算法一样吗

A. 什么是缓存穿透

缓存穿透又称缓存击穿,是指在高并发场景下缓存中(包括本地缓存和Redis缓存)的某一个Key被高并发的访问没有命中,此时回去数据库中访问数据,导致数据库并发的执行大量查询操作,对DB造成巨大的压力。

B. 布隆过滤器详解

布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为 ， ， 。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：

所有散列函数都有如下基本特性：

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。

在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。

如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器的典型应用有：

知道了布隆过滤去的原理和使用场景，我们可以自己实现一个简单的布隆过滤器

分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。

当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。

Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。

Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。

在已安装 Redis 的前提下，安装 RedisBloom，有两种方式

直接编译进行安装

使用Docker进行安装

使用

布隆过滤器基本指令：

我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。

上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。

Redis 还提供了自定义参数的布隆过滤器， bf.reserve 过滤器名 error_rate initial_size

但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错

我是一名 javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

由于使用较少，暂不深入。

https://www.cs.cmu.e/~dga/papers/cuckoo-conext2014.pdf

http://www.justdojava.com/2019/10/22/bloomfilter/

https://www.cnblogs.com/cpselvis/p/6265825.html

https://juejin.im/post/5cc5aa7ce51d456e431adac5

C. 该怎么解决 Redis 缓存穿透和缓存雪崩问题

缓存雪崩： 由于缓存层承载着大量请求，有效地 保护了存储层，但是如果缓存层由于某些原因不能提供服务，比如 Redis 节点挂掉了，热点 key 全部失效了，在这些情况下，所有的请求都会直接请求到数据库，可能会造成数据库宕机的情况。
预防和解决缓存雪崩问题，可以从以下三个方面进行着手：
1、使用 Redis 高可用架构：使用 Redis 集群来保证 Redis 服务不会挂掉
2、缓存时间不一致： 给缓存的失效时间，加上一个随机值，避免集体失效
3、限流降级策略：有一定的备案，比如个性推荐服务不可用了，换成热点数据推荐服务
缓存穿透： 缓存穿透是指查询一个根本不存在的数据，这样的数据肯定不在缓存中，这会导致请求全部落到数据库上，有可能出现数据库宕机的情况。
预防和解决缓存穿透问题，可以考虑以下两种方法：
1、缓存空对象： 将空值缓存起来，但是这样就有一个问题，大量无效的空值将占用空间，非常浪费。
2、布隆过滤器拦截： 将所有可能的查询key 先映射到布隆过滤器中，查询时先判断key是否存在布隆过滤器中，存在才继续向下执行，如果不存在，则直接返回。布隆过滤器有一定的误判，所以需要你的业务允许一定的容错性。

D. 缓存击穿、穿透、雪崩及Redis分布式锁

分布式锁: setnx ,redisson 并发问题
幂等问题: 落表状态,Redis

缓存击穿: 指缓存中无,db中有
原因: 一个key高并发恰好失效导致大量请求到db
方案: 加锁,自旋锁,或一个线程查db,一个线程监控(直接用Redisson分布式锁)

缓存穿透:指缓存和db中均无
原因: 一般是恶意请求
方案: 加布隆过滤,或查db无时,也设置缓存,value为某些特殊表示或"null"

雪崩:指缓存同时大量失效
原因: 大量的key同时失效,db压力加大
方案: 设置失效时间是增加随机数

问题方案文献:
https://www.jianshu.com/p/31ab9b020cd9 (图例分析)

https://blog.csdn.net/fcvtb/article/details/89478554

Redis分布式锁:

事务未执行完锁已到期释放问题：使用Redissoin解决续租问题，内部已解决

分布式锁文献:
https://www.jianshu.com/p/4838f8be00c9
https://blog.csdn.net/qq_30038111/article/details/90696233 (setnx + expire同时操作)

====================================

https://www.runoob.com/redis/keys-scan.html
https://www.jianshu.com/p/611a492d9121 Redis原理与应用

E. 缓存穿透的意义

缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中时被动写的，并且正羡出于容错考虑，如举斗拍果从存储层查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到存储层去查询，失去了缓存的意义。在流销租量大时，可能DB就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。