之前，小马在聊缓存击穿和穿透的文中有介绍过防止缓存穿透其中的一种方式是使用布隆过滤器，那什么是布隆过滤器呢？今天就来喝喝茶以通俗的方式聊一聊，一起学习学习。
场景引入
首先，我们先来看一个场景。比如现在需要判断数据是否存在，你会用什么方式。有的小伙伴觉得查DB啊，呃，如果面试你这样子很可能会被out。有小机灵鬼有方案了，那我用HashMap吧。将值映射到HashMap的KEY再用上Redis这种内存级的缓存，时间复杂度O（1），效率杠杠的。嗯，听起来好像是没啥问题，但是如果数据量非常大，比如上亿，那HashMap占据的内存大小就很值得关注了。这个时候，布隆过滤器出现了，相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少。它是如何做到比HashMap还要优秀的呢？我们来一层一层剥开。
什么是布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好很多，缺点是有一定的误识别率和删除困难。
其实它本质上是一种数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。缺点是其返回的可能存在结果是概率性的，而不是确切的。值得一提的是，这里的删除困难其实智慧的人类早就有找到解决方案了。
布隆过滤器为什么这么优秀
布隆过滤器是一个bit向量或者说bit 数组，如下借用一张图。当然这只是个示例，实际上的位数是N倍。
我们回顾上面的百科定义。如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的bit位置1。
比如我们现在对“xiaoma”这个值进行多个函数的哈希，得到的哈希值为3、5、7，好的，我们将3,5,7号位置为1。我们再来一个值，比如“大胖”得到三个值为1、5、6，于是我们对1,5,6号位置为1。我们注意到5号位是被两个值的哈希都落位到的。
此时如果我们要开始查找了，假设查找“xiaomanong”这个值，哈希后得到1、2、6，我们发现2号位是0，于是我们很果断地说，“xiaomanong”这个值是不存在的。那话又说回来，假如我们此时查找“xiaoma”自然会得到3、5、7，我们发现这几号位上全是1，于是我们就可以果断地说“xiaoma”这个值就一定存在了？自然不行，因为你刚也看到了，5号的1有可能是其他值的哈希置为1的，所以只能说，可能存在。这就为什么它只能告诉你“一定不存在或者可能存在”的原理，也就是布隆会误判的原因。
Redis布隆过滤器要怎么实现
笔者也没有亲践，但整理了两个实现方案供参考。
1、Redis的rebloom模块扩展
下载并编译git clone git://github.com/RedisLabsModules/rebloom。配置文件中加载rebloom：loadmodule /your_path/rebloom.so。重启Redis服务器即可。
接下来就是一系列的操作命令了。大致可分为添加元素，判断元素是否存在，增量保存持久化。比如命令：
BF.EXISTS {key} {item}
判断单个元素是否存在
如果存在，返回1，否则返回0
2、redis-lua-scaling-bloom-filter
利用Redis的Bitmaps实现布隆过滤器，GitHub上已经开源了类似的方案可以自行搜索git（这里就不方便贴链接了），这种方法适用于数据命中不高、数据相对固定、实时性低（通常是数据集较大）的应用场景，代码维护较为复杂，但是缓存空间占用少。
总而言之，错误率越小(即对误差的容忍度越低)，每个过滤器条目的空间消耗就越大。布隆过滤器是可以牺牲准确率换空间，当然这个准确率大小是可以通过参数调整的，也和本身数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关。
应用场景
1、爬虫中对大量页面URL判断，已经爬过的就不再爬了，当然这个是存在误判的，有些没爬过的URL可能被错过；
2、垃圾邮件的过滤，普遍都用了布隆过滤器。如果邮箱存在于垃圾邮件的布隆中就放入垃圾邮箱列表。同样存在误判，所以有些正常的邮箱也被放入垃圾列表中，但一般这种概率比较低。那么试想一下，可不可以把正常邮箱放入布隆中进行过滤呢能不能解决误判问题，留给观者思考哈；
3、防止缓存击穿和过滤一些黑客攻击。
未经允许请勿转载。
网友评论