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算法能检测出更多的冗余 数据。但是滑动分块技术需要同时存储所有数据块