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

DataDomain中的重复数据检查：

上篇我们介绍了Bloom Filter，以及其以“正确率换空间”的特性。而它的这种特性，非常适合需要对海量数据进行快速检索而内存空间又有限的场景。比如在重复数据删除系统(DataDomain)中可以配合fingerprint Cache，加速重复数据的检查。

我们都知道DataDomain(DD)采用数据块级的去重技术，文件或数据流被切割为较小的segment， 然后使用160-bit的SHA1算法求取每个segment的哈希值，这些哈希值被称为segment fingerprint，用来标志一个segment。具有相同fingerprint的两个segment即为duplicate segment。当有数据写入的时候，DD会首先把数据切成很多小的segment，然后计算出fingerprint，再与系统上现有的fingerprint进行比较，来判断这个数据块是否是重复数据。

为了保证DD的写性能，我们希望快速判断新来的数据是否是重复数据。

最直接的方式是在内存中维护所有的fingerprint。fingerprint的比较直接在内存中完成，性能最优。但是采用这种方式会带来巨大的内存开销。假设现有一台DD上有8TB去重后的数据，以平均一个segment大小8KB来计算，那么系统上一共存在10亿个这样的fingerprint。每个fingerprint 20byte, 我们需要20GB的内存只是来存储所有的fingerprint！显然这种方式是不能接受的。

既然内存不够维护所有的fingerprint，那么通常的做法就是缓存一部分fingerprint在内存，当有新的fingerprint需要比较的时候，先检查Cache，如果Cache没有再检查disk上的。DD就是这样做的，其使用一种叫做Locality Preserved Caching(LPC)的缓存技术来加速重复数据判断，该技术利用了备份数据的一个特性：对同一个文件进行多次备份，其segment出现的序列是相同的。假设有一个1MB的文件被切成了100多个小的数据块，在每次对这个文件进行备份的时候，这些segment总是以相同的顺序出现的。即使某次文件的内容中有了一些修改，会有新的segment产生，但是剩下的segment也会以同样的顺序出现。利用这个特性，当DD发现一个写入的segment和DD上的segment x重复的时候，会尽量把与x来自同一个文件的后续fingerprint放到Cache中，以提高后面的Cache命中率。

但是只有Cache还不够，我们并不能保证在Cache中没有命中的fingerprint一定不在DD上。所以当写入的segment在Cache中没有对应的fingerprint时，我们还是要去disk上找, 这就带来性能瓶颈。那么DD是怎么解决这个问题的呢？就是用前面说的Bloom Filter嘛！

Bloom Filter在DD中的应用：

使用Bloom Filter来表示DD上已有fingerprint的集合，从而只需要很少的内存就可以快速判断出待写入的segment哪些肯定是新的segment，哪些可能是重复的segment。把肯定是新的segment过滤掉，DD只需要继续检查那些可能重复的segment。

DD将这个Bloom Filter称为Summary Vector。和典型的Bloom Filter一样，Summary Vector也由一个很长的位向量组成，这个位向量被初始化为全0。当有新的fingerprint需要加入的时候，会将该fingerprint传入不同的HASH函数，计算出几个HASH值，再映射到位向量上将对应的位设为1.

当需要查询该fingerprint是否在DD上时，同样将通过fingerprint计算出的HASH值，映射到位向量上，如果对应的位置有一个不为1，则可以判断出该fingerprint一定不在DD上。

使用Summary Vector在存在一定误判的基础上大大降低了判断重复数据时对内存的要求，以m/n=8为例，对于8TB的非重复数据，Summary Vector只需要1GB的容量就可以把绝大多数(2%的误差率)的新segment过滤掉！

下面这张图描述了DD进行重复数据判断时的流程，我们可以看到DD分别通过Cache和Summary Vector来过滤掉不必要的segment index lookup的操作。Cache会首先过滤掉很大一部分重复的segment, 接下来Summary Vector又会把绝大多数新的segment过滤掉，受益于Bloom filter以及Cache，DataDomain系统可以减少99%的磁盘访问，从而利用少量的内存空间大幅提高了数据块查重性能。

总结：

除了在重复数据删除系统中的应用，Bloom filter还被广泛应用于各种领域，比如拼写检查、字符串匹配算法、网络包分析工具、Web Cache、文件系统。下面列了一些Bloom Filter在其他领域的应用，有兴趣的同学可以看看：

1. Google BigTable, Apache HBase  Apache Cassandra, 和 Postgresql使用Bloom Filter减少对不存在的行列的磁盘查询， 提高数据库查询操作性能。
2. Google Chrome 使用Bloom Filter来判断恶意URLs。任何URL都会先经过客户端的Bloom Filter作检查，只有当Bloom Filter返回positive的时候，才会将URL发到Google服务器上作完整的检查。
3. Bitcoin 使用Bloom Filter加速钱包的同步

作者简介：

Walker Huang from Avamar

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