字节二面：蘑菇博客是怎么解决缓存穿透的?
作者：陌溪
陌溪的学习笔记：http://note.moguit.cn
大家好，我是周末还在肝文的卷溪。
陌溪之前在面试字节提前批的时候，二面的面试官就问过 Redis 缓存穿透的问题，下面让我们一起深度还原一下陌溪当初的面试场景吧~
面试官：你的蘑菇博客项目用到了 Redis ？
陌溪：主要是为了缓解数据库压力，将首页的一些热门文章信息储存在 Redis 中。
面试官：好，那你知道什么是缓存穿透么？
陌溪：那我以蘑菇博客的场景来聊聊什么是缓存穿透。
什么是缓存穿透？
举个蘑菇博客中的案例来说，现在有一个博客详情页，详情页中的内容是存储在 Redis 中的，通过博客的 uid 进行获取，正常的情况是：用户进入博客详情页，传递 uid 获取 Redis 中缓存的文章详情，如果有内容就直接访问，如果缓存为空，那么需要访问数据库，然后从数据库中查询我们的博客详情后，再存储到 Redis 中，最后把数据返回给我们的页面。
但是可能存在一些非法用户，会通过不合法的 uid 去请求博客后台，首先 redis 的缓存没有命中该 key，那么就会去请求数据库，这样大量非法的请求直接打在数据库中，可能会导致数据库直接宕机，无法对外提供服务，这就是我们所说的缓存穿透问题。
面试官：OK，那来谈谈蘑菇是怎么解决缓存穿透的？
陌溪（内心）：糟糕，蘑菇博客中我并没有去解决缓存穿透问题，要是直接说没有解决，岂不是 回家等通知 了？
陌溪：针对上面出现的情况，我们有一种简单的解决方法就是，在数据库没有查询该条数据的时候，我们让该 key缓存一个 空数据，这样用户再次以该 key 请求后台的时候，会直接返回 null，避免了再次请求数据库。
面试官：好的，但是如果非法用户使用不同的 key 去请求后台时，那这样还是每次都不会命中缓存，都会查询数据库，针对这种情况，你有什么解决方法呢？
陌溪（内心）：这面试连环炮有些遭不住，还好之前看八股文的时候，有看到过布隆过滤器，这会刚好可以说了。
陌溪：这种情况，我会使用布隆过滤器来解决这个问题~
什么是布隆过滤器？
布隆过滤器的巨大作用 ，就是能够迅速判断一个元素是否存在一个集合中。因此它有如下几个使用场景
网站爬虫对 URL 的去重，避免爬取相同的 URL。
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮件（同理，垃圾短信）
缓存穿透，将所有可能的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时，迅速返回避免缓存以及DB 挂掉。
布隆过滤器其内部维护了一个全为 0 的 bit 数组，需要说明的是，布隆过滤器有一个误判的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间多少。
假设，根据误判率，我们生成一个 10 位的 bit 数组，以及 2 个 hash 函数 f1 和 f2，如下图所示：生成的数组的位数 和 hash 函数的数量。这里我们不用去关心如何生成的，因为有数学论文进行验证。
然后我们输入一个集合，集合中包含 N1 和 N2，我们通过计算 f1(N1) = 2，f2(N1) = 5，则将数组下标为 2 和下标为 5 的位置设置成 1，就得到了下图。
同理，我们再次进行计算 N2的值， f1(N2) = 3，f2(N2) = 6。得到如下所示的图
这个时候，假设我们有第三个数 N3 过来了，需要判断 N3 是否在集合 [N1,N2] 中，需要做的操作就是，使用 f1 和 f2 计算出数组中的地址
若值恰巧都位于上图的红色位置，我们认为 N3在集合 [N1,N2] 中
若值有一个不位于上图的红色部分，我们认为N3不在集合 [N1,N2] 中
这就是布隆过滤器的计算原理。
如何使用布隆过滤器
在 Java 中使用布隆过滤器，首先需要引入依赖，布隆过滤器拥有 Google 提供的一个开箱即用的组件，来帮助实现布隆过滤器。其实布隆过滤器的核心思想其实并不难，难的是在于如何设计随机映射函数，到底映射几次，二进制向量设置多少比较合适。
<dependencies>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>22.0</version>
</dependency>
</dependencies>
然后编写代码，测试某元素是否存在于百万元素集合中
private static int size = 1000000;//预计要插入多少数据
private static double fpp = 0.01;//期望的误判率
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
public static void main(String[] args) {
//插入数据
for (int i = 0; i < 1000000; i++) {
bloomFilter.put(i);
}
int count = 0;
for (int i = 1000000; i < 2000000; i++) {
if (bloomFilter.mightContain(i)) {
count++;
System.out.println(i + "误判了");
}
}
System.out.println("总共的误判数:" + count);
}
代码分析
上面的代码中，我们创建了一个布隆过滤器，其中有两个重要的参数，分别是要预计插入的数据和我们所期望的误判率，误判率率不能为 0 。
首先向布隆过滤器中插入 0 ~ 100万 条数据，然后在用 100万 ~ 200万的数据进行测试
最后输出结果，查看一下误判率
1999501误判了
1999567误判了
1999640误判了
1999697误判了
1999827误判了
1999942误判了
总共的误判数:10314
现在有 100万 不存在的数据，误判了 10314 次，通过计算可以得出误判率
10314 / 1000000 = 0.010314
和之前定义的误判率为 0.01 相差无几，这也说明了布隆过滤器在处理 Redis 缓存穿透问题上，也具有比较好的表现。
我是陌溪，我们下期再见~
往期推荐
结语
应各位小伙伴们的需求，陌溪已经把 学习笔记 已经整理成 PDF 版本啦，方便大家在手机或者电脑上阅读。以下笔记仓库的部分 PDF 文件 。如果有需要离线阅读的小伙伴可以到公众号回复 PDF ，即可获取下载地址~
同时本公众号申请较晚，暂时没有开通留言功能，欢迎小伙伴们添加我的私人微信【备注：加群】，我将邀请你加入到蘑菇博客交流群中，欢迎小伙伴们找陌溪一块聊天唠嗑，共同学习进步。最后，如果你觉得本文对你有所帮助，麻烦小伙伴们动动手指给文章点个「赞」和「在看」，非常感谢大家的支持。