聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

白话布隆过滤器

2020-06-22 14:17 浏览: 165 次 我要评论(0 条) 字号:

日常开发中,一个常见需求是判断一个元素是否在一个集合中。比如当你在浏览器中输入一个网址的时候,浏览器会判断网址是否在黑名单里。通常的解决方案是直接查询数据库,看看是否存在相关的记录,不过这往往会比较慢,于是我们又会引入缓存来提升速度,可是当数据比较多的时候,缓存会消耗大量的内存。有没有既速度快又节省内存的解决方案呢?本文介绍一种算法:布隆过滤器(Bloom filter)。

所谓布隆过滤器,是由一个名叫布隆的人提出的:当一个元素被加入集合时,通过多个哈希函数将元素映射到一个比特数组中的若干个位置,并把它们置为 1 ,查询时,只要看看这些位置是不是都是 1 就知道元素是否(可能)在集合中了:如果这些位置中有任意一个是 0,那么此元素一定不在集合中;如果都是 1,那么此元素可能在集合中,注意是「可能」在,也就是说「可能」不在,这被称作「False positive」。实际使用中,布隆过滤器可以用在对 False positive 不那么敏感的领域,比如开头说的检测网址是否在黑名单里的问题,因为用户浏览的大部分网址都是正常的网址,所以可以先用布隆过滤器进行一次初筛,一旦发现可疑目标后再查询数据库确诊。

Bloom filter

Bloom filter

如上图所示,字符串「Hello」被哈希函数映射到比特数组中索引 1 和 3 的位置,布隆过滤器就会把这些位置置为 1;字符串「Bloom」被哈希函数映射到比特数组中索引 1 和 2 的位置,布隆过滤器也会把这些位置置为 1。细心的读者可能已经发现,两个字符串在哈希的时候发生了碰撞,都映射了索引 1,是否有问题?好消息是问题不大,布隆过滤器使用的是多个哈希函数,查询时,必须所有的哈希函数映射的索引位置都确认才行;坏消息是如果比特数组长度不够大,那么随着新元素的不断加入,比特数组中的大部分索引位置都会被置为 1,后续的误报率会越来越大。

由此可见,在使用布隆过滤器的时候,如果想获得一个可接受的误报率,那么首先要选择合适的哈希函数,其次要协调好哈希函数数量和比特数组大小之间的关系。

哈希函数应该尽可能保证数据分布均匀,此外,为了保证运行效率,应该选择尽可能快的哈希函数,比如:murmurhashFNV,至于 md5、sha1 等等,并不是好选择。

如果使用很多很多的哈希函数,加上很大很大的比特数组,那么无疑可以把误报率降低到趋近于零,不过出于效率和成本的考虑,我们不会那样干,实际使用中,会通过调整哈希函数数量和比特数组大小之间的关系,来获得一个可接受的误报率,在 wiki 中给出了计算方法,本文省略证明过程,直接给出结论:「k = (m/n) ln2」,其中:k 是哈希函数的个数;m 是比特数组的大小;n 是过滤器中元素的数量;ln2 约等于 0.693:

  • 如果比特数组大小是过滤器中元素数量的 4 倍(也就是 m/n = 4),那么哈希函数数量为 3(实际为 2.77 四舍五入)的时候,误报率(14.7%)相对较低。
  • 如果比特数组大小是过滤器中元素数量的 6 倍(也就是 m/n = 6),那么哈希函数数量为 4(实际为 4.16 四舍五入)的时候,误报率(5.61%)相对较低。
  • 如果比特数组大小是过滤器中元素数量的 8 倍(也就是 m/n = 8),那么哈希函数数量为 6(实际为 5.55 四舍五入)的时候,误报率(2.16%)相对较低。

Bloom Filters – the math 一文中,对 k 和 m/n 的关系进行了详细的统计分析,供参考:

False positive

False positive

实际使用中,我们可以先确认系统能忍受的最大误报率是多少,然后再确认 k 和 m/n。假设我们觉得 2% 左右的误报率是可以接受的,那么我们就可以选择 k=6,m/n=8,此时虽然看上去保存 n 个元素就需要创建 8n 个大小的比特数组,从数值上看似乎有点浪费空间,但是别忘了,我们用的是比特数组,8bit=1byte,换句话说,此场景下,保存一个元素仅需要一个字节的成本,所以说相比较直接保存元素本身而言还是很节省内存的。

虽然布隆过滤器简单好用,但是它也有自己的缺点:不支持删除元素。原因是如果删除元素,那么需要把元素对应的若干个索引位置的值从 1 置为 0,可是这些索引位置可能关系到别的元素,一旦置为 0,所有的相关元素都会被删除。如果你使用布隆过滤器,并且需要删除元素的话,那么你只能删除元素后重建整个数据结构。当然,你也可以选择其它的算法,比如布谷鸟过滤器(Cukoo filter),它支持删除元素,更酷,但是也更复杂,篇幅所限,本文就不多说了,有兴趣的读者可以参照相关资料自行学习。

本文关于布隆过滤器就介绍到这里,如果大家跃跃欲试的话,很多现成的选择,比如:

  • Mozilla 开发的适用于 openresty 的 lua 版本布隆过滤器:Lua Bloom Filter Module
  • Willf 开发的 Golang 版本布隆过滤器:bloom

当然,明白了原理,自己实现一个也不难,如果使用 Redis 的话,直接包装一下 Bitmap 就可以,如果还想更简单点,可以直接使用 RedisLabs 提供的 RedisBloom 模块。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复