数据去重中重复数据检测技术研究

摘要

随着信息技术的快速发展，各种应用产生的数据也呈现爆炸式增长的趋势，这给数据的存储及备份造成一定的挑战。数据去重作为一种冗余数据消除技术得到了学者及存储业界广泛的研究，特别是备份系统，数据去重已成为系统中最为关键的技术之一。相对于传统的数据压缩技术，数据去重技术更注重于发现系统中存在的冗余数据，对冗余数据进行识别和消除，能以比压缩技术更高效地对冗余数据进行识别和清理。利用数据去重技术，不仅可以大量减少所需的存储介质降低数据存储成本，同时有效降低数据传输的过程中所需要的网络带宽，提高数据传输的速度和效率。数据去重可部署于多种应用场景，但由于应用类型的复杂性，设计一款高效的数据去重系统也面临诸多的挑战。特别是重复数据检测技术，其去重率及性能指标直接影响到数据去重的整体性能及去重效果。考虑到不同类应用产生的数据集，其特征差异较大，无法用一种重复数据检测算法来优化所有数据集去重。本文针对该问题开展重复数据检测算法研究。
　　从冗余度来说，目前数据大致可以分类两大类。一类是高冗余数据集。这种数据集多由备份、快照、归档等应用产生。在这类高冗余数据集中，数据通常表现出较强的相似性及数据局部性，如增量备份数据集，其主要呈现出较强的数据局部性，而全量备份、快照等则更多地呈现出数据的相似性。另一类数据集是冗余度相对较低的数据集，这类数据集内部含有较少的重复数据，数据集整体数据冗余度不高（相对备份数据集而言）。针对以上特点，作者根据不同的数据集特点提出了三种不同的算法来优化重复数据的检测。
　　针对数据局部性较强的数据集，作者提出一种高效的重复数据检索方法HsDedup。HsDedup同时利用布隆过滤器、哈希表及各种缓存机制充分挖掘数据的时间局部性及空间局部性，提高重复指纹的查找效率及指纹预取的准确性。具体的来说，对于数据流中可能的重复数据，HsDedup首先利用布隆过滤器对数据块的重复性进行预判，接下来根据不同的条件分别对缓存区的热区及冷区及磁盘进行三级重复数据的检测，充分利用重复数据中的局部性，提升重复数据的检测效能。从对HsDedup的测试来看，HsDedup比现有方案有着更优的重复指纹检索性能。
　　针对于数据相似性较强的数据集类型，作者提出了一种高效指纹检索方案RMD。RMD采用布隆过滤器阵列及数据相似算法，有效缩小指纹检索的范围。具体来说，RMD利用数据相似理论快速地定位相似的数据段，利用指纹容器对相似段中的指纹进行吸收及聚合。使指纹容器中的指纹样本不断聚集以提高数据去重效率同时减少磁盘的访问并提高指纹检索的效率。实验表明，该方案和其他现有方案有着相似的数据去重效率，并具备更高的指纹检索性能。
　　针对于缺乏数据局部性和相似性的数据集来说，作者原创性地提出一种精简索引表的策略。并把该策略应用于在线数据去重系统中的资源调度。具体来说，在源端数据去重系统中通过增加对高频指纹的检索，降低在线传输的数据量。在线数据去重（inline-deduplicaiton）系统中，低频度指纹转移到后处理数据去重（post-deduplication）服务器中，而高频度指纹得以保留。本文设计了一个在线数据去重方案Inte-dedupe，并对该方案中指纹清理环节进行了测试，从测试的结果来看，通过对在线数据去重系统中低频度指纹的转移，可以使其指纹索引表中的指纹数量减小到原来的约20％，性能得到两到三倍的提升，而在线数据去重在索引表中低频指纹清理后，相对去重率保持在92%以上。而这剩余不到8%漏检的重复数据则可以由后处理数据去重服务器来找回。

目录

声明

1绪 论

1.1研究背景和选题依据

1.2数据去重基本原理

1.3数据去重的分类

1.4课题研究内容

1.5论文章节安排

2数据去重的研究现状

2.1数据分块技术研究现状

2.2重复指纹检测技术研究现状

2.3源端去重与目的端去重的研究现状

3基于局部性优化的重复数据检测方法研究

3.1 HsDedup研究背景

3.2 HsDedup研究动机

3.3 HsDedup系统结构设计

3.4 HsDedup性能评估

3.5本章小结

4基于相似与融合的重复数据检测方法研究

4.1 RMD的研究背景与贡献

4.2 RMD的研究动机

4.3 RMD系统结构设计

4.4 RMD综合评估

4.5本章小结

5基于频度优化的重复数据检测研究

5.1 Inte-dedupe研究背景与贡献

5.2 Inte-dedupe的研究动机

5.3 Inte-dedupe在线去重系统结构设计

5.4相关评估

5.5本章小结

6全文总结与展望

致谢

参考文献

附录1：攻读学位期间发表的学术论文目录

附录2：攻读学位期间参与项目及申请的专利和软件著作权