基于(k+2,k)MSR的多容错低修复带宽编码

曹 凯,文 捷

(复旦大学 计算机科学技术学院,上海 200433)

0 概述

最大距离可分码(Maximum Distance Separable Code,MDS)是一种常见的纠错码。假设M大小的文件被均分成了k个分片,将它们存储在具有n个节点的分布式存储系统中(这里n>k)。存储原始数据的前k个节点一般称为系统节点,其余n-k个节点称为奇偶校验节点。如果一个编码满足在n个节点中任意选k个节点都可以重建原始数据,那么就说此码拥有MDS属性。基于MDS码的编码方案与传统的基于拷贝的方案相比具有更低的存储开销和更高的可靠性,但是与此同时它的修复带宽也随之提升(修复带宽是指修复失效节点需要从其他节点连接下载的总的数据量),文献[1-2]分别提出了新的网络编码的编码算法来探索这一问题。

为了解决MDS码高修复带宽的问题,最小存储再生码(Minimum Storage Regeneration Code,MSR)应运而生。MSR码是拥有最优修复属性的MDS码[3]。在一个(n,k)MDS码中(例如Reed-Solomon码[4]),当某个系统节点失效时需要下载其余幸存节点的所有数据,而在MSR码的修复过程中却只需要从每个幸存节点下载部分内容。文献[5]探索了显示的最小存储再生码,文献[6]为降低分布式存储系统中节点的存储量,构造了一类新(k+2,k) Hadamard MSR码,文献[7]对MSR码提出了一种新的Piggybacking架构设计,文献[8]提出了一种最优本地修复码的方案,文献[9]提出了应用于分布式存储系统的准循环再生码构造方案,文献[10]提出一种具有独立奇偶符号的MDS码,此外,文献[11]构造了拥有最优访问属性和最优更新属性的MSR码的框架,文献[12-14]提出了构造高码率的再生码方案。以……