（模式识别与智能系统专业论文）一种基于重复数据删除的备份系统设计与实现.pdf

北京邮电大学硕士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：壑垒键 日期： 圣里! 翌! 至17 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释。本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：蓥垒叁 日期： 刷磁名彩和巡1 日期： 北京邮电大学硕士学位论文 毫囊 北京邮电大学硕士学位论文 一种基于重复数据删除的备份系统 摘要 随着信息化程度的不断提高，数据对于企业的重要性愈发凸显。 由于企业日常生产过程中会产生了大量的生产数据，尤其是近年来， 海量数据的爆炸性增长对数据中心的存储能力提出了更高的要求。统 计数据表明，企业日常新增海量数据之间存在着许多相似的数据，为 此，提出了重复数据删除技术。当前，采用重复数据删除技术以改进 数据存储效率、提高海量数据处理性能具有重要的理论和实用价值。 本文设计了一种基于重复数据删除的文件备份系统，该系统能够 有效地对文件进行存储并压缩从而节约存储空间，并且，在数据压缩 同时也能够节省传输带宽，可以让各个版本的数据在存储器上有效保 存，降低磁盘开销。 基于重复数据删除的文件备份系统在功能点上可以分为两大功 能模块：重复数据删除模块，用于实现文件分块以及数据消重；性能 改进模块，用于实现预处理功能和负载均衡。 在重复数据删除模块中，为了满足对文件数据变化敏感度低的性 能需求，文件分块模块设计采用的是变长分块模式，从而保证了各个 版本文件分成的块之间相似性更大。在系统消重模块，引入了b l o o m f i l t e r 算法，以o ( 1 ) 的时间复杂度完成一次判重处理，该算法在效率 上比传统使用数据库进行消重快许多。虽然b l o o mf i l t e r 有一定的误 判率，但是经理论论证与实验表明，当其处理数据在一定的范围内， 误判率的大小仍然是可控的。 在系统的性能改进模块，定义了一种数据结构目录层级哈希 树，使用该数据结构对待备份目录树进行判重剪枝，以缩短备份时间。 对系统的服务器端加入了分布式处理，以保证b l o o mf i l t e r 的误判率 较小，同时在中控器中使用m o s s 代理，把客户端的请求均衡到不 同的节点上，保证响应客户端的服务请求。 实验结果显示，该系统的文件备份能力，在数据压缩比和带宽 占用比都明显优于经典的r s y n c 和l b f s 系统。 北京邮电大学硕士学位论文 关键词：重复数据删除目录层级哈希树文件分块分布式文 件系统 d e s i g na n di m p l e m e n t i o no fa b a c k u ps y s t e mb a s e d o nd a t ad e d u p l i c a n o n a b s t r a c t w i t ht h e d e v e l o p m e n t o fi n f o r m a t i o n t e c h n o l o g yl e v e l ，t h e i m p o r t a n c eo fd a t af o re n t e r p r i s e sb e c o m e sm o r ep r o m i n e n t a st h e b u s i n e s sd a i l yp r o c e s sw i l lp r o d u c eal o to fp r o d u c t i o nd a t a ，i np a r t i c u l a r ， i nr e c e n ty e a r s ，i th a sp u tf o r w a r dh i g h e rr e q u i r e m e n t sb e c a u s eo ft h e e x p l o s i v eg r o w t ho fm a s s i v ed a t as t o r a g ec a p a c i t yo fd a t ac e n t e r s s t a t i s t i c ss h o wt h a tn u m e r o u sd a t ai m p r o v ei nc o m p a n i e sd a yb yd a y b u t t h e r ea r em a n yd u p l i c a t ed a t ab e t w e e nt h e m , f o rt h i s r e a s o n ，t h ed a t a d e d u p l i c a t i o nt e c h n o l o g yi sp r o p o s e d a tp r e s e n t ，t h ed a t ad e d u p l i c a t i o n t e c h n o l o g yi s n o to n l yu s e dt o i m p r o v ed a t as t o r a g ee f f i c i e n c ya n d p e r f o r m a n c e ，b u ta l s oh a ss i g n i f i c a n tt h e o r e t i c a la n dp r a c t i c a lv a l u e t h i st h e s i s p r e s e n t s af i l e b a c k u ps y s t e m b a s e do nd a t a d e d u p l i c a t i o n ，w h i c hc a ne f f e c t i v e l ys t o r ea n dc o m p r e s sf i l e st os a v e s p a c ea l s oc a ns a v et h eb a n d w i d t h ， d a t ai n m e m o r yo nt h e e f f e c t i v e o v e r h e a d m e a n w h i l e ，a l l o w i n gv e r s i o n so ft h e c o n s e r v a t i o na n dr e d u c et h ed i s k t h i ss y s t e mc a nb ed i v i d e di n t ot w of u n c t i o n a l m o d u l e s ：d a t a d e - d u p l i c a t i o nm o d u l eb l o c k su s et od i v i d ef i l e si n t oc h u n k sa n dd e l e t e d u p l i c a t i o n ；p e r f o r m a n c ei m p r o v e m e n tm o d u l eu s e st o i m p l e m e n t p r e p r o c e s s i n gc a p a b i l i t i e sa n dl o a db a l a n c i n g i nt h ed a t ad e d u p l i c a t i o nm o d u l e ，i no r d e rt oa v o i df i l e s h i f t i n g s e n s i t i v i t y ，t h e f i l eb l o c km o d u l a rd e s i g nu s e s av a r i a b l e 1 e n g t hb l o c k m o d e ，s oa st oe n s u r ev a r i o u sv e r s i o n so ft h ef i l ed i v i d e di n t oag r e a t e r s i m i l a r i t yb e t w e e nb l o c k s i nt h ed e l e t i n gd u p l i c a t i o nm o d u l e ，b l o o m f i l t e r a l g o r i t h mc o n s u m e so ( 1 ) t i m ec o m p l e x i t yt oc o m p l e t eo n c e i i i 北京邮电大学硕士学位论文 d e d u p l i c a t i o np r o c e s s i n g ，t h ea l g o r i t h mi sm o r ee f f i c i e n ta n df a s t e rt h a n t h et r a d i t i o n a l u s i n gt h ed a t a b a s e a l t h o u g hb l o o mf i l t e rh a sf a l s e p o s i t i v er a t e ，h o w e v e r ，d e m o n s t r a t e db yt h et h e o r ya n de x p e r i m e n t s h o w e dt h a tw h e ni t sp r o c e s s i n gd a t aw i t h i nac e r t a i nr a n g e ，t h es i z eo f t h ef a l s ep o s i t i v er a t ei ss t i l lc o n t r o l l a b l e p e r f o r m a n c ei m p r o v e m e n t si nt h es y s t e mm o d u l e ，d e f i n e sad a t a s t r u c t u r e d i r e c t o r y h i e r a r c h i c a lh a s h t r e e ，u s i n gt h ea p p r o a c ht o p r e p r o c e s sab a c k u pd i r e c t o r yt r e eb yp r u n i n gt os h o r t e nt h eb a c k u pt i m e t h es y s t e m ss e r v e re m p l o y st h ed i s t r i b u t e dp r o c e s s i n gi no r d e rt oe n s u r e as m a l l e rf a l s ep o s i t i v er a t eo fb l o o mf i l t e r ，w h i l et h ec o n t r o l l e r sb y a d d i n gm o s sa g e n t sb a l a n c et h er e q u e s t so ft h ec l i e n tt oe n s u r es e r v i c e s r e s p o n d t h er e s u l t ss h o wt h a tt h es y s t e mb a c k u pc a p a b i l i t yi so b v i o u s l y b e t t e rt h a nr s y n ea n dl b f ss y s t e mi nd a t ac o m p r e s s i o nr a t i oa n dt h e b a n d w i d t ho c c u p i e d k e yw o r d s ：d a t ad e d u p l i c a t i o n , d i r e c t o r yh i e r a r c h i c a lh a s ht r e e , f i l e c h u n k i n g , d i s t r i b u t e d f i l es y s t e m 北京邮电大学硕士学位论文 目录 第一章概述1 1 1 信息系统灾难备份的重要性和意义1 1 2 灾难备份与重复数据删除技术。2 1 2 1 数据备份类型2 1 2 2 数据备份的原则3 1 3 重复数据删除技术发展现状4 1 3 1 国外研究状况4 1 3 1 1r s y n c 系统。4 1 3 1 2l b f s 系统5 1 3 2 国内研究状况7 1 3 2 1a d m a d 系统7 1 3 2 2f b b m 系统7 1 3 3 工业界状况7 1 4 论文组织结构8 第二章技术分析与系统算法概述9 2 1 文件分块。1 0 2 1 1 文件分块种类1 0 2 1 2r a b i nf i n g e r p r i n t 算法。11 2 2 哈希算法1 2 2 2 1m d 5 算法1 2 2 2 2s h a 1 算法1 3 2 3b l o o mf i l t e r 的相关原理1 4 2 3 1 实现原理。1 4 2 3 2 误判率估计1 5 2 3 3 最优的哈希函数个数1 6 2 3 4 位数组的大小1 7 2 4 目录层级哈希树。1 8 2 4 1 哈希树建立算法1 9 2 4 2 哈希树遍历剪枝算法2 0 2 5 分布式与负载均衡2 0 2 5 1 负载均衡分类2 0 2 5 2 分布式负载均衡模型2 2 第三章系统架构设计2 3 3 1 总体结构2 3 3 2 预处理模块2 6 3 2 1 目录层级哈希树建树2 6 3 2 2 目录层级哈希树剪枝2 7 3 3 文件分块2 7 3 3 1 滑动窗口2 7 3 3 2 滑动窗口的基本原理2 8 3 3 3 指纹计算2 9 3 3 4 文件分块的实现过程3 1 v 北京邮电大学硕士学位论文 3 3 4 1 读取文件3 1 3 3 4 2 块边界确定。31 3 4 数据消重3 2 3 4 1 哈希函数的选择。3 2 3 4 2 位数组设计3 2 3 4 3 消重步骤3 3 3 5 数据传输与存储。3 4 3 5 1 数据传输3 4 3 5 2 数据存储3 6 3 6 数据恢复模块3 6 3 7 分布式架构3 7 3 7 1 备份任务分配3 7 3 7 2 负载均衡策略分析3 8 3 7 3 负载均衡策略选择3 9 第四章性能测试与评价4 0 4 1 系统搭建和测试方法4 0 4 1 1 系统相关测试软件4 0 4 1 】【】ii o z o n e 4 0 4 1 1 2i o z o n e 测试模式4 0 4 1 1 3m r t g 4 2 4 2 性能测试。4 3 4 2 1 哈希函数测试。4 3 4 2 2b l o o mf i l t e r 性能测试。4 3 4 2 3 系统性能测试4 4 第五章总结与展望。4 7 参考文献一4 9 致谢。! ；：! v i f 北京邮电大学硕士学位论文 第一章概述 1 1 信息系统灾难备份的重要性和意义 伴随着计算机技术的发展，社会的数字化与信息化的步伐越来越快。科技 的进步和企业问竞争的加剧，企业的生存和发展越来越依赖于信息系统。但是， 由于各种原因，人们无法预测和避免信息系统故障乃至灾难的发生。硬件故障、 人员操作失误、病毒攻击、恐怖袭击、断电、火灾、地震等原因会造成计算机系 统无法访问甚至丢失，由此造成的损失是昂贵的【1 1 。 据国家标准信息系统灾难恢复规范( g b 厂r2 0 9 8 8 2 0 0 7 ) 的定义：灾难 是指由于人为或自然的原因，造成信息系统运行严重故障或瘫痪，使信息系统支 持的业务功能停顿或服务水平不可接受、达到特定时间的突发性事件。典型的灾 难事件是自然灾难，如火灾、洪水、地震、飓风、龙卷风、台风等，还有提供给 业务运营所需的服务中断，如设备故障、软件错误、电信网络中断和电力故障等 等。此外，人为的因素往往也会造成灾难，如操作员错误、破坏、植入有害代码 和恐怖袭击等。由于各种灾难或突发事件而造成的业务服务中断，以及不能及时 恢复系统导致企业停止运行和丢失数据，会对企业的服务质量、声誉造成严重影 响。受世界范围内恐怖分子袭击和自然灾害的影响，世界上各个国家的关键企业 和政府部门都在评审自身面对灾难和攻击的应对能力，r r 产业更是重新评估本 身的抗灾难水平和现状。 灾难备份与灾难恢复是降低灾难发生造成的损失和保证计算机系统连续运 行的重要措施。灾难恢复是指为了将信息系统从灾难造成的故障或瘫痪中恢复到 可正常运行状态，并将其支持的业务功能从灾难造成的不正常状态恢复到可接受 状态，而设计的活动或流程。灾难备份是指为了灾难恢复而对数据、业务处理系 统、网络系统、基础设施、技术支持能力和运行管理能力进行备份的过程。 通过大量的数据表明：如果没有r r 环境的连续性运行的保障，企业的发展甚 至生存都将面临极大的困难。据i d c 的统计数字表明，美国在2 0 0 0 年以前的1 0 年 间发生过灾难的公司中，有5 5 当时倒闭，剩下的4 5 中，因为数据丢失，有2 9 也在两年之内倒闭，生存下来的仅占1 6 。国际调查机构g a r t n e rg r o u p 的数据也 表明，在经历大型灾难而导致系统停运的公司中有2 5 再也没有恢复运营，剩下 的公司中也有1 3 在两年内破产。这些事故导致企业丧失了部分或全部业务处理 能力，引起企业营业收入下降、信誉降低和形象受损，甚至威胁其生存。此外， 发生于因特网上的蠕虫、冲击波等病毒，都使得网络资源损失惨重。调查显示： 北京邮电大学硕士学位论文 商业数据失效的平均代价是2 5 万美元小时，其中有8 更达到1 百万美元小时， 数据丢失的代价甚至更高。 在9 1 1 事件之后，计算机系统的灾难备份与恢复建设受到高度重视。如何在 突发或紧急情况下使得灾难造成的损失降到最低限度，更好地保护重要数据，保 证计算机系统的连续、安全、可靠运行，已成为当前计算机与信息安全领域的研 究热点。 1 2 灾难备份与重复数据删除技术 1 2 1 数据备份类型 随着网络的快速发展，信息系统和数据存储、备份和恢复技术也发生着翻天 覆地的变化，目前主要有以下三种备份方式【2 j ： 全备份：是对整个服务器系统进行备份，包括服务器操作系统和应用程序生 成的数据。这种备份方式的特点就是备份的数据最全面、最完整。这种备份方式 的好处就是很直观，容易被人理解。而且当发生数据丢失的灾难时，只要用一盘 磁带( 即灾难发生之前一天的备份磁带) ，就可以恢复丢失的数据。然而它也有 不足之处：首先由于每天都对系统进行完全备份，因此在备份数据中有大量是重 复的，例如操作系统与应用程序。这些重复的数据占用了大量的磁带空间，这对 用户来说就意味着增加成本；其次，由于需要备份的数据量相当大，因此备份所 需时间较长。对于那些业务繁忙，备份时间有限的用户来说，选择这种备份策略 无疑是不明智的。 差额备份：每次备份的数据是相对于上一次全备份之后新增加的和修改过的 数据。注意，这是相对于上一次全备份之后新增加或修改过的数据，而并不一定 是相对于上一次备份。例如：w i n d o w s 操作系统的活动目录数据( n t d s ) ，必 须采取差额备份对系统状态进行覆盖方式的备份。举例来说，在星期一，网络管 理员按惯例进行系统完全备份；在星期二，假设系统内只多了一个资产清单，于 是管理员只需将这份资产清单一并备份下来即可；在星期三，系统内又多了一份 产品目录，于是管理员不仅要将这份目录，还要连同星期二的那份资产清单一并 备份下来。如果在星期四系统内有多了一张工资表，那么星期四需要备份的内容 就是，工资表+ 产品目录+ 资产清单。 增量备份：是针对全备份的后续备份，增量备份指每次备份的数据只是相当 于上一次备份后增加的和修改过的数据。这种备份方式没有重复地备份数据，既 节省磁带空间，又缩短了备份时间。 f 北京邮电大学硕士学位论文 以上提到的三中备份方式中，以增量备份的压缩效果最为显著，高压缩率可 以使得备份空间得以高效利用，高效利用的结果，就是在不需要增加硬件设备的 情况下，现有的存储设备可以存储更多的数据，为企业节约成本。 增量备份所使用到的技术就是重复数据删除技术。 重复数据删除是一种无损数据压缩技术，通常用于基于磁盘的备份系统，旨 在减少存储系统中使用的存储容量。它的工作方式是在某个时间周期内查找不同 文件中不同位置的重复可变大小数据块。重复的数据块用一个极少冲突的哈希 ( h a s h ) 值取代，如m d 5 或者s h a - 1 ，然后使用哈希值进行判重处理，以达到 完全相同的数据只存储一个实例的效果。高度冗余的数据集( 例如备份数据) 从数 据重复删除技术的获益极大；用户可以实现1 0 1 ：l 1 至5 0 1 ：1 1 , 1 的缩减比。而且，重复 数据删除技术可以允许用户的不同站点之间进行高效，经济的备份数据复制。 1 2 2 数据备份的原则 对数据进行备份是为了保证数据的一致性和完整性，不同的应用环境有不同 解决方案，一般来说一个完整的备份系统需要遵循以下原则1 3 j ： 1 1 稳定性。备份产品的主要作用是为系统提供一个数据保护的方法，于是 该产品本身的稳定性和可靠性就变成了最重要的一个方面。首先，备份软件一定 要与操作系统1 0 0 的兼容，其次，当事故发生时，能够快速有效地恢复数据。 2 ) 全面性。在复杂的计算机网络环境中，可能会包括了各种操作平台，并 安装了各种应用系统。选用的备份软件，要支持各种操作系统、数据库和典型应 用。 3 )自动化。很多企业由于工作性质，对何时备份、用多长时间备份都有一 定的限制。在下班时间系统负荷轻，适于备份。可是这会增加系统管理员的负担， 由于精神状态等原因，还会给备份安全带来潜在的隐患。因此，备份方案应能提 供定时的自动备份，并利用磁带库等技术进行自动换带。在自动备份过程中，还 要有日志记录功能，并在出现异常情况时自动报警。 4 ) 高性能。随着业务的不断发展，数据越来越多，更新越来越快，在休息 时间来不及备份如此多的内容，在工作时间备份又会影响系统性能。这就要求在 设计备份时，尽量考虑到提高数据备份的速度，利用多个磁带机并行操作的方法。 5 ) 操作简单。数据备份应用于不同领域，进行数据备份的操作人员也处于 不同的层次。这就需要一个直观的、操作简单的图形化用户界面，缩短操作人员 的学习时间，减轻操作人员的工作压力，使备份工作得以轻松地设置和完成。 3 北京邮电大学硕士学位论文 6 ) 实时性。有些关键性的任务是要2 4 小时不停机运行的，在备份的时候， 有一些文件可能仍然处于打开的状态。那么在进行备份的时候，要采取措施，实 时地查看文件大小、进行事务跟踪，以保证正确地备份系统中的所有文件 7 ) 容错性。数据备份并不是总能保证备份的正确性。进行还原时，不能因 为有错误的数据块存在而使备份失效。 1 3 重复数据删除技术发展现状 1 3 1 国外研究状况 重复数据删除作为一种文件间的无损压缩技术，在数据备份领域，特别是 灾难备份领域得到广泛的运用，因为可以跨文件压缩，并且能达到较高的压缩比， 因此国外诸多的研究机构都对它做了较为深入的研究，而且设计开发了较为成熟 的系统，比如r s y n c 和l b f s 等。 1 3 1 1r s y n c 系统 r s y n c 4 】算法由a 瓢d g e l l 于1 9 9 9 年在他的博士论文中提出，它通过检测、传 输新旧文件的差异部分，可以实现快速、高效的文件同步。 其算法过程如下： a ) 服务器s e n ，e r 将文件l 进行固定分块，每一个块长为七b y t e ，露可以由用户 进行配置，最后一个块的长度可能小于k 。 b ) 服务器s e r v e r 计算每个数据块的滚动弱校验和与h a s h 值，h a s h 值采用1 2 8 b i tm d 4 哈希算法算得。 c ) 服务- 器s e r v e r 建立哈希表，对于每一对校验值，以滚动校验值为关键值进行 哈希排序，表示为吃( 羁，m ；) ，并将哈希表传送给客户端c l i e n t 。 d ) 客户端c l i e n t 从头搜索文件厶，产生滚动校验和与i ( 墨，m ；) 中的r 比较， 发现与r 相匹配的数据块，再计算其m i m 哈希值与强校验和m ；比较。如果与强 校验和相等，说明这两个数据块相同；如果不匹配，说明这两个数据块不同，则 记录该数据块的第一个字节，然后向后移动一个偏移量，继续比较，直到文件末 尾。 4 北京邮电大学硕士学位论文 曲所有比较完成后，服务器s e r v e r 收到客户端c l i e n t 包含差异内容和h a s h 指示 值的数据流，更新厶，生成厂删。 r s y n c 算法也有一定的缺陷：首先，r s y n c 使用固定分块的方法，这种分块 方法对数据变化非常敏感，因为当文件内部数据有部分变化时，后续一系列文件 块会相应地改变。其次，其中对于数据相似性检测的方法与文件目录结构有关， 所以倘若目录结构有所改变，但相应文件内容未做修改，其也会当作新文件处理， 产生多余的网络流量。 1 3 1 2l b f s 系统 l b f s 5 】是麻省理工学院于2 0 0 1 年由a t h i c h am u t h i t a c h a r o e n ， b e n j i ec h e n 等 人开发的一款文件系统，该系统使用r a b i nf i n g e r p r i n t 算法来实现变长分块，该 方法对文件数据变化不敏感，是一种基于内容的分块方法，同时使用s h a - 1 值作 为i d ，向服务器进行块存储校验，以判断数据块是否已存储，若已存在则不用发 送数据块，以此达到了减小传输带宽的目的。 其算法主要包含两个主要步骤，读文件与写文件如下： 1 读文件：当客户端要从服务器端读取文件时，客户端通过一个g e t h a s h 客户端服务器 组织文件并写入数据库 图1 - 1l b f s 系统读文件算法 5 文件分块，并记录块偏移 量和长度 返回s h a l 的相关数据 返回s h a 2 的相关数据 北京邮电大学硕士学位论文 一? ? ? 蝴 图1 - 2 写文件 6 北京邮电大学硕士学位论文 该系统作为一款文件系统提出，但是其中使用到了文件分块处理，以及文件 块单一实例化存储的思想，使得该系统在重复数据删除技术中一直被作为经典系 统进行引用研究，但其对备份目录处理的过程中对于未改变的文件仍然要先进行 分块，然后再判断数据块的重复与否，若目录树比较大则有可能降低算法的效率， 成为整个系统备份的瓶颈。 1 3 2 国内研究状况 国内有清华大学网络存储实验室和华中科技大学计算机科学与技术学院两 家科研机构对重复数据删除领域进行了一定的研究，并分别开发t a d m a d 和 f b b m 系统。 1 3 2 1a d m a d 系统 清华大学计算机系网络存储实验室与明尼苏达大学共同合作开发了a d m a d 归档备份系统【6 l ，该系统使用不同等级i o 通道的元数据信息把文件分成有一定 意义的文件块，以此来削减文件问的重复数据，该系统同样使用变长分块的方式。 1 3 2 2f b b m 系统 f b b m 7 1 系统由华中科技大学计算机科学与技术学院开发的一款文件备份系 统，它把文件使用变长分块算法，分成多个数据块，然后使用锚点分级的策略进 行重复数据块的发现检测，同时建立文件块内容建立一个哈希表，以此来实现文 件块存储的唯一性，接着把唯一的数据块存入一次性写入的r a i d 设备中。 1 3 3 工业界状况 重复数据删除技术作为一个新兴的领域，不但受到国内外高校研究机构的高 度重视，同时也受到工业界储存行业的大力追捧，诸如e m c ，赛门铁克，飞康， 昆腾等等知名公司。 e m c 的a v a m a r 系统采用重复数据消除和全局单实例存储( s i s ) 技术，确保 备份数据段在全局范围内仅存储一次，还可以有效地将移动和恢复的数据量缩减 3 0 0 倍，同时还可以实现每日完整备份和快速恢复。 赛门铁克n e t b a c k u pp u r e d i s k 远程办公室备份软件，具有全局单一实例存储 的基于磁盘的安全数据保护将备份所消耗的存储和网络降低1 0 倍n 5 0 倍；同时， 能将备份的存储和网络消耗降低1 0 至5 0 倍。 北京邮电大学硕士学位论文 飞康的重复数据删除存储软件名为“s i n g l ei n s t a n c er e p o s i t o r y ( s i r ) 。s i r 提 供一个基于策略的冗余数据删除( r d e ) 引擎，只存储数据文件或数据块的单一 实例( s i n g l ei n s t a n c e ) 昆腾的数据重复删除技术按自然边界把数据拆分为非常细粒度的子块元素， 然后对细粒度的子块进行单一实例存储。利用数据重复删除技术后，1 t b 的备份 数据可根据备份数据的共性，存储为3 0 0 7 0 0 g b 不等。因此可以实现1 0 ：1 到5 0 ：1 的备份比率。 1 4 论文组织结构 本论文主要是对重复数据删除技术和基于该技术的文件系统进行研究，在此 基础上设计并实现了一种基于重复数据删除的网络文件系统。 本文的组织结构如下： 第一章为概述，首先简要介绍了信息系统灾难备份的重要性以及研究意义， 紧接着阐述了灾难备份与重复数据删除的关系，然后介绍了重复数据删除技术国 内外研究现状和论文组织结构。 第二章为重复数据删除技术的分析以及系统算法介绍，分析重复数据删除的 主要技术，并对系统使用的算法进行相应介绍，1 、用于变长分块的r a b i n f i n g e r p r i n t 算法；2 、用于消重技术的m d 5 和s h a - 1 算法，并对性能进行比较取舍， 3 、用于提高备份效率的目录层级哈希树l4 、用于防止数据库膨胀的b l o o mf i l t e r 数据结构；5 、为了增加系统的备份响应能力，介绍了分布式处理与负载均衡。 第三章为系统架构设计，主要介绍整个系统的整体架构，以及各个系统模块 的作用，同时对服务器系统做出了分布式处理，以求均衡负载，提升服务器对客 户端的服务能力。 第四章为系统性能测试评价，主要是与现有的t s y n c 系统和i b f s 系统在备份压 缩比和带宽节省上进行对比。 第五章为总结与展望，对论文进行了总结，同时提出了进一步努力的方向。 8 北京邮电丈学硕士学位论文 第二章技术分析与系统算法概述 重复数据删除技术主要包含了两个步骤： 1 、文件分块，也就是把一个文件分成若干个小块，目的是为了在接下来的 处理中更好的发现重复的数据块，本系统沿用经典的r a b i nf i n g e r p r i n t 变长分块 算法，它有对数据变化不敏感，基于文件内容划分等优点。 2 、消重技术，也就是找到相同的文件块，只留下一个实例，然后把多余的 块去掉。从算法的有效性来说，使用h a s h 值作为块i d 进行消重，一方面缩短了 串长易于比较，另一方面也方便了数据块管理，因此选用一个抗冲突性能优秀的 哈希算法，是保证消重结果准确的关键。从系统性能来说，在判重方面，本系统 采用b l o o mf i l t e r 进行判重，接下来的章节可以得知，该数据结构的判重复杂度 是一个o ( 1 ) 的常数时间复杂度，而传统的l b f s 等系统都采用数据库进行数据块 管理，当备份数据增加，数据块的个数增多，将会加剧数据库的膨胀，导致系统 性能下降。 为提升系统的性能，这里引入了目录层级哈希树作为目录预处理模块，以 及对系统做了分布式均衡负载： 1 、目录层级哈希树，作为一种拓扑与源备份目录拓扑结构相同的数据结构， 它有着良好的文件内容变化监控性质，当哈希树中文件夹某个节点的值未发生改 变，则该目录下的所有文件均未发生改变，就可以对该节点进行剪枝，该目录下 的所有文件将不再处理，以此提高系统的性能。 2 、分布式负载均衡，引入分布式结构的好处主要有两个：均衡负载，增 强服务器处理数据的能力，缩短服务器响应客户请求的时间。提高判重准确性， 数据i d 的判重分配到各个节点中，不同的节点处理不同的数据，以保证b l o o m f i l t e r 的处理数据量级在1 亿条左右，这样可以在6 0 0 m 左右的位数组空间内达到足 够d , ( 1 0 - 9 ) 的误判率。 下面将从重复数据删除技术和系统性能优化两个方面，对各个技术以及算 法以分别进行阐述 9 北京邮电大学硕士学位论文 2 1 文件分块 2 1 1 文件分块种类 文件分块是重复数据删除技术的关键，因为该技术是通过对文件块单实例 化存储来达到删除重复数据这个目的。目前对于文件分块的方法主要有两种：固 定分块与变长分块。 固定分块：就是从文件头部开始，根据预设的块长度值，对文件进行相同 长度的攫取，直到文件末尾，这罩允许最后一个块长小于预设块长度。这种分块 方法的优点是，实现简单，处理速度快，缺点是当文件块头部或者中间出现小部 分数据增加或者减少的变化时，后面的数据虽然与之前备份的文件相同，但因为 是固定分块，这将使得后面分得的文件块与数据变化之前文件分得的块不一致， 对数据的变化非常敏感。使用固定分块的系统除了r s y n c 之外，还有v e n t i s l 、 o c e a n s t o r e l 9 l 等。 变长分块l 这是一种基于内容c o n t e n t d e f i n e dc h u n k i n g ( c d c ) 技术的分块 方法，与固定分块不同的是它的块断点不以一个预设值来确定，而是以其文件内 容进行计算，当满足一定的标准之后方认为其为块断点。使用变长分块的系统除 了之前提到的l b f s ，a d m a d ，f b b m 之外，还有d e e ps t o r e o o j 。在实现变长 分块前，首先建立一种弱h a s h 的机制，满足两个规则：( 1 ) h a s h 值相同的时候 内容不一定相同，h a s h 值不同的时候内容一定不同。( 2 ) h a s h 的冲突较之m d 5 和s h a - l 一类强指纹映射尽可能的频繁，这样可以避免文件块变得异常的大， 进而能确定文件的块断点使用这种h a s h 函数，对文件进行计算，当h a s h 值满 足一定条件，比如等于一个预定义值的时候，就可以认为此时该内容所在的地方 为一个块断点。 这种分块的缺点是，实现复杂，处理速度比固定分块慢，优点是对数据变 化不敏感，对两个文件间的共同数据查找效果好。如下例： 图2 2 中为源文件，该文件已经被分成不同大小的数据块，每个数据块 的边界是由每4 8 字节区域( 即滑动窗口长度，在3 3 节将进行详细介绍) 产生一个h a s h 值来确定的。 当向文件插入一部分数据所产生的影响。这部分数据被插入块c a 后， 产生了一个新的大的数据块c 8 ，其他的数据块保持不变。此时，只需 要将数据块c 8 发送给已经保存了该文件旧的版本的接收端。 1 0 ， 北京邮电大学硕士学位论文 插入数据的地方包含边界时，插入数据所产生的影响。当几个字节被插 入c 5 时，该数据块分裂成两个数据块c 9 和c i o 。同样的，传输这两个 新的数据块c 9 和c i o 就相当于传输了整个文件。 说明了插入的部分使边界消失的情况。当插入一部分数据后，旧的文件 版本的数据块c 2 和c 3 被合并成一个新的数据块c ll ，这个数据块被传 输到彼端。 d 图2 - 1 变长分块算法 在两种分块方式中，变长分块由于其对数据变化的低敏感性，以及属于基 于内容的分块，所以在重复数据删除技术领域，变长分块逐渐成为文件分块方式 的主流。 2 1 2r a b i nf i n g e r p r i n t 算法 r a b i nf i n g e r p i m t 1 4 1 算法由美国哈佛大学教授r a b i n 提出，其算法思想如下： 假设么( 阪，也，吒 ) 是包含朋个二进制字符的二进制字符串，那么可以根据 彳构造相应的m 一1 度的多项式如下，其中t 是不定元。 a ( t ) 一婶”。1 + b 2 t “一2 + + 6 i 一，+ 6 k 式( 2 1 ) 给定一个最高次方位k 的多项式p ( f ) ，如下： p ( f ) 一口，+ a 2 t - l + + 口i 一，+ 口i 式( 2 2 ) 那么4 ( f ) 处以尸( f ) 的余数，( f ) 的度数为七一1 。对于给定的字符串爿，定义 彳的指纹，( 彳) 如下： f ( a ) - a ( t ) m o d p ( t ) 式( 2 - 3 ) 北京邮电大学硕士学位论文 r a b i n 指纹有如下性质，如果字符翱的指纹不同于字符串b 的指纹，那么字 符翱也不同于字符串b ：f ( a ) ，i 厂f b ) 本a b ，但是字符串彳的指纹等于b 的 指纹并不等于字符串彳一定等于字符串丑，厂( a 1 i l lf ( b 1 声a - b ，根据这个两个 性质，可见r a b i n 指纹满足了上面所说的弱h a s h 性质，因此r a b i n 算法在重复数据 删除技术中作为基于内容的变长分