布隆过滤器（Bloom Filter）1

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）



现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

 

 

Bloom Filter 数据结构的应用:

 上一篇文章简单介绍了 Bloom Filter 数据结构的原理，现在介绍一下它的应用。

    应用1：存储字典。大家可能对于 Word 的拼写检查功能非常了解，当你拼错一个单词的时候，Word 会自动将这个单词用红线标注出来。 Word 的具体工作原理不得而知，但是在另一个拼写检查器 UNIX spell-checkers 这个软件中用到了 Bloom Filter。UNIX spell-checkers 将所有的字典单词存成 Bloom Filter 数据结构，而后直接在 Bloom Filter 上进行查询。

出错的情况：漏掉出错的单词。

  应用2：数据库的 semi-join 操作。举个例子，TA 存储了 employee / city 字段， TB 存储了 city / cost of living 字段。现在需要将所有 cost of living > 50,000$ 的 employee 找出来，显然需要 join TA 和 TB。直观地看，需要将 TB 的所有 city / cost of living 字段值发给 TB，然后找到 city 相匹配的 join 一下，得出所有 employee / city 字段值。这样做是又费时又费力的。Bloom Filter 的做法是把 TB 的 city 字段做成 Bloom Filter 数据结构发给 TA，让 TA 中的 city 在这个 Bloom Filter 上做匹配，把所有找到的 employee / city 再重新发个 TB 做 join。 这样做相当于过滤掉了一部分不存在于 TA 中的city，提高了执行效率。

出错的情况：不存在。

    应用3：分布式缓存技术。Web 缓存技术的原理是一个 proxy 如果要请求网页，它会先查看其他 proxy 是不是有这个网页，而不是直接向Web 请求。这样做可以提高下载网页的速度。为了减少网络传输的数据量，proxy 定时广播自己以 Bloom Filter 格式存储的 url，而不是把自己庞大的 url 列表广播给其他 proxy。

出错的情况：某 proxy 以为一个 proxy 中存在某个 url，而实际上那个 proxy 中并没有这个 url。因此会造成一定的延迟。

因为，缓存的内容频繁变化，所以 proxy 通常使用 counting bloom filter 存自己缓存的 url, 而只用 0-1 bloom filter 存别的 proxy 缓存的 url。

    应用4：p2p。p2p 技术的基本原理是 peer 从源站下载文件的同时也从其他 peer 处下载文件。通常是一个很大的文件分布式存储在很多个 peer 上，这样就要求在下载时 peer 们相互合作，peer A 需要把自己有但 peer B 没有的数据发送给 peer B，使用 bloom filter 可以方便地进行集合运算 SA-SB 来找到需要传输的数据。

出错的情况：可能有 SA-SB 中的数据被漏掉，没有传到 peer B。