分布式存储系统中基于纠删码的备份与修复技术研究

摘要

分布式存储系统通过多节点存储和管理数据，能够实现数据的海量存储。这类系统一般采用商用服务器节点构建，节点的频繁失效使得数据的可靠性较低。纠删码技术可以通过对数据进行编码，实现数据的冗余存储，提高数据的可靠性。然而，将纠删码应用于分布式存储系统时，会出现数据插入效率低、失效数据的修复开销高、修复时间长等问题。本文针对这些问题展开研究，取得了以下成果：
　　针对传统纠删码方案下数据插入效率较低的问题，提出了一种面向数据插入的均衡分发方法，以有效减小数据插入时间，提高插入过程的吞吐量。该方法的基本思想是：将各数据块拆分为粒度更小的数据片，利用中间节点间的传输能力转发数据片，达到并行传输的效果；将并行传输下的数据块划分方案建模为一个二次规划问题，求解出最小插入时间，获得最优的数据块划分方案。实验表明，与传统的星型数据插入模式相比，该方法降低了数据插入时间，提高了插入过程的吞吐量，提高了数据插入效率。
　　针对纠删码在数据修复时开销较高的问题，提出了一种交织层次复合码，称为IZSHC。采用IZSHC，以有效降低数据修复时从磁盘读取的数据量和数据传输量。构建IZSHC的基本思想是：通过分解IZS码的重复码结构得到最小的IZS编码组，将IZS编码组的数据修复开销小的基本特性融合到层次码中；利用层次码的层组结构对IZS编码组进行扩展，减少数据修复时参与修复的节点数目。该方法将IZS码的重复码可分解特性与层次码的分层分组模式结合起来，从总体上降低了修复开销。实验表明，与纠删码相比，IZSHC减少了数据修复中参与的节点数目，使得修复中的总磁盘开销与总传输带宽开销降低。
　　针对纠删码下的单节点修复方法修复时间较长的问题，提出了一种协作式的多树修复方法，以有效减小单节点修复时间。该方法的基本思想是：通过将网络中更多的可用带宽组织成多树实现对单个数据块的协作修复模式，每个树单独修复数据块的一部分，加快修复过程；通过迭代式的边交换方式尽力提高每棵树的瓶颈带宽，实现对网络带宽的充分使用，进一步减小修复时间。实验表明，与基于网络编码的单树修复模式相比，能够减小失效节点的修复时间。
　　针对纠删码下的多节点修复方法修复时间较长的问题，提出了一种基于MSR码的多树修复方法，以有效减小节点平均修复时间。该方法的基本思想是：依次为每个失效节点构造一棵极小最大瓶颈生成树；在每次构造单树时，在不减小当前树中瓶颈带宽的前提下，将其它带宽较大的边留给余下的树的构造，提高这些树获取更大瓶颈带宽边的机会。该方法有效利用了并行多树中瓶颈带宽之间的关联特点，实现了对网络中可用带宽的高利用率。实验表明，与现有的多节点并行修复方法相比，能够减小节点的平均修复时间。

目录

声明

第一章 绪论

1.1 研究背景

1.2 难点与挑战

1.3 本文主要工作

1.4 全文组织

第二章 相关研究

2.1 纠删码技术

2.2 数据修复

2.3 多节点修复

2.4 数据插入

2.5 本章小结

第三章 面向数据插入的均衡数据分发方法

3.1 引言

3.2 星形插入的时间问题及改进分析

3.3 均衡数据分发方法

3.4 分析评估

3.5 本章小结

第四章 面向低修复开销的交织层次复合码：IZSHC

4.1 引言

4.2 IZSHC的设计思想

4.3 IZSHC的基础组

4.4 IZSHC的层次化扩展

4.5 IZSHC的数据重构和修复

4.6 实验评估

4.7 本章小结

第五章 面向单节点失效的协作式多树修复方法

5.1 引言

5.2 协作式的多树修复

5.3 OMRT的近似构造算法

5.4 实验评估

5.5 本章小结

第六章 基于再生码的多节点失效的多树并行修复方法

6.1 引言

6.2 多节点修复的多树模型

6.3 MMBST构造算法

6.4 基于MSR的多MMBST构造算法

6.5 实验评估

6.6 本章小结

第七章 总结和未来工作

7.1 工作总结

7.2 研究展望

致谢

参考文献

作者在学期间取得的学术成果