Redis布隆过滤器之初体验
之前,小马在聊缓存击穿和穿透的文中有详情过防止缓存穿透其中的一种方式是使用布隆过滤器,那什么是布隆过滤器呢?今天就来喝喝茶以浅显的方式聊一聊,一起学习学习。
场景引入
首先,我们先来看一个场景。比方现在需要判断数据能否存在,你会用什么方式。有的小伙伴觉得查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、防止缓存击穿和过滤少量黑客攻击。
未经允许请勿转载。
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Redis布隆过滤器之初体验