英文摘要:Data de-duplication technology can be used to de-duplicate instances of the same data or similar data. Same data de-duplication includes de-duplication of fixed-length blocks, Content Defined Chunking (CDC), sliding blocks, and characteristic-based elimination of duplicate data algorithm. This technology is especially applicable in data backup systems, archival storage systems, and remote disaster recovery systems.
英文关键字:data de-duplication; storage; intelligent compression
基金项目：国家高技术研究发展(“863”)计划(2009AA01A403)
重复数据删除也称为智能压缩或单一实例存储，是一种可自动搜索重复数据，将相同数据只保留唯一的一个副本，并使用指向单一副本的指针替换掉其他重复副本，以达到消除冗余数据、降低存储容量需求的存储技术。
本文首先从不同角度介绍重复数据删除技术的分类，然后分别介绍相同数据重复数据删除技术和相似数据重复数据删除技术，并介绍重复数据消除的性能提升方法，最后分析重复数据技术的应用场景。
1 重复数据删除技术的分类
1.1 基于重复内容识别方法的分类
(1)基于散列识别
该方法通过数据的散列值来判断是否是重复数据。对于每个新数据块都生成一个散列，如果数据块的散列与存储设备上散列索引中的一个散列匹配，就表明该数据块是一个重复的数据块。Data Domain、飞康、昆腾的DXi系列设备都是采用SHA-1、MD-5等类似的散列算法来进行重复数据删除。
基于散列的方法存在内置的可扩展性问题。为了快速识别一个数据块是否已经被存储，这种基于散列的方法会在内存中拥有散列索引。随着数据块数量增加，该索引也随之增长。一旦索引增长超过了设备在内存中保存它所支持的容量，性能会急速下降，同时磁盘搜索会比内存搜索更慢。因此，目前大部分基于散列的系统都是独立的，可以保持存储数据所需的内存量与磁盘空间量的平衡。这样的设计使得散列表就永远不会变得太大。
(2)基于内容识别
该方法采用内嵌在数据中的文件系统的元数据识别文件，与其数据存储库中的其他版本进行逐字节地比较，找到该版本与第一个已存储版本的不同之处并为这些不同的数据创建一个增量文件。这种方法可以避免散列冲突，但是需要使用支持该功能的应用设备以便设备可以提取元数据。
(3)基于ProtecTier VTL的技术
这种方法像基于散列的方法产品那样将数据分成块，并且采用自有算法决定给定的数据块是否与其他数据块的相似，然后与相似块中的数据进行逐字节的比较，以判断该数据块是否已经被存储。
1.2 基于去重粒度的分类
(1)全文件层次的重复数据删除
以整个文件为单位来检测和删除重复数据，计算整个文件的哈希值，然后根据文件哈希值查找存储系统中是否存在相同的文件。这种方法的好处是在普通硬件条件下计算速度非常快；这种方法的缺点是即使不同文件存在很多相同的数据，也无法删除文件中的重复数据。
(2)文件块消冗
将一个文件按不同的方式划分成数据块，以数据块为单位进行检测。该方法的优点是计算速度快、对数据变化较敏感。
(3)字节级消冗
从字节层次查找和删除重复的内容，一般通过差异压缩策略生成差异部分内容。字节级消冗的优点是去重率比较高，缺点就是去重速度比较慢。
1.3 基于消冗执行次序的分类
(1)在线式消冗
在线处理的重复数据删除是指在数据写入磁盘之前执行重复数据删除。其最大的优点是经济高效，可以降低对存储容量的需求，并且不需要用于保存还未进行重复数据删除的数据集。在线处理的重复数据删除减少了数据量，但同时也存在一个问题，处理本身会减慢数据吞吐速度。正是因为重复数据删除是在写入到磁盘之前进行的，因此重复数据删除处理本身就是一个单点故障。
(2)后处理式消冗
后处理的重复数据删除，也被称为离线重复数据删除，是在数据写到磁盘后再执行重复数据删除。数据先被写入到临时的磁盘空间，之后再开始重复数据删除，最后将经过重复数据删除的数据拷贝到末端磁盘。由于重复数据删除是数据写入磁盘后再在单独的存储设备上执行的，因此不会对正常业务处理造成影响。管理员可以随意制订重复数据删除的进程。通常先将备份数据保留在磁盘上再进行重复数据删除，企业在需要时可以更快速地访问最近存储的文件和数据。而后处理方式的最大问题在于它需要额外的磁盘空间来保存全部还未删除的重复数据集。
1.4 基于实现层次的分类
(1)基于软件的重复数据删除
在软件层次，重复数据删除可以有两种集成方式，即可以将软件产品安装在专用的服务器上实现，也可以将其集成到备份/归档软件中。基于软件的重复数据删除的部署成本比较低；但是基于软件的重复数据删除在安装中容易中断运行，维护也更加困难。
基于软件的重复数据删除产品有EMC公司的Avamar软件产品、Symantec公司的Veritas NetBackup产品以及Sepaton公司的DeltaStor存储软件等。
(2)基于硬件的重复数据删除
基于硬件的重复数据删除主要由存储系统自己完成数据的删减，例如：在虚拟磁带库系统、备份平台或者网络附加存储(NAS)等一般目的的存储系统中融入重复数据删除机制，由这些系统自身完成重复数据删除功能。
基于硬件的重复数据删除的优点是高性能、可扩展性和相对无中断部署，并且重复数据删除操作对上层的应用都是透明的。这种设备的缺点就是部署成本比较高，要高于基于软件的重复数据删除。
目前基于硬件的重复数据删除系统主要包括VTL和NAS备份产品两大类，例如：Data Domain公司的DD410系列产品、Diligent Technologies公司的ProtecTier VTL、昆腾公司的DXi3500和DXi5500系列产品、飞康的VTL产品、ExaGrid Systems公司的NAS备份产品以及NetApp的NearStore R200和FAS存储系统。
2 相同数据重复数据删除技术
相同数据重复数据删除技术是将数据进行划分，找出相同的部分，并且以指针取代相同的数据存储。
2.1 相同文件重复数据删除技术
相同文件重复数据删除技术以文件为粒度查找重复数据[1]。如图1所示。相同文件重复数据删除技术先以整个文件为单位计算出哈希值(采用SHA-1或MD5算法)，然后与已存储的哈希值进行比较，如果发现相同的哈希值则认为该文件为重复的文件，不进行存储；否则，该文件为新文件，将该文件及其哈希值存储到系统中。
EMC的Centera系统[2]、Windows的单实例存储系统[3]采用了以文件为单位的数据消冗方法。
Windows2000的单一实例存储(SIS)应用该技术对具有20个不同Windows NT映像的服务器进行测试，结果表明总共节省了58%的存储空间。该方法的优点是重复数据删除的速度比较快，缺点是不能删除不同文件内部的相同数据。
2.2 固定长度分块的重复数据删除技术
基于固定长度分块的重复数据删除方法如图2所示。将数据对象(文件)分成互不重叠的定长块，然后计算每个数据块的哈希值，并将该哈希值与已存储的哈希值进行检索比较。如果发现相同的哈希值，则认为该数据块是重复的数据块，不存储该数据块，只存储其哈希值及引用信息；否则，认为该数据块是新数据块，则存储该数据块、其哈希值以及引用信息等等。
该方法存在的主要问题是：当向数据对象中插入数据或者从中删除数据时，会导致数据块边界无法对齐，严重地影响重复数据删除的效果。如图3所示，数据对象的版本1生成了n个定长数据块D1、D2……Dn。版本2在版本1的基础上插入了部分内容(阴影部分所示)。对版本2分块产生的数据块D1、D'2……D'n中，只有D1是重复的数据块，D'2……D'n都不是重复的数据块，使得数据对象中从插入位置到结尾的重复数据都无法被消除，影响了消冗率。
该方法已经在很多系统获得了应用，典型的应用是针对网络存储的Venti归档存储系统[4]。该系统采用该技术大约节省了30%的空间。
2.3 CDC算法的重复数据删除技术
针对上述问题，研究者提出了采用基于内容分块(CDC)的重复数据删除方法[5]。如图4所示。该方法的思路是通过一个不断滑动的窗口来确定数据块分界点，采用Rabin指纹算法计算滑动窗口的指纹，如果满足预定条件，就将该窗口的开始位置作为数据块的结尾，这样通过不断滑动窗口并计算指纹实现对数据对象的分块。为了避免极端情况下数据块过长或者过短的情况，可以设定数据块的下限和上限。对于每一个划分得到的数据块，就可以通过比较其哈希值来确定重复的数据块，具体过程与上面描述的相同。
因为数据块是基于内容而不是基于长度确定的，因此能够有效地解决上述问题。当数据对象中有内容插入或者删除时，如果插入或者删除的内容不在边界滑动窗口区域，该边界不会改变；当插入的内容产生一个新的边界时，一个数据块会分成两个数据块，否则数据块不会变化。如果变化的内容发生在滑动窗口内，可能会破坏分界数据块，导致两个数据块合成一个数据块，或者两个数据块之间的边界发生变化，产生新的数据块。因此，插入或者删除内容只影响相邻的一个或者两个数据块，其余数据块不会受影响，这就使得该方法能够检测出对象之间更多的重复数据。如图5所示，当文件中插入部分内容后，分块时将该内容划分到一个数据块中，保持其后续的数据块不变，从而保证后面重复的数据块都能够被删除。
该方法的典型应用包括：Shark[6]、Deep Store[7]和低带宽网络系统LBFS。
在LBFS系统中，系统对分块长度加上了上下边界长度，以避免数据块太长和太短的现象。
2.4 基于滑动块的重复数据删除技术
内容划分块方法解决了字节插入和删除的问题，但是引入了变长块的存储问题。在存储系统中，边长块的存储组织比较复杂。针对该问题，出现了基于滑动块重复数据删除检测消除方法[8]。该方法如图6所示，解决了定长块和内容划分块所存在的问题。
滑动块方法采用了Rsync Checksum算法和滑动窗口方法进行分块。Rsync Checksum算法具有计算速度快、效率高的优点。计算的Checksum值与以前存储的Checksum值进行比较，如果匹配，则与计算数据块的SHA-1值进行比较来检测重复数据。
如果发现重复数据块，则将重复数据块记录下来，并移动滑动窗口滑过该重复块，继续进行重复数据检测。另外，还要将从上个块结尾到新检测的重复块之间的数据块记录并存储下来。当Checksum值或者哈希值没有匹配上，继续数据检测过程。如果在发现重复块之前滑动窗口移动的距离达到定长块的长度，则计算该块的哈希值，并将该值存储下来供将来的数据块进行校验。
滑动块方法通过检测对象的每一个块解决数据插入问题。如果部分内容插入数据对象，只有周围的块发生变化，后面的块仍然能够通过该算法识别和检测。同理，当删除部分内容时，该部分内容之后的数据块不会受到影响，仍然可以采用该方法进行检测。
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余项。