白话布隆过滤器

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

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

Bloom filter

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

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

哈希函数应该尽可能保证数据分布均匀，此外，为了保证运行效率，应该选择尽可能快的哈希函数，比如：murmurhash、FNV，至于 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

实际使用中，我们可以先确认系统能忍受的最大误报率是多少，然后再确认 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 模块。