基于(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]提出了构造高码率的再生码方案。以上述研究为基础,本文提出一种基于(k+2,k)MSR码的高容错低修复带宽的编码方案。

1 传统MSR码的修复方案与问题描述

1.1 传统(k+r,k)MSR码的修复方案

fk+j=Aj,1f1+Aj,2f2+…+Aj,kfk

其中,矩阵Aj,i(1≤i≤k)是一个a×a的满秩矩阵,将其称为第j个校验节点对第i个系统节点的编码矩阵。表1和表2给出了一般(k+r,k)MSR码的节点存储结构。

表1 (k+r,k)MSR码的系统节点存储结构

表2 (k+r,k)MSR码的校验节点存储结构

假设第i个(1≤i≤k)系统节点发生故障,对于(k+r,k)MSR码,需要从其他所有幸存节点下载Si,jfj(j≠i)。其中,矩阵Si,j是一个(a/r×a)的矩阵(秩为a/r),称为第j个节点对第i个系统节点的修复矩阵。然后就可以恢复原始数据fi。假设r=2,为了更加简单直观地表示,设定:

Si,j=Si,1≤i≤k,1≤j≠i≤k+2

Aj,i=Ai,1≤i≤k

在修复节点i的过程中,可以得到以下的线性方程:

通过以上分析可以看到,为了修复单个失效的系统节点i(1≤i≤k),只需要从其他k+r-1个幸存节点中分别下载1/r比例的数据,总的修复带宽就为(k+r-1)a/r,所以,对于修复单个失效的系统节点(现已有对所有节点修复均符合最优属性的码,如文献[15]),MSR码拥有最优修复属性。

1.2 问题描述

在1.1节中本文已经详细地描述了当单个系统节点失效时,传统MSR码的修复过程,但是当有多个节点失效(比如r个),此时,MSR码并没有最优修复属性了。以最常见且应用广泛的(k+2,k)MSR码为例,当有2个系统节点失效时,此时总的修复带宽就是M=ka。而本文提出的方案正是为了解决此问题。

本文提出一种基于(k+2,k)MSR码的高容错低修复带宽的编码方案。在新编码方案中,当有2个系统节点失效时,新码修复带宽几乎为原来的一半。

2 新码的构造与修复带宽分析

2.1 新编码的具体构造

表3 C1系统节点存储结构

表4 C1校验节点存储结构

表5 C2系统节点存储结构

表6 C2校验节点存储结构

2.2 新编码的修复带宽分析

在本文编码方案中,由于新码上下半部C1、C2是MSR码,因此局部修复满足最优修复属性。依托于此性质,接下来具体分析下新码的修复带宽,这里γold代表了传统(k+2,k)MSR码的修复带宽,γnew代表新码的修复带宽。由于MSR码也是MDS码,因此满足MDS属性,在原来编码上添加了4个备份校验节点,所以,这里最多只需要讨论到4系统节点失效的情况。

情况1当单个系统节点失效。很明显,此时新码的修复带带宽与(k+2,k)MSR码是一样的,均为(k+1)α/2。即:

情况2当有2个系统节点失效并且都分布在了C1上(发生概率:1/2×1/2=25%)。首先和之前分析的一样,γold=ka,并且需要连接k个节点进行下载,在新码中,只需要连接上面一半的幸存节点,但是每个幸存节点所需要传输的数据量都是a,即:

γold=ka

情况3当有2个系统节点失效并且都分布在了C2上(发生概率:1/2×1/2=25%)。这种情况实际与情况2是一致的,即:

γold=ka

γold=ka

γnew=(k+2)×a/2=(k+2)a/2

情况5当有3个系统节点失效并且都分布在了C1上(发生概率:(1/2)×(1/2)×(1/2)=12.5%)。由于C1只有2个校验节点,通过MDS属性得知,此时新码也不能修复。

情况6当有3个系统节点失效并且都分布在了C2上(发生概率:(1/2)×(1/2)×(1/2)=12.5%)。结论同情况5。

情况9当有4个系统节点失效并且2个分布在了C1上,2个分布在了C2上(发生概率为37.5%)。

这里额外分析一下这种情况的发生概率:用4位的2进制(0000～1111)来表示总共的16种分布情况,4位代表了4个失效节点,某位为0代表该失效节点在上半部分,某位为1代表该失效节点在下半部分,列出总的16种情况:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

其中,只有0011 0101 0110 1001 1010 1111的情况下满足2-2分布,所以,事件发生概率为37.5%。

情况104个失效节点或者以上时的失效节点其他分布情况。原理和上面一样,此时新码也将不能修复。

表7为(k+2,k)MSR码与本文方案总的修复带宽的对比情况,其中,表中的比数分布指的是失效节点在C1、C2上的分布情况,失效节点只包含系统节点。

表7 (k+2,k)MSR码与新码的修复带宽对比

综上,本文的编码方案在一定程度上对比传统的(k+2,k)MSR码有一定的宽带修复优势。尤其是当k≪r时,新的编码仍然符合高码率的要求,本文的编码方案试用于所有的(k+2,k)MSR码,如文献[3]中所提到的。

3 实验结果分析

表8中给出当k取值固定时(k取4),随着p的变化初始(k+2,k)MSR码和新编码的实际修复带宽的变化。为了方便分析,这里只列出单节点失效和双节点失效的情况,其中γold和γnew的单位均为α。

表8 k固定时的修复带宽对比

根据表8给出的实验数据,可以很容易看出,模拟实验结果基本和理论分析的结果相符合。并且从表8的对比数据可以看出,随着p的增大,本文方案的修复带宽与初始方案相比优势越来越大:γold随着p的增大而增大而γnew却始终在分析的理论期望值2.500周围徘徊。为了进一步地研究新码的修复带宽,接下来再来模拟当p取固定值而k变化时的情景,如表9所示。在此次模拟实验中,设定节点失效概率p取0.1保持不变,并且设定节点之间的失效是相互独立无相关的,其中γold和γnew的单位均为α。从表9给出的实验数据可以看到,随着k取值变大,本文方案的修复带宽与初始方案相比优势也稳定提升。从理论来分析,不管是p还是k的增大,都会导致双节点失效事件发生的概率相比较而提升,所以,本文方案的优势也会得以体现。

表9 p固定时的修复带宽对比

4 结束语

基于传统的(k+2,k)MSR码,本文提出一种改进的低修复带宽的编码方案。仿真结果表明,无论随着单节点失效概率的变化还是随着系统节点数的变化,该方案均能取得较好的修复带宽。由于考虑到了计算的复杂性,后期需将其扩展至(k+r,k)MSR码中,此外需考虑再增加一层甚至多层的MSR码结构,以获得更好的实验结果。

[1] 徐光宪,徐山强,许春艳,等.基于汉明重量网络编码的广播重传算法[J].计算机工程,2016,42(9):38-42.

[2] 刘宴涛,夏桂阳,徐 静,等.一种基于子树分解的组播线性网络编码算法[J].计算机工程,2015,41(11):152-159.

[3] RASHMI K V,SHAH N B,KUMAR P V.Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points Via a Product-matrix Construction[J].IEEE Transactions on Information Theory,2011,57(8):5227-5239.

[4] REED I S,SOLOMON G.Polynomial Codes Over Certain Finite Fields[J].Journal of the Society for Industrial & Applied Mathematics,1960,8(2):300-304.

[5] WANG Z,TAMO I,BRUCK J.Explicit Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2016,62(8):4466-4480.

[6] 张司娜,唐小虎,李 杰.一类新的(k+2,k)Hadamard MSR码[J].西南交通大学报,2016,51(1):234-237.

[7] YANG Bin,TANG Xiaohu,LI Jie.A Systematic Piggybacking Design for Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2015,61(11):5779-5786.

[8] TAMO I,BARG A.A Family of Optimal Locally Recoverable Codes[J].IEEE Transactions on Infor-mation Theory,2013,60(8):4661-4676.

[9] 李晨卉.应用于分布式存储系统的准循环再生码构造方案[J].计算机工程,2015,41(3):81-87.

[10] BLAUM M,BRUCK J,VARDY E.MDS Array Codes with Independent Parity Symbols[J].IEEE Transactions on Information Theory,1995,42(2):529-542.

[11] LI Jie,TANG Xiaohu,PARAMPALLI U.A Framework of Constructions of Minimal Storage Regenerating Codes with the Optimal Access,Update Property[J].IEEE Transactions on Information Theory,2015,61(4):1920-1932.

[12] PAPAILIOPOULOS D S,DIMAKIS A G,CADAMBEM V R.Repair Optimal Erasure Codes Through Hadamard Designs[J].IEEE Transactions on Information Theory,2013,59(5):3021-3037.

[13] TAMO I,WANG Z,BRUCK J.ZigZag Codes:MDS Array Codes with Optimal Rebuilding[J].IEEE Tran-sactions on Information Theory,2013,59(3):1597-1616.

[14] GOPARAJU S,TAMO I,CALDERBANK R.An Improved Sub-packetization Bound for Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2014,60(5):2770-2779.

[15] GOPARAJU S,FAZELI A,VARDY A.Minimum Storage Regenerating Codes for All Parameters[J].IEEE Transactions on Information Theory,2016,99(1):1-10.