什么是Bloom Filter

布隆过滤器本质上是一种高效的数据结构,概率型的数据结构。特点是能够高效的插入和查询,可以告诉你“某个数据一定不存在或者可能存在”,但并不能告诉你一定存在。

相比于传统的List,Set等数据结构,它的占用空间更小,缺点是返回的结果是概率性的,不是确切的。

Bloom Filter实现原理

实现原理

原理:当一个元素被加入集合时,通过k个散列函数将这个元素映射成一个bit数组中的k个点,把它们置为1。如果这些点有任何一个0,那么被检元素一定不存在;如果都是1,则被检元素就很可能存在。

Bloom Filter实现

布隆过滤器有许多的实现,可以参考Guava中对Bloom Filter的实现。

使用Bloom Filter,设置两个点

  • 预估数据量n
  • 期望的误判率fpp

实现Bloom Filter,考虑两个点

  • hash函数的数量
  • bit数组的大小

布隆过滤器数据结构

假设我们需要将“dustin”的值映射到布隆过滤器中,通过3个哈希函数生成3个哈希值,并对每个哈希值指向 bit 位置1,哈希值为1,4,7,如下图

向布隆过滤器插入dustin

然后我们继续存入一个值“China”,哈希函数返回3,4,8,图变成下图

向布隆过滤器插入China

其中,4这个bit位由于两个值的哈希函数都返回了这个bit为,所以覆盖了。

现在想要查询 “Japan” 这个值,假设返回2,3,4,我们可以发现2这个bit位为0,那么这个值就不存在。而我们查询“dustin”,返回1,4,7,三个bit位都为1,那么“dustin”这个值就可能存在,但是不是一定存在。

为什么呢?因为随着增加的值越来越多,被置为1的bit位也越来越多,这样的话,即使某个值没有被存储过,但是有可能出现他的哈希函数返回的bit位都为1,那么我们的程序还是会判定为存在。

如何选择Bloom Filter的哈希函数个数和数组长度呢?

很显然,很小的布隆过滤器很快就会把所有的bit位都置为1,那么所有的查询结果都是可能存在,就起不到过滤的作用了。

但是数组越大占用内存也越大,哈希函数越多,误判率越低但是效率也越低,所以,还是要做权衡。

Size of bit array(m)

k为哈希函数个数,m为布隆过滤器长度,n为插入元素个数,纵坐标p为误判率,至于这个图如何推导,可以上google上查,我们只记住就行。

Bloom Filter使用场景

布隆过滤器的使用可以减少磁盘IO或网络请求,只要判定一个值必然不存在,就可以直接返回,不需要进行后续昂贵的查询请求了。

  • 在缓存穿透问题上,使用布隆过滤器判断数据是否存在,不存在直接返回
  • 海量数据去重:爬虫系统中对成千上万的url的去重等
  • 邮箱系统的垃圾邮件过滤功能

Bloom Filter的缺点

  • 存在误判。可以根据业务的容忍度,控制误判率。
  • 删除困难。一个放入布隆过滤器的元素映射到bit数组k个位置上都是1,删除的时候不能简单的直接将这些bit位置为0,因为可能会影响到其他元素的判断。可以采用
  • 布隆过滤器的不当使用有可能产生大Value,增加redis等的阻塞风险,生产环境建议对体积庞大的布隆过滤器进行拆分。(拆分的大致做法:拆分成多个小bitmap,然后一个key的所有哈希函数必须都落在同一个bitmap上,不要分散在不同的bitmap上即可)