基于冗余数据消除的备份系统性能优化研究

摘要

随着电子信息的爆炸式增长，作为冗余数据消除的重要手段，数据去重和差量压缩技术受到越来越多的关注。数据去重可以消除重复的数据块，而差量压缩可以消除不重复但相似的数据块间的冗余数据。将这两种技术应用于备份系统可以有效地减少冗余数据，但是也会降低系统的备份和恢复性能。对于仅使用数据去重的备份系统来说，现有的基于内容的分块算法开销过大，使分块环节成为了备份时的性能瓶颈。数据去重和差量压缩在效果上可以互补，因此可以将两种技术联合起来应用于备份系统以尽量减少冗余数据。然而，在联合数据去重和差量压缩技术的备份系统中，差量压缩对系统的备份和恢复性能的影响都未讨论过。 在使用数据去重的备份系统中，针对基于内容的分块算法存在的计算开销过大导致的性能瓶颈问题，提出了在非对称区域内寻找极值来做切点判断的非哈希分块算法AE，来移除分块环节的性能瓶颈。典型的Rabin分块算法需要较大计算开销来计算Rabin指纹，MAXP算法需要复杂的回溯处理，因此都面临吞吐量过低的问题。在MAXP的基础上，AE在非对称区域内寻找极值点，避免了回溯处理。此外，现有的分块算法块长方差过大且不能对低熵字符串进行去重，而AE的块长方差小，且可以对低熵字符串进行去重，因此可以获得更高的去重率。实验测试表明，AE算法的吞吐量是传统的基于内容的分块算法的3-5倍，可以移除备份时分块环节的性能瓶颈，将系统吞吐量提高50%以上，并且获得与之相当或更高的去重率。 在联合数据去重和差量压缩技术的备份系统中，针对现有的相似性检测算法的计算开销过大导致的性能瓶颈问题，提出了基于局部性的快速相似性检测方法SIRD，来移除相似性检测环节的性能瓶颈。相似性检测环节的计算开销与单个区域内需要提取的特征值个数成正比。备份系统中最常用的相似性检测算法是超级特征值法（Super-feature），该方法将整个数据块视为单个区域并从中提取出多个特征值，因此需要较大的计算开销。分析发现，备份数据集中的相似数据块存在局部性。为了挖掘该局部性，SIRD将数据块划分成多个子区域，并对单个子区域只提取一个特征值来减少计算开销。为了提高相似性检测的准确度，匹配时SIRD将多个子区域的特征值联合起来匹配来查看数据块内是否多个对应子区域都相似。实验测试表明，SIRD可以移除相似性检索环节的性能瓶颈并提高系统吞吐量1.42-3.2倍。 在联合数据去重和差量压缩技术的备份系统中，针对引用块碎片化所导致的恢复性能降低的问题，提出了利用局部性来选择性进行差量压缩的方法SDC，来避免引用块的碎片化并提高系统的恢复性能。引用块的碎片化产生的原因无选择性地进行差量压缩导致引用块的位置分散，从而在恢复时需要大量的读操作来读取引用块。引用块碎片化严重影响恢复性能且无法被现有的重写算法解决。分析发现对引用块存在局部性的数据块进行差量压缩可以避免引用块碎片化。为了判断引用块的局部性，SDC在备份时模拟一个恢复缓存，并仅对引用块存在于模拟的恢复缓存中（即引用块局部性强）的数据块进行差量压缩，来避免引用块的碎片化。实验测试表明，与直接在数据去重后做差量压缩相比，SDC可以提升恢复性能1.93-7.48倍，而压缩率的损失仅为2.6%～4.5%。

目录

第一个书签之前

摘 要

Abstract

1 绪论

1.1 数据冗余和冗余数据消除技术

1.2 数据去重和差量压缩相关技术

1.3 数据去重和差量压缩技术的研究现状

1.4 本文研究的主要内容

2 非对称极值分块算法

2.1 数据去重的分块算法相关研究

2.2 系统性能瓶颈和分块算法分析

2.3 非对称极值分块算法

2.4 AE性能评价

2.5 本章小结

3 基于局部性的相似性检测方法

3.1 相似性检测的相关研究

3.2 超级特征值法分析

3.3 基于局部性的相似性检测方法

3.4 SIRD性能评价

3.5 本章小结

4 选择性差量压缩方法

4.1 差量压缩和数据块碎片化的相关研究

4.2 引用块碎片化

4.3 差量压缩提高恢复性能

4.4 选择性差量压缩

4.5 SDC性能评价

4.6 本章小结

5 全文总结与展望

5.1 主要成果贡献

5.2 下步研究展望

致 谢

参考文献

1 攻读博士学位期间发表的学术论文目录

2 攻读博士学位期间申请的发明专利和著作权

3 攻读博士学位期间参与的科研项目