使用Bloom Filter提高索引效率（上）

Bloom Filter 介绍：

在日常生活中，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用hash table来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，雅虎或者Gmail总是需要过滤垃圾邮件，一个办法就是记录下那些发垃圾邮件的 email 地址。如果用哈希表，每存储一亿 个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹， 然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。而全世界少说也有几十亿个发垃圾邮件的地址，因此可能需要上百 GB 的内存，一般服务器是无法存储的。

而Bloom Filter作为一种传统hash table的改良算法。通过“正确率换空间”的思想，摆脱了传统hash table的存储方式，允许用户在错误率和存储空间之间作权衡，很好的解决了在存储空间有限的条件下，快速判断元素是否在海量集合中的问题。

Bloom Filter是1970年由一个叫布隆的提出的，目前广泛应用在很多互联网应用中，其主要具有下面两个特点：

1. 查询时间和传统hash索引的方式相当，空间效率却远远超过一般的hash算法

2. 在保证空间效率的同时，会有一定的正向错误率

它实际上由一个m位的位数组和k个hash函数组成。初始状态下，位数组中所有位的值都设置为。我们假设取m=10, k=3, 用蓝色表示某位为0，红色表示为1：

插入元素的过程是三步走：

1. 计算k个hash值

2. 将k个hash值对m取模得到k个下标

3. 将数组中k个下标对应的位设置为1

比如向刚才的Bloom Filter插入元素“Alice”。分别用3个hash函数计算“Alice”的hash值，将hash值对10取模，得到在[0, 10)范围内的r1、r2、r3，假设计算结果为：

r1 = h1("Alice") % m = 1
r2 = h2("Alice") % m = 3
r3 = h3("Alice") % m = 5

于是将数组中第1位、第3位和第5位的值置为1：

再插入元素“Bob”的过程还是一样的，假设：

r1 = h1("Bob") % m = 8
r2 = h2("Bob") % m = 2
r3 = h3("Bob") % m = 3

那就将数组中第2位、第3位、第8位的值置为1（值已经为1的第3位不动）：

以此类推，Bloom Filter运行过程中不断插入新元素，位数组里的0逐渐被翻转成1.

那我们怎么判断元素是否在集合里呢？同样还是三步走：

1. 计算k个hash值

2. 将k个hash值对m取模得到k个下标

3. 检查数组中k个下标对应的位是否都为1

如果元素对应的hash值在数组中不全为1，那么该元素肯定不在集合中。

但是如果元素对应的hash值在数组中全为1，该元素就一定在集合中吗？答案是不一定。这就是Bloom Filter会产生正向错误率的地方。那么Bloom Filter的正向错误率有多大？

经过一系列严谨的数学推导，Bloom Filter的误报率是：

其中m表示Bloom Filter中位数组的长度，n表示已有的元素个数，k表示hash函数的个数。那么误报率到底是多大呢？下图就是一个当m/n=8时的例子。可以看到，此时最佳的误差率仅在2%左右。

总结：

现在我们学习了Bloom Filter这种数据结构，了解了它是怎样通过允许少量的错误(Fale Positive)来节省大量的存储空间的。在下篇的文章中，我们一起来看看DataDomain中的重复数据检查，以及Bloom Filter如何在其中发挥威力的。

作者简介：

Walker Huang from Avamar

2016年2月加入Dell EMC Avamar，现在主要从事Avamar与DataDomain集成数据备份系统的开发和维护。资深跑友，有7次全程马拉松完赛经历。