之前Pony详细讲过缓存击穿和渗透。防止缓存渗透的一种方法是使用布隆过滤器。那么什么是布鲁姆滤镜呢？今天一起喝杯茶，深入浅出的聊一聊，一起学习。 场景介绍先来看一个场景。 比如你需要判断数据现在是否可以存在，你会用什么方法？ 有朋友觉得查DB，诶你这样面试的话很可能就出局了 聪明人有计划，我就用HashMap。 将值映射到HashMap的键，然后使用内存级缓存Redis，时间复杂度为O(1)，效率高。 嗯，听起来没什么问题，但是如果数据量非常大，比如说几亿，HashMap占用的内存大小就值得注意了。 这时候，布鲁姆滤镜出现了。与链表、集合、映射等传统数据结构相比，效率更高，占用空间更少。 它怎么比HashMap做得好？让我们一层一层地剥开它。 什么是布鲁姆过滤器布鲁姆过滤器是布鲁姆在1970年提出的。 它实际上是一个长的二元向量和一系列随机映射函数。 布隆过滤器可用于检索一个元素是否可以在一个集合中。 它的优点是空间效率和查询时间远优于一般算法，缺点是有正误识率和删除难度。 实际上，它本质上是一种数据结构，特点是高效的插入和查询，可以用来告诉你“某个东西肯定不存在或者可能存在” 缺点是其可能存在的结果是概率性的，而不是精确的。 值得一提的是，这里很难删除。其实聪明的人类早就找到了解决办法。 为什么布鲁姆滤镜这么好？布隆过滤器是位向量或位数组。请借一张图如下。 当然，这只是一个例子。其实位数是N次。 我们来回顾一下上面的百科定义。 如果要将一个值映射到Bloom filter，需要使用不同的hash函数生成多个hash值，并将每个生成的hash值的比特位设置为1。 比如我们现在用多个函数对“马骁”的值进行散列，散列值为3、5、7。好，我们将3，5，7的位置设为1。 我们再取一个值，比如“大胖”得到1、5、6三个值，所以我们把1、5、6的位置设为1。 我们注意到第5位是由两个值的散列值设置的。 此时，如果我们要开始搜索，假设我们查找“小满农”的值，哈希后得到1，2，6，我们发现bit 2为0，那么我们果断地说“小满农”的值不存在。 话又说回来，如果我们这个时候查“马骁”，自然会得到3，5，7，我们发现这些位都是1，那么我们就可以果断的说“马骁”的值肯定是存在的了？自然，就像你刚才看到的，5号的1可能是其他值设置为1的哈希，所以只能说可能存在。 这就是为什么它只能告诉你“肯定不存在或者可能存在”的原理，也就是布鲁姆误判的原因 Redis Bloom filter如何实现不是作者亲自实践，整理了两个实现方案供参考。 1.Redis的rebloom模块扩展、下载并编译git clone git://github . com/redislabsmodules/re bloom。 在配置文件中加载re bloom:load module/your _ path/re bloom . so 只需重启Redis服务器。 接下来就是一系列的操作命令。 大致可以分为添加元素、判断元素是否可以存在、增量保存和持久化。 例如，命令:BF。EXISTS {key} {item}确定单个元素是否可以存在。如果存在，返回1，否则返回02。redis-lua-scaling-bloom-filter使用redis的位图来实现Bloom filter。类似的方案已经在gitHub上开源了，你可以自己搜索Git(这里不方便贴链接)。这种方法适用于数据命中率低、数据相对固定、实时性低的应用场景(通常是大数据集)。代码维护复杂，但是缓存空间占用空间少。 总之，错误率越小(即对错误的容忍度越低)，每个过滤器条目的空间消耗就越大。 布隆过滤器可以为了空间而牺牲准确性。当然，精度是可以通过参数来调整的，也与其数组的大小、哈希函数的个数以及每个哈希函数的质量有关。 应用场景一:判断爬虫中的大量页面URL，如果已经爬了，就不会再爬了。当然有误判的，可能会漏掉一些没爬上来的网址；2.Bloom filter通常用于垃圾邮件过滤。 如果邮箱存在于垃圾邮件群发中，将其放入垃圾邮件列表。 还有一种是误判，所以把一些正常的邮箱也放入垃圾列表，但这种概率一般较低。 然后想象一下，你能把正常邮箱放在Bloom里过滤吗？能不能把误判的问题处理好，留给观者去思考？3.防止缓存崩溃，过滤一些黑客攻击。 未经许可，请勿转载。