分布式存储系统中一种新的再生码及其译码算法研究

摘要

近年来，“大数据”受到互联网行业及学术界越来越多的重视，如何存储及处理“大数据”是我们的当务之急。分布式存储系统在过去30多年里，在数据存储及处理方面发挥了很大的作用，它很好的平衡了数据的可靠性，存储成本及修复失效节点的计算复杂度等性能。纠删码（Erasure Codes，也翻译为擦除码）及复制码(Replication Codes)是在分布式存储中使用最为广泛的编码。一个系统参数为（n，k)的Erasure Code，原始的k个数据块经过编码后，生成n个编码后的数据块，当某个存储节点失效时，新加入的节点会从剩下未失效的数据节点中任意的链接k个，并下载节点中全部的数据进行运算，修复失效的节点。纠删码具有存储消耗小，可靠性高等优点，但运算的复杂度较高，下载带宽大。与纠删码相比，复制码在修复带宽及计算开销等方面的性能更优。
　　在网络编码理论引入分布式存储系统之后，Dimakis等提出了再生码的概念。在再生码理论中，单个的存储结点不仅具有存储和转发功能，而且还能进行运算。自2010年起，学者们提出了性能各异的MBR(Minimum Bandwidth Regenerating)码，MSR(Minimum Storage Regenerating)码和LRC(Locally Repairable Codes)。而Rashmi等人提出的Product Matrix构造法，由于不受构造参数的限制，被广泛的研究。另外，针对基于移位操作的再生码，Yang等提出一种基于Xor的In-place算法，能很大程度的降低修复时的运算复杂度。
　　前面提到的Product Matrix MBR码及BASIC码虽然下载带宽已达到最优，但修复时的数据读取量(Data I/O)却依然不理想。本文在基于移位操作的Product Matrix MBR码的基础上，做出了改进，改进后的编码具有原始Product Matrix码的所有优点，并且还具有最佳I/O性质，使得修复时，总的数据读取量达到理论最优。同时，本文中提出了一种新的基于移位的译码算法，新的算法与In-place相比，译码时的时间消耗降低了50％。

目录

声明

摘要

第1章 绪论

1．1 研究意义

1．2 研究现状

1．2．1 复制码与纠删码

1．2．2 再生码

1．3 本文主要研究内容

1．3．1 BASIC码简介

1．3．2 In-place译码算法

1．3．3 本文中提出的新的编码及算法

1．4 本文的章节分布

第2章 再生码的相关理论基础

2．1 MDS(Maximum Distance Separable)性质简介

2．2 存储消耗及修复带宽的理论界

2．3 Product Matrix MBR码

2．3．1 Product Matrix构造简介

2．3．2 由Product Matrix构造的MBR码

2．4 基于移位的编码简介

2．4．1 编码中移位操作的背景知识

2．4．2 基于移位操作的编码

2．4．3 基于移位的编码在计算机中的实现

2．4．4 基于移位编码的实例

第3章 一种基于移位的新再生码编码

3．1 BASIC MBR码

3．1．1 构造方法

3．1．2 编码及译码实例

3．2 一种新的MBR码

3．2．1 新编码的构造

3．2．2 系统码形式

3．2．3 新编码A的实例

3．3 新编码与其他MBR码的对比

第4章 一种基于移位的新的译码算法

4．1 In-place算法简介

4．1．1 按位异或算法的背景知识

4．1．2 In-place算法的实现

4．1．3 In-place算法与其他算法的性能对比

4．2 新译码算法

4．2．1 新算法简介

4．2．2 新算法的译码过程

4．3 新算法实例

4．3．1 节点修复过程

4．3．2 数据重构

4．4 新算法与In-place算法的对比

第5章 仿真及结果分析

5．1 原编码及其译码

5．1．1 BASIC MBR Codes编码

5．1．2 译码过程

5．2 新编码及新的译码算法

5．2．1 新编码A的编码过程

5．2．2 利用新算法译码

5．3 新编码及新的译码算法与原编码及算法的对比

结论与展望

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果