缓存穿透

简单来说用户查询一个数据,发现redis内存中没有,也就是缓存没有命中,于是向持久层数据库查询,发现也没有，则本次查询失败,当用户很多的时候,且缓存中都没有他们的请求查询,于是都去持久层查询,就会给持久层数据库，造成很大的压力,这就是缓存穿透

面试中面试官问到怎么避免缓存穿透，你的第一反应可能就是布隆过滤器，缓存穿透=布隆过滤器似乎成了标配，但具体什么是布隆过滤器,这里给出一点个人理解

一道经典的面试题

• 如何在海量元素中（例如 10 亿无序、不定长、不重复）快速判断一个元素是否存在?

好，我们最简单的想法就是把这么多数据放到数据结构里去，比如List、Map、Tree，遍历一下不就出来了吗，比如map.get(),我们假设一个元素10个字节的字段，10亿的数据大概需要 74G 的内存空间，这个对于普通的服务器来说是承受不了的，当然面试官也不希望听到你这个答案，因为太笨了吧，我们肯定是要用一种好的方法，巧妙的方法来解决，这里引入一种节省空间的数据结构，位图，他是一个有序的数组，只有两个值，0 和 1。0代表不存在，1代表存在。

现在我们还需要一个映射关系，将元素映射到位图上面去,存在就是1,否则是0,可以使用哈希函数，用哈希函数有两个好处，第一是哈希函数无论输入值的长度是多少，得到的输出值长度是固定的，第二是他的分布是比较均匀的,关于HashMap取索引的算法可以看我昨天发布的文章:HashMap索引算法
但是,总所周知,hash算法免不了发生hash碰撞的情况，为了尽可能减少hash碰撞,一般有两种方法

• 第一种是可以扩大维数组的长度或者说位图容量，因为我们的函数是分布均匀的，所以位图容量越大，在同一个位置发生哈希碰撞的概率就越小。但是越大的位图容量，意味着越多的内存消耗，所以我们想想能不能通过其他的方式来解决
• 第二种方式就是经过多几个哈希函数的计算，两个元素现在经过一次计算就碰撞了，那我经过5次，10次，100次计算还能碰撞的话那真的是缘分了，但也不是越多次哈希函数计算越好，因为这样很快就会填满位图，而且计算也是需要消耗时间，所以我们需要在时间和空间上寻求一个平衡

布隆过滤器

在 1970 年的时候，弗雷尔卓德之心-布隆前辈对于判断海量元素中元素是否存在的问题进行了研究，也就是到底需要多大的位图容量和多少个哈希函数，它发表了一篇论文，提出的这个容器就叫做布隆过滤器。(图片来自网络)

里面的f1(),f2(),f3()就是hash取索引函数了,集和S中的a,b,c经过三次hash分别将得到的三个索引处的位子设置为1.

• 当取的时候，元素a通过f1(a)函数计算，发现这个位置上是1，没问题，第二个位置也是1，第三个位置上也是 1，这时候我们说这个a在布隆过滤器中是存在的，同理我们看下面的这个d，通过三次计算发现得到的结果也都是1，那么我们能说d在布隆过滤器中是存在的吗，显然是不行的，我们仔细看d得到的三个1其实是f1(a)，f1(b)，f2(c)存进去的，并不是d自己存进去的，这个还是哈希碰撞导致的，我们把这种本来不存在布隆过滤器中的元素误判为存在的情况叫做假阳性
• 我们再来看另一个元素，e 元素。我们要判断它在容器里面是否存在，一样地要用这三个函数去计算。第一个位置是 1，第二个位置是 1，第三个位置是 0。那么e元素能不能判断是否在布隆过滤器中？答案是肯定的，e一定不存在。如果e存在的话，他存进去的时候这三个位置都置为1，现在查出来有一个位置是0，证明他没存进去。。通过上面这张图说明，我们得出两个重要的结论:

1. 如果布隆过滤器判断元素在集合中存在，但不一定存在

2. 如果布隆过滤器判断不存在，则一定不存在

提供一些解决缓存穿透的策略吧

(2021-07-19补充)

• 可以将数据库中所有的查询条件，放入布隆过滤器中，当一个查询请求过来时，先经过布隆过滤器进行查，如果判断请求查询值存在，则继续查；如果判断请求查询不存在，直接丢弃。(来自网络,这个查询条件说的不是很具体,我也有点迷,权当参考吧)
• 比较实用的:在布隆过滤器中存储目前数据库中存在的所有key(比如order_id,product_id)当业务系统有查询请求的时候，首先去BloomFilter中查询该key是否存在。若不存在，则说明数据库中也不存在该数据，因此缓存都不要查了，直接返回null。若存在，则继续执行后续流程，先前往缓存中查询，缓存没命中的话再前往数据库中查询。

另外,布隆过滤器在多哈希函数的情况下是不支持删除元素的,具体原因大家可以思考一下

布隆过滤器其他使用场景

• 网页爬虫对URL去重，避免爬取相同的 URL 地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
• Google Chrome 使用布隆过滤器识别恶意 URL；
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra使用布隆过滤器减少对不存在的行和列的查找。

以上简单总结了布隆过滤器的核心-位图的原理，有什么不足欢迎评论区指出~