《基于多特征匹配和bloom filter的重复数据删除算法-张宗华.pdf》由会员分享，可在线阅读，更多相关《基于多特征匹配和bloom filter的重复数据删除算法-张宗华.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第33卷第5期 深圳大学学报理工版 v0133 No52016年9月 JOURNAL OF SHENZHEN UNIVERSrIY SCIENCE AND ENGINEERING Sep2016【电子与信息科学Electroni璐锄d bfo珊a廿蚰science】基于多特征匹配和Bloom 6lter的重复数据删除算法张宗华1，屈 英2，叶志佳2，牛新征21)国家电网公司北京电力医院信息通讯部，北京100073；2)电子科技大学计算机科学与工程学院，四川成都61173l摘要：针对EB(extreme binning)算法重复数据删除率低，磁盘LO开销大的缺陷，提出基于多特征匹配和Bloom
2、filter的重复数据删除算法DBMB(deduplication based on multifeature matching and Bloomfilter)将小文件聚合为局部性文件单元，作为一个整体进行去重处理，采用最大、最小以及中间数据块ID的多重相似性特征进行匹配，并基于Bloom filter优化磁盘数据块的查找和匹配过程结果表明，DBMB算法能有效提升重复数据删除率，降低算法执行时间，同时减少处理小文件的内存开销，性能提升显著关键词：计算技术；重复数据删除；多特征匹配；布隆过滤器；EB算法；磁盘优化中图分类号：11P 3016 文献标志码：A doi：103724SPJ12492
3、01605531Deduplication based on multifeature matching andBloom filterZhang Zonghual，Qu Yin92，Ye Zhijia2，and Niunzhen92+1)Ministry of Infb珊ation aIld Com咖nication，Beijing Electric Power H0spital，State G谢Corf)0mtion of China，Beijing 100073，PRChina2)School of Computer Science arId En舀neering，University
4、of Electmnic Science觚d Technolo影0f China，Chengdu 61173 l，Sichu龃ProVince，PRChinaAbstract：Aiming at low deduplication rate and high disk LO overhead of EB(extreme binning)，we propose adeduplication algorithm based on multifeature matching and Bloom filter(DBMB)Firsdy，we group smaU files asa local file
5、 unit in order t0 Drocess山em as a wholeThen we take tle maximum，minimum and middle ID of datachunk for similarity matching FinaUy，we optimize the pmcess of searching aIld matching disk data blocks based onBloom filterThe experiment results show tllat DBMB algorithm can efIectively increause the dedu
6、plication rate andreduce the execution timeIn the meantime，DBMB reduces tIe memory overhead of smaU files deduplication，thecomprehensive pedo咖ance is improVed signmcantlyI【ey words： computing technology； deduplication； multifeature matching； B100m filter； extreme binning； diskoDtimization重复数据删除(dedu
7、plication)是一种能有效优化存储空间、提高存储效率的技术，目前被广泛应用于数据备份和归档系统中在基于数据块的重复数据删除技术中，索引的内存占用量和运行效率是影响系统性能的关键EB(extreme binning)是Bhagwat掣11提出的一种可扩展的数据块级去重技术，能较好地缓解内存占用问题EB算法基于数据流的相似性，通过建立和维护文件的代表块(rep-Reived：20160812；Acpted：20160905Founda廿on：NationaI Natural Science Foundation of Cna(61300192)；Fund砌ental Research Fun
8、ds for山e Centml UIliveIsities(zYGX2014J052)；Inte刚ion of 0per8tional MoIlitoring and M肌agement PmjectBe可ing ElectIic Power Hospital卡Con屯叩帅ding加thor：Associate pmfessor Niu Xinzheng Email：xinzhengniuuestceducncita舶n：zhaIl异zonghua，Qu Ying，Ye za，et a1 Deduplication based on mumfeature matching a11d B100m
9、 mterJJou卜nal 0f Shenzhen Universitv Science粕d En西neering，2016，33(5)：531535(in chine)万方数据532 深圳大学学报理工版 第33卷resentative chunk)指纹索引，并将文件主体在磁盘中以指纹容器(bin)保存由于EB算法只在内存中保存文件的代表块ID，且对于每个文件的备份至多只需访问一次磁盘，有效减小了内存占用以及磁盘的访问时间然而，传统的EB算法采用文件的最小块ID作为主索引，实质是牺牲部分重复删除率来获取低内存占用，其去重率相对较低为此，张志珂等【21提出一种基于相似哈希的二级索引结构，以相似哈
10、希计算文件指纹，提高了小文件的重复数据删除率但相似哈希只适用于处理文档数据，很难满足实际应用场景中复杂多样的文件类型xia等1提出一种重复数据删除算法SiLo，该算法通过聚合强关联文件为一个数据段，挖掘数据段间的数据相似性，同时结合数据流的局部性特征，以此提高文件重删率，然而该算法对数据段大小较敏感，选取合适的段长度较困难EB算法的另一个缺陷是，虽然对于每个备份的文件至多需要访问一次磁盘，但其访问磁盘时采用顺序遍历的方式，当磁盘中存储的指纹容器较大时，遍历所需时间较长zhang等Ho对EB算法进行拓展，提出一种wWrR策略，通过同时访问和更新多个磁盘数据块和指纹，降低总的IO操作次数，然而该算
11、法未能优化磁盘数据块的查找和匹配过程，导致时间开销仍较高针对上述EB算法的缺陷，本研究提出了基于多特征匹配和Bloom filter(布隆过滤器)的重复数据删除算法DBMB(deduplication based onmultifeature matching and B100m 6lter)针对传统EB算法去重率较低，且小文件对内存占用影响较大的问题，通过聚合局部小文件为一个文件单元，采用多特征匹配进行重复数据删除处理；同时针对EB算法遍历磁盘中指纹容器耗时较多的缺陷，采用Bloom 6lter对每个存人磁盘的数据块进行记录，查询时只需通过Bloom filter再次计算即可，有效降低了磁盘
12、查询时间在两个真实数据集上进行测试，结果显示相较于EB，DBMB能降低对小文件的内存开销，并有效提高重复数据删除率和算法运行效率1 DBMB算法为了解决EB算法去重率较低以及磁盘访问开销较高的问题，本研究提出DBMB算法，主要改进思路如下：1)聚合多个小文件为局部文件单元，并对文件单元进行去重处理，提高对小文件的去重率；2)提出一种多特征匹配策略，选取文件的最大块、最小块以及中间块进行匹配，若均不同才认为两文件完全不同；否则表明存在相似部分，进行去重处理；3)采用Bloom filter，记录和维护磁盘中数据块的存储状态，使算法执行过程中无需读取磁盘数据，有效减少磁盘LO开销11小文件聚合及多
13、特征匹配在典型的存储系统中，小文件(一般小于64kbyte)所占物理空间为20左右，其文件数目却高达总数的80，在采用传统的EB算法去重时，内存开销大而去重效果较差为此，本研究提出聚合小文件为局部性文件单元，将其作为一个整体进行重复数据删除具体而言，对于在顺序存储的小文件(例如存储在同一个文件夹下)，通过聚合成局部性文件单元，将多个小文件作为一个整体进行重复数据删除，减少小文件在主索引中的记录条数，最终使小文件的内存开销得以降低为了改善EB算法去重率较低的缺陷，本研究提出一种多特征匹配的文件相似性检测策略对于一个新文件，计算所有数据块指纹，并选取具有最大、最小以及中间特征指纹值的数据块与主索引
14、中已有记录进行匹配若存在匹配成功的指纹，则可判定新文件与已存储的文件存在相同的数据块，进行去重处理只有当所有特征都不匹配时，才判定该文件不存在重复数据块，在主索引中增加一条对该文件的描述记录，分别存储代表块特征指纹，并将文件的其他数据块存入磁盘根据Broder理论”J，两个文件的最小数据块指纹相同的概率为F。n F、Pmin(日(F。)=min(日(R)=-(1)，l U，2其中，F，和疋是两个以数据块集合表示的文件；日(菇)是哈希函数同理，两文件的最大块和中间块指纹相同的概率也有类似结论由式(1)可以看出，由于采用了最小块、最大块以及中间块指纹进行特征匹配，所以理论上本研究的多特征匹配策略相
15、较于只采用最小块匹配的EB算法，在去重率方面具有更好的性能万方数据第5期 张宗华，等：基于多特征匹配和Bloom filter的重复数据删除算法12 基于Blm mter的磁盘数据块去重由于EB算法对磁盘数据块去重时，需要遍历磁盘中的指纹容器，这会造成大量的LO开销为此，本研究通过建立和维护一个B100m 6lter，当数据块存入磁盘时，记录相应状态位；当需要查询磁盘中是否存在相同数据块时，只需通过再次计算状态位的值即可，避免了将磁盘的指纹容器读人内存算法添加和查询一个元素的时间复杂度均为D(丘)(Jj为哈希函数个数)，大大提高了访问磁盘的时间效率在判断一个元素是否已存在时，Bloom 6lt
16、er会有一定的误检率(脚se positive rate)，所以需要根据数据块集合的大小，选择合适的哈希函数个数七和位数组长度m误检率的计算公式为，=(1一e“砌) (2)令p=e一“”，贝0有1n，=后ln(1一p)=一(mn)lnpln(1一p)，由对称性法则可知，当p=l2即I|=(m凡)ln 2时，误检率，取得最小值同时，当给定误检率的上限9时，位数组长度m需满足 mnlbe1b(1佃)：一罢(3)(1n 2)由式(3)可见，当已知文件数据块数量n以及系统的误检率上限9时，就能相应地计算出最佳的位数组长度m以及哈希函数个数晟妒一般根据经验来确定，本研究取001基于前文所述，改进的算法主
17、索引结构如图1其中最大、最小以及中间块ID作为文件的代表ID进行多特征匹配，位数组用于B100m矗1ter记录磁盘数据块的存储状态，文件指针则用于连接主索引记录与磁盘指纹容器代表块ID 位数组 文件指针图l改进的主索引结构Fi昏1 Stmctllre of impmVed pril岫ry index13 DBMB算法流程DBMB算法伪代码如图2，对于给定的源文件夹和目标文件夹，图2中第47行算法首先对小于64 kbyte的小文件进行聚合，并采用基于内容的分块算法(contentde6ned chunking，CDC)61对文件进行变长分块，随后基于MD5信息摘要算法计算数据块指纹第7行算法选取
18、最大、最小以及中间块ID(MD5值)作为文件代表块ID，并进行文件的多特征匹配第816行，若在主索引中找到该代表ID，则表明已存储了相似的文件，采用Bloom 61ter对磁盘中的数据块进一步匹配，并存储不同的数据块；否则，直接将所有数据块存储算法：DBMB(sourceFolder，targetFolder)输入：源文件夹sourceFolder，目标文件夹ta喀etFolder输出：主索引primaryIndex1illitialize primaryIndex；初始化主索引2readile如m sourceFolder；读取文件3for aU fileisourceFolder do4
19、iffile。size()=64 kb”e5 merlsmall 6les；聚合小文件6 chunkFile=CDC(filei)；文件分块7 chunkID=MD5(file。)；计算数据块的MD5值8 find representID f而m chuIlkID；9 if find representID fmm研maryIndex找到代表块ID10 for aU chunkIDchunkID do11 iffmd chunkIDf12 b100mFilterinsert(chunkID。)；13 bininsen(chunkID。)；14else未找到代表块ID15 bloomFilte
20、rinsert(chunkID)；16 bininsert(chunkID)；17write bin file to t棚毫etFolder；l 8retum primaryIndex图2 DBMB算法伪代码n孚2脚udo code ofDBM吣2 实验测试与分析本研究通过实验评估DBMB算法的去重性能，主要从重复数据删除率(去重率)、算法执行时间以及算法的内存开销3个维度测试，其中去重率定义为原始数据量与存储数据量之比，内存开销定义为处理1 Mbyte数据所需的内存实验采用“nuxKemel Archives数据【_7J和某公司真实的运维数据，其数据集特征如表1本研究在Linux系统下实现了
21、DBMB算法，硬件环境为24 GHz四核处理器，4Gbyte内存，500 Gbyte硬盘首先初始化Bloom filter的相关参数，由存储备万方数据534 深圳大学学报理工版 第33卷份系统的统计经验，每个指纹容器的元素数目一般不超过1 ooO，同时Bloom 6lter的误检率取001，则由式(3)可计算出最小的数组长度m为2 500字节，哈希函数个数|j=(mn)1n 2=14表l测试数据集特征Tahel 1 f：harnc“!risd冀of tl螺t data鸵ts数据集特征 Linux数据集 运维数据集数据总大小Gbyte文件总数目相似性特征文件类型10l 62888106强源代码、
22、配置文件等文档数据从1113到2633数据内容 共900个版本的Linux源代码2 569弱JSON和BSoN格式的数据库文件某公司运维系统7个月的主机负载信息21 Lill呱数据集实验对于Linux数据集，传统EB算法和DBMB算法重复数据删除后的存储空间变化如图3(a)图3(a)中横坐标表示内核代码版本，实验中是从1113到2633顺序排列；纵坐标表示占用的存储空间由图3(a)可见，在前350个版本的去重中，DBMB算法和EB算法的去重效果相差不大，这是因为前期版本改动相对较小，文件重复率较高但随着数据量的进一步增大，DBMB算法展现出了多特征匹配的优势，对相似度较低的文件也能检测出重复数
23、据块EB算法处理的数据最终占用空间为769 Gbyte，去重率为1313：100；而DBMB算法占用的存储空间为564 GB，去重率为1791：100，相比前者提高了3641DBMB算法和EB算法在unux数据集上的执行时间如图3(b)从图3(b)可以看出，当数据量较小时，两个算法的执行时间增长较慢而随着数据量的增大，指纹容器中的元素个数也相应增多，对磁盘中数据的匹配成为EB算法的瓶颈，其算法执行时间陡增对于DBMB算法，由于其采用了Bloom 61ter优化磁盘去重过程，添加和查询操作的时间复杂度均为D(七)，其算法执行时间不受数据规模的影响，故保持缓慢增长EB算法最终执行时间为12547
24、s，而DBMB算法为7654 s，相较于前者性能提升了3899代码版本，)存储空间变化代码版本(b)算法执行时间图3 Lin呱数据集实验结果n昏3 R嚣lllts of Linux data set22运维数据集实验分别采用EB算法和DBMB算法对运维数据集进行重复数据删除，实验结果与Linux数据集相似，最终实验结果如图4其中EB算法去重后的数据为76138 Mbyte，去重率为844：100，算法执行时间为1684 s；而DBMB算法处理后的数据为53778Mb)rte，去重率为1195：100，算法执行时间为1205 sDBMB算法的去重率和运行效率比EB算法分别提升了4159和2844
25、图5展示了EB算法和DBMB算法在对两个数据集去重的内存开销由于“nux数据集小文件较多，所以DBMB算法聚合小文件的策略在一定程度上减小内存占用量而对于运维数据集，由于其主要是大文件，故DBMB算法的内存开销与EB算法基本持平由上述两个数据集的测试结果可知，本研究提出的基于多特征匹配和B100m 6lter改进的EB算法比传统EB算法具有更高的去重性能和更快的时间效率，且对于小文件占主导的存储系统能有效减小内存开销万方数据第5期 张宗华，等：基于多特征匹配和B100m filter的重复数据删除算法 535时间月a)存储空间变化时间，月)算法执行时间图4运维数据集实验结果Fig4 Resul
26、ts of operational data setI|jm，x数l，t二 运纠E数瓶t襄删试数据集图5 EB和DBMB的内存开销Fi蛋5 M咖ory oVerh朗d 0fEB and DBMB挂 五；口 F口针对传统EB算法去重率较低以及磁盘数据匹配吞吐率较低的缺陷，提出聚合小文件为局部性单元，并基于最大块、最小块以及中间块的多特征匹配策略，提高重复数据删除率；同时采用Bloomfilter记录和维护指纹容器中的数据，有效提高了磁盘数据匹配的时间效率实验结果表明，本研究提出的DBMB算法的去重率和执行时间均优于传统EB算法，且对小文件去重时具有较低的内存开销基金项目：国家自然科学基金资助项目
27、(61300192)；中央高校基本科研业务费资助项目(zYG)(2014J052)；北京电力医院一体化运维监控与管理资助项目作者简介：张宗华(1977一)，男，国家电网公司北京电力医院工程师研究方向：电力信息化Em8il：zIaIl昏nglluancsgccconLcn引 文：张宗华，屈 英，叶志佳，等基于多特征匹配和Bloom fnter的重复数据删除算法J深圳大学学报理工版，2016，33(5)：531-535参考文献Refe眦髑：1Bhagwat D，Eshghi K，kng D D E，et a1Extremebinning：scalable，paraue王dedupljcation
28、for chunkbasedfile backupCIEEE Intemational symposi啪onModeling，AnalysisSimulation of Computer粕d Tele-communic撕on Systems Dresden， Ge珊明y： IEEE，2009：192张志珂，蒋泽军，蔡小斌，等相似索引：适用于重复数据删除的二级索引J计算机应用研究，2013，30(12)：3614-3617ZhaIlg Zhike，Jiang Zejun，Cai Xiaobin，et a1Similarindex：two1evel index used for deduplica
29、tionJAppli-cation Research“Computers，2013，30(12)：36143617(in Chinese)3xia wen，Ji锄g Hong，Feng Dan，et a1sik：a similarity-locality b鹊ed near-exact deduplication scheme withlow RAM overhead and h讪througllputcuSENIxA肌ual TechIlical Confbr；ence Compton，USA：USENIXAssociation2011：26-284zhang zhike，Bhagwat D
30、，Lifwin w，et a1Impmved deduplication througll p心lllel birulingcIEEE tlle 31 stIntemational Pe而nIlaIlce Computing a11d Co咖unicationsCo山rence0ttawa，Canada：IEEE，2012：130-1415Bmder A zon the reseIIlblaIlce锄d contai砌ent 0f documentsCCompression and Comple)【ity of SequencesAnaIlta。USA：IEEE，1997：21296付印金，肖
31、侬，刘芳重复数据删除关键技术研究进展J计算机研究与发展，2叭2，49(1)：12-20Fu Yinjin，Xiao Nong，Liu Fang Research and devdopment on key techniques 0f data deduplicationJJounlalof C0mputer Research a11d Development，2012，49(1)：12_20(in Chinese)7Linux Kemel 0rganizationThe Linux KemelDB0LCompton，UsA：Linux Kemal 0rganization2016-0512https：wwwkemelorg【中文责编：坪梓；英文责编：子兰】万方数据