《高性能计算发展与应用》：重复数据删除技术研究进展（西安交通大学：姜晓夏、张兴军、王龙翔、伍卫国、董小社）

36<性能计算发展与应用21年第三期总第四十人朋 重复数据删除技术研究进展 ●姜晓夏张兴军王龙翔伍卫国董小社 安交通大学电子与信息工程学院西安710049 摘要 重复数据删除是一种在存储系统中检测并消除数据冗余的技术。它通过将数据进行划分 只存储单一内容及其他引用该内容的指针,达到缩减数据空间的目的。重复数据删除技术能够 极大地缩减数据存储容量需求,提高网络带宽利用率,降低企业运营成本,成为产业界和学 术界的研究热点。在EMC、BM、HP、 N eta pp、NEC等存储厂商的推动下,重复数据删除己 经逐渐成为存储系统的标准配置。本文首先介绍了重复数据删除技术的定义、分类,以及一般 过程。然后对重复数据删除领域一些热门问题的研究现状进行了总结。热门的研究问题包括主 存储和二级存储数据集特性、数据划分方法、减轻磁盘索引瓶颈、提高恢复性能、可靠性、可 扩展性等。最后通过对研究现状进行总结,结合存储和高性能计算的新兴技术,指出重复数据 删除技术未来可能的研究方向。 键词:重复数据删除,数据集特性,磁盘索引瓶颈,恢复性能,可扩展性 根据⑩C的预测,到2020年,全球数字量将会膨 重复数据删除发生的位置、时机以及重复检测 胀到40ZB,而这一数字量将继续以每两年翻一番的粒度可以根据应用场景来综合选择。一般情况下, 速度增长。需要加以保护的数据比率将从2010年的相比于目的端去重,源端去重可以在缩减数据量的 不到三分之一增长到2020年的40%以。企业数据中心同时节约网络带宽,但消耗客户端资源:在线去重 的存储需求量越来越庞大,已从之前的TB级上升到相比于后处理去重会增加系统延迟,但不用进行额 PB级,甚至EB级。 外的磁盘读写:去重的粒度越细,获得的数据缩减 研究发现,在备份和归档存储系统中,有高达率越高,但付出的代价也越大。 80%90%的数据冗余。虚拟化系统(如 VM ware 除了对数据缩减率的考虑,重复数据删除延长 Ⅹen等)中的操作系统镜像间也产生了大量的冗余数了存储系统的D0路径,因此如何减少额外的I0代 据,基于虚拟机的主存储系统中有80%的冗余B对价,提高系统的吞吐率是一个经典的研究热点。此 文件服务器来说,邮件和文档也会成为主要的重复外,对系统恢复性能、可靠性、可扩展性等问题的 来源。这些系统都可以用重复数据删除技术来有效研究都取得了一定的进展 地节约存储空间。重复数据删除技术还可以用来减 本文第一节描述了重复数据删除技术的基本概 少网络中传输的数据量,从而缓解数据量的井喷式念、分类及关键指标。第二节介绍了重复数据删除 增长给企业带来的高存储容量和高带宽要求 般过程。第三节对重复数据删除技术各热点研究 重复数据删除技术应需求而生,并得到了广问题进行了总结。第四节对本文进行总结,并提出 泛应用。据⑩C的统计,在2010年,基于磁盘的重今后可能的研究方向。 复数据删除备份设备保护了468PB的数据,预计 到2015年,这一数字将超过8EB田。目前重复数据1.重复数据删除技术介绍 删除技术主要应用于备份和归档的二级存储系统 本节介绍重复数据删除技术的基本概念、分类 中5,在虚拟机环境下的主存储系统中也有应 以及几个重要的评价指标 用。与传统的数据压缩和编码不同,重复数据删除 技术既可以消除文件内的冗余,又可以消除文件间1.1重复数据删除技术的概念 的冗余。 重复数据删除是一种在存储系统中检测并消 肖除

36 《高性能计算发展与应用》 2014年第三期 总第四十八期 重复数据删除技术研究进展  姜晓夏 张兴军 王龙翔 伍卫国 董小社 西安交通大学电子与信息工程学院 西安 710049 摘要： 重复数据删除是一种在存储系统中检测并消除数据冗余的技术。它通过将数据进行划分， 只存储单一内容及其他引用该内容的指针，达到缩减数据空间的目的。重复数据删除技术能够 极大地缩减数据存储容量需求，提高网络带宽利用率，降低企业IT运营成本，成为产业界和学 术界的研究热点。在EMC、IBM、HP、NetApp、NEC等存储厂商的推动下，重复数据删除已 经逐渐成为存储系统的标准配置。本文首先介绍了重复数据删除技术的定义、分类，以及一般 过程。然后对重复数据删除领域一些热门问题的研究现状进行了总结。热门的研究问题包括主 存储和二级存储数据集特性、数据划分方法、减轻磁盘索引瓶颈、提高恢复性能、可靠性、可 扩展性等。最后通过对研究现状进行总结，结合存储和高性能计算的新兴技术，指出重复数据 删除技术未来可能的研究方向。 关键词：重复数据删除，数据集特性，磁盘索引瓶颈，恢复性能，可扩展性 根据IDC的预测，到2020年，全球数字量将会膨 胀到40ZB，而这一数字量将继续以每两年翻一番的 速度增长。需要加以保护的数据比率将从2010年的 不到三分之一增长到2020年的40%[1]。企业数据中心 的存储需求量越来越庞大，已从之前的TB级上升到 PB级，甚至EB级[2]。 研究发现，在备份和归档存储系统中，有高达 80%~90%的数据冗余。虚拟化系统（如VMware、 Xen等）中的操作系统镜像间也产生了大量的冗余数 据，基于虚拟机的主存储系统中有80%的冗余[3]。对 文件服务器来说，邮件和文档也会成为主要的重复 来源。这些系统都可以用重复数据删除技术来有效 地节约存储空间。重复数据删除技术还可以用来减 少网络中传输的数据量，从而缓解数据量的井喷式 增长给企业带来的高存储容量和高带宽要求。 重复数据删除技术应需求而生，并得到了广 泛应用。据IDC的统计，在2010年，基于磁盘的重 复数据删除备份设备保护了468PB的数据，预计 到2015年，这一数字将超过8EB[4]。目前重复数据 删除技术主要应用于备份和归档的二级存储系统 中[5][6][7][8][9][10]，在虚拟机环境下的主存储系统中也有应 用[3]。与传统的数据压缩和编码不同，重复数据删除 技术既可以消除文件内的冗余，又可以消除文件间 的冗余。 重复数据删除发生的位置、时机以及重复检测 粒度可以根据应用场景来综合选择。一般情况下， 相比于目的端去重，源端去重可以在缩减数据量的 同时节约网络带宽，但消耗客户端资源；在线去重 相比于后处理去重会增加系统延迟，但不用进行额 外的磁盘读写；去重的粒度越细，获得的数据缩减 率越高，但付出的代价也越大。 除了对数据缩减率的考虑，重复数据删除延长 了存储系统的I/O路径，因此如何减少额外的I/O代 价，提高系统的吞吐率是一个经典的研究热点。此 外，对系统恢复性能、可靠性、可扩展性等问题的 研究都取得了一定的进展。 本文第一节描述了重复数据删除技术的基本概 念、分类及关键指标。第二节介绍了重复数据删除 一般过程。第三节对重复数据删除技术各热点研究 问题进行了总结。第四节对本文进行总结，并提出 今后可能的研究方向。 1. 重复数据删除技术介绍 本节介绍重复数据删除技术的基本概念、分类 以及几个重要的评价指标。 1.1 重复数据删除技术的概念 重复数据删除是一种在存储系统中检测并消除

高性能计算技术37 数据冗余的技术。它将数据进行划分,并与已经存的所有写请求都在写入之前进行哈希检测、重复消 储的数据内容进行比对,对检测到重复的数据,用除、更新元数据,因此延长了写I路径,降低系统 指向原来存储位置的指针来代替存储重复的数据内吞吐率υ。在线重复数据删除技术可与源端重复数据 容,从而实现存储空间的节约。重复数据删除技术删除技术联合使用,在目的端维持一张最新的索引 的执行过程可被简称为去重 表供源端查询,以减少网络中传输数据量 如图1所示,文件1、2、3各自有6MB大小,在 后处理重复数据删除技术要求将完整数据先写 重复数据删除之前,按顺序依次存储共需要占用18入存储,然后当系统空闲时对这些数据用批处理的 MB的空间。重复数据删除技术将每个文件切分成方式进行去重。这种方式要求系统有额外的空间来 IMB大小的块,检测重复数据块,通过比较判断出文存储去重之前的数据,且由于要先对全部数据进行 件2中的每个块都已经在之前被存储过,同理在文件写入,然后读出,因此增加了额外的I0。对于在线 3中检测出4个重复的数据块。去重后的3个文件大小或后处理方式的选择,需要考虑到应用场合对性能 共8MB,达到了节约存储空间的目的。相比于传统的的要求。 数据压缩技术,重复数据删除技术不仅可以消除文 后处理重复数据删除技术适用于对访问延迟 件内的数据冗余,还能消除共享数据集内文件之间要求较高的场合,如主存储D3。而在线重复数据删 的数据冗余 除技术一般应用于对吞吐率要求较高、对延迟要求 ABC ABCBCE 低的二级存储b。也有少量主存储系统如 DEF DEF edup5、DBLK采用在线重复数据删除,并且采 文件2 文件3总大小 用选择性去重减少系统访问延迟。 原始大小6 18 VB 1.2.3不同粒度的重复数据删除技术 去重后大小6姻 重复数据删除技术可以根据数据划分和重复检 图1重复数据删除概念示例 测的粒度分为文件级去重、块级去重以及相似检测 和编码技术。文件级去重可以检测出相同内容的文 1.2重复数据删除技术的分类 件,但不能检测出文件内部的冗余。由于其计算速 1.2.1源端重复数据删除和目的端重复数据删除 度快,元数据量小,因此应用非常广泛。块级去重 重复数据删除可以在客户端、存储控制器,或按照分块方法的不同又可以分为固定分块(FSC)、 者专门的重复数据删除服务器上进行。按照重复数基于内容分块(CDC)、滑动分块(SW)等。文献 据删除发生的位置,可以分为源端去重和目的端去[7对这三种分块方法进行了性能评测。结果显示 SW方法在所有的数据集上都能达到最优的数据缩减 客户端指要进行去重的数据来源的位置。如果结果,其次是CDC,FSC最差。但SW占用的元数据量 对于一台邮件服务器中的数据进行备份,则客户端也是这三种方法中最多的,其次是FSC,CDC在这三 指邮件服务器。发生在客户端的重复数据删除技术者中最节约元数据空间 被称为源端去重ω。源端去重需要在客户端进行数 没有一种技术能够适用于所有的应用场景。重 据的划分和指纹值的计算,然后将指纹序列发送给复数据删除发生的位置、时间、数据划分方法的选 目的端,目的端进行重复检测,将结果返回给客户择需要综合考虑各种因素。这些因素包括应用场景 端,客户端仅需要在网络中传输去重后的数据2。源中的数据冗余特性,对于延迟的要求,对于恢复性 端去重具有节约网络带宽的优点,但是分块和指纹能的要求,备份时间窗口的限制,以及网络传输带 值计算操作会加重客户端的负担。 宽的限制 发生在存储控制器或者重复数据删除服务器上 的重复数据删除技术称为目的端去重叫。目的端去1.3重复数据删除系统的关键指标 重要求客户端将完整的文件内容发送到目的端进行 重复数据删除系统的首要目标是缩减存储空 数据划分和哈希值计算操作,因此不占用客户端资间,文献8]定义了衡量数据缩减程度的重要指标 源,但最大的弊端是不能节约网络传输带宽ω。 称为数据缩减率。定义数据缩减率r为 1.22在线重复数据删除和后处理重复数据删除 重复数据删除可以发生在数据写入磁盘之前, 称为在线重复数据删除:也可以发生在数据写入磁 盘之后,称为后处理重复数据删除 式(1)中:s为输入数据量即存储数据的逻辑 在线重复数据删除技术对于向存储系统发出大小,而实际存储的数据大小等于去重后的数据s与

高性能计算技术 37 数据冗余的技术。它将数据进行划分，并与已经存 储的数据内容进行比对，对检测到重复的数据，用 指向原来存储位置的指针来代替存储重复的数据内 容，从而实现存储空间的节约。重复数据删除技术 的执行过程可被简称为去重。 如图1所示，文件1、2、3各自有6MB大小，在 重复数据删除之前，按顺序依次存储共需要占用18 MB的空间。重复数据删除技术将每个文件切分成 1MB大小的块，检测重复数据块，通过比较判断出文 件2中的每个块都已经在之前被存储过，同理在文件 3中检测出4个重复的数据块。去重后的3个文件大小 共8MB，达到了节约存储空间的目的。相比于传统的 数据压缩技术，重复数据删除技术不仅可以消除文 件内的数据冗余，还能消除共享数据集内文件之间 的数据冗余。 图1 重复数据删除概念示例 1.2 重复数据删除技术的分类 1.2.1 源端重复数据删除和目的端重复数据删除 重复数据删除可以在客户端、存储控制器，或 者专门的重复数据删除服务器上进行。按照重复数 据删除发生的位置，可以分为源端去重和目的端去 重。 客户端指要进行去重的数据来源的位置。如果 对于一台邮件服务器中的数据进行备份，则客户端 指邮件服务器。发生在客户端的重复数据删除技术 被称为源端去重[11]。源端去重需要在客户端进行数 据的划分和指纹值的计算，然后将指纹序列发送给 目的端，目的端进行重复检测，将结果返回给客户 端，客户端仅需要在网络中传输去重后的数据[12]。源 端去重具有节约网络带宽的优点，但是分块和指纹 值计算操作会加重客户端的负担。 发生在存储控制器或者重复数据删除服务器上 的重复数据删除技术称为目的端去重[11]。目的端去 重要求客户端将完整的文件内容发送到目的端进行 数据划分和哈希值计算操作，因此不占用客户端资 源，但最大的弊端是不能节约网络传输带宽[11]。 1.2.2 在线重复数据删除和后处理重复数据删除 重复数据删除可以发生在数据写入磁盘之前， 称为在线重复数据删除；也可以发生在数据写入磁 盘之后，称为后处理重复数据删除。 在线重复数据删除技术对于向存储系统发出 的所有写请求都在写入之前进行哈希检测、重复消 除、更新元数据，因此延长了写I/O路径，降低系统 吞吐率[12]。在线重复数据删除技术可与源端重复数据 删除技术联合使用，在目的端维持一张最新的索引 表供源端查询，以减少网络中传输数据量。 后处理重复数据删除技术要求将完整数据先写 入存储，然后当系统空闲时对这些数据用批处理的 方式进行去重。这种方式要求系统有额外的空间来 存储去重之前的数据，且由于要先对全部数据进行 写入，然后读出，因此增加了额外的I/O。对于在线 或后处理方式的选择，需要考虑到应用场合对性能 的要求。 后处理重复数据删除技术适用于对访问延迟 要求较高的场合，如主存储[13]。而在线重复数据删 除技术一般应用于对吞吐率要求较高、对延迟要求 低的二级存储[5][6][7][8][9][10][14]。也有少量主存储系统如 iDedup[15]、DBLK[16]采用在线重复数据删除，并且采 用选择性去重减少系统访问延迟。 1.2.3 不同粒度的重复数据删除技术 重复数据删除技术可以根据数据划分和重复检 测的粒度分为文件级去重、块级去重以及相似检测 和编码技术。文件级去重可以检测出相同内容的文 件，但不能检测出文件内部的冗余。由于其计算速 度快，元数据量小，因此应用非常广泛。块级去重 按照分块方法的不同又可以分为固定分块（FSC）、 基于内容分块（CDC）、滑动分块（SW）等。文献 [17]对这三种分块方法进行了性能评测。结果显示， SW方法在所有的数据集上都能达到最优的数据缩减 结果，其次是CDC，FSC最差。但SW占用的元数据量 也是这三种方法中最多的，其次是FSC，CDC在这三 者中最节约元数据空间。 没有一种技术能够适用于所有的应用场景。重 复数据删除发生的位置、时间、数据划分方法的选 择需要综合考虑各种因素。这些因素包括应用场景 中的数据冗余特性，对于延迟的要求，对于恢复性 能的要求，备份时间窗口的限制，以及网络传输带 宽的限制。 1.3 重复数据删除系统的关键指标 重复数据删除系统的首要目标是缩减存储空 间，文献[18]定义了衡量数据缩减程度的重要指标， 称为数据缩减率。定义数据缩减率r为 （1） 式（1）中：si为输入数据量即存储数据的逻辑 大小，而实际存储的数据大小等于去重后的数据so与

38<性能计算发展与应用2年第三总第四十人朋 额外产生的元数据s之和。其中,元数据s包括两部2.2重复检测 分:记录文件对应哈希序列的元数据和索引表元数 重复检测这一过程非常关键。它是将计算好 据。对于同一个数据集,越大,重复数据删除效果的各指纹值与己存储的数据的指纹值进行比较的过 越好 程。去重系统需要维持一张索引表以供查询,其中 重复数据删除系统的吞吐率也是一个重要的衡每个索引项记录了一个指纹以及该指纹对应的数据 量指标,这里说的吞吐率是写吞吐率。吞吐率衡量内容在磁盘上的存储位置和引用次数。对于数据量 了单位时间内被重复数据删除系统所处理和存储的大的系统,完整的索引表需要存储在磁盘上,加载 逻辑数据量。相比于一般的存储系统,重复数据删到内存中的索引项通常以散列表或者B+树的形式进 除系统可能会因为引入的额外计算和查询过程造成行组织,以加快查询速度。在内存查询不命中时需 吞吐率的降低,但是也有可能因为减少了大量重复要进行随机的磁盘访问,因此在数据量大的时候, 数据的实际读写过程而使吞吐率增大。目前有很多重复检测过程是去重系统的性能瓶颈。 研究专注于提高系统的吞吐率b9。 通过查询索引表,可以获取指纹值是否已经存 重复数据删除系统的读性能可以用单位时间在的信息。对于已经存在的指纹值,不再进行对应 内从去重系统读取的数据量来度量。由于数据块共数据内容的存储,只是更新索引项中数据块的引用 享,逻辑上连续的数据经过去重后在物理上不再连次数:对于新的指纹值,进行数据存储和元数据更 续,因此重复数据删除系统的数据读取速度比一般新。在冗余消除的过程中,有的时候为了降低数据 的存储系统要差。对于二级存储,读取速度即恢复块分布的碎片化程度,会进行选择性的消除,以保 速度,决定了系统是否能在要求的恢复时间窗口完持数据恢复性能2。 成数据恢复:对于主存储系统则决定了系统的读延 。针对提高恢复速度也开展了大量研究u5m。2.3数据存储 对于上一步重复检测判断为不存在的指纹,需 2.重复数据删除的一般过程 将其数据内容和元数据信息写入磁盘。元数据信息 重复数据删除的一般执行过程可以划分成 即一个索引项的全部内容,包括指纹值、数据块位 个阶段。首先对接收到的数据流进行划分和指纹计置、引用次数。如果以数据块或者索引项为单位进 算,然后对获得的指纹值进行重复检测,最后根据行写入,则会引起大量的随机I 检测的结果进行相应的数据存储或者元数据更新操 在一些利用数据流的重复局部性进行性能优化 的系统中,数据内容和元数据以 con tainer为单位进行 存储和读写B。 Con taine是一个自治的单位,大小 2.1数据划分和指纹计算 般能够存放一千到几千个数据块及它们对应的元 在这一阶段,首先根据预先设定好的策略对数数据。经检测为不重复的数据,先写入内存中为该 据进行划分,然后对划分好的数据单元(可以是文数据流开放的 con tainer缓存中,如果 con tainer已满则 件、或者数据块)分别计算指纹,最后记录构成每将其整个写到磁盘中。恢复过程中也是以 con tainer为 个文件的指纹序列。 单位加载数据和元数据。这么做的目的有四:第 指纹是指利用抗冲突特性好的哈希算法(如,充当写缓存,避免了过多的磁盘随机I0:第 SHA-1,MD5)对数据内容计算得到的一个固定长二, con tainer中的数据和元数据都维持了数据流的逻 度的值,该值可以用来唯一标识数据内容。在判别辑顺序,存在数据流重复局部性:第三,在读的时 数据单元内容是否相同的时候,采用逐字节的方法候以 con tainer为单位进行预取,可以提高缓存命中 本身比对过程慢,而且需要先将原先存储的内容读率;第四,合理的 Icon taine大小可以使底层的RAD达 出,对系统吞吐率影响非常大師。因此,重复数据删 到全条带写。 除系统通过指纹来判断数据内容的相同与否。 对于一个EB级的存储系统,采用160位的SHA 3.重复数据删除技术研究现状 1算法,发生哈希冲突的概率在10-2以下B。如果未 对重复数据删除技术的研究集中在以下几个方 来数据量继续增大,可以选择位数更多的哈希算法面 降低哈希冲突的概率,NST提供了256、384、512位 1)数据集研究 的SHA算法。因此两个指纹值相同的数据块或者文件 对于不同应用场景下数据集特征的研究对设计 可以被认为完全相同。 存储系统来说非常重要。 M icrosof2和EMC分别对 主存储和二级存储文件系统上的文件的一般特征进

38 《高性能计算发展与应用》 2014年第三期 总第四十八期 额外产生的元数据sm之和。其中，元数据sm包括两部 分：记录文件对应哈希序列的元数据和索引表元数 据。对于同一个数据集，r越大，重复数据删除效果 越好。 重复数据删除系统的吞吐率也是一个重要的衡 量指标，这里说的吞吐率是写吞吐率。吞吐率衡量 了单位时间内被重复数据删除系统所处理和存储的 逻辑数据量。相比于一般的存储系统，重复数据删 除系统可能会因为引入的额外计算和查询过程造成 吞吐率的降低，但是也有可能因为减少了大量重复 数据的实际读写过程而使吞吐率增大。目前有很多 研究专注于提高系统的吞吐率[5][6][7][8][19][20]。 重复数据删除系统的读性能可以用单位时间 内从去重系统读取的数据量来度量。由于数据块共 享，逻辑上连续的数据经过去重后在物理上不再连 续，因此重复数据删除系统的数据读取速度比一般 的存储系统要差。对于二级存储，读取速度即恢复 速度，决定了系统是否能在要求的恢复时间窗口完 成数据恢复；对于主存储系统则决定了系统的读延 迟。针对提高恢复速度也开展了大量研究[15][21][22][23]。 2. 重复数据删除的一般过程 重复数据删除的一般执行过程可以划分成三 个阶段。首先对接收到的数据流进行划分和指纹计 算，然后对获得的指纹值进行重复检测，最后根据 检测的结果进行相应的数据存储或者元数据更新操 作。 2.1 数据划分和指纹计算 在这一阶段，首先根据预先设定好的策略对数 据进行划分，然后对划分好的数据单元（可以是文 件、或者数据块）分别计算指纹，最后记录构成每 个文件的指纹序列。 指纹是指利用抗冲突特性好的哈希算法（如 SHA-1，MD5）对数据内容计算得到的一个固定长 度的值，该值可以用来唯一标识数据内容。在判别 数据单元内容是否相同的时候，采用逐字节的方法 本身比对过程慢，而且需要先将原先存储的内容读 出，对系统吞吐率影响非常大[5]。因此，重复数据删 除系统通过指纹来判断数据内容的相同与否。 对于一个EB级的存储系统，采用160位的SHA- 1算法，发生哈希冲突的概率在10-20以下[37]。如果未 来数据量继续增大，可以选择位数更多的哈希算法 降低哈希冲突的概率，NIST提供了256、384、512位 的SHA算法。因此两个指纹值相同的数据块或者文件 可以被认为完全相同。 2.2 重复检测 重复检测这一过程非常关键。它是将计算好 的各指纹值与已存储的数据的指纹值进行比较的过 程。去重系统需要维持一张索引表以供查询，其中 每个索引项记录了一个指纹以及该指纹对应的数据 内容在磁盘上的存储位置和引用次数。对于数据量 大的系统，完整的索引表需要存储在磁盘上，加载 到内存中的索引项通常以散列表或者B+树的形式进 行组织，以加快查询速度。在内存查询不命中时需 要进行随机的磁盘访问，因此在数据量大的时候， 重复检测过程是去重系统的性能瓶颈[14]。 通过查询索引表，可以获取指纹值是否已经存 在的信息。对于已经存在的指纹值，不再进行对应 数据内容的存储，只是更新索引项中数据块的引用 次数；对于新的指纹值，进行数据存储和元数据更 新。在冗余消除的过程中，有的时候为了降低数据 块分布的碎片化程度，会进行选择性的消除，以保 持数据恢复性能[22][23]。 2.3 数据存储 对于上一步重复检测判断为不存在的指纹，需 将其数据内容和元数据信息写入磁盘。元数据信息 即一个索引项的全部内容，包括指纹值、数据块位 置、引用次数。如果以数据块或者索引项为单位进 行写入，则会引起大量的随机I/O。 在一些利用数据流的重复局部性进行性能优化 的系统中，数据内容和元数据以container为单位进行 存储和读写[5][6][24]。Container是一个自治的单位，大小 一般能够存放一千到几千个数据块及它们对应的元 数据。经检测为不重复的数据，先写入内存中为该 数据流开放的container缓存中，如果container已满则 将其整个写到磁盘中。恢复过程中也是以container为 单位加载数据和元数据。这么做的目的有四：第 一，充当写缓存，避免了过多的磁盘随机I/O；第 二，container中的数据和元数据都维持了数据流的逻 辑顺序，存在数据流重复局部性；第三，在读的时 候以container为单位进行预取，可以提高缓存命中 率；第四，合理的container大小可以使底层的RAID达 到全条带写。 3. 重复数据删除技术研究现状 对重复数据删除技术的研究集中在以下几个方 面。 1) 数据集研究 对于不同应用场景下数据集特征的研究对设计 存储系统来说非常重要。Microsoft[25]和EMC[26]分别对 主存储和二级存储文件系统上的文件的一般特征进

高性能计算技术39 行了研究和比较,并对其冗余特性进行了重点分析超过96%的文件在磁盘上连续存储。除此之外,还在 研究 该数据集上对WFC、FSC、CDC三种去重算法进行了 2)提升数据缩减率 数据缩减率指标的评估。实验表明,全部857个文件 为提高数据缩减率,研究者提出了多种经典的系统经过CDC的处理可以将空间缩减到原来的32% 数据划分算法28,并针对经典的算法进行改而其中3A的冗余可以用WFC和稀疏文件技术检测 进890。除此之外,研究者还将数据压缩技术、相到。相比于取得的空间提升,主存储去重使用CDC代 似检测和编码技术与相同数据检测相结合,以获取价高昂。 更高的数据缩减率 EMC利用从10000个 Data d om ain用户中收集到 3)减少去重代价 的备份文件系统(DDFS)的元信息,对备份文件系 去重过程中会产生两类元数据:第一类记录统的文件特性和冗余特性进行研究,并与文献25的 文件哈希序列,与存储数据的逻辑大小成正比:第研究结果做对比。备份文件系统中的文件特性与主 类是索引表元数据,与存储数据的物理大小成正存储呈现出很大的不同2。由于主流的备份软件如 比。当数据缩减率很高的时候,元数据会占用相当 EMC Netl orker、 Sym an tec NetB ackup通常会对要进 大的一部分空间。一些研究者提出了在保持算法冗行备份的数据先打包再传送到备份设备,因此备份 余检测能力的情况下通过增加块平均大小8或者压文件系统中的文件平均大小比主存储高三个数量 缩元数据来缩减元数据空间。 级。拼接后的大文件完全相同的概率非常低,因此 去重过程使得数据存储I路径变长,影响写数WFC不适用。此外,研究发现备份文件系统还具有 据的延迟和吞吐率ω。提升去重系统吞吐率的研究以下特点:文件结构扁平:文件平均寿命比主存储 有很多,研究者从分块和指纹值计算B、索引表查短:单位时间(每周)文件流失率高达21%:写操作 询5]、写数据和元数据各个阶段分别提出提高占的比例高:空间利用率较主存来说高:在典型的 系统吞吐率的方法 应用场景中应用基于内容的去重算法可以节约10倍 去重过程引入了数据块共享,使得逻辑上连续以上空间。 的数据物理上不连续,数据恢复需要进行多次L0。 经典的重复数据删除算法并不能完全适用于所 围绕这一问题,一些研究者提出了衡量读性能的指有的应用场景。对应用场景中数据集特性的掌握是 标,并提出了提升读性能的方法mB 设计高效重复数据删除算法的首要条件。 M icrosoft和 去重会导致一个关键的数据块被很多文件共EMC的研究代表了存储环境的两大类型,有普遍意 享,这一关键数据块的丢失会造成很多文件不可恢义。对于更加专门的应用环境,如邮件服务器、网 复0。一些研究者提出通过冗余复制技术om域或者页服务器:更加单一的数据类型,如银行交易数 纠删码技术来增加去重系统的可靠性 据、天文数据等,可以设计有针对性的数据缩减方 4)系统可扩展性研究 随着企业数据量的迅速增长,单节点无法满足 吞吐率和容量要求。文献]9]35]37]B8]重复数3.2数据划分方式研究 据删除技术在集群存储中应用的可扩展性问题进行 在对数据划分方式的研究中,主要追求两个目 了研究 的:第一,寻找合适的边界点使得划分的数据块能 够尽可能的被检测出冗余:第二,在检测到冗余不 3.1数据集特性研究 变的情况下,尽量增大数据块的平均大小,以减少 数据缩减率从根本上取决于数据本身的冗余程元数据开销。 度。研究数据集特性对于设计去重算法非常重要 已有的数据划分方式有以下几种 M icrosoft25和EMC2分别针对主存储和二级存储文件 1)全文件划分( W hole file chunk ing) 系统中的数据集特性进行了研究。 全文件划分,简称为WFC,是一种以文件为 对通用文件系统的研究很多,比较有代表性的粒度进行去重的数据划分方式,即对整个文件内容 是 M icrosoft的研究。 M icrosoft搜集了857台微软工作计算指纹,具有相同指纹的文件内容仅进行一次存 人员4周时间内个人电脑文件系统上的数据,对文件储。EMC的 Centeral9和 W indow s2000的Ss都采用 系统元数据(文件大小分布、类型分布、目录和文这种技术实现重复数据删除。SI对具有20个不同 件数目分布、空间利用率等〕进行了研究,该研究 W indows NTI映像的服务器进行测试,共节省了58% 对于文件系统的设计和优化非常有意义。微软还对的存储空间。文献配5的研究表明,在通用主存 文件在磁盘上存储的连续性进行了研究,结果表明储文件系统上,超过3A的冗余数据可以通过WFC和

高性能计算技术 39 行了研究和比较，并对其冗余特性进行了重点分析 研究。 2) 提升数据缩减率 为提高数据缩减率，研究者提出了多种经典的 数据划分算法[14][17][27][28]，并针对经典的算法进行改 进[18][29][30]。除此之外，研究者还将数据压缩技术、相 似检测和编码技术与相同数据检测相结合，以获取 更高的数据缩减率。 3) 减少去重代价 去重过程中会产生两类元数据：第一类记录 文件哈希序列，与存储数据的逻辑大小成正比；第 二类是索引表元数据，与存储数据的物理大小成正 比。当数据缩减率很高的时候，元数据会占用相当 大的一部分空间[31]。一些研究者提出了在保持算法冗 余检测能力的情况下通过增加块平均大小[18][30]或者压 缩元数据[31]来缩减元数据空间。 去重过程使得数据存储I/O路径变长，影响写数 据的延迟和吞吐率[12]。提升去重系统吞吐率的研究 有很多，研究者从分块和指纹值计算[32][33]、索引表查 询[5][6][8][9][20]、写数据和元数据[5]各个阶段分别提出提高 系统吞吐率的方法。 去重过程引入了数据块共享，使得逻辑上连续 的数据物理上不连续，数据恢复需要进行多次I/O。 围绕这一问题，一些研究者提出了衡量读性能的指 标，并提出了提升读性能的方法[21][22][23][34]。 去重会导致一个关键的数据块被很多文件共 享，这一关键数据块的丢失会造成很多文件不可恢 复[11]。一些研究者提出通过冗余复制技术[10][17][35]或者 纠删码技术[14]来增加去重系统的可靠性。 4) 系统可扩展性研究 随着企业数据量的迅速增长，单节点无法满足 吞吐率和容量要求。文献[7][19][35][37][38]就重复数 据删除技术在集群存储中应用的可扩展性问题进行 了研究。 3.1 数据集特性研究 数据缩减率从根本上取决于数据本身的冗余程 度。研究数据集特性对于设计去重算法非常重要。 Microsoft[25]和EMC[26]分别针对主存储和二级存储文件 系统中的数据集特性进行了研究。 对通用文件系统的研究很多，比较有代表性的 是Microsoft的研究[25]。Microsoft搜集了857台微软工作 人员4周时间内个人电脑文件系统上的数据，对文件 系统元数据（文件大小分布、类型分布、目录和文 件数目分布、空间利用率等）进行了研究，该研究 对于文件系统的设计和优化非常有意义。微软还对 文件在磁盘上存储的连续性进行了研究，结果表明 超过96%的文件在磁盘上连续存储。除此之外，还在 该数据集上对WFC、FSC、CDC三种去重算法进行了 数据缩减率指标的评估。实验表明，全部857个文件 系统经过CDC的处理可以将空间缩减到原来的32%， 而其中3/4的冗余可以用WFC和稀疏文件技术检测 到。相比于取得的空间提升，主存储去重使用CDC代 价高昂[25]。 EMC利用从10000个Data Domain用户中收集到 的备份文件系统（DDFS）的元信息，对备份文件系 统的文件特性和冗余特性进行研究，并与文献[25]的 研究结果做对比。备份文件系统中的文件特性与主 存储呈现出很大的不同[26]。由于主流的备份软件如 EMC NetWorker、Symantec NetBackup通常会对要进 行备份的数据先打包再传送到备份设备，因此备份 文件系统中的文件平均大小比主存储高三个数量 级。拼接后的大文件完全相同的概率非常低，因此 WFC不适用。此外，研究发现备份文件系统还具有 以下特点：文件结构扁平；文件平均寿命比主存储 短；单位时间（每周）文件流失率高达21%；写操作 占的比例高；空间利用率较主存来说高；在典型的 应用场景中应用基于内容的去重算法可以节约10倍 以上空间。 经典的重复数据删除算法并不能完全适用于所 有的应用场景。对应用场景中数据集特性的掌握是 设计高效重复数据删除算法的首要条件。Microsoft和 EMC的研究代表了存储环境的两大类型，有普遍意 义。对于更加专门的应用环境，如邮件服务器、网 页服务器；更加单一的数据类型，如银行交易数 据、天文数据等，可以设计有针对性的数据缩减方 案。 3.2 数据划分方式研究 在对数据划分方式的研究中，主要追求两个目 的：第一，寻找合适的边界点使得划分的数据块能 够尽可能的被检测出冗余；第二，在检测到冗余不 变的情况下，尽量增大数据块的平均大小，以减少 元数据开销。 已有的数据划分方式有以下几种。 1) 全文件划分（Whole File Chunking） 全文件划分，简称为WFC，是一种以文件为 粒度进行去重的数据划分方式，即对整个文件内容 计算指纹，具有相同指纹的文件内容仅进行一次存 储。EMC的Centera[39]和Windows 2000的SIS[27]都采用 这种技术实现重复数据删除。SIS对具有20个不同 Windows NT映像的服务器进行测试，共节省了58% 的存储空间[27]。文献[25]的研究表明，在通用主存 储文件系统上，超过3/4的冗余数据可以通过WFC和

40c性能计算发展与应用201年第三期总第四十人明 稀疏文件技术检测出。WFC最大的优点是计算速度出双除数以解决边界点条件难以匹配的问题。 快阿,缺点是不能识别文件内部的冗余数据 由于平均分块大小会影响到元数据量,进一步 2)固定分块算法(Fied- sized Chunking) 影响处理速度,其他对于CDC算法的改进致力于在保 固定分块算法,简称为FSC。由于全文件划分无持数据缩减率的情况下增加平均分块的大小,以减 法检测出文件内部的冗余,研究者提出了块级别的少元数据开销。 Fingerd方法的主要思想是:首先 数据划分方法,其中最简单的是固定分块算法按照CDC算法对文件进行切分,切分后的块称为子 固定分块算法将数据流按照预先设定的长度进行划块:之后将连续的新子块或者连续的旧子块合并 分,对每个数据块计算指纹,然后进行后续的重复最多合并多少个连续子块由预先设定的参数决定 检测。早期的Vent和 Foundation E.用固定分块算最后为合并后的数据子块记录元数据。因为连续的 法来检测重复。 V.是一个基于磁盘的归档系统, 数据子块得到了合并,因此平均长度变大。 B im odal 采用固定分块算法缩减了大约30%的存储空间。文CDC8的思想是采用双参数,进行两个粒度的CDC划 献阻1采用固定块哈希的方法减少在虚拟机迁移时网分。数据流中的临界区是指从重复区域到非重复区 络传输的数据量。FSC能够检测出文件内部的冗余数域过渡或者是从非重复区域到重复区域过渡的部 据,因此相对于WFC能够获取更大的数据压缩比m。分。算法的目的是确定临界区并且只在临界区对数 FSC的局限性体现在其对插入和删除操作非常敏感 据流进行细粒度的划分,非临界区的块维持在粗粒 哪怕一个字节的插入或者删除都会影响之后所有重度,从而增加平均分块大小。 复数据块的检测。 4)滑动分块算法 3)基于内容的分块( Content-defined Chunking) CDC算法尽管解决了FSC的增删问题,但引入了 为克服固定分块算法对数据插入和删除敏感的不好管理的变长数据块。BM的研究者提出了一种结 问题, LBFS中提出了一种基于内容的变长分块算合CDC与FSC优点的数据划分方法,称为滑动分块算 法(CDC算法)。算法过程如图2所示:CDC算法利 1,划分过程如图3所示。 用 Rabin指纹来确定数据块的边界,从文件头开始 用一个固定大小的窗口(如48B)在文件上逐字节 滑动,每滑动一个字节,计算其 Rab in指纹值,并 判断该值是否满足边界点条件。边界点条件可以用 hW房D=r来表示,其中hW)是窗口内容的 Rabin指 纹,D是期望分块大小,r是预先设定的余数 界点条件不满足,则继续滑动到下一字节进行相同 图3滑动分块过程0 的计算和判断。边界点条件如果满足,则将窗口的 滑动分块技术用固定块大小的窗口在文件上滑 右边界作为数据块边界,对划分出的数据块进行指动,与CDC不同的是,这个滑动窗口要大得多,是期 纹计算,进行后续的重复检测。CDC算法将少量插入望分块的大小(如4KB),并且采用 rsync求和校验函 和删除的影响控制在附近的一到两个块之内,相对数来计算窗口中数据的校验和,校验和相对于哈希 FSC来说能检测出更多的冗余。但CDC算法需要逐字计算速度快的多。将求得的校验和与已经存储的校 节进行Rabi指纹计算,极端情况下计算次数几乎与验和的集合进行比较,如果没有匹配,则继续滑动 文件的字节数相同,因此效率相比FSC低得多 窗口:如果找到了匹配的项,则进一步的计算比对 强哈希SHA-1,若SHA-1已经存在,则窗口跨过重复 块继续滑动。如果窗口滑过了一个块的长度仍然没 有找到重复的数据内容,则把已经滑过去的内容作 为单独的数据块进行单独存储,连同这个数据块的 SHA-1和 rsync值。 滑动分块技术对插入问题和删除问题处理高 Hash Values Duplcate 效,同时具有FSC分块大小固定和CDC数据缩减率高 图2基于内容分块过程07 的优点。插入一小部分数据或删除一小部分数据会 目前,CDC及其改进算法已经得到广泛的应形成一个小于固定块长度的碎片,并不影响周围重 用。文献巴9]研究了数据块大小分布对数据缩减率复块的识别。实验表明,对于相同的数据集,滑动 的影响,对LBFS的变长分块算法进行改进,提出分块算法相对于FSC和CDC算法能检测出更多的冗余 TTTD算法,给出数据块大小的上限和下限,并且给数据。但是滑动分块技术需要同时存储所有数据块

40 《高性能计算发展与应用》 2014年第三期 总第四十八期 稀疏文件技术检测出。WFC最大的优点是计算速度 快[35]，缺点是不能识别文件内部的冗余数据。 2) 固定分块算法（Fixed-sized Chunking） 固定分块算法，简称为FSC。由于全文件划分无 法检测出文件内部的冗余，研究者提出了块级别的 数据划分方法，其中最简单的是固定分块算法[11]。 固定分块算法将数据流按照预先设定的长度进行划 分，对每个数据块计算指纹，然后进行后续的重复 检测。早期的Venti[14]和Foundation[40]采用固定分块算 法来检测重复。Venti是一个基于磁盘的归档系统， 采用固定分块算法缩减了大约30%的存储空间[14]。文 献[41]采用固定块哈希的方法减少在虚拟机迁移时网 络传输的数据量。FSC能够检测出文件内部的冗余数 据，因此相对于WFC能够获取更大的数据压缩比[42]。 FSC的局限性体现在其对插入和删除操作非常敏感， 哪怕一个字节的插入或者删除都会影响之后所有重 复数据块的检测[11]。 3) 基于内容的分块（Content-defined Chunking） 为克服固定分块算法对数据插入和删除敏感的 问题，LBFS[28]中提出了一种基于内容的变长分块算 法（CDC算法）。算法过程如图2所示：CDC算法利 用Rabin指纹来确定数据块的边界，从文件头开始， 用一个固定大小的窗口（如48B）在文件上逐字节 滑动，每滑动一个字节，计算其Rabin指纹值，并 判断该值是否满足边界点条件。边界点条件可以用 h(W)%D=r来表示，其中h(W)是窗口内容的Rabin指 纹，D是期望分块大小，r是预先设定的余数[29]。边 界点条件不满足，则继续滑动到下一字节进行相同 的计算和判断。边界点条件如果满足，则将窗口的 右边界作为数据块边界，对划分出的数据块进行指 纹计算，进行后续的重复检测。CDC算法将少量插入 和删除的影响控制在附近的一到两个块之内，相对 FSC来说能检测出更多的冗余。但CDC算法需要逐字 节进行Rabin指纹计算，极端情况下计算次数几乎与 文件的字节数相同，因此效率相比FSC低得多。 图2 基于内容分块过程[17] 目前，CDC及其改进算法已经得到广泛的应 用。文献[29]研究了数据块大小分布对数据缩减率 的影响，对LBFS的变长分块算法进行改进，提出 TTTD算法，给出数据块大小的上限和下限，并且给 出双除数以解决边界点条件难以匹配的问题。 由于平均分块大小会影响到元数据量，进一步 影响处理速度，其他对于CDC算法的改进致力于在保 持数据缩减率的情况下增加平均分块的大小，以减 少元数据开销。Fingerdiff[30]方法的主要思想是：首先 按照CDC算法对文件进行切分，切分后的块称为子 块；之后将连续的新子块或者连续的旧子块合并， 最多合并多少个连续子块由预先设定的参数决定； 最后为合并后的数据子块记录元数据。因为连续的 数据子块得到了合并，因此平均长度变大。Bimodal CDC[18]的思想是采用双参数，进行两个粒度的CDC划 分。数据流中的临界区是指从重复区域到非重复区 域过渡或者是从非重复区域到重复区域过渡的部 分。算法的目的是确定临界区并且只在临界区对数 据流进行细粒度的划分，非临界区的块维持在粗粒 度，从而增加平均分块大小。 4) 滑动分块算法 CDC算法尽管解决了FSC的增删问题，但引入了 不好管理的变长数据块。IBM的研究者提出了一种结 合CDC与FSC优点的数据划分方法，称为滑动分块算 法[17]，划分过程如图3所示。 图3 滑动分块过程[17] 滑动分块技术用固定块大小的窗口在文件上滑 动，与CDC不同的是，这个滑动窗口要大得多，是期 望分块的大小（如4KB），并且采用rsync求和校验函 数来计算窗口中数据的校验和，校验和相对于哈希 计算速度快的多。将求得的校验和与已经存储的校 验和的集合进行比较，如果没有匹配，则继续滑动 窗口；如果找到了匹配的项，则进一步的计算比对 强哈希SHA-1，若SHA-1已经存在，则窗口跨过重复 块继续滑动。如果窗口滑过了一个块的长度仍然没 有找到重复的数据内容，则把已经滑过去的内容作 为单独的数据块进行单独存储，连同这个数据块的 SHA-1和rsync值。 滑动分块技术对插入问题和删除问题处理高 效，同时具有FSC分块大小固定和CDC数据缩减率高 的优点。插入一小部分数据或删除一小部分数据会 形成一个小于固定块长度的碎片，并不影响周围重 复块的识别。实验表明，对于相同的数据集，滑动 分块算法相对于FSC和CDC算法能检测出更多的冗余 数据。但是滑动分块技术需要同时存储所有数据块

高性能计算技术41 因此元数据量比以上两种方法都要多置信息 的校验和与指纹值,以及与它们对应的位置 采用 B loom Filter技术,对索引表进行全局抽象。 B loom Filter占用空间小,可以常驻内存,插入和查 5)基于应用的分块 询时间都是常数。对于 B loom filter判断为不存在的 以上的几种数据划分方法都是通用的,没有指纹,可以直接认为其在索引表中也不存在;对于 考虑到数据的语义。如果考虑到不同文件格式的差 Bloom filter判断为存在的指纹,需访问索引表进行进 异,为不同的文件类型设计专用的数据划分方法 一步验证。采用 Bloom filter有效的避免了对新指纹进 就能够获取更高的数据缩减率。 ADMAD眵是一个基行査询时的磁盘访问。 DBLK DE主存储系统提出了 于应用的去重归档系统。 ADMAD对于文件的划分是多层 Bloom filter,以使用少量内存存储尽量多的索引 与应用相关的,即理解文件语义的。它利用文件的信息 元数据,对不同数据类型的文件自动选择与之适应 2)利用数据流重复局部性进行优化 的分块策略,并针对MP3,FLV,HTML和 Em ail等文 在传统的磁盘到磁盘的备份中,备份客户端将 件类型设计了不同的分块策略,实验表明基于应用目录树合并成大文件,或者是客户端产生满足虚拟 分块相对于基于内容分块能够获得更高的数据缩减磁带库协议的文件0。以备份操作为例,第一次备份 率B。 中同一个文件夹下有B、C、D这三个文件。假设按照 6)Delt编码技术 B、C、D的顺序进行处理和存储,那么在后续的备份 Del编码是以字节为粒度进行重复数据删除的中,有极大的可能性B的后面接着C、D文件。在文件 技术。采用 shingling、 B lom Filter等相似性检测技术的内部也存在着重复局部性,一个文件可能包含成 检测数据的相似性:然后对相似度超过某个阈值的千上万个数据块,即使文件有修改,这些数据块在 数据采用 Delta编码的方法,存储一个块相对于基准后续的备份中也有极大的可能性一起出现b。数据 块的变化部分。由于Del编码进行数据比对的粒流的重复局部性在这种传统的以任务为粒度的备份 度最小,其数据缩减率最高。Dela编码可以作为重中表现得较为明显,对于新型的备份操作,即以单 复块检测技术的补充,对于检测为相似的数据块进个文件为粒度的备份操作,或者是增量备份,这种 行进一步的编码。但是块的重建会降低系统读取数局部性表现较弱 据的性能。 数据流的重复局部性对于设计高效的去重系统 去重系统的数据缩减率与几个因素有关:第有如下启发。在上面的例子中,如果将B、C、D这 数据本身的冗余程度:第二,数据划分策略 个文件的索引项连续存放,那么在查询B文件块 合适的边界点能够识别出更多的冗余数据块:第指纹的时候,可以连续加载一大段索引表到内存 ,数据块的平均大小,更小的数据块意味着检测这样,对于C和D的指纹查找也极有可能在缓存中命 重复的粒度更细,但同时意味着更高的元数据开销中,减少了随机访问磁盘的次数。目前利用数据流 和计算开销。在以上提出的不同的数据划分算法的重复局部性减轻磁盘访问瓶颈的系统有很多,以 中,WFC和FSC主要被应用于主存储中,而在二级存 EM C Data dom ain系列产品的DDFS和HPD2D产品的 储的产品和研究中几乎都用CDC或者其改进算法。 Sparse Indexing技术为代表 DDFS采用了摘要向量,SBL技术,以及保持局 33减轻磁盘索引瓶颈 部性的缓存策略LPC,使査询过程中的访问磁盘操作 指纹值查询是去重检测过程中关键的一步 减少了99%。DDFS将逻辑上连续的数据块在磁盘上 在数据量小的时候,整个索引表可以放在内存中 连续存放,其对应的索引项也连续存放,以保持数 只要索引表在内存中采用的组织方式合理,查询时据流的重复局部性,称为SISL。SISL配合高命中率的 间就可以控制在常数范围,并且实现全局去重。但缓存LPC,有效地减少了代价 是,索引表会随着数据量的增加而线性增长。对于 HP的D2D备份系统采用基于数据流局部性的稀 8TB的数据,以4KB大小分块,每个索引项40字节 疏索引技术。 Sparse Indexing将到达的数据流划分成 仅指纹值就要占用80GB的空间。当索引表大到无法相对较大的段,每个段只相对于最为相似的几个段 装到内存中时,查询过程就要进行磁盘访问,这种做重复检测。当两个段有多个样本相似的时候,认 频繁的随机访问过程成为去重过程的瓶颈 为这两个段相似。这种方法减少了指纹查询的比较 )利用 Bloom filter进行优化 范围,是一种局部去重的方法。在获得相同数据缩 Ⅴent采用索引缓存和块缓存来减少磁盘访问减量的情况下,采用 Sparse Indexing技术相对DDFS内 次数,但是由于哈希值分布的随机性,缓存命中率存用量更小。 非常低。 Data dom ain5、 HYDRA stor、 Foundation0 3)利用文件相似性进行L0优化

高性能计算技术 41 的校验和与指纹值，以及与它们对应的位置信息， 因此元数据量比以上两种方法都要多[17]。 5) 基于应用的分块 以上的几种数据划分方法都是通用的，没有 考虑到数据的语义。如果考虑到不同文件格式的差 异，为不同的文件类型设计专用的数据划分方法， 就能够获取更高的数据缩减率。ADMAD[9]是一个基 于应用的去重归档系统。ADMAD对于文件的划分是 与应用相关的，即理解文件语义的。它利用文件的 元数据，对不同数据类型的文件自动选择与之适应 的分块策略，并针对MP3，FLV，HTML和Email等文 件类型设计了不同的分块策略，实验表明基于应用 分块相对于基于内容分块能够获得更高的数据缩减 率[9]。 6) Delta编码技术 Delta编码是以字节为粒度进行重复数据删除的 技术。采用shingling、Bloom Filter等相似性检测技术 检测数据的相似性；然后对相似度超过某个阈值的 数据采用Delta编码的方法，存储一个块相对于基准 块的变化部分[11]。由于Delta编码进行数据比对的粒 度最小，其数据缩减率最高。Delta编码可以作为重 复块检测技术的补充，对于检测为相似的数据块进 行进一步的编码。但是块的重建会降低系统读取数 据的性能。 去重系统的数据缩减率与几个因素有关：第 一，数据本身的冗余程度；第二，数据划分策略， 合适的边界点能够识别出更多的冗余数据块；第 三，数据块的平均大小，更小的数据块意味着检测 重复的粒度更细，但同时意味着更高的元数据开销 和计算开销。在以上提出的不同的数据划分算法 中，WFC和FSC主要被应用于主存储中，而在二级存 储的产品和研究中几乎都用CDC或者其改进算法。 3.3 减轻磁盘索引瓶颈 指纹值查询是去重检测过程中关键的一步。 在数据量小的时候，整个索引表可以放在内存中， 只要索引表在内存中采用的组织方式合理，查询时 间就可以控制在常数范围，并且实现全局去重。但 是，索引表会随着数据量的增加而线性增长。对于 8TB的数据，以4KB大小分块，每个索引项40字节， 仅指纹值就要占用80GB的空间。当索引表大到无法 装到内存中时，查询过程就要进行磁盘访问，这种 频繁的随机访问过程成为去重过程的瓶颈。 1) 利用Bloom Filter进行优化 Venti[14]采用索引缓存和块缓存来减少磁盘访问 次数，但是由于哈希值分布的随机性，缓存命中率 非常低。Data Domain[5]、HYDRAstor[7]、Foundation[40] 采用Bloom Filter[46]技术，对索引表进行全局抽象。 Bloom Filter占用空间小，可以常驻内存，插入和查 询时间都是常数。对于Bloom Filter判断为不存在的 指纹，可以直接认为其在索引表中也不存在；对于 Bloom Filter判断为存在的指纹，需访问索引表进行进 一步验证。采用Bloom Filter有效的避免了对新指纹进 行查询时的磁盘访问[5]。DBLK[16]主存储系统提出了 多层Bloom Filter，以使用少量内存存储尽量多的索引 信息。 2) 利用数据流重复局部性进行I/O优化 在传统的磁盘到磁盘的备份中，备份客户端将 目录树合并成大文件，或者是客户端产生满足虚拟 磁带库协议的文件[19]。以备份操作为例，第一次备份 中同一个文件夹下有B、C、D这三个文件。假设按照 B、C、D的顺序进行处理和存储，那么在后续的备份 中，有极大的可能性B的后面接着C、D文件。在文件 的内部也存在着重复局部性，一个文件可能包含成 千上万个数据块，即使文件有修改，这些数据块在 后续的备份中也有极大的可能性一起出现[5][6]。数据 流的重复局部性在这种传统的以任务为粒度的备份 中表现得较为明显，对于新型的备份操作，即以单 个文件为粒度的备份操作，或者是增量备份，这种 局部性表现较弱[19]。 数据流的重复局部性对于设计高效的去重系统 有如下启发。在上面的例子中，如果将B、C、D这 三个文件的索引项连续存放，那么在查询B文件块 指纹的时候，可以连续加载一大段索引表到内存。 这样，对于C和D的指纹查找也极有可能在缓存中命 中，减少了随机访问磁盘的次数。目前利用数据流 的重复局部性减轻磁盘访问瓶颈的系统有很多，以 EMC Data Domain系列产品的DDFS[5]和HP D2D产品的 Sparse Indexing[6]技术为代表。 DDFS采用了摘要向量，SISL技术，以及保持局 部性的缓存策略LPC，使查询过程中的访问磁盘操作 减少了99%[5]。DDFS将逻辑上连续的数据块在磁盘上 连续存放，其对应的索引项也连续存放，以保持数 据流的重复局部性，称为SISL。SISL配合高命中率的 缓存LPC，有效地减少了I/O代价。 HP的D2D备份系统采用基于数据流局部性的稀 疏索引技术。Sparse Indexing[6]将到达的数据流划分成 相对较大的段，每个段只相对于最为相似的几个段 做重复检测。当两个段有多个样本相似的时候，认 为这两个段相似。这种方法减少了指纹查询的比较 范围，是一种局部去重的方法。在获得相同数据缩 减量的情况下，采用Sparse Indexing技术相对DDFS内 存用量更小。 3) 利用文件相似性进行I/O优化

42c性能计算发展与应用20年第三期总第四十人期 考虑一种更细粒度的备份场景,到达服务器端得不进行多次L0和频繁寻道。由于机械磁盘的随机 的并不是大的数据流,而是随机的不同来源的单个0性能与顺序L性能的巨大差距,这种碎片化的分 文件。这种情况下,在一个给定的时间窗口内,文布严重影响了恢复性能。文献B4观察了两个数据集 件之间没有局部性。这种类型的场景有:NAS客户的恢复性能随时间变化的规律,其中一个数据集在 端做的备份和恢复请求,持续数据保护,一经收到个月内恢复性能下降了4倍,而另一在两年后下降 立刻进行备份的电子邮件系统吟9。 Extrem e b inn ing技了11倍 术将索引表分层:第一层为文件索引,放在内存 块碎片形成的原因是数据块共享,即新的数据 中;第二层为块索引,以bin为单位放在磁盘上。对需要引用之前存储数据的重复内容,而在恢复的时 于每一个文件的查询只进行一次磁盘访问,相对于 候就需要访问旧数据的存储位置。在备份系统中 Ⅴent大大减少了磁盘访问频率。 Extrem e B inning可以这一现象在最近的备份中表现最为明显,糟糕的是 很容易的扩展到分布式环境下。同 Sparse Indexing最近的备份是最有可能被恢复的。关于数据恢复性 样, Extrem e b inning是一种局部去重的策略。 能的研究,目前有几项重要进展。 4)索引表分层策略 1)提出恢复性能的量化指标 索引表分层策略基于真实数据的冗余特性。 Nam等人提出用 CFL ( Chunk Fragm entation Level) DEBAR8提是一个后处理的重复数据删除系统,它提来衡量碎片化程度2,定义为理论上应该占用的 出了两阶段去重策略。第一阶段利用前一次备份的 con taner数目与实际读取的 con tamer数目的比例。经 元数据过滤掉大部分的重复数据,实现源端去重 验证CFL与恢复性能之间存在着近乎线性的关系, 第二阶段对剩余的数据块进行离线的批处理。在备但是CFL忽略了数据集内部相互引用的情况,因此并 份的场景下,大多数的冗余产生于单个用户的连不能衡量内部重复率高时的恢复性能。HP的研究者 续备份。DAM田根据这一特点,在内存中建立了用也定义了一个块碎片化程度的衡量指标,用恢复每 户、组、全局三级索引表。 Extrem e B inn ing的索引MB数据平均所需读出的 con taine的真实个数作为碎 表分层也有效地减少了查询范围 片化的度量,并且将其倒数作为衡量恢复性能的指 5)基于SSD的优化策略 标( speed factor)阴。相对于CFL,HP定义的指标也 新型的存储介质SSD具有高I0PS数、高吞吐能够适用于数据集内部引用频率高的场合。在典型 量、低访问延迟的特点。它的随机读取性能比普通的应用中, con taner大小一般是4MB,上述两个指 磁盘高出几个数量级。 Chunks tash和 dedupv1采标可以较好地标识恢复性能。但是在 con tane大小变 用固态盘来存储索引表,并且设计实现了符合固态化的时候,会影响评价的准确性。这是因为上述指 盘特征的数据存储方式和算法,以整页为单位对固标基于一个基本假设: con tainer的读取时间与它的长 态盘进行写入,从而彻底消除了磁盘随机Io瓶颈 度成正比,当 con taner过小的时候,寻道时间相对于 Chunkstash相对于传统的磁盘存储技术可以有7-60倍读取的时间过长。 的性能提升 2)提出在写过程中确保以后恢复性能的方法 目前减轻磁盘索引瓶颈的技术已经相对成熟 主存储去重系统 iD edup为了获取可接受的读 研究者利用 B loom filter、数据集重复局部性特性、文延迟,仅对于在磁盘上连续存放且连续块数超过一 件相似性、索引表分层或者利用新型的存储介质减定阈值的数据块序列进行去重。文献②2]提出了一 少査询过程中的磁盘访问,减少内存用量。磁盘索种保持数据读性能的机制。在备份过程中持续监控 引瓶颈引起的根本原因是索引表大小超过了内存的每个数据流的CFL即碎片化指标,一旦其低于某个 承受能力。在存储集群日益普及的现在,可以通过阈值,就从全去重模式切换到选择去重模式,直到 划分索引表、进行分布式査询来解除单节点的内存CFL回到阈值以上。在选择去重模式下,仅对连续长 度超过某个阈值的重复块进行去重。这种方法的缺 点在于去重与否与数据块的顺序有关,并且忽略了 34恢复性能 读缓存的作用。缓存大小的区域中可能包含了多个 尽管重复数据删除技术为企业节省了十几倍属于同一个 con taner的重复序列,但因为每个序列的 甚至几十倍的存储空间,但由于块碎片( Chunk长度都不超过给定的阈值,即使重复数据块占整个 Fragm en tation)的存在,这些备份系统的恢复性能变 con tamer的比重较高,仍会被当做新数据进行处理。 差,并且随着备份数据的累积而变得更加严重2 而事实上,由于读缓存的存在,一次 con tamer的读取 块碎片是指一次逻辑备份的所有数据块在磁盘就可以完成所有重复数据的恢复,并不会造成读性 上分散存储。这种存储方式使得数据在恢复时,不能恶化。文献B4提出的 Capping和文献23]中提出的

42 《高性能计算发展与应用》 2014年第三期 总第四十八期 考虑一种更细粒度的备份场景，到达服务器端 的并不是大的数据流，而是随机的不同来源的单个 文件。这种情况下，在一个给定的时间窗口内，文 件之间没有局部性。这种类型的场景有：NAS客户 端做的备份和恢复请求，持续数据保护，一经收到 立刻进行备份的电子邮件系统[19]。Extreme Binning技 术将索引表分层：第一层为文件索引，放在内存 中；第二层为块索引，以bin为单位放在磁盘上。对 于每一个文件的查询只进行一次磁盘访问，相对于 Venti大大减少了磁盘访问频率。Extreme Binning可以 很容易的扩展到分布式环境下。同Sparse Indexing一 样，Extreme Binning是一种局部去重的策略。 4) 索引表分层策略 索引表分层策略基于真实数据的冗余特性。 DEBAR[38]是一个后处理的重复数据删除系统，它提 出了两阶段去重策略。第一阶段利用前一次备份的 元数据过滤掉大部分的重复数据，实现源端去重； 第二阶段对剩余的数据块进行离线的批处理。在备 份的场景下，大多数的冗余产生于单个用户的连 续备份。DAM[47]根据这一特点，在内存中建立了用 户、组、全局三级索引表。Extreme Binning[19]的索引 表分层也有效地减少了查询范围。 5) 基于SSD的优化策略 新型的存储介质SSD具有高IOPS数、高吞吐 量、低访问延迟的特点。它的随机读取性能比普通 磁盘高出几个数量级。ChunkStash[20]和dedupv1[24]采 用固态盘来存储索引表，并且设计实现了符合固态 盘特征的数据存储方式和算法，以整页为单位对固 态盘进行写入，从而彻底消除了磁盘随机I/O瓶颈。 ChunkStash相对于传统的磁盘存储技术可以有7-60倍 的性能提升。 目前减轻磁盘索引瓶颈的技术已经相对成熟。 研究者利用Bloom Filter、数据集重复局部性特性、文 件相似性、索引表分层或者利用新型的存储介质减 少查询过程中的磁盘访问，减少内存用量。磁盘索 引瓶颈引起的根本原因是索引表大小超过了内存的 承受能力。在存储集群日益普及的现在，可以通过 划分索引表、进行分布式查询来解除单节点的内存 限制。 3.4 恢复性能 尽管重复数据删除技术为企业节省了十几倍 甚至几十倍的存储空间，但由于块碎片（Chunk Fragmentation）的存在，这些备份系统的恢复性能变 差，并且随着备份数据的累积而变得更加严重[21]。 块碎片是指一次逻辑备份的所有数据块在磁盘 上分散存储。这种存储方式使得数据在恢复时，不 得不进行多次I/O和频繁寻道。由于机械磁盘的随机 I/O性能与顺序I/O性能的巨大差距，这种碎片化的分 布严重影响了恢复性能。文献[34]观察了两个数据集 的恢复性能随时间变化的规律，其中一个数据集在 三个月内恢复性能下降了4倍，而另一在两年后下降 了11倍。 块碎片形成的原因是数据块共享，即新的数据 需要引用之前存储数据的重复内容，而在恢复的时 候就需要访问旧数据的存储位置。在备份系统中， 这一现象在最近的备份中表现最为明显，糟糕的是 最近的备份是最有可能被恢复的。关于数据恢复性 能的研究，目前有几项重要进展。 1) 提出恢复性能的量化指标 Nam等人提出用CFL（Chunk Fragmentation Level） 来衡量碎片化程度[21]，定义为理论上应该占用的 container数目与实际读取的container数目的比例。经 验证CFL与恢复性能之间存在着近乎线性的关系， 但是CFL忽略了数据集内部相互引用的情况，因此并 不能衡量内部重复率高时的恢复性能。HP的研究者 也定义了一个块碎片化程度的衡量指标，用恢复每 MB数据平均所需读出的container的真实个数作为碎 片化的度量，并且将其倒数作为衡量恢复性能的指 标（speed factor）[34]。相对于CFL，HP定义的指标也 能够适用于数据集内部引用频率高的场合。在典型 的应用中[5]，container大小一般是4MB，上述两个指 标可以较好地标识恢复性能。但是在container大小变 化的时候，会影响评价的准确性。这是因为上述指 标基于一个基本假设：container的读取时间与它的长 度成正比，当container过小的时候，寻道时间相对于 读取的时间过长。 2) 提出在写过程中确保以后恢复性能的方法 主存储去重系统iDedup[15]为了获取可接受的读 延迟，仅对于在磁盘上连续存放且连续块数超过一 定阈值的数据块序列进行去重。文献[22]提出了一 种保持数据读性能的机制。在备份过程中持续监控 每个数据流的CFL即碎片化指标，一旦其低于某个 阈值，就从全去重模式切换到选择去重模式，直到 CFL回到阈值以上。在选择去重模式下，仅对连续长 度超过某个阈值的重复块进行去重。这种方法的缺 点在于去重与否与数据块的顺序有关，并且忽略了 读缓存的作用。缓存大小的区域中可能包含了多个 属于同一个container的重复序列，但因为每个序列的 长度都不超过给定的阈值，即使重复数据块占整个 container的比重较高，仍会被当做新数据进行处理。 而事实上，由于读缓存的存在，一次container的读取 就可以完成所有重复数据的恢复，并不会造成读性 能恶化。文献[34]提出的Capping和文献[23]中提出的

高性能计算技术43 CBR忽略了在一个段中数据块的顺序,避免了上面的DDFS采用RAD6,最多可容忍两个磁盘故障 问题 前的重复数据删除系统通过应用传统的副本 为了在写的过程中减少数据在磁盘上分布的碎策略和纠错编码技术来实现可靠性。如何达到数据 片化程度,确保恢复性能,现有的研究采用的都是缩减率和可靠性的平衡是一个具有挑战性的问题 选择性去重,即以少量数据缩减率的损失换取读性 能的提升。 3.6可扩展性研究 3)提出在恢复过程中提高性能的方法 重复数据删除系统的可扩展性也是一个研究 文献B4提出了一种高效的缓存和预取机制 热点。去重最开始都在单节点上实现。但随着企业 在恢复的过程中提升性能。之前在对恢复性能的研数据量的迅速增长,单个节点很快无法满足吞吐率 究中广泛使用的是以 con taine为单位的LRU缓存四, 和容量要求。解决这一问题的方法之一是采用集群 而在去重系统的恢复过程中,可以提前从文件元数存储,目前由数十甚至上百个存储节点构成大规模 据中获取将要恢复的数据块。文献β4]利用这一特分布式存储系统在企业越来越普遍。集群存储具有 性,减少对无用数据块的缓存,并且减少了同一个如下好处:①解除了单节点性能和容量上的限制 con tainer的换入换出次数,采用该机制在测试集上表②方便添加冗余节点和错误保障与恢复机制,以使 现出的性能是LRU的1.2-4.3倍。 系统可靠运行:③便于添加或删除存储节点,以适 以往对重复数据删除技术的研究关注点在提高应存储容量的动态需求 数据缩减率和提高系统吞吐率。但随着恢复时间窗 文献⑦J9]B6]B7]B8]就重复数据删除技术在集 口越来越小,数据量越来越大,保持恢复性能显得群存储中应用的可扩展性问题进行了研究。重复数 至关重要。如何在保证数据缩减率的情况下改善数据删除系统的可扩展性研究主要需解决以下问题。 据块的磁盘分布,提高数据的恢复性能是今后的 1)全局去重和局部去重 个研究方向。 在集群重复数据删除系统中,索引表分布在各 个存储节点,由去重服务器转发指纹值到各个节点 3.5可靠性研究 中进行重复检测。大多数的重复数据删除集群为了 去重导致一个关键的数据块被很多文件共享 保证性能,达不到与单节点时一样的数据缩减率。 这一关键数据块的丢失会造成很多文件不可恢复 由于每个节点中只存储了部分索引表,因此指纹值 在用Del编码进行去重的系统中,一个原始版本的能进行部分比对,如果要与其他节点上的索引表 文件很可能成为随后众多版本文件的参考文件,如进行比较,则需要与其他节点进行通信,这会带来 果依赖树很深,那么关键的根节点的丢失会造成所较大的通信开销。一种解决方法是在每个节点用少 有后续版本的损坏υ。如何在降低数据冗余度和提高量内存存储其他节点索引表的摘要,当自身查找不 数据可靠性之间进行平衡,是重复数据删除技术研命中时,则查询其他节点在本地的索引表摘要。 究中一个具有挑战性的问题B一些研究者提出通过 2)节点的动态添加和删除问题 冗余复制技术域或者纠错编码技术以来增加去重 好的集群存储系统,应该允许用户动态的添加 系统的可靠性。 和删除节点,以满足不断变化的容量和性能需求。 文献B5]根据块的重要性程度进行副本添加和 在用户添加存储节点的时候,现存各节点的 副本分布。它假定每一个数据块至少有一个冗余 哈希表和数据需要平滑的过渡到新的节点上,使各 并且对引用次数非常高的数据块设置了最大冗余次节点的空间利用率和系统负载重新达到平衡。文献 数。同一个块的冗余数据块存放在不同的设备,以B6冲中采用数据迁移的方法,在其他操作进行的过程 确保一个设备的损坏不会导致同个块的多个副本损中透明的将旧的数据和索引表迁移到新的节点,重 坏。而属于同一个文件的数据块则尽量放在一台设新达到负载平衡。同样,在用户删除一个节点时, 备中,以使设备的故障损坏尽可能少的文件 这个节点中的数据也应该可以平滑的转移到其他的 HYDRAstor采用纠删码技术来增加系统可靠节点上。 性。对于每个数据块,将其分成n个片,编码后形成 3)路由问题 m个片(m>n),将这m个片存储在不同的物理节点 路由是指指纹值和数据块转发到各个重复数据 上。只要保证皿个片里有任意n个正确,就可以正确检测和存储节点的策略。路由策略主要涉及到以下 的恢复整个块。相比冗余复制技术,纠删码技术更两个问题。 节省空间,但在存储和重建的过程中都需要大量的 i路由粒度 计算,使Ⅰ路径变长,增加了系统设计的复杂度 路由可以按照整个文件9、超级块、单个数据

高性能计算技术 43 CBR忽略了在一个段中数据块的顺序，避免了上面的 问题。 为了在写的过程中减少数据在磁盘上分布的碎 片化程度，确保恢复性能，现有的研究采用的都是 选择性去重，即以少量数据缩减率的损失换取读性 能的提升。 3) 提出在恢复过程中提高性能的方法 文献[34]提出了一种高效的缓存和预取机制， 在恢复的过程中提升性能。之前在对恢复性能的研 究中广泛使用的是以container为单位的LRU缓存[22]， 而在去重系统的恢复过程中，可以提前从文件元数 据中获取将要恢复的数据块。文献[34]利用这一特 性，减少对无用数据块的缓存，并且减少了同一个 container的换入换出次数，采用该机制在测试集上表 现出的性能是LRU的1.2-4.3倍。 以往对重复数据删除技术的研究关注点在提高 数据缩减率和提高系统吞吐率。但随着恢复时间窗 口越来越小，数据量越来越大，保持恢复性能显得 至关重要。如何在保证数据缩减率的情况下改善数 据块的磁盘分布，提高数据的恢复性能是今后的一 个研究方向。 3.5 可靠性研究 去重导致一个关键的数据块被很多文件共享， 这一关键数据块的丢失会造成很多文件不可恢复[11]。 在用Delta编码进行去重的系统中，一个原始版本的 文件很可能成为随后众多版本文件的参考文件，如 果依赖树很深，那么关键的根节点的丢失会造成所 有后续版本的损坏[10]。如何在降低数据冗余度和提高 数据可靠性之间进行平衡，是重复数据删除技术研 究中一个具有挑战性的问题[2]。一些研究者提出通过 冗余复制技术[10][17][35]或者纠错编码技术[7]来增加去重 系统的可靠性。 文献[35]根据块的重要性程度进行副本添加和 副本分布。它假定每一个数据块至少有一个冗余， 并且对引用次数非常高的数据块设置了最大冗余次 数。同一个块的冗余数据块存放在不同的设备，以 确保一个设备的损坏不会导致同个块的多个副本损 坏。而属于同一个文件的数据块则尽量放在一台设 备中，以使设备的故障损坏尽可能少的文件。 HYDRAstor[7]采用纠删码技术来增加系统可靠 性。对于每个数据块，将其分成n个片，编码后形成 m个片（m>n），将这m个片存储在不同的物理节点 上。只要保证m个片里有任意n个正确，就可以正确 的恢复整个块。相比冗余复制技术，纠删码技术更 节省空间，但在存储和重建的过程中都需要大量的 计算，使I/O路径变长，增加了系统设计的复杂度。 DDFS采用RAID6[5]，最多可容忍两个磁盘故障。 目前的重复数据删除系统通过应用传统的副本 策略和纠错编码技术来实现可靠性。如何达到数据 缩减率和可靠性的平衡是一个具有挑战性的问题。 3.6 可扩展性研究 重复数据删除系统的可扩展性也是一个研究 热点。去重最开始都在单节点上实现。但随着企业 数据量的迅速增长，单个节点很快无法满足吞吐率 和容量要求。解决这一问题的方法之一是采用集群 存储，目前由数十甚至上百个存储节点构成大规模 分布式存储系统在企业越来越普遍。集群存储具有 如下好处：①解除了单节点性能和容量上的限制； ②方便添加冗余节点和错误保障与恢复机制，以使 系统可靠运行；③便于添加或删除存储节点，以适 应存储容量的动态需求。 文献[7][19][36][37][38]就重复数据删除技术在集 群存储中应用的可扩展性问题进行了研究。重复数 据删除系统的可扩展性研究主要需解决以下问题。 1) 全局去重和局部去重 在集群重复数据删除系统中，索引表分布在各 个存储节点，由去重服务器转发指纹值到各个节点 中进行重复检测。大多数的重复数据删除集群为了 保证性能，达不到与单节点时一样的数据缩减率[36]。 由于每个节点中只存储了部分索引表，因此指纹值 只能进行部分比对，如果要与其他节点上的索引表 进行比较，则需要与其他节点进行通信，这会带来 较大的通信开销。一种解决方法是在每个节点用少 量内存存储其他节点索引表的摘要，当自身查找不 命中时，则查询其他节点在本地的索引表摘要[37]。 2) 节点的动态添加和删除问题 好的集群存储系统，应该允许用户动态的添加 和删除节点，以满足不断变化的容量和性能需求。 在用户添加存储节点的时候，现存各节点的 哈希表和数据需要平滑的过渡到新的节点上，使各 节点的空间利用率和系统负载重新达到平衡。文献 [36]中采用数据迁移的方法，在其他操作进行的过程 中透明的将旧的数据和索引表迁移到新的节点，重 新达到负载平衡。同样，在用户删除一个节点时， 这个节点中的数据也应该可以平滑的转移到其他的 节点上。 3) 路由问题 路由是指指纹值和数据块转发到各个重复数据 检测和存储节点的策略。路由策略主要涉及到以下 两个问题。 i. 路由粒度 路由可以按照整个文件[19]、超级块[36]、单个数据

44<海性能计算发展与应用204年第三期总第四十人期 块以为粒度进行。路由粒度大,能使单个节点保持较 有状态路由在路由决策的时候,会查询每个节 大的数据流重复局部性,这对利用数据流重复局部点的 B loom filter,以获取与每个节点重复数据块的数 性进行吞吐率加速的系统来说非常重要。而过大的目,选择重复数据块最多的节点进行路由。通常, 路由粒度,可能会导致存在于其他节点的很多重复个节点上的数据越多,它与新到来的超级块中重 数据块检测不出来。当以单个数据块进行路由时, 复块数目最多的可能性也就越大,如果仅仅依靠重 理论上通过定义规则,可以准确的判断单个数据块复块的数目作为路由的依据,则可能导致单个节点 应该发往哪个节点从而实现全局去重。如定义规则上的数据越积越多。解决方法之一是在判断路由目 hash%k==n发往第n个节点,那么所有满足这一规则的节点的时候,将各节点当前的空间利用率也考虑 的索引项都会存在于节点n。但是以单个数据块为在内。文献B6采用的机制是用超级块与单个物理节 粒度进行路由会完全破坏节点上的数据流重复局部点重复的块数除以存储空间利用率作为路由决策的 性,使原有的加速机制(如DDFS中的SISL、LPC) 权重。实验验证,有状态路由能够适应更多的节点 无效。 数,达到更高的去重率,并且因其在路由的过程中 Extrem e B inn ing以文件为粒度进行路由,它通就考虑到了负载的平衡,不需要做数据迁移。但其 内存中的一级索引表确定相似文件的bi所在的引入的额外计算、内存开销不容小觑。 节点位置,然后把文件发送到该节点。 Extreme 随着数据存储要求的不断提高以及集群存储在 B inn ing在分布式情况下能够达到与单节点时相同企业范围内的广泛应用,对重复数据删除技术的研 的数据缩减率,且各个节点之间不存在依赖性。但究重点也从单节点转移到了集群环境下。重复数据 Extrem e b inning针对的是数据流以单个文件随机到删除技术适用的集群架构、在集群中面临的去重率 来的场景。大多数备份应用先将大量备份文件进行和效率的平衡、集群的动态扩展性问题都需要进行 打包,在这种情况下利用文件相似性进行路由的进一步的研究 Extrem e b inn ing方法有效性会降低 HYDRAstori是一个以单个数据块为粒度进行路3.7其他研究问题 由的集群重复数据删除存储系统,它采用分布式哈 在对重复数据删除系统性能研究方面,除了经 希表分布索引表项。将备份数据流切成6KB的较大典的对磁盘索引瓶颈的研究,还有对分块和哈希计 的块,然后路由到存储节点。 HYDRA Stor采用的是简算过程的优化。文献B3用协处理器 PadLock来加速哈 单的路由策略,在存储节点上对指纹空间进行均匀希计算过程。文献B2提出了采用流水线方式和计算 划分,各节点之间不存在依赖。在4-12个存储节点操作并行化来加速去重过程,相对于传统的串行执 上获得了几百兆的吞吐率 行方式获得了3-4倍的加速。文献5提出了考虑数 文献B6]提出了以超级块为粒度进行路由的方据类型和硬件平台的自适应流水线,比固定流水线 法。超级块由多个连续数据块组成,既保留了大部有50%的性能提升 分的数据流重复局部性,又不至于因为粒度太大造 因为记录哈希序列的文件元数据(被称为file 成大量重复数据块检测不出来。实验表明超级块平 recipe)与数据的逻辑大小成正比。数据缩减率越 均大小在IMB的时候能够获得数据缩减率和吞吐率的高, file recipe占用的比例就越高。因此有研究者致力 折中 于研究减少 file recipe占用空间的方法。文献B1提出 ⅱ负载均衡 了一种有效的压缩方法,减少了93%的文件元数据占 文献B6]提出了两种路由策略,分别称为无状空间。 态的路由策略和有状态的路由策略。无状态的路由 重复数据删除技术已经在二级存储得到了非常 策略仅仅参考超级块的内容进行决策,它首先为超广泛的应用,EMC、HP、BM、NEC、 Neta pp等大型 级块计算一个特征(如选择其最小数据块的哈希存储供应商都推出了用于二级存储的重复数据删除 值),然后根据特征进行路由。而有状态的路由策设备。但考虑到去重对系统延迟的影响,主存储系 略则要考虑到各节点目前的状态,以达到更高的去统很少采用重复数据删除技术。 DEDE3I是一个主存 重率,但需要更多的计算资源和内存空间。 储去重系统,构建在VMFS之上,在SAN环境中采用 无状态路由有可能造成一个节点上的数据越积后处理的方式对分布式文件系统中的文件进行块级 越多,需要平衡各节点的负载。策略是在某节点的别去重。对主存储采用在线去重技术是一个挑战 负载超过平均负载的某个阈值时,进行数据迁移。 id edup s和DBLK分别提出了减轻主存储去重系统 数据的迁移以bi为单位进行,一个bin中存放着多个访问延迟的方法。如何将重复数据删除技术在主存 具有相同映射值的超级块 储中进行高数据缩减率、低延迟的应用是今后的一

44 《高性能计算发展与应用》 2014年第三期 总第四十八期 块[7]为粒度进行。路由粒度大，能使单个节点保持较 大的数据流重复局部性，这对利用数据流重复局部 性进行吞吐率加速的系统来说非常重要。而过大的 路由粒度，可能会导致存在于其他节点的很多重复 数据块检测不出来。当以单个数据块进行路由时， 理论上通过定义规则，可以准确的判断单个数据块 应该发往哪个节点从而实现全局去重。如定义规则 hash%k==n发往第n个节点，那么所有满足这一规则 的索引项都会存在于节点n。但是以单个数据块为 粒度进行路由会完全破坏节点上的数据流重复局部 性，使原有的加速机制（如DDFS中的SISL、LPC） 无效。 Extreme Binning以文件为粒度进行路由，它通 过内存中的一级索引表确定相似文件的bin所在的 节点位置，然后把文件发送到该节点[19]。Extreme Binning在分布式情况下能够达到与单节点时相同 的数据缩减率，且各个节点之间不存在依赖性。但 Extreme Binning针对的是数据流以单个文件随机到 来的场景。大多数备份应用先将大量备份文件进行 打包，在这种情况下利用文件相似性进行路由的 Extreme Binning方法有效性会降低。 HYDRAstor[7]是一个以单个数据块为粒度进行路 由的集群重复数据删除存储系统，它采用分布式哈 希表分布索引表项。将备份数据流切成64KB的较大 的块，然后路由到存储节点。HYDRAstor采用的是简 单的路由策略，在存储节点上对指纹空间进行均匀 划分，各节点之间不存在依赖。在4-12个存储节点 上获得了几百兆的吞吐率。 文献[36]提出了以超级块为粒度进行路由的方 法。超级块由多个连续数据块组成，既保留了大部 分的数据流重复局部性，又不至于因为粒度太大造 成大量重复数据块检测不出来。实验表明超级块平 均大小在1MB的时候能够获得数据缩减率和吞吐率的 折中。 ii. 负载均衡 文献[36]提出了两种路由策略，分别称为无状 态的路由策略和有状态的路由策略。无状态的路由 策略仅仅参考超级块的内容进行决策，它首先为超 级块计算一个特征（如选择其最小数据块的哈希 值），然后根据特征进行路由。而有状态的路由策 略则要考虑到各节点目前的状态，以达到更高的去 重率，但需要更多的计算资源和内存空间。 无状态路由有可能造成一个节点上的数据越积 越多，需要平衡各节点的负载。策略是在某节点的 负载超过平均负载的某个阈值时，进行数据迁移。 数据的迁移以bin为单位进行，一个bin中存放着多个 具有相同映射值的超级块。 有状态路由在路由决策的时候，会查询每个节 点的Bloom filter，以获取与每个节点重复数据块的数 目，选择重复数据块最多的节点进行路由。通常， 一个节点上的数据越多，它与新到来的超级块中重 复块数目最多的可能性也就越大，如果仅仅依靠重 复块的数目作为路由的依据，则可能导致单个节点 上的数据越积越多。解决方法之一是在判断路由目 的节点的时候，将各节点当前的空间利用率也考虑 在内。文献[36]采用的机制是用超级块与单个物理节 点重复的块数除以存储空间利用率作为路由决策的 权重。实验验证，有状态路由能够适应更多的节点 数，达到更高的去重率，并且因其在路由的过程中 就考虑到了负载的平衡，不需要做数据迁移。但其 引入的额外计算、内存开销不容小觑。 随着数据存储要求的不断提高以及集群存储在 企业范围内的广泛应用，对重复数据删除技术的研 究重点也从单节点转移到了集群环境下。重复数据 删除技术适用的集群架构、在集群中面临的去重率 和效率的平衡、集群的动态扩展性问题都需要进行 进一步的研究。 3.7 其他研究问题 在对重复数据删除系统性能研究方面，除了经 典的对磁盘索引瓶颈的研究，还有对分块和哈希计 算过程的优化。文献[33]用协处理器PadLock来加速哈 希计算过程。文献[32]提出了采用流水线方式和计算 操作并行化来加速去重过程，相对于传统的串行执 行方式获得了3-4倍的加速。文献[45]提出了考虑数 据类型和硬件平台的自适应流水线，比固定流水线 有50%的性能提升。 因为记录哈希序列的文件元数据（被称为file recipe）与数据的逻辑大小成正比。数据缩减率越 高，file recipe占用的比例就越高。因此有研究者致力 于研究减少file recipe占用空间的方法。文献[31]提出 了一种有效的压缩方法，减少了93%的文件元数据占 用空间。 重复数据删除技术已经在二级存储得到了非常 广泛的应用，EMC、HP、IBM、NEC、NetApp等大型 存储供应商都推出了用于二级存储的重复数据删除 设备。但考虑到去重对系统延迟的影响，主存储系 统很少采用重复数据删除技术。DEDE[3]是一个主存 储去重系统，构建在VMFS之上，在SAN环境中采用 后处理的方式对分布式文件系统中的文件进行块级 别去重。对主存储采用在线去重技术是一个挑战， iDedup[15]和DBLK[16]分别提出了减轻主存储去重系统 访问延迟的方法。如何将重复数据删除技术在主存 储中进行高数据缩减率、低延迟的应用是今后的一

高性能计算技术45 个研究方向。 势,并且功耗要远远的低于通用处理器。近年来异 跨用户的去重会带来安全性问题,有可能使 构多核技术发展迅速,而重复数据删除算法的并行 个用户获取另一个用户的文件内容。在云存储中应性还没有得到充分的挖掘。未来可以充分利用异构 用重复数据删除技术就要解决这一安全性问题。文多核处理器的特点,进行合理的任务划分和部署 献3提出了一种称为 Random Solution的保证系统安以加块重复数据删除技术的整个过程。 全性的策略。 4)集群重复数据删除 近些年,随着集群存储的快速普及和发展。重 4.总结与展望 复数据删除技术需要考虑其在几十甚至上百个存储 本文对重复数据删除技术的概念、分类、关键节点上的可扩展性问题。在集群节点增加的时候如 指标以及研究现状进行了全面的总结。涉及到的关何维持缩减率水平和吞吐率水平,并且综合考虑到 键技术点有数据划分方法、减轻磁盘索引瓶颈、提负载均衡和容错的要求,需要进一步的探索 高恢复性能、提高重复数据删除系统的可靠性和可 5)主存储去重 扩展性等。重复数据删除技术的应用使得企业能够 在线重复数据删除技术在数据保护领域已经有 更好的应对日益增加的存储空间和网络带宽的压力 非常广泛的应用。几乎所有的存储供应商都推出了 目前对重复数据删除技术的研究已经涵盖到多有去重功能的数据保护产品,将重复数据删除逻辑 个方面,但还有一些问题尚未得到解决。 嵌入到数据保护硬件(如备份平台、VTL、NAS) 1)新型存储介质影响去重发展方向 或者软件中。除了在二级存储上的应用,去重一样 由于磁盘技术的迅速发展,才使磁带备份逐渐可以在主存储领域大有作为,例如虚拟机和虚拟桌 被磁盘备份所取代,从而推动了重复数据删除技术面,项目的共享文件、共享网络卷都存在大量的冗 的研究和应用。而新型存储介质(如SSD、相变存储余数据。尽管以 NetA pp和EMC为代表的存储厂商相 器)的出现,也对重复数据删除技术未来的发展带继推出了主存储去重产品,主存储去重技术的应用 来了新的机遇。 Pure Storage公司已经在其企业级的全现状远不如二级存储广泛,去重引入的读写延迟依 闪存阵列中应用了在线的重复数据删除技术,以帮旧是最大的技术障碍。尽管固态盘技术可以成为解 助用户更好的利用昂贵的闪存。新型存储介质催生决延时的一种方案,但会增加用户的主存储成本。 新型的存储架构,如目前应用广泛的SS和磁盘混合如何克服技术障碍,将去重应用到主存储系统是 存储架构。如何设计适应新型存储架构的重复数据个研究难点。 删除算法,充分利用新型存储介质的访问和存储特 6)安全性问题 性,优化系统的吞吐率和延迟,是一个需要不断研 跨用户的重复数据删除技术会造成安全隐患, 究的问题。 攻击者可以通过查询获取其他用户的数据内容。这 2)去重在其他数据保护领域的应用 现象在云存储中尤其值得考虑。安全性已经成为 目前重复数据删除技术在数据保护领域主要应了限制公有云发展的一个重要问题,如何消除去重 用于备份和归档。而一些更细粒度的数据保护应用系统中由用户共享数据带来的安全隐患需要进一步 (如持续数据保护)也会产生大量的冗余数据,如 研究。 何设计符合应用场景的算法,将重复数据删除技术 重复数据删除技术自产生以来,受到了研究 应用于其他的数据保护应用,也需要进一步的研究 者深入而广泛的探讨。在未来,重复数据删除有望 3)任务划分 在应用程序、文件系统、主存储设备和备份归档软 重复数据删除技术中涉及到大量的分块和哈希硬件多个环节应用,成为数据中心标准配置之 计算操作。通用的处理器(如血lx86处理器)对于重复数据删除技术将与快速发展的云存储技术相结 哈希计算的效率并不高,而一些专用的协处理器(如合,应用场景从二级存储向主存储系统转变,成为 GPU、 PadLock等)在计算哈希的速度上具有明显优存储领域不可或缺的核心技术。 参考文献: 0].I G antz, D. R einsel "the digital un iverse in 2020: big data, bigger digital shadow s and biggest grow th in the far east, IdCIvIeW,sponsoredbyEmcCorporation1-162012),http://www.emc.com/collateravanalyst-reports/idc-the-digitah universe- in-2020 pdf

高性能计算技术 45 个研究方向。 跨用户的去重会带来安全性问题，有可能使一 个用户获取另一个用户的文件内容。在云存储中应 用重复数据删除技术就要解决这一安全性问题。文 献[43]提出了一种称为Random Solution的保证系统安 全性的策略。 4. 总结与展望 本文对重复数据删除技术的概念、分类、关键 指标以及研究现状进行了全面的总结。涉及到的关 键技术点有数据划分方法、减轻磁盘索引瓶颈、提 高恢复性能、提高重复数据删除系统的可靠性和可 扩展性等。重复数据删除技术的应用使得企业能够 更好的应对日益增加的存储空间和网络带宽的压力。 目前对重复数据删除技术的研究已经涵盖到多 个方面，但还有一些问题尚未得到解决。 1) 新型存储介质影响去重发展方向 由于磁盘技术的迅速发展，才使磁带备份逐渐 被磁盘备份所取代，从而推动了重复数据删除技术 的研究和应用。而新型存储介质（如SSD、相变存储 器）的出现，也对重复数据删除技术未来的发展带 来了新的机遇。Pure Storage公司已经在其企业级的全 闪存阵列中应用了在线的重复数据删除技术，以帮 助用户更好的利用昂贵的闪存。新型存储介质催生 新型的存储架构，如目前应用广泛的SSD和磁盘混合 存储架构。如何设计适应新型存储架构的重复数据 删除算法，充分利用新型存储介质的访问和存储特 性，优化系统的吞吐率和延迟，是一个需要不断研 究的问题。 2) 去重在其他数据保护领域的应用 目前重复数据删除技术在数据保护领域主要应 用于备份和归档。而一些更细粒度的数据保护应用 （如持续数据保护）也会产生大量的冗余数据，如 何设计符合应用场景的算法，将重复数据删除技术 应用于其他的数据保护应用，也需要进一步的研究。 3) 任务划分 重复数据删除技术中涉及到大量的分块和哈希 计算操作。通用的处理器（如Intel x86处理器）对于 哈希计算的效率并不高，而一些专用的协处理器（如 GPU、PadLock等）在计算哈希的速度上具有明显优 势，并且功耗要远远的低于通用处理器。近年来异 构多核技术发展迅速，而重复数据删除算法的并行 性还没有得到充分的挖掘。未来可以充分利用异构 多核处理器的特点，进行合理的任务划分和部署， 以加块重复数据删除技术的整个过程。 4) 集群重复数据删除 近些年，随着集群存储的快速普及和发展。重 复数据删除技术需要考虑其在几十甚至上百个存储 节点上的可扩展性问题。在集群节点增加的时候如 何维持缩减率水平和吞吐率水平，并且综合考虑到 负载均衡和容错的要求，需要进一步的探索。 5) 主存储去重 在线重复数据删除技术在数据保护领域已经有 非常广泛的应用。几乎所有的存储供应商都推出了 有去重功能的数据保护产品，将重复数据删除逻辑 嵌入到数据保护硬件（如备份平台、VTL、NAS）， 或者软件中。除了在二级存储上的应用，去重一样 可以在主存储领域大有作为，例如虚拟机和虚拟桌 面，项目的共享文件、共享网络卷都存在大量的冗 余数据。尽管以NetApp和EMC为代表的存储厂商相 继推出了主存储去重产品，主存储去重技术的应用 现状远不如二级存储广泛，去重引入的读写延迟依 旧是最大的技术障碍。尽管固态盘技术可以成为解 决延时的一种方案，但会增加用户的主存储成本。 如何克服技术障碍，将去重应用到主存储系统是一 个研究难点。 6) 安全性问题 跨用户的重复数据删除技术会造成安全隐患， 攻击者可以通过查询获取其他用户的数据内容。这 一现象在云存储中尤其值得考虑。安全性已经成为 了限制公有云发展的一个重要问题，如何消除去重 系统中由用户共享数据带来的安全隐患需要进一步 研究。 重复数据删除技术自产生以来，受到了研究 者深入而广泛的探讨。在未来，重复数据删除有望 在应用程序、文件系统、主存储设备和备份归档软 硬件多个环节应用，成为数据中心标准配置之一。 重复数据删除技术将与快速发展的云存储技术相结 合，应用场景从二级存储向主存储系统转变，成为 存储领域不可或缺的核心技术。 参考文献： [1] J. Gantz, D. Reinsel, “The digital universe in 2020: big data, bigger digital shadows, and biggest growth in the far east,” IDC IVIEW, sponsored by EMC Corporation, 1-16 (2012),http://www.emc.com/collateral/analyst-reports/idc-the-digital￾universe-in-2020.pdf