基于双布鲁姆过滤器的数据排重技术

席晔文，杨金民

湖南大学 信息科学与工程学院，长沙 410082

基于双布鲁姆过滤器的数据排重技术

席晔文，杨金民

湖南大学 信息科学与工程学院，长沙 410082

1 引言

随着计算机技术的飞速发展，数字信息量呈爆炸式的增长，占用的储存空间越来越多。有研究指出，一般系统中数据有60%是冗余的，这个数据还会随着系统运行时间的推移而继续增长。由此，重复数据删除技术[1]得到了大量的关注：它使系统数据的存储空间暴增问题得以缓解，对系统中已存在的资源进行最大化利用；在网络数据传输前将重复数据查找出来，减少对网络带宽的占用。

如何简洁地表示海量的数据信息，如何快速地在海量数据中快速查找重复数据，是排重技术应用于大规模数据管理的关键。

现在流行的排重技术有Message Digest Algorithm MD5（MD5码）[2]排重法，MD5码是对任意长度的明文输入，通过函数计算，得出的只属于该输入的独一无二的指纹值，所以可以通过比对MD5码来验证2个文件是否相同。它的具体算法流程如下：将系统中所有文件计算MD5码存储到集合中并建立索引，称为集合S。当更新文件时，计算传入文件MD5码并在集合S中查找，若发现集合中存在相同的MD5码，说明该传入文件是重复文件，删除该文件，就达到了数据排重的目的。在效率方面，其查找过程就是将传入文件MD5码与全集S的MD5码元素按集合索引一条条比对，时间复杂度为O(n)，若传入文件全为新文件，则每次查找都要将集合从头查到尾，所以该算法的查找时间并不尽人意，没有对MD5码进行任何处理直接进行查找，对其利用率还处于原始阶段。而通过使用布鲁姆过滤器技术来处理MD5码可以帮助减少查找重复数据的耗时。

2 相关技术

标准布鲁姆过滤器（Bloom Filter）[3-5]是一种高效、快速、精简的信息表示查找技术，其应用相当广泛，如P2P节点协作交互[6-7]和文件操作[8]等。Bloom Filter原理是将数据集合里的所有元素通过多个相互独立的哈希函数映射到位串向量上，Bloom Filter所需存储空间与元素自身大小和集合规模无关，使用一个共有m位的V向量来表示n个元素的集合，则每个元素平均只需要m n比特位，所以使用Bloom Filter表示数据可以极大地节约存储空间。

布鲁姆过滤器的具体原理如图1：数据集合s= {x1，x2，…，xn}共n个元素分别代入到k个相互独立的哈希函数，计算地址并映射到长度为m位的位串向量V向量中，所以一个布鲁姆过滤器由k个相互独立的哈希函数 {h1，h2，…，hk-1，hk}（它们值域为 {0，1，…，m}）和一个位串向量（它的向量初始值全为0）组成。

图1 布鲁姆过滤器结构示意图

对向量进行插入元素操作时，当一个向量地址多次被置为1，只有第一次会起作用，后面几次将没有任何效果。在图2中，X1和 X2都映射到了同1个向量地址（从左边数第五位）。这也是Bloom Filter出现假阳性误判[9]（false positive）的原因。

图2 插入元素

查询 y是否属于数据集合，将 y代入k个哈希函数，如果所有hi(y)的位置不全为1(1≤i≤k)，那么就判定y不是集合中的元素，否则说明 y可能是集合中的元素。每查询一个元素只需比对向量相应地址是否为1，这就是使用Bloom Filter排重远快于MD5码排重的原因。图3中 y1不是集合中的元素，y2或者属于这个集合；或者刚好是一个假阳性误判（把不属于这个集合的元素误判属于这个集合），这是因为查询元素的地址可能是由其他元素置1的。

图3 查询元素

因为假阳性的存在，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间节省与耗时的极大缩短。因此，布鲁姆过滤器是允许存在一定误判的前提下，在查询准确率与存储代价、算法耗时之间的折中。

3 双布鲁姆过滤器排重算法

3.1 算法设计思想

由于MD5码排重算法对MD5码没有进行任何处理，直接使用MD5码进行重复查询，导致算法查找耗时过长的缺点。使用布鲁姆过滤器技术将文件MD5码映射到一个位串向量上，查找时只需进行位与操作即可判断查询元素是否已存在，这极大地减少了查询元素的耗时。

但是使用布鲁姆过滤器，若只按文件为单位计算MD5码值排重，很可能一个大文件中已经包含了另一个小文件中的全部内容，但由于这两个文件大小都不相同，它们的MD5码也是不同的，小文件作为重复数据得不到排重，这说明文件级单布鲁姆过滤器排重粒度太大，无法满足高精度的数据排重要求。

如果将文件分割成等大小的数据块，对所有数据块的MD5码集合以布鲁姆过滤器向量形式表示进行排重。这种数据块级单布鲁姆过滤器排重虽然进入文件内部进行数据排重，但文件的大量分块，大大增加了重复元素查找的工作量，耗时也数倍增长。

在保证高精度排重的前提下，提高排重速度，减少算法耗时，就是新算法设计的中心思想。数据块级单布鲁姆过滤器排重算法固然完成了高精度的排重，但在算法的排重过程中，有很多完全相同的文件被分割成了大量的数据块后再一一排重，若在数据级排重前先进行一次文件级MD5码排重，将所有相同文件先排重掉，就可以为数据块级排重减少相当大的工作量，从而提高算法效率。

3.2 算法设计

新算法使用双布鲁姆过滤器对文件进行2级排重。第一级采用文件级的重复数据删除策略，计算文件MD5码值，在预先映射好的文件级布鲁姆过滤器向量上查询，发现重复值则删除文件；第二级采用数据块级的重复数据删除策略[10-11]，通过预先设定好的数据块大小将第一级排重过滤后的文件分块，计算数据块MD5码，通过映射到数据块级布鲁姆过滤器向量上比对，对数据块排重。

该算法不同于数据块级单布鲁姆过滤器一开始就对文件进行分割扫描，而是先进行以文件为单位的重复数据查找，通过第一次排重对文件集合进行过滤，减少第2级过滤器需要排重的文件数，再进行数据块级扫描排重，以提高数据排重的细粒度。在重复文件率高的场合，可以既达到数据级排重的效果，又有趋近于文件级排重的速度。

新算法的具体流程如下：

（1）将原有文件按文件级和数据块级分别计算MD5码值，并映射为相应的布鲁姆过滤器向量BF1，BF2。

（2）计算新传入文件的MD5码，在第一级布鲁姆过滤器中查询该MD5码值。

（3）若有该MD5码，说明该文件为重复文件，删除文件，结束算法。

（4）若无该MD5码，将该MD5映射到第一级布鲁姆过滤器向量中。

（5）将该文件按设定的数据块大小分割，并计算数据块的MD5码值。

（6）在第二级布鲁姆过滤器中查询数据块MD5码值。

（7）若有该MD5码，说明该数据块为重复，删除数据块，结束算法。

（8）若无该MD5码，说明是新数据块，存储，将该MD5更新到第二级布鲁姆过滤器向量中。

图4 算法流程图

3.3 算法误判率分析

（1）假阴性误判率 f-：该算法基于标准布鲁姆过滤器实现，将数据MD5码映射到对应的BF向量上，向量对应位不全为1则判定该数据不属于集合，数据属于集合则向量对应位全为1，所以算法出现假阴性误判率（将属于集合的数据判断为不属于集合）为0%，这说明算法不会将重复文件判断为新文件，对信息进行重复储存。

（2）假阳性误判率 f+：设第一级布鲁姆过滤器BF1假阳性误判率为 f1，第二级布鲁姆过滤器BF2假阳性误判率为 f2，2级布鲁姆过滤器采用的都是参数相同的标准布鲁姆过滤器，它的假阳性误判率为 fbf，所以2层布鲁姆过滤器单独的假阳性误判率都为：

（3）设有查询文件集合S，它与原始文件的重复率为r，在第二级排重中，BF2的文件集合S′是第一次排重中减去重复文件和第一级假阳性误判文件剩下判为不重复的文件，这其中没有误判文件（布鲁姆过滤器不存在假阴性误判）：

设该算法误判率为 f，为假阴性误判文件加上假阳性误判文件与全集合文件的大小之比。假阴性误判率为0，则

从式（4）可知该算法误判率只与选择的布鲁姆过滤器假阳性误判率和查询文件集合的重复文件率有关。在选定布鲁姆过滤器参数后，理论上该算法对数据冗余越多的系统排重误判率越低。

3.4 算法时间空间复杂度分析

3.4.1 算法时间复杂度

在初次运行该算法时，需要把原系统中所有文件分别映射为文件级和数据块级布鲁姆过滤器向量，设T1为将原计算机里的文件映射到第一级布鲁姆过滤器向量BF1的时间；T2为将原计算机里的文件按分割块大小映射到第二级布鲁姆过滤器向量BF2的时间，使用标准布鲁姆过滤器插入一个元素，需要进行k次哈希运算，所以一个元素插入操作的时间复杂度为O(k)。这2个耗时只在初次运行时出现，不计入一般排重时间开销，设本算法的耗时为T：

（1）Tmd5为算法对查询集合文件和第一次过滤后不重复文件分割的数据块计算MD5码的时间。

（2）T3为文件MD5码代入 BF1中查询的时间，T4为数据块MD5码代入BF2中查询的时间。当查询元素是否在集合中时，只需进行k次哈希计算。这也是使用布鲁姆过滤器查询优于MD5码直接索引查询的地方，它使得快速匹配成为可能，因为布鲁姆过滤器的查询操作是在位向量上进行，按位与操作。

（3）S的文件个数不会改变，而S和S′之间的关系由式（2）可知，当新算法在面对重复率相当大的数据集的时候，留给BF2排重的文件数也大幅减少，所以在实际应用中设定好布鲁姆过滤器误判率 fbf后，算法耗时将随着查询集合的重复率的增大而减少。

3.4.2 算法空间复杂度

作为一种精简的信息表示方案，对于n个元素的集合，只需要m位向量V，其空间复杂度为O(m)。同时在分布式系统的文件排重中，排重算法将BF1和BF2传送到待传输机器上，比传输占用空间更大的MD5值集合，也可以帮助节省网络带宽。

4 实验分析与结果

在实际测试中，使用的操作系统为Windows XP，机器的配置如表1。

表1 实验配置

实验具体为：在一个目录中存放有8 000个待传输文件的集合B，将集合B传输到另一个目录A下。改变集合B中的文件使之与目录A中的文件有不同的重复文件率r，文件分割块设定为0.5 MB。分别使用MD5排重、文件级单布鲁姆过滤器排重、数据块级单布鲁姆过滤器排重、双层布鲁姆过滤器排重新算法将集合B传输到目录A下。图5～图7、表2从各方面比较了4种不同算法的性能：（1）数据集重复文件率与数据排重率关系（r-p见图5）。（2）数据集重复文件率与算法耗时关系（r-t见图6）。（3）数据集重复文件率与实验重复文件误判率关系（r-f见图7）。（4）4种排重算法的理论误判率与实际误判率（见表2）。

图5 集合重复文件率与数据排重率的关系

（1）图5发现，对同一数据集，采用相同参数的布鲁姆过滤器，双层排重新算法在4种排重算法里的排重效果是最好的，对4个数据集的排重率分别达到61.62%、66.07%、70.12%、72.83%，其他3种算法里只有数据级单布鲁姆过滤器排重率与之接近。

图6 集合重复文件率与算法耗时关系

图7 集合重复文件率与算法误判率关系

（2）图6得出，同排重率相近的数据块级单布鲁姆过滤器相比，双布鲁姆过滤器排重算法最少减少了43%耗时，其他3种算法耗时与文件重复率参数无关，算法时间基本保持不变，而双布鲁姆过滤器排重算法随着r的提高耗时继续保持下降，当重复率达到60%时，新算法比数据块单布鲁姆过滤器减少了68%耗时，这是因为新算法在1级排重中已经将重复文件进行了排重，减少了2级排重的工作量，所以新算法对于重复率高的数据集有着良好的耗时表现，随着重复率的提升，耗时逐渐向文件级单布鲁姆过滤器排重算法靠近。

（3）图7得出，实验中MD5码排重算法保持0误判率；布鲁姆排重算法使用的标准布鲁姆过滤器的参数取值分别为n=8 000；m=131 072；k=4，2种单层布鲁姆过滤器排重算法误判率基本保持不变，稍有上下浮动，说明重复文件比例对单层布鲁姆过滤器排重算法误判率没有影响；而双层布鲁姆过滤器排重算法同理论分析的一样，随着实验数据集重复文件比例的增加，误判率呈减少趋势，向单层布鲁姆过滤器排重算法误判率靠拢。

表2 4种算法排重误判率

（4）表2得出，当布鲁姆排重算法使用的标准布鲁姆过滤器的参数取值分别为n=8 000；m=131 072；k=8时，使用双布鲁姆过滤器排重算法，平均每10 000个文件出现7个误删除，相比单层布鲁姆过滤器平均每10 000个文件出现5个误删除差别不大，对于绝大多数排重系统，该算法是稳定可靠的。并且随着排重系统中冗余数据的增多，新算法不管是耗时还是误判率都会有更好的表现。

5 结束语

双布鲁姆过滤器排重算法的文件级和数据块级的双重排重结构是算法的优势所在。通过文件级排重减少了第2级排重的工作量，减少了算法耗时，通过数据块级的排重获得了数据块级的排重细粒度。实验表明，双布鲁姆过滤器排重算法在保持低假阳性误判率的前提下，对4个数据集的排重率分别达到61.62%、66.07%、70.12%、72.83%，虽然数据块级单布鲁姆过滤器排重率与新算法接近，但是耗时上新算法比之提高了43%、55%、62%、68%。随着数据集重复率的继续增加，新算法将呈现出越来越好的排重判断率，所需的时间也将随之减少。

本算法还有可进一步提高的空间，如采用改进型布鲁姆过滤器[12-13]满足集合动态增长问题，使用CDC检测技术[14]、滑动块分割技术[15]根据文件自身内容的特征和变化对文件进行分割。

[1]敖莉，舒继武，李明强.重复数据删除技术[J].软件学报，2010，21（5）：916-929.

[2]廖海生，赵跃龙.基于MD5算法的重复数据删除技术的研究与改进[J].计算机测量与控制，2010，18（3）：635-638.

[3]谢鲲，文吉刚，张大方，等.布鲁姆过滤器查询算法[J].软件学报，2009，20（1）：96-108.

[4]谢鲲，张大方，文吉刚，等.布鲁姆过滤器布尔代数探讨[J].电子学报，2008，36（5）：869-874.

[5]谢鲲，闵应骅，张大方.分档布鲁姆过滤器的查询算法[J].计算机学报，2007，30（4）：597-607.

[6]Jonathan L，Jacob M T，Laura S，et al.Self-organization in peer-to-peer systems[C]//Proc of the 10th Workshop onACM SIGOPS European Workshop.Saint-Emilion：ACM，2002：125-132.

[7]谢鲲，张大方，谢高岗，等.基于轨迹标签的无结构P2P副本一致性维护算法[J].软件学报，2007，18（1）：105-116.

[8]Gremillion L L.Designing a bloom filter for differential file access[J].Communications of the ACM，1982，25（9）：600-604.

[9]Mitzenmacher M.Compressed bloom filters[J].ACM Trans on Networking，2002，10（5）：604-612.

[10]付印金，肖侬，刘芳.重复数据删除关键技术研究进展[J].计算机研究与发展，2012，49（1）：12-20.

[11]马建庭，杨频.基于重复数据删除的多用户文件备份系统[J].计算机工程与设计，2011，32（11）：3586-3589.

[12]AlmeidaP S，BaqueroC，PreguiçaN，et al.Scalable bloom filters[J].Information Processing Letters，2007，101：255-261.

[13]肖明忠，代亚非，李晓明.拆分型Bloom filter[J].电子学报，2004，32（2）：241-245.

[14]Bobbarjung D R，Jagannathan S，Dubnicki C.Improving duplicate elimination in storage systems[J].ACM Trans on Storage，2006，2（4）：424-448.

[15]Jain N，Dahlin M，Tewari R.Taper：tiered approach for eliminating redundancy in replicasynchronization[C]// Procofthe4th Usenix Confon Fileand Storage Technologies（FAST 2005）.Berkeley：USENIX Association，2005：281-294.

XI Yewen,YANG Jinmin

School of Information Science and Technology,Hunan University,Changsha 410082,China

Aiming at the disadvantage of file level single bloom filter duplicate data delete algorithm deletes duplicate data only at file size,block level single bloom filter duplicate data delete algorithm’s time-consuming is too much.In this paper, it uses 2 bloom filter,creates a 2 level duplicate data delete algorithm structure-file level and block level.The experimental results show that,double bloom filter duplicate data delete algorithm could delete duplicate data at block level,keep false positive error rate at a low level,time-consuming gets 43%～68%shorter compared with block level single bloom filter duplicate data delete algorithm.

duplicate data delete;query elements;bloom filter;MD5;false positive error rate

针对文件级单布鲁姆过滤器排重算法只能以文件为单位进行数据排重，数据块级单布鲁姆过滤器排重算法耗时过多的缺点，采用2个布鲁姆过滤器，创建文件级和数据块级2级数据排重的算法结构。实验结果表明，双布鲁姆过滤器排重算法可以以数据块为单位对数据排重，在保持低假阳性误判率的同时，相比数据块级单布鲁姆过滤器排重算法耗时缩短了43%～68%。

重复数据删除；集合元素查询；布鲁姆过滤器；MD5；假阳性误判率

A

TP311.13

10.3778/j.issn.1002-8331.1301-0141

XI Yewen,YANG Jinmin.Duplicate data delete technology based on double bloom filter.Computer Engineering and Applications,2014,50（23）：198-202.

国家自然科学基金（No.61272401，No.61173167）；“973”子项目（No.2012CB315801）。

席晔文（1987—），男，硕士研究生，研究方向为数据处理；杨金民（1967—），男，博士，教授，研究领域为故障恢复与系统容错、系统可靠性、软件工程。E-mail：402595164@qq.com

2013-01-14

2013-03-22

1002-8331（2014）23-0198-05

CNKI网络优先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1646.008.html