白皮书：重复数据删除技术解决方案.pdf

NETAPP 白皮书

真伪之辨:
评估重复数据删除解决方案

Larry Freeman, NetApp, Inc.
2007 年 9 月| WP-7028-0907
目录


重复数据删除的真伪之辨 3

什么是重复数据删除? 3

重复数据删除工作原理 3

重复数据删除设计的考虑因素 4

哈希法 4

哈希法利弊 5

索引法 5

索引法利弊 6

选择内嵌式还是后处理式 7

内嵌式与后处理式利弊 7

源位置或目标位置的重复数据删除 8

源位置及目标位置法利弊 8

重复数据删除的空间节约 8

空间节约的真谛 10

总结 10
2
重复数据删除的真伪之辨

毫无疑问,重复数据删除是数据存储界今年最热门的话题之一。重复数据删除所采用的基本原理
很简单:消除重复数据,减少备份及其它数据复制活动期间所需的存储容量。但是,在许多供应
商提供的各种各样的重复数据删除方法中,除了其独特的优点之外往往还隐藏着许多陷阱,让用
户受到蒙蔽。用户在考虑各种重复数据删除产品时,往往不会关注那些意义重大的基本设计差
别。

本白皮书将着重介绍重复数据删除的重要设计环节,为评估者提供基本信息,帮助其辨明重复数
据删除解决方案之真伪,在选购重复数据删除解决方案时能够做出明智选择。
什么是重复数据删除技术?

重复数据删除即“删除重复数据”的过程。“重复数据删除”这一术语是多年以前由数据库管理员提出
的,用来描述在合并两个数据库后删除重复数据库记录的过程。

在磁盘存储环境中,重复数据删除是指搜索重复数据对象(如数据块、数据束或文件)并删除这些
重复数据的任何算法。当检测到重复对象时,其参考指针将被修改。该对象仍然可以定位和搜索,
但它与其它相同的对象“共享”一个物理位置。此类数据共享是所有类型的重复数据删除的基础。
重复数据删除技术的工作原理

无论操作系统、应用程序或文件系统类型如何,所有数据对象都是通过数据参考指针写入到存储
系统中,没有参考指针将无法引用或检索数据。在传统(非重复数据删除)的文件系统中,数据
对象不论其相似性一律存储在同一个文件系统中。在图 1 中,文件系统内存储了五个相同的对
象,每个对象有着不同的数据指针。尽管所有五个数据对象都相同,但每个对象都是作为独立的
实例存储,每个对象都占用物理磁盘空间。

数据对象参考指针




已分配已分配已分配已分配已分配
存储存储存储
存储存储


图 1) 未经重复数据删除的数据
3
重复数据删除文件系统引入了两个重要的新概念:

•维护一个所有数据对象的目录。此目录包含所有数据对象的记录,它利用“哈希”来识别每
个对象的独特内容。本章后面的“重复数据删除设计的考虑因素”将详细讨论哈希法。

•文件系统能够支持许多数据指针引用相同的物理数据对象。

编目数据对象、比较对象和重定向参考指针构成重复数据删除算法的基础。如图 2 所示,用单个
主对象来引用多个相同对象,就可以将重复对象占用的空间归还给存储系统。


数据对象参考指针重复数据删除
目录/索引


免费免费已分配免费免费
存储存储存储存储存储

图 2) 删除重复的相同对象可以得到可用空间。

重复数据删除设计的考虑因素

由于所有重复数据删除供应商都必须保留某种形式的目录,且必须支持某种形式的数据块引用,
因此也就存在着五花八门的实施(它们都有着细微的差别,以便其申请专利)。以下部分阐述供
应商在设计重复数据删除时所使用的方法。
哈希法
重复数据删除的出发点是比较两个数据对象。在新对象写入数据卷时,扫描整个数据卷来查找重
复对象是不切实际的,同时也很困难。正由于此,重复数据删除供应商为每个新对象创建了小哈
希值,并将这些值存储在目录中。

哈希值又称为数字指纹或数字签名,它是从一个较长的数据串生成的较小编号。哈希值远小于数
据对象本身,它是由一种数学公式生成的,两个不相同的数据对象不太可能(尽管不是不可能)
产生相同的哈希值。

哈希值可以像奇偶校验计算一样简单,也可以像 SHA-1 或 MD-5 加密哈希一样复杂。在任何情况
下,一旦创建哈希值,就很容易进行比较,从而就可以识别重复数据删除的候选对象。

4
如果发现匹配的哈希值,则有两种方法来处理这些“候选对象”。首先,您可以假定哈希值相同始
终表示数据对象相同,然后直接