布隆过滤器(Bloom Filter)的原理和应用

布隆过滤器的概念

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n)O(logn))。不过世界上还有一种叫作散列表又叫哈希表(Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。

布隆过滤器的算法思想

  1. 首先需要k个hash函数,每个函数可以把key散列成一个整数。

  2. 初始化时,需要一个长度为n比特的数组,每个比特位初始化为0。

  3. 当个key要加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置置为1。

  4. 判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

    布隆过滤器(Bloom Filter)的原理和应用

    布隆过滤器(Bloom Filter)的原理和应用

数据结构如上图所示。布隆过滤器其中重要的实现就是位图的实现,也就是位数组,并且在这个数组中每一个位置只占有1个bit,而每个bit只有0和1两种状态。如上图所示,bitarray也叫bitmap,大小就是布隆过滤器的大小。

假设一种有k个哈希函数,且每个哈希函数的输出范围都大于m,接着将输出值对k取余(%m),就会得到k个[0, m-1]的值,由于每个哈希函数之间相互独立,因此这k个数也相互独立,最后将这k个数对应到bitarray上并标记为1(涂黑)。等判断时,将输入对象经过这k个哈希函数计算得到k个值,然后判断对应bitarray的k个位置是否都为1(是否标黑),如果有一个不为黑,那么这个输入对象则不在这个集合中,如果都是黑,那说明在集合中,但有可能会误,由于当输入对象过多,而集合也就是bitarray过小,则会出现大部分为黑的情况,那样就容易发生误判!因此使用布隆过滤器是需要容忍错误率的,即使很低很低!

如果输入量过大,而bitarray空间的大小又很小,那么误判率就会上升。那么bitarray空间大小怎么确定呢?不要慌,已经有人通过数据推倒出公式了!

假设输入对象个数为n,bitarray大小(也就是布隆过滤器大小)为m,所容忍的误判率p和哈希函数的个数k。计算公式如下:(小数向上取整)

布隆过滤器(Bloom Filter)的原理和应用

注意:由于我们计算的m和k可能是小数,那么需要经过向上取整,此时需要重新计算误判率p。

假设一个网页黑名单有URL为100亿,每个样本为64B,失误率为0.01%,经过上述公式计算后,需要布隆过滤器大小为25GB,这远远小于使用哈希表的640GB的空间。

并且由于是通过hash进行查找的,所以基本都可以在O(1)的时间完成。

布隆过滤器的优点&缺点

优点:布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。布隆过滤器可以表示全集,其它任何数据结构都不能。

缺点:误算率是其中之一,随着存入的元素数量增加,误算率随之增加。常见的补救办法是建立一个小的白名单,存储那些可能被误判的元素。但是如果元素数量太少,则使用散列表足矣。另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

布隆过滤器的应用场景

布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等,有人会想,我直接将网页URL存入数据库进行查找不就好了,或者建立一个哈希表进行查找不就OK了。当数据量小的时候,这么思考是对的,但如果整个网页黑名单系统包含100亿个网页URL,在数据库查找是很费时的,并且如果每个URL空间为64B,那么需要内存为640GB,一般的服务器很难达到这个需求。那么,在这种内存不够且检索速度慢的情况下,不妨考虑下布隆过滤器,但业务上要可以忍受判断失误率。比较经典的案例如下:

  • Redis缓存穿透问题

Redis 是基于缓存的数据存储,极大的提升了应用程序的性能的效率,尤其是在数据的查询方面,但同时也有一些问题,比如:缓存穿透,缓存雪崩,缓存击穿。

缓存穿透,指的是查询一个数据库中不一定存在的数据。正常使用Redis查询收据的流程是,根据key去查询value,如果key不存在或者key已经过期,再对数据库进行查询,并把查询的对象,放到缓存中。如果数据库查询对象为空,则不放进缓存中。

但是如果频繁的请求查询一个不存在value的key,由于缓存中没有数据,所以每次都要去查询数据库。当对key查询的并发请求很大时,每次都访问DB,就对DB造成了影响,由于缓存不命中,每次都要去查询持久层,就失去了缓存的意义。

方法1:将数据库中的空值也缓存层中,这样查询空值就不会再去访问持久层,而是直接在缓存层访问就行。但是弊端就是缓存太多空值占用了更多的空间,可以通过给缓存层空置设立一个较短的过期事件来解决,例如60S。

方法2:这时候只要增加一个布隆过滤器,后端每次插入一个数据时,都在布隆过滤器中设置一次。每当需要查询后端时,先判断key在后端是否存在,这样就能避免了后端的压力。

  • 推荐去重问题

例如新闻客户端的推送去重功能,当推荐系统推荐新闻时会从每个用户的历史记录中进行筛选,过滤掉那些已经存在的记录。

实际上,如果历史记录存储在关系数据库中,去重就需要频繁的对数据库进行exists查询,当系统并发量很高时,数据库很难扛住压力。但是如果使用缓存把历史记录都放在缓存中又会占用空间太大,这时候布隆过滤器就起到作用了,它就是用来解决这种去重问题的。同时还能节省90%以上的空间,但就是稍微有那么一点不精确,也就是有一定的误判概率。

用户浏览记录存入数据库中时,需要将其设置到布隆过滤器中。查询时在过滤器上通过key的hash算法存储判断其是否存在,避免了每次是否存在都要去数据库查询一遍,这样推送新闻时只要通过布隆过滤器判断,如果不存在就推送。可能由于误判率过滤掉极小的一部分,但仍然可以保证推荐给用户的都是无重复的。

上一篇:效果展示2(原创)


下一篇:布隆过滤器(Bloom Filter)详解