重复数据删除中的可变分块算法[开题报告].doc

1、（2011届）本科毕业论文（设计）开题报告题目重复数据删除中的可变分块算法学院专业信息管理与信息系统班级学号姓名指导教师开题日期教务处制一、选题的背景和意义随着数字图书馆、电子商务、科学计算、多媒体等应用的不断发展，数据从万亿字节TB急速增长到千万亿字节PB，甚至到一百亿亿字节EB。据IDC国际数据公司统计显示，去年全球产生的数字信息量共计161EB字节，世界上有足够存储185EB字节的存储设备，到2010年，世界上将有能够存储601EB字节的设备。然而到2010年，全球所产生的数码信息量将由现在的161EB字节猛增到988EB字节1。由于信息的海量增长，磁盘备份设备的容量已经趋于饱和，在数据

2、中心需要不停地增加硬盘来备份PB级的数据，在这种情况下，当我们希望将备份数据保存一个月时，却只能保存两到三天，硬盘里的数据开始变得臃肿和庞大，但对这些数据进行仔细分析，不难发现其中有太多的重复数据，因此重复数据删除技术开始受到工业与学术界的关注2。为了缓解存储系统的空间增长问题，缩减数据占用空间，降低成本、最大程度的利用已有资源，我们需要对重复数据删除技术进行研究。一方面，利用重复数据删除技术，可以对存储空间的利用率进行优化。因传统的数据压缩技术主要根据一些固定的模式利用传统的数据分析工具和技术来消除重复数据，不能有效地改善基于磁盘数据的成本效益3，所以我们需要通过探究重复数据的特性，利用相应

3、的重复数据删除技术，以消除分布在存储系统中的相同文件或者数据块。另一方面，利用重复数据删除技术，可以减少在网络中传输的数据量，进而降低能量消耗和网络成本。由于重复数据删除技术的目标是消除分布在存储系统中的相同及相似文件或者数据块，因此能够减少大量的磁盘消耗，并且为数据复制大大节省网络带宽。二、研究的基本内容与拟解决的主要问题1研究的基本内容为了缓解存储系统的空间增长问题，缩减数据占用空间，降低成本、最大程度的利用已有资源，我们需要对重复数据删除技术进行研究。重复数据删除技术可以有效提高存储设备的利用率，减少存储容量。同时在重复数据删除技术中存在一种可变分块算法，这种算法允许某些数据片段进行伸缩

4、，而不影响后面的数据块，有助于提高系统查找重复数据块的能力，从而达到大幅节省空间的目的。同时这种算法对于数据的敏感性不高，所以对于数据的一些小的改变不会引起数据的大规模的改变。例如该算法对于插入问题和删除问题处理高效。无论是插入还是删除一小部分字节，只会影响一到两个块，其余的块保持不变。这种算法对于数据的重复冗余有着更多的清理和检测。本课题设计并实现重复数据删除中的可变分块算法，实现数据块的可变长切分，并将其应用于重复数据删除软件中，检验算法的性能。2拟解决的主要问题本次的设计过程中，主要针对数据加密算法方法进行学习和研究，并在熟悉加密算法的基础上用系统开发软件，本次设计中需要解决的问题为（1

5、）掌握该算法中记录指纹和计算数据块HASH值，重复数据比较，数据存储等。（2）运用开发工具进行系统的加密算法的开发与设计。由于目前有许多不同的系统平台，为了使软件有良好的跨平台性，在不同的系统环境下都能有效的运行，本次设计选用C来编写。因为C在设计时就具有避免平台限定或没有普遍用途的特性。三、研究的方法与技术路线、研究难点，预期达到的目标1研究方法和技术路线本次设计通过运用文献分析方法、面向对象程序设计方法来完成预定的目标。具体研究方法和技术路线如下（1）首先实现重复数据删除技术，国外经过多年的发展，重复数据产出技术已形成完整的运作体系，鉴于一般过程达到共识，分析重复数据删除主要运用的关键技术

6、。（2）对数据块进行HASH值计算，文件被切分成数据块之后，需要对每个数据块的内容计算HASH值，保存下数据块的各个HASH值，一边以后数据比较。内容不同，HASH值不同。内容相同，HASH相同。对于数据块进行HASH值，使得数据块的存在不同时，HASH值不同，使得数据重复检测成为可能。（3）重复数据删除中的可变分块算法。（4）重复数据删除中的可变分块算法的实现。（5）对整个软件实现过程进行安排，并总结参考资料，完成本次设计。2研究难点当然，设计过程中也会有许多难点需要解决第一，目前，没有一种方法可以作为通用的检测技术，因此，如何高效的结合这些技术点，找到一个最佳融合点将是一个研究的难点。第二

7、，因相同数据检测的每种技术对存储空间的节省，网络带宽的消耗以及系统为支持每种方法所需的计算和存储的额外开销的影响都不同，如何在融合各技术特征的同时，对数据特性进行充分的分析和挖掘，找到其规律性的认识来为系统各种开销的缩减提供一种技术支持，也将是一个研究热点。3系统预期目标本系统预期达到的目标是通过方便易懂的界面操作，完成对重复数据删除技术；同时达到高安全性和高效率。系统的基本设计目标（1）调研重复数据删除技术和可变分块算法。（2）研究并实现基于CDC算法的可变分块检测技术。（3）在重复数据删除软件中评测算法，并改进。四、论文详细工作进度和安排2011011120110301完成重复数据删除中的

8、可变分块算法，完成论文提纲。2011030120110315论文初稿。2011031620110505毕业实习，论文完善。2011050620110520论文定稿，评阅老师评阅。20110521毕业答辩五、主要参考文献1程菊生重复数据删除技术的研究J华赛科技,2008,48112DOUGLIS,F,IYENGAR,AAPPLICATIONSPECIFICDELTAENCODINGVIARESEMBLANCEDETECTIONRINUSENIXANNUALTECHNICALCONFERENCE,SANANTONIO,TEXASUSENIXASSOCIATION,20031131263刘俊辉HUS

9、H消息摘要算法实现及改进J福建电脑,2007,492934颜军重复数据删除带来集群架构革命J计算机世界技术与应用,2008,62440415范涛网络存储技术的研究与应用J福建电脑,2008690936LAWRENCELYOU,KRISTALTPOLLACK,DARRELLDELONGDEEPSTOREANARCHIVALSTORAGESYSTEMARCHITECTURERINPROCEEDINGSOFTHE21STINTERNATIONALCONFERENCEONDATAENGINEERINGICDETOKYO,JAPANIEEECOMPUTERSOCIETY,20058048157蔡盛鑫一种

10、基于重复数据删除的备份系统D北京邮电大学硕士论文,20068JMCKNIGHT,TASARO,BBABINEAUDIGITALARCHIVINGENDUSERSURVEYANDMARKETFORECASTJTHEENTERPRISESTRATEGYGROUP,200630359ATHICHAMUTHITACHAROEN,BENJIECHEN,DAVIDMAZIERESALOWBANDWIDTHNETWORKFILESYSTEMAINPROCEEDINGSOFTHESYMPOSIUMONOPERATINGSYSTEMSPRINCIPLESSOSP01CHATEAULAKELOUISE,BANFF

11、,CANADAACMASSOCIATION,200117418710SAVAGES,WETHERALLD,KARLINA,ETALNETWORKSUPPORTFORIPTRACEBACKJACM/IEEETRANSACTIONSONNETWORKING,2001,9322623711胡汗平,王凌斐,郭文轩,等一次性可变概率分片标记及其压缩标记J华中科技大学学报（自然科学版）,2007,353151812RICHARDSW著,范伟华,胥光辉,张清,等译TCP/IP详解一卷1协议M北京机械工业出版社200011敖莉,舒继武,李明强重复数据删除技术研究综述J软件学报,2010,21591692912

12、CALICRATESPOLICRONIADES,IANPRATTALTERNATIVESFORDETECTINGREDUNDANCYINSTORAGESYSTEMSDATARINPROCEEDINGSOFTHEUSENIXANNUALTECHNICALCONFERENCE2004ONUSENIXANNUALTECHNICALCONFERENCEBOSTON,MAUSENIXASSOCIATION2004738613WALTERSAVITCH著，周靖译C面向对象程序设计基础数据结构与编程思想（第四版）M清华大学出版社200311334514AMAZONSIMPLESTORAGESERVICEAMAZONS3EB/OL20100616HTTP/AWSAMAZONCOM/S3/15BRODERA,MITZENMACHERMNETWORKAPPLICATIONSOFBLOOMFILTERSASURVEYJINTERNETMATHEMATICS,2004,14485509