重复数据删除技术的发展及应用

2.5 基于Fingerdiff算法的重复数据删除技术

针对基于内容的分块(CDC)算法额外存储空间开销比较大的问题，研究者提出了Fingerdiff算法，其核心思想是将没有变化的块尽可能的合并，以减少数据块的元数据所占用的存储空间。该技术包括3个主要过程：(1)一个文件按照CDC算法进行数据块划分；(2)每个子块按照Fingerdiff设置最大子块数进行合并；(3)每个块用Hash函数计算出它的指纹值，然后对比已存储的数据块指纹值，如果检测到相同的指纹值，则删除其对应的数据块，否则将大块进行拆分，找到最小的不同数据块进行存储，其余块仍然保持合并状态。

2.6 基于数据特征的重复数据消除算法

CDC的划分块策略虽然在一定程度上解决了定长块所存在的问题，但是针对特定类型的数据文件，仍然无法获得较好的数据块划分。针对该问题，出现了基于数据特征的数据块划分策略。例如针对PPT类型文件的划分策略，根据PPT文件的格式按每页PPT划分成不同的数据块，从而有效地将相同的PPT页面消除。另外有人提出了根据数据类型动态选择不同分块策略的重复数据删除技术，例如针对PPT文件和DOC文件采用基于文件特征的重复数据消除策略，针对可执行文件采用定长块的分块策略。

3 相似数据重复数据删除技术

除了通过删除完全相同的数据可以实现数据消冗外，还可以通过相似数据的检测与编码节省存储空间，提高存储空间的利用率。相似数据重复数据删除包括相似数据检测和编码两个阶段。相似数据检测技术有以下3种。

Shingle检测技术通过为每个文档提取一组特征[9]，从而将文档相似性问题简化为集合相似性问题。Shingle检测技术简单易实现，适用范围广，但它的计算开销很高，而且检测相似数据的精度取决于Shingle的取样技术，容易出现较大的偏差。

Bloom Filter是一种用位数组表示的集合[10]，支持查询某个元素是否在该集合当中。Bloom Filter弥补了Shingle检测技术难度高计算开销大的缺陷，在性能和相似数据精度之间取得了平衡。Bloom Filter进行数据匹配是通过位操作的，所以可以快速匹配，而且计算开销很小。

通过模式匹配挖掘数据的特征，也可以进行相似数据的检测。模式匹配技术的匹配算法是利用一定数量的公共字串来进行文件间的相似性查找与判别。该检测技术需要对整个文件扫描，所以开销也比较大。

在相似数据检测技术基础上，对有较大相似度的数据进行编码处理，同样能为整个系统节省大量的存储空间。相似数据压缩技术存在着编码效率和适用范围的问题。

4 重复数据删除的性能提升技术

重复数据删除技术在提高存储空间利用率的同时，为系统数据访问性能带来了一定影响。这是因为重复数据的检测过程序要耗费大量的系统资源，严重影响了存储系统访问性能。针对该问题，目前也出现了一系列的解决方案。

针对内存空间无法容纳所有数据索引的问题，Data Domain采用了三级查询机制[11]：Bloom Filter过滤、Hash缓冲查询和Hash文件查询。首先在内存中的Bloom Filter中进行查找。一个Bloom filter用一个m位向量来概括在块索引中n个块指纹值的存在信息。如果Bloom filter指出这个块不存在，则这个块一定不存在。如果Bloom filter指出该数据块存在，表明该数据块可能存在，再到Hash缓存中进行查找，如果存在则说明该数据块存在，否则再到磁盘上去查询。对于数据在磁盘上的组织采用了基于流的块排列技术，以有效利用数据的局部特性，提高缓存的命中率。

针对数据访问局部性特征不明显的系统，研究者提出了基于文件相似性的特点来降低重复数据删除过程中的查询次数，以提高重复数据删除性能；另外，有人也采用了两阶段的重复数据删除机制[12]，通过将随机的小磁盘I/O调整为序列化的大的磁盘I/O提高重复数据删除的吞吐率；还有人采用了两层次的索引技术来降低磁盘I/O次数[13]，提高重复数据删除的吞吐率。

分析现有技术可以看出，提高重复数据删除吞吐率的关键是降低磁盘I/O次数。现有方法都是通过各种策略来尽量减少数据块检索过程中磁盘的I/O次数。

5 重复数据删除技术的应用

5.1 数据备份系统

重复数据删除技术为数据保护领域带来革命性突破，有效地改善了磁盘数据保护的成本效益。因为在传统数据保护中无法实现重复数据删除，往往采用廉价的磁带库作为备份设备，而磁带备份在备份窗口、恢复速度方面难以满足用户的需求。现在，基于磁盘的数据保护方案如虚拟磁盘库(VTL)被广泛采用，并且在未来会继续增长。备份到VTL或其他基于磁盘的备份已经缩小了备份窗口，改善了备份和恢复能力，但由于数据量的不断增加，人们所要备份的数据越来越多，面临容量膨胀的压力。重复数据删除技术的出现，为最小化存储容量找到有效的方法。

5.2 归档存储系统

重复数据删除技术对归档存储非常重要。由于参考数据的数量不断增长，而法规遵从要求数据在线保留的时间更长，并且由于高性能需求需要采用磁盘进行归档，因此，企业一旦真正开始进行数据的归档存储就面临成本问题。理想的归档存储系统应能满足长期保存归档数据的需求，并且总拥有成本也要低于生产环境。重复数据删除技术通过消除冗余实现高效率的归档存储，从而实现最低的成本。目前，归档存储系统的重复数据删除技术主要是基于Hash的方法，产品的销售理念是以内容寻址存储(CAS)技术为主，分为纯软件和存储系统两类。

5.3 远程灾备系统

在远程灾备系统中，需要将大量的数据迁移到异地的系统中。随着数据量的不断增长，数据传输的压力越来越大，通过重复数据删除技术在数据传输前检测并删除重复的数据，可以有效地减少传输的数据量，提高数据传输速度，例如飞康的MicroScan软件就采用了该技术。

6 结束语

随着数字信息的爆炸式增长，所存在的重复数据越来越多，造成了存储资源的极大浪费。重复数据消除技术的出现在很大程度上缓解了该问题，该技术也得到了越来越广泛的认可。本文综合地介绍了重复数据消除技术的概念和发展现状，介绍了重复数据消除技术的应用场景，探讨了重复数据消除的发展趋势。

7 参考文献

[1] BOBBARJUNG D R, JAGANNATHAN S, DUBNICKI C. Improving Duplicate Elimination in Storage Systems [J]. ACM Transactions on Storage, 2006, 2(4):424-448.

[2] GUNAWI H S, AGRAWAL N, ARPACI-DUSSEAN A C, et al. Deconstructing Commodity Storage Clusters [C]//Proceedings of the 32nd International Symposium on Computer Architecture (ISCA’05), Jun 4-8, 2005, Madison, WI, USA. Los Alamitos, CA, USA: IEEE Computer Society, 2005: 60-71.

[3] BOLOSKY W J, CORBIN S, GOEBEL D, et al. Single Instance Storage in Windows 2000 [C]//Proceedings of the 4th USENIX Conference on File and Storage Technologies(FAST’05),Dec 13-16,2005, San Francisco, CA,USA. Berkeley, CA, USA: USENIX Association, 2005:13-24.

[4] QUINLAN S, DORWARD S. Venti: A New Approach to Archival Storage [C]//Proceedings of the 2nd USENIX Conference on File and Storage Technologies(FAST’02), Jan 28-30,2002, Monterey, CA,USA. Berkeley, CA, USA: USENIX Association, 2002:89-101.

[5] POLICRONIADES C, PRATT I. Alternatives for Detecting Redundancy in Storage Systems Data [C]//Proceedings of the 2004 USENIX Annual Technical Conference (USENIX’04), Jun 27-Jul 2, 2004, Boston, MA,USA. Berkeley, CA, USA: USENIX Association, 2004:73-86.

[6] ANNAPUREDDY S, FREEDMAN M J, MAZIERES D. Shark: Scaling File Servers Via Cooperative Caching [C]//Proceedings of the 2nd Symposium on Networked Systems Design and Implementation(NSDI'05),Mar 2-4,2004, Boston, MA, USA. Berkeley, CA, USA: USENIX Association, 2005:129-142.

[7] YOU L, POLLACK K, LONG D. Deep Store: An Archival Storage System Architecture [C]//Proceedings of the 21st IEEE International Conference on Data Engineering(ICDE’05), Apr 5-8, 2005, Tokyo, Japan. Los Alamitos, CA, USA: IEEE Computer Society, 2005: 804-815.

[8] BRODER A Z. Identifying and Filtering Near-duplicate Documents [C]//Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching(CPM’00), Jun 21-23, 2000, Montreal, Canada. Berlin, Germany: Springer-Verlag, 2000:1-10.

[9] DOUGLIS F, IYENGAR A. Application-specific Delta encoding Via Resemblance Detection [C]//Proceedings of the 2003 USENIX Annual Technical Conference (USENIX’03), Jun 9-14, 2003, San Antonio, TX,USA. Berkeley, CA, USA: USENIX Association, 2003:113-126.

[10] BRODER A Z, MITZENMACHER M. Network Applications of Bloom Filters: A Survey [J]. Internet Mathematics, 2003, 1(4):485-509.

[11] ZHU B, LI K, PATTERSON H. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System [C]//Proceedings of the 6th USENIX Conference on File and Storage Technologies(FAST’08), Feb 26-29, 2008, San Jose, CA, USA. Berkeley, CA, USA: USENIX Association, 2008: 1-14.

[12] YANG T, JIANG H, FENG D, et al. DEBAR: A Scalable High-performance De-duplication Storage System for Backup and Archiving [R]. TR-UNL-CSE-2009-0004.St Lincoln, NE, USA: University of Nebraska-Lincoln.2009.

[13] BHAGWAT D, ESHGHI K, LONG D E, et al. Extreme Binning: Scalable, Parallel Deduplication for Chunk-based File Backup [C]//Proceedings of the 17th IEEE International on Modeling, Analysis & Simulation of Computer and Telecommunication Systems(MASCOTS’09), Sep 21-23,2009, London, UK. Piscataway, NJ, USA: IEEE, 2009.

王树鹏，哈尔滨工业大学博士毕业；中科院计算所助理研究员，中科院计算所海量数据存储保护研究课题组组长；已发表学术论文20余篇，申请专利10余项。

作者：王树鹏 来源：中兴通讯技术——2010年 第5期