面向数据备份的高效数据去重系统构建方法研究

摘要

在大数据时代，如何高效地存储和管理海量数据成为存储系统研究者和实践者面临的一大挑战。大量的研究表明，冗余数据普遍存在于各类存储系统中，例如备份存储系统、桌面文件系统等。通过消除这些冗余数据，可以节约大量存储成本。在这样的背景下，数据去重作为一种高效的压缩技术，逐渐应用到各类存储系统中。然而，构建高效数据去重系统仍然存在大量的问题和挑战，例如数据块碎片、大规模指纹索引和存储可靠性等。本文将首先在备份存储系统中解决由于数据去重产生的数据块碎片问题，再研究数据去重对存储可靠性的影响，最后系统地讨论如何设计面向备份负载的高效数据去重系统。
　　数据去重引起的数据块碎片会严重降低备份数据流的恢复性能，并且在用户删除备份后，降低垃圾回收的效率。通过对长期备份数据集的分析，发现数据块碎片主要来自两类容器：稀疏容器和乱序容器。稀疏容器直接放大读操作，而乱序容器会在恢复缓存不足时降低恢复性能，因此需要不同的解决方案。现有基于缓冲区的重写算法无法准确区分稀疏和乱序容器，导致存储效率和恢复性能低。提出了历史感知的数据块碎片处理方法，包括历史感知重写算法HAR、最优恢复缓存算法OPT、缓存感知过滤器CAF和容器标记算法CMA。历史感知的数据块碎片处理方法对稀疏容器执行重写，且通过恢复缓存减少乱序容器的影响，从而减少存储开销。HAR利用连续备份数据流的相似性精确地识别稀疏容器，是区分稀疏容器和乱序容器的关键。OPT在备份时纪录下数据块的访问顺序，用于实现Belady最优缓存算法，减少乱序容器对恢复性能的影响。为了进一步减少对恢复缓存的需求，CAF通过仿真恢复缓存准确识别和重写少量的降低恢复性能的乱序容器。为了减少垃圾回收的时间和空间开销，CMA利用HAR清理稀疏容器。在先进先出的备份删除策略下，CMA无需耗时的容器合并操作即可回收大量存储空间。由于CMA直接追踪容器的利用率，其开销与容器数量成正比，而不是与数据块数量成正比。使用4个长期备份数据集进行测试，历史感知的数据块碎片处理方法比现有算法的存储成本更低，且恢复性能更好。
　　数据去重对存储可靠性的影响长期未知。通过消除冗余数据，数据去重可以减少磁盘的数量，因此减少遇到磁盘错误的概率；同时，数据去重会增加每次磁盘错误的严重性，因为丢失一个数据块可能会损坏多个文件。提出了一套数据去重系统可靠性的量化分析方法，引入逻辑数据丢失量的概念扩展了现有可靠性指标NOMDL，使其可以衡量数据去重系统的可靠性。设计了针对数据去重系统的可靠性仿真器SIMD。SIMD利用企业公布的统计数据仿真扇区错误和整盘故障，并产生磁盘阵列的各类数据丢失事件。为了计算每次数据丢失事件的逻辑数据丢失量，SIMD根据真实文件系统镜像生成块级和文件级模型。通过对18个真实文件系统镜像的分析和仿真实验，发现：由于文件内部冗余的存在，数据去重可以显著减少扇区错误损坏的文件数量；但是，数据去重带来的数据块碎片增加了整盘故障的危害。为了提高存储可靠性，提出了DCT副本技术。DCT将磁盘阵列的1％物理空间分配给高引用数据块的副本，并在磁盘阵列重建时优先修复这些副本。DCT的存储开销很小，可以将因整盘故障丢失的数据块和文件分别减少31.8%和25.8%。
　　构建高效数据去重系统还需要考虑指纹索引等其它模块对系统的影响。为了系统地理解和比较现有的设计方案，并提出新的更高效的设计方案，设计和实现了通用数据去重原型系统Destor。将数据去重系统理解为多维参数空间，每个维度代表了系统的一个子模块或参数，包括分块、指纹索引、重写算法、恢复算法等。每个参数都有若干候选设计方案。现有的设计方案和潜在的新方案被看作多维参数空间的点。Destor实现了该多维参数空间，涵盖了多种主流的数据去重系统的设计方案。研究人员利用Destor可以比较现有设计方案，并探索参数空间得到潜在的新设计方案。为了发现更高效的潜在设计方案，用3个长期备份数据集探索了数据去重系统的参数空间，关注的性能指标包括内存开销、存储成本、备份性能和恢复性能。目标方案必须能长期维持稳定的高备份性能，并在其余三个指标取得合理的权衡。得到了17个实验发现，并总结了以下满足要求的设计方案：当需求最低的存储成本时，应该采用利用逻辑局部性的精确去重；当需求最低的内存开销时，可以采用利用逻辑或物理局部性的近似去重；当需求稳定的高恢复性能时，应该采用利用物理局部性的精确去重，以及历史感知的数据块消除方法。当需求更高可靠性时，以上方案都可以采用DCT副本技术，仅增加极少存储成本而不影响备份和恢复性能。

目录

封面

声明

中文摘要

英文摘要

目录

一 绪论

1.1 海量数据和数据冗余

1.2 数据去重方法

1.3 数据去重研究现状

1.4 本文的研究内容

二 历史感知的数据块碎片处理方法

2.1 数据块碎片问题的描述

2.2 数据块碎片的分类和分析

2.3 历史感知数据块碎片处理方法的设计与实现

2.4 性能评估

2.5 本章小结

三 数据去重可靠性量化分析方法和DCT副本技术

3.1 量化分析可靠性面临的挑战

3.2 数据集及其特征

3.3 数据去重系统的可靠性量化分析方法

3.4 仿真结果和优化方法

3.5 本地压缩对可靠性的影响

3.6 本章小结

四 高效数据去重原型系统的实现和性能权衡

4.1 数据去重系统及其参数空间

4.2 指纹索引的参数空间

4.3 重写和恢复算法

4.4 可靠性的讨论

4.5 数据去重原型系统Destor的设计与实现

4.6 参数空间的实验分析

4.7 本章小结

五 全文总结和展望

5.1 主要成果

5.2 研究展望

致谢

参考文献

附录1 攻读学位期间发表的学术论文

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

附录3 攻读学位期间参与的科研项目