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。