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]中提出的