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

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值或者哈希值没有匹配上，继续数据检测过程。如果在发现重复块之前滑动窗口移动的距离达到定长块的长度，则计算该块的哈希值，并将该值存储下来供将来的数据块进行校验。

滑动块方法通过检测对象的每一个块解决数据插入问题。如果部分内容插入数据对象，只有周围的块发生变化，后面的块仍然能够通过该算法识别和检测。同理，当删除部分内容时，该部分内容之后的数据块不会受到影响，仍然可以采用该方法进行检测。

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