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

发布时间：2017-11-05 05:27

  本文关键词：分布式存储系统中一种新的再生码及其译码算法研究

  更多相关文章： 分布式存储系统 再生码 Product Matrix 移位操作 按位异或

【摘要】：近年来,“大数据”受到互联网行业及学术界越来越多的重视,如何存储及处理“大数据”是我们的当务之急。分布式存储系统在过去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%。
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP333

【相似文献】

中国期刊全文数据库 前10条

1 何公明;张元涛;;面向数字媒体的高性能分布式存储系统的研究与应用[J];广播电视信息;2009年10期

2 范剑波,郭建康;分布式存储系统性能模型的建立与应用[J];计算机工程与应用;2001年13期

3 范剑波,徐利浩;分布式存储系统可靠性的研究[J];计算机工程;2001年06期

4 吴英;谢广军;刘t，

本文编号：1142799