论文部分内容阅读
近年来,“大数据”受到互联网行业及学术界越来越多的重视,如何存储及处理“大数据”是我们的当务之急。分布式存储系统在过去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%。