0 回复 最新回复: Nov 27, 2017 11:19 PM Leo Li RSS

使用Bloom Filter提高索引效率(下)

Leo Li

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次全程马拉松完赛经历。