基于差集矩陣的部分重復(fù)碼構(gòu)造

王 靜 何亞錦 雷 珂 劉向陽(yáng)

①(長(zhǎng)安大學(xué)信息工程學(xué)院 西安 710064)

②(西北工業(yè)大學(xué)電子信息學(xué)院 西安 710129)

1 引言

由于社交媒體和網(wǎng)絡(luò)信息的興起，數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，傳統(tǒng)的集中式存儲(chǔ)已經(jīng)無(wú)法滿足需求。分布式存儲(chǔ)系統(tǒng)以其價(jià)格低廉、性能優(yōu)異等優(yōu)點(diǎn)，日益成為主流存儲(chǔ)系統(tǒng)。在分布式存儲(chǔ)系統(tǒng)中，即使存在故障節(jié)點(diǎn)的情況下，也需要保證數(shù)據(jù)存儲(chǔ)的完整性和數(shù)據(jù)訪問(wèn)的速度。這個(gè)問(wèn)題通常使用復(fù)制和糾刪碼策略[1,2]來(lái)解決。

復(fù)制策略就是將數(shù)據(jù)塊復(fù)制若干倍，然后將其分別存放在不同的存儲(chǔ)節(jié)點(diǎn)上。其中最常見(jiàn)的為3副本復(fù)制，如Google文件系統(tǒng)(Google File System,GFS)[3]。在節(jié)點(diǎn)故障的時(shí)候，由于副本的存在，只需簡(jiǎn)單復(fù)制數(shù)據(jù)即可修復(fù)。整個(gè)修復(fù)過(guò)程簡(jiǎn)單易實(shí)現(xiàn)，但是卻增加了分布式存儲(chǔ)系統(tǒng)的存儲(chǔ)負(fù)擔(dān)。為了進(jìn)一步優(yōu)化存儲(chǔ)開(kāi)銷，提出糾刪碼策略。糾刪碼策略是將原始文件分成若干塊進(jìn)行編碼產(chǎn)生冗余校驗(yàn)塊來(lái)保證數(shù)據(jù)存儲(chǔ)的可靠性，目前在Windows[4],Facebook的Hadoop集群(Facebook’s Hadoop cluster)[5]等已經(jīng)投入使用。雖然糾刪碼減少了存儲(chǔ)開(kāi)銷，但是在節(jié)點(diǎn)故障修復(fù)的時(shí)候，需要下載整個(gè)原文件，過(guò)程復(fù)雜，且修復(fù)帶寬開(kāi)銷大。

為了進(jìn)一步優(yōu)化存儲(chǔ)系統(tǒng)，文獻(xiàn)[6]提出了再生碼(Regenerating Codes, RC)，在單節(jié)點(diǎn)故障時(shí)，再生碼不需重構(gòu)原文件就能修復(fù)，降低了修復(fù)帶寬開(kāi)銷，但是在修復(fù)過(guò)程中涉及的計(jì)算量比較大。Papailiopoulos等人[7]利用線性組合的思想構(gòu)造了無(wú)參數(shù)限制的最小帶寬再生碼(Minimum Bandwidth Regenerating, MBR)，結(jié)構(gòu)簡(jiǎn)單。Rashmi等人[8]提出了鋸齒狀最小存儲(chǔ)再生碼(Minimum Storage Regenerating, MSR)構(gòu)造，在有限域F3上計(jì)算開(kāi)銷較小。隨后，Guan等人[9]在較小的有限域內(nèi)構(gòu)造了MSR碼，構(gòu)造復(fù)雜度低。為了降低故障節(jié)點(diǎn)的修復(fù)局部性，Gopalan等人[10]和Papailiopoulos等人[11]提出了局部修復(fù)碼(Locally Repairable Codes, LRC)的概念，即單個(gè)故障節(jié)點(diǎn)可以通過(guò)訪問(wèn)最多r個(gè)存活節(jié)點(diǎn)來(lái)實(shí)現(xiàn)數(shù)據(jù)恢復(fù)。文獻(xiàn)[12]將再生碼和局部修復(fù)碼結(jié)合，提出了基于系統(tǒng)MSR碼的局部再生碼，節(jié)點(diǎn)故障修復(fù)時(shí)利用相鄰局部碼進(jìn)行協(xié)作修復(fù)。文獻(xiàn)[13]給出具有(r,t)局部性的局部修復(fù)碼的最小距離上界，并且構(gòu)造的LRC能容忍多節(jié)點(diǎn)故障，在修復(fù)過(guò)程中可以并行讀取數(shù)據(jù)，減少修復(fù)時(shí)間。

El Rouayheb等人[14]提出了部分重復(fù)(Fractional Repetition, FR)碼，它是基于最小帶寬點(diǎn)的精確修復(fù)再生碼，采用外部的最大距離可分(Maximum Distance Separable, MDS)碼和內(nèi)部的重復(fù)碼構(gòu)成。FR碼在修復(fù)故障節(jié)點(diǎn)時(shí)，只需要復(fù)制相應(yīng)的編碼塊，無(wú)需編碼計(jì)算就可完成修復(fù)[15]。文獻(xiàn)[16]給出了基于Steiner系的FR碼的構(gòu)造和仿射幾何等可分解組合設(shè)計(jì)，并利用Kronecker和構(gòu)造出具有較低修復(fù)局部性的新FR碼。文獻(xiàn)[17]提出了基于部分有序集的普遍好的FR碼的簡(jiǎn)單構(gòu)造，構(gòu)造的FR碼易于實(shí)現(xiàn)且可擴(kuò)展，與MBR碼相比，允許存儲(chǔ)更大的文件。Zhu等人[18–20]研究了FR碼與其對(duì)偶碼之間的關(guān)系，進(jìn)一步利用正則圖和組合設(shè)計(jì)構(gòu)造達(dá)到最小距離上限的FR碼，并給出了FR碼重構(gòu)度的下限。

此后，還有很多學(xué)者進(jìn)行了這方面的研究，F(xiàn)R碼的構(gòu)造一直是一個(gè)重要的研究課題。文獻(xiàn)[21]引入一種新的組合模型，構(gòu)造具有均衡訪問(wèn)頻率的最優(yōu)FR碼。文獻(xiàn)[22]基于二部圖的任意周長(zhǎng)構(gòu)造出參數(shù)可調(diào)節(jié)的FR碼，并證明其最優(yōu)性。Prajapati等人[23]使用部分正則圖構(gòu)造異構(gòu)的(每個(gè)節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)包數(shù)量不同)普遍好的FR碼，對(duì)于部分參數(shù)，使用環(huán)構(gòu)造和t?設(shè)計(jì)構(gòu)造普遍好的FR碼。上述構(gòu)造的FR碼都是基于圖構(gòu)造的，過(guò)程相對(duì)復(fù)雜，并且重復(fù)度通常是由結(jié)構(gòu)固定，不能對(duì)任意參數(shù)的FR碼進(jìn)行構(gòu)造。

考慮到現(xiàn)有的FR碼的構(gòu)造算法復(fù)雜且不能靈活地選擇構(gòu)造參數(shù)，本文提出一種基于差集矩陣的FR碼的構(gòu)造算法，可以同時(shí)調(diào)整數(shù)據(jù)塊的重復(fù)度和節(jié)點(diǎn)的存儲(chǔ)容量，且在參數(shù)選取上不受限制。進(jìn)一步可以通過(guò)調(diào)整差集矩陣的參數(shù)λ，構(gòu)造局部性較小的FR碼。實(shí)驗(yàn)結(jié)果表明，構(gòu)造的FR碼具有更低的修復(fù)局部性，修復(fù)簡(jiǎn)單且效率高，減少了故障節(jié)點(diǎn)的修復(fù)時(shí)間。

2 預(yù)備知識(shí)

2.1 FR碼

(n,k,d)分布式存儲(chǔ)系統(tǒng)(Distributed Storage System, DSS)中，其中n表示的是系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn)總數(shù)，k表示重構(gòu)原始文件需要連接的節(jié)點(diǎn)數(shù)，d(≥k)表示修復(fù)單個(gè)故障節(jié)點(diǎn)需要連接的節(jié)點(diǎn)數(shù)。當(dāng)存儲(chǔ)節(jié)點(diǎn)故障時(shí)，新生節(jié)點(diǎn)需要從其他存活節(jié)點(diǎn)下載β個(gè)數(shù)據(jù)塊進(jìn)行精確修復(fù)，即修復(fù)后的數(shù)據(jù)和失效時(shí)的數(shù)據(jù)是完全一樣的。文獻(xiàn)[23]指出在精確修復(fù)模式下，當(dāng)β=1時(shí) ，系統(tǒng)的存儲(chǔ)容量CMBR為

在DSS中，F(xiàn)R碼外部采用MDS碼，將MDS碼編碼后的θ個(gè)編碼塊復(fù)制ρ倍，再將它們分別存放在n個(gè)不同的存儲(chǔ)節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)的存儲(chǔ)大小為α，連接任意k個(gè)節(jié)點(diǎn)就可以重構(gòu)原始文件，記為FR(n,θ,ρ,α)?？紤]到節(jié)點(diǎn)之間會(huì)存儲(chǔ)相同編碼塊，本文給出FR碼的文件大小M(k) 的定義，即任意k個(gè)節(jié)點(diǎn)Vi(i ∈{1,2,...,k})所獲得的不同數(shù)據(jù)塊的個(gè)數(shù)即求并集

文獻(xiàn)[13]指出如果滿足M(k)≥CMBR(n,k,d)，則稱該FR碼是最優(yōu)的。

2.2 差集矩陣

如果矩陣G表示一個(gè)p階可加群，其元素為0,1,...,p ?1。 給定一個(gè)矩陣D，如果矩陣D中的任意兩列的有序差中，G的每個(gè)元素都出現(xiàn)且出現(xiàn)的次數(shù)相同，本文稱矩陣D為差集矩陣(difference matrix)，用D(λp,q;p)表 示。它是元素屬于G的一個(gè)具有p水 平的λp×q的差集矩陣，λ表示D中的任意兩列的有序差中，G中的每個(gè)元素出現(xiàn)的次數(shù)。

2.3 Kronecker和及正交排列

G表示一個(gè)n階可加群，其元素為0 ,1,...,n ?1。假設(shè)矩陣A=(aij)n×r,B=(bij)m×s，則矩陣A和B的Kronecker和為

其中，aij+B表 示aij與B中 的每個(gè)元素做模n加法運(yùn)算。接下來(lái)，為了后面表述更加方便，用1r表示r×1 階 的 全1 矩 陣，(r) 表 示r×1 矩 陣(0,1,...,r ?1)T。

一個(gè)λn2×l的 矩陣，如果滿足矩陣的任意兩列由G的n個(gè)元素所構(gòu)成的n2個(gè)序?qū)?，任一序?qū)Χ汲霈F(xiàn)在這兩列的λ個(gè)行中，則稱這個(gè)矩陣為正交排列，記為O A(n,l;λ)。

3 基于差集矩陣的FR碼構(gòu)造

本節(jié)利用差集矩陣構(gòu)造FR碼，構(gòu)造的FR碼可以調(diào)整編碼塊的重復(fù)度，并且可以通過(guò)設(shè)計(jì)參數(shù)λ，進(jìn)一步調(diào)節(jié)節(jié)點(diǎn)之間共有的編碼塊數(shù)，達(dá)到減小修復(fù)局部性的目的。

3.1 基于差集矩陣的FR碼的構(gòu)造算法

設(shè)G為p階可加群，元素為0 ,1,...,p ?1。若存在元素屬于G的一個(gè)差集矩陣D(λp,q;p)，構(gòu)造矩陣為

具體地，基于差集矩陣λ=1的FR碼的具體構(gòu)造步驟如下所示：

當(dāng)l>1,p>1 且l≤q+1(q為p的 最 小 素 因數(shù))時(shí)，給出了 OA(p,(q+1);1)的通用構(gòu)造方法，并在此基礎(chǔ)上構(gòu)造了普遍好的FR碼。

設(shè)α=[0,1,...,p ?1]T,αi=[i,i,...,i]T(i=0,1,...,p ?1)， 定義函數(shù)Mj(α)=[0+j, 1+j, ...,p ?1+j]T，其中i+j(i=0,1,...,p ?1)表 示模p加 ，構(gòu)造如式(5)的正交矩陣

矩陣O A可以進(jìn)一步表示成

根據(jù)差集矩陣的定義，O A(p,(q+1);1)=[D(p,q;p)⊕(p),(p)⊕0p]，可以驗(yàn)證得

是一個(gè)模p加法群上的差集矩陣。這里的OA(p,(q+1);1),D(p,q;p) 中 的(p ?1) 和(q ?1)分 別 表示數(shù)p?1 和數(shù)q?1 ，而(p)=(0,1,...,p ?1)T。

定理1正交排列 OA(p,(q+1);λ)構(gòu)造FR碼，共有p(q+1)個(gè) 節(jié)點(diǎn)，λp2個(gè) 編碼塊，重復(fù)度為q+1，節(jié)點(diǎn)存儲(chǔ)大小為λp，即F R(λp2,p(q+1),q+1,λp)。節(jié)點(diǎn)故障時(shí)，需要連接p個(gè)節(jié)點(diǎn)修復(fù)。

證明正交排列OA(p,(q+1);λ)=[D(λp,q;p)⊕(p),(p)⊕0λp]矩 陣是一個(gè)λp2×(q+1)矩 陣，O A 的λp2行對(duì)應(yīng)λp2個(gè)不同的編碼塊，O A 的q+1列對(duì)應(yīng)著FR碼的重復(fù)度。由構(gòu)造過(guò)程可知， OA 的任一列都包含了所有的編碼塊，且每個(gè)編碼塊都正好與唯一的節(jié)點(diǎn)相關(guān)聯(lián)，因此由正交排列 OA矩陣構(gòu)造的FR碼有q+1個(gè) 平行類，即正交排列O A矩陣的每一列都是一個(gè)平行類，本文稱FR碼是可分解的。每列取p個(gè)不同的元素，每個(gè)元素在該列中出現(xiàn)λp次。針對(duì)某列，將取相同元素所在行編碼塊放置在一個(gè)節(jié)點(diǎn)中，節(jié)點(diǎn)之間有λ個(gè)相同的編碼塊。故單節(jié)點(diǎn)故障時(shí)，只需從p個(gè)節(jié)點(diǎn)上下載λ個(gè)編碼塊即可修復(fù)。考慮多節(jié)點(diǎn)故障時(shí)，因?yàn)槊總€(gè)平行類含有p個(gè)節(jié)點(diǎn)，故多節(jié)點(diǎn)故障時(shí)同樣僅需從p個(gè)節(jié)點(diǎn)中下載數(shù)據(jù)即可完成修復(fù)。 證畢

定理2由上述λ=1的差集矩陣構(gòu)造的FR碼是最優(yōu)的FR碼。

證明λ=1時(shí) ，正交排列O A(p,(q+1);1)，矩陣O A任兩列的元素所組成的有序?qū)H出現(xiàn)1次，即任意兩列中的兩行的元素對(duì)不會(huì)完全相同。由FR碼的構(gòu)造方法可知，每一列對(duì)應(yīng)一個(gè)平行類，所以平行類之間的存儲(chǔ)節(jié)點(diǎn)有一個(gè)編碼塊相同。假定FR碼每個(gè)節(jié)點(diǎn)存儲(chǔ)大小為d，即修復(fù)度，連接任意k個(gè)節(jié)點(diǎn)可以重構(gòu)原文件。因?yàn)閮蓚€(gè)節(jié)點(diǎn)之間最多相交一個(gè)編碼塊，所以當(dāng)連接k個(gè)不同的節(jié)點(diǎn)時(shí)，最多可以得到個(gè)重復(fù)數(shù)據(jù)塊，根據(jù)FR碼原文件大小的定義可得M(k)≥kd ?()=CMBR。因此，由λ=1的差集矩陣構(gòu)造的FR碼是最優(yōu)的FR碼。 證畢

引理1當(dāng)λ=1 且p為素?cái)?shù)時(shí)，構(gòu)造的FR碼的重復(fù)度ρ=2。

證明p為素?cái)?shù)時(shí)，其最小素因子q=1，則構(gòu)造的差集矩陣為D(p,1;p)， 進(jìn)一步得到一個(gè)p×2的正交矩陣 O A(p,2;1)，已知正交矩陣有兩列，故構(gòu)造的FR碼的重復(fù)度ρ=2。 證畢

引理2當(dāng)p為合數(shù)時(shí)，構(gòu)造的FR碼的重復(fù)度ρ ≥3。

證明p為合數(shù)時(shí)，可知其最小素因子最小為q(q ≥2) ， 構(gòu)造的差集矩陣為D(p,q;p)，進(jìn)一步得到一個(gè)p×(q+1)的 正交矩陣O A(p,(q+1);1)，又已知構(gòu)造的FR碼的重復(fù)度為q+1(q+1≥3)，所以構(gòu)造的FR碼的重復(fù)度ρ≥3。 證畢

定理3由λ=2的差集矩陣構(gòu)造的FR碼，令k=p+1 ，且k= 3w+v，任意連接k個(gè)節(jié)點(diǎn)所獲得的最小文件大小為

證明考慮λ=2 ，故λp的最小素因子為2，即q=2 ，則進(jìn)一步構(gòu)造基于λ=2 的差集矩陣的FR(2p2, 3p, 3, 2p)碼 。FR碼每個(gè)節(jié)點(diǎn)存儲(chǔ)大小為2p， 一個(gè)平行類含有p個(gè)節(jié)點(diǎn)，不論單節(jié)點(diǎn)還是多節(jié)點(diǎn)的節(jié)點(diǎn)故障，僅需連接p個(gè)節(jié)點(diǎn)即可修復(fù)。

考慮節(jié)點(diǎn)故障修復(fù)的局部性，令k=p+1 ，其中k= 3w+v，文件大小為M(k)=min|Ui∈kVi|,k ∈{1,2,...,p},|k|=k

考慮兩個(gè)節(jié)點(diǎn)相交的編碼塊數(shù)，優(yōu)先考慮不在一個(gè)平行類中的節(jié)點(diǎn)。任取k個(gè)節(jié)點(diǎn)所獲得的編碼塊為2kp，根據(jù)k= 3w+v可知，有3?v個(gè) 平行類取w個(gè) 節(jié)點(diǎn)，有v個(gè)平行類取w+1個(gè)節(jié)點(diǎn)。由于同一平行類內(nèi)的節(jié)點(diǎn)之間無(wú)相交編碼塊，而平行類間的兩節(jié)點(diǎn)之間有一個(gè)相同的編碼塊。當(dāng)0w＜2時(shí) ，k個(gè)節(jié)點(diǎn)至少有2[()?v]個(gè) 編碼塊，w≥2 時(shí)，k個(gè)節(jié)點(diǎn)至少有2 [()?v()?(3?v)()]個(gè) 相同編碼塊?？紤]p是每個(gè)節(jié)點(diǎn)存儲(chǔ)的編碼塊數(shù)，p最小取2，故k最小為3。由構(gòu)造過(guò)程可知，分別從3個(gè)平行類中取1個(gè)節(jié)點(diǎn)，則3個(gè)節(jié)點(diǎn)最少相交1個(gè)編碼塊。故

3.2 構(gòu)造法的應(yīng)用

例1當(dāng)p為素?cái)?shù)且p=3 時(shí)，其最小素因數(shù)q=1 ，則構(gòu)造正交矩陣OA(3,2;1)=[D(3,1;3)]⊕(3),(3)⊕03] 如式(11)所示，矩陣O A(3,2;1)后面為所對(duì)應(yīng)的編碼塊。

由于 O A(3,2;1)矩陣的每一列都包含了所有的編碼塊，且每個(gè)編碼塊只對(duì)應(yīng)唯一的一個(gè)節(jié)點(diǎn)。因此每一列都是一個(gè)平行類?？紤]矩陣的最后一列，前3個(gè)元素取第1水平0，即水平“0”，于是把“1,2,3”放到p2的第“1”個(gè)節(jié)點(diǎn)中。類似地，把“4,5,6”放到p2的第“2”個(gè)節(jié)點(diǎn)中，把“7,8,9”放到p2的第“3”個(gè)節(jié)點(diǎn)中，這3個(gè)節(jié)點(diǎn)構(gòu)成平行類p2。 同理可以得到平行類p1的3個(gè)節(jié)點(diǎn)，最終得到6個(gè)節(jié)點(diǎn)。

將原文件M分成6 個(gè)數(shù)據(jù)塊，采用(9, 6)MDS碼編碼，得到9個(gè)編碼塊。用戶連接任意3個(gè)節(jié)點(diǎn)至少可以獲得6個(gè)不同的數(shù)據(jù)塊，即可重構(gòu)原文件M。又由CMBR=3×3?=6，所以構(gòu)造的FR碼是最優(yōu)的。構(gòu)造的FR碼的重復(fù)度ρ=2，并且有2個(gè)平行類，每個(gè)平行類包含了所有的數(shù)據(jù)塊。

例2令p=4， 其最小素因子q=2，則可以得到一個(gè) 4×2 的差集矩陣D(4,2;4)。利用差集矩陣D(4,2;4) ，構(gòu)造得到矩陣OA(4,3;1)=[D(4,2;4)⊕(4),(4)⊕04]， 如式(13)所示。矩陣O A(4,3;1)后面附的是相對(duì)應(yīng)的編碼塊

采用系統(tǒng)( 16,13)MDS碼，每個(gè)節(jié)點(diǎn)存儲(chǔ)4個(gè)編碼塊。如果選取其中的任意兩個(gè)平行類，則可以得到一個(gè)重復(fù)度ρ=2的FR碼；如果取3個(gè)平行類，就得到了重復(fù)度ρ=3的FR碼。

例3考慮λ=2 ， 利用差集矩陣D(6,2;3)，構(gòu)造得到矩陣O A(3,3;2)=[D(6,2;3)⊕(3),(3)⊕06]，如下所示。通過(guò)該設(shè)計(jì)，我們可以得到一個(gè)ρ=3的FR碼，并且有3個(gè)平行類。更具體地說(shuō)，采用系統(tǒng)(18, 15)MDS碼，對(duì)15個(gè)數(shù)據(jù)塊編碼，可以生成3個(gè)校驗(yàn)塊，其中每個(gè)節(jié)點(diǎn)存儲(chǔ)6個(gè)數(shù)據(jù)包。如果節(jié)點(diǎn)V1故障，則新生節(jié)點(diǎn)可以從節(jié)點(diǎn)V4下載{1,10}，從V5下 載{4,13}，從V6下載{7,16}，來(lái)修復(fù)故障節(jié)點(diǎn)V1；或者從V7下載{1,4}，從V8下載{7,10}，從V9下 載{13,16}，實(shí)現(xiàn)故障節(jié)點(diǎn)V1的修復(fù)。進(jìn)一步可以看出，任意連接k=4個(gè)節(jié)點(diǎn)，用戶都可以恢復(fù)原文件。且當(dāng)λ=2時(shí)，上述構(gòu)造出來(lái)的FR碼是局部修復(fù)碼，單節(jié)點(diǎn)的修復(fù)局部性為3

3.3 故障節(jié)點(diǎn)修復(fù)

分布式存儲(chǔ)系統(tǒng)中出現(xiàn)節(jié)點(diǎn)故障，在修復(fù)過(guò)程中需要連接的節(jié)點(diǎn)集合稱為修復(fù)組。本節(jié)主要從單節(jié)點(diǎn)故障、兩節(jié)點(diǎn)故障以及多節(jié)點(diǎn)故障進(jìn)行分類討論，具體修復(fù)過(guò)程如下：

當(dāng)單節(jié)點(diǎn)故障的時(shí)候，只需要連接任意一個(gè)完整平行類即可進(jìn)行精確無(wú)編碼修復(fù)。如例2構(gòu)造的FR碼，當(dāng)?shù)?個(gè)平行類p1中 的節(jié)點(diǎn)V1故障時(shí)，可以從平行類p2中 的節(jié)點(diǎn)V5下載編碼塊1，從節(jié)點(diǎn)V6下載編碼塊5，從節(jié)點(diǎn)V7下載編碼塊9，從節(jié)點(diǎn)V8下載編碼塊13，進(jìn)行無(wú)編碼精確修復(fù)。節(jié)點(diǎn)V1故障也可以從平行類p3中 的4個(gè)節(jié)點(diǎn){V9,V10,V11,V12}進(jìn)行修復(fù)，或者利用平行類p2和p3混合修復(fù)如修復(fù)集{V5,V6,V11,V12}等多種修復(fù)選擇方案。連接任意修復(fù)組中的4個(gè)節(jié)點(diǎn)通過(guò)復(fù)制相關(guān)編碼塊即可進(jìn)行無(wú)編碼精確修復(fù)故障節(jié)點(diǎn)。

當(dāng)系統(tǒng)中出現(xiàn)兩個(gè)節(jié)點(diǎn)同時(shí)故障時(shí)，分為以下情況：如果重復(fù)度ρ=2，兩個(gè)故障節(jié)點(diǎn)在同一個(gè)平行類中，則可以利用另一個(gè)平行類進(jìn)行修復(fù)；如果兩個(gè)故障節(jié)點(diǎn)不在同一個(gè)平行類，且兩個(gè)故障節(jié)點(diǎn)有一個(gè)編碼塊相同，這種情況下就不能采用復(fù)制的方式進(jìn)行修復(fù)，需要利用其余存活節(jié)點(diǎn)恢復(fù)原文件，進(jìn)一步修復(fù)故障節(jié)點(diǎn)。如例1中的節(jié)點(diǎn)V1和V2故 障，兩個(gè)故障節(jié)點(diǎn)都在平行類p1，則可以用另一個(gè)平行類p2中 的3個(gè)節(jié)點(diǎn){V4,V5,V6}來(lái)修復(fù)故障節(jié)點(diǎn)。如果節(jié)點(diǎn)V1和 節(jié)點(diǎn)V4同時(shí)故障，由于兩個(gè)故障節(jié)點(diǎn)中含有相同編碼塊，故不能采用簡(jiǎn)單復(fù)制的方式，可以連接其余兩個(gè)節(jié)點(diǎn)V2和V3進(jìn)行MDS碼編碼恢復(fù)原文件，進(jìn)一步精確修復(fù)故障節(jié)點(diǎn)V1和V4。針對(duì)重復(fù)度ρ>2的情況，不論是兩個(gè)故障節(jié)點(diǎn)在一個(gè)平行類，還是其他情況，均可以利用其他平行類中的節(jié)點(diǎn)下載相應(yīng)編碼塊進(jìn)行精確修復(fù)。如例2中的節(jié)點(diǎn)V1和V5故障，可以利用平行類p3中的4個(gè)節(jié)點(diǎn){V9,V10,V11,V12}進(jìn)行修復(fù)。

對(duì)于修復(fù)多個(gè)故障節(jié)點(diǎn)，可以分為以下4種情況：(1) 若多個(gè)故障節(jié)點(diǎn)都在同一個(gè)平行類，則可以利用其他平行類進(jìn)行修復(fù)；(2)對(duì)于多個(gè)故障節(jié)點(diǎn)不在同一個(gè)平行類的情況，若還存在不包括故障節(jié)點(diǎn)的平行類，那么就可以直接用不包括故障節(jié)點(diǎn)的平行類進(jìn)行修復(fù)；(3)若多個(gè)故障節(jié)點(diǎn)分布在所有平行類中，且不存在所有平行類中的故障節(jié)點(diǎn)都包含同一個(gè)或者多個(gè)編碼塊的情況，此時(shí)可以通過(guò)連接多個(gè)平行類中的存活節(jié)點(diǎn)來(lái)修復(fù)故障節(jié)點(diǎn)。(4)若多個(gè)故障節(jié)點(diǎn)分布在所有平行類中，且有一個(gè)或者多個(gè)編碼塊無(wú)法從現(xiàn)有存活節(jié)點(diǎn)中獲得，此時(shí)無(wú)法再采用復(fù)制方式進(jìn)行修復(fù)，需要利用存活節(jié)點(diǎn)先恢復(fù)原文件，從而修復(fù)故障節(jié)點(diǎn)。

4 性能分析

基于差集矩陣構(gòu)造的FR碼的性能分析主要集中在節(jié)點(diǎn)修復(fù)選擇度、修復(fù)復(fù)雜度、修復(fù)帶寬開(kāi)銷和修復(fù)局部性這幾方面，并將其與里德-所羅門(mén)(Reed-Solomon, RS)碼和簡(jiǎn)單再生碼(Simple Regenerating Codes, SRC)進(jìn)行性能比較。

表1給出了相同文件情況下RS碼、SRC和基于λ=1差集矩陣構(gòu)造的FR碼的修復(fù)帶寬開(kāi)銷和修復(fù)局部性。本文構(gòu)造的FR碼外部采用(k+3,k)MDS碼。

表1 RS碼、SRC和FR碼的故障節(jié)點(diǎn)修復(fù)性能比較

4.1 節(jié)點(diǎn)修復(fù)選擇度

節(jié)點(diǎn)修復(fù)選擇度指的是故障節(jié)點(diǎn)修復(fù)過(guò)程中的修復(fù)選擇方案?？紤]單節(jié)點(diǎn)故障的修復(fù)選擇度，對(duì)于 (n,k)R S碼，從n?1 個(gè)存活節(jié)點(diǎn)隨機(jī)選取k個(gè)來(lái)修復(fù)故障節(jié)點(diǎn)。因此， (n,k)RS碼的修復(fù)選擇度為。 對(duì)于SRC，從n?1個(gè) 存活節(jié)點(diǎn)隨機(jī)選取f個(gè)存活節(jié)點(diǎn)來(lái)修復(fù)故障節(jié)點(diǎn)，故其修復(fù)選擇度為。 基于λ=1差集矩陣構(gòu)造的FR碼，其選擇度主要與重復(fù)度ρ和節(jié)點(diǎn)存儲(chǔ)大小α有關(guān)。如果構(gòu)造的FR碼的重復(fù)度ρ=2，那么節(jié)點(diǎn)故障時(shí)的修復(fù)選擇度僅為1，只需要連接具有相同編碼塊的存活節(jié)點(diǎn)即可修復(fù)。如果構(gòu)造的FR碼的重復(fù)度ρ>2時(shí)，故障節(jié)點(diǎn)修復(fù)可以有多種修復(fù)方案。對(duì)于任意單節(jié)點(diǎn)故障，都可以從其他ρ?1個(gè)存活節(jié)點(diǎn)選擇修復(fù)。對(duì)于重復(fù)度為ρ、節(jié)點(diǎn)存儲(chǔ)大小為α的FR碼，節(jié)點(diǎn)故障的時(shí)候，只需要從其他副本中下載相應(yīng)的數(shù)據(jù)塊即可。由于任意兩個(gè)節(jié)點(diǎn)之間最多相交1個(gè)編碼塊，修復(fù)一個(gè)節(jié)點(diǎn)中的第1個(gè)編碼塊和第2個(gè)編碼塊均有ρ?1 種選取方案，故其修復(fù)選擇度為(ρ ?1)α。從圖1看出，當(dāng)FR碼節(jié)點(diǎn)存儲(chǔ)大小α=3時(shí)，基于λ=1差集矩陣構(gòu)造的FR碼節(jié)點(diǎn)修復(fù)選擇度隨著重復(fù)度的增加呈指數(shù)倍增加。

圖1 節(jié)點(diǎn)修復(fù)選擇度與重復(fù)度ρ 之間的關(guān)系，其中α=3

4.2 修復(fù)復(fù)雜度

對(duì)于(n,k)R S碼，在修復(fù)過(guò)程中需要連接k個(gè)節(jié)點(diǎn)恢復(fù)原文件，再重新編碼生成故障節(jié)點(diǎn)。整個(gè)故障節(jié)點(diǎn)修復(fù)過(guò)程涉及大量的有限域運(yùn)算，需要k2+k次有限域乘法運(yùn)算和k2?1次有限域加法運(yùn)算，因此RS碼在單節(jié)點(diǎn)故障時(shí)的修復(fù)復(fù)雜度為O(2k2+k ?1)。對(duì)于SRC，修復(fù)一個(gè)編碼塊需要進(jìn)行f?1 次 異或運(yùn)算，由于每個(gè)節(jié)點(diǎn)存儲(chǔ)f+1個(gè)編碼塊，因此SRC的修復(fù)過(guò)程需要(f+1)(f ?1)次異或運(yùn)算，其修復(fù)復(fù)雜度為O(f2?1)?；诓罴仃嚇?gòu)造的FR碼，整個(gè)過(guò)程只涉及文件的讀取，無(wú)需編碼，過(guò)程簡(jiǎn)單，修復(fù)復(fù)雜度明顯低于RS碼和SRC這兩種編碼方案。

4.3 修復(fù)帶寬開(kāi)銷

分布式存儲(chǔ)系統(tǒng)中出現(xiàn)節(jié)點(diǎn)故障，在修復(fù)過(guò)程中下載的數(shù)據(jù)量大小稱為修復(fù)帶寬開(kāi)銷。針對(duì)單節(jié)點(diǎn)故障，傳統(tǒng)的(n,k)RS碼在修復(fù)過(guò)程中需要下載整個(gè)原文件來(lái)修復(fù)故障節(jié)點(diǎn)，故單節(jié)點(diǎn)修復(fù)帶寬開(kāi)銷為M；對(duì)于(n,k,f)SRC, SRC在修復(fù)過(guò)程中需要連接f個(gè)存活節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存儲(chǔ)f+1個(gè)數(shù)據(jù)塊，且單個(gè)數(shù)據(jù)塊大小為M/fk，故單節(jié)點(diǎn)修復(fù)帶寬開(kāi)銷為 (f+1)M/k；針對(duì)本文基于λ=1差集矩陣構(gòu)造的FR碼，由構(gòu)造可知一個(gè)平行類中有λp2個(gè)編碼塊，節(jié)點(diǎn)存儲(chǔ)大小為λp， 由于外部采用系統(tǒng)(k+3,k)M DS碼，故有λp2=k+3，經(jīng)計(jì)算可知，一個(gè)平行類中含有p=個(gè)節(jié)點(diǎn)，每個(gè)數(shù)據(jù)塊大小為M/k， 故基于λ=1差集矩陣構(gòu)造的FR碼的修復(fù)帶寬開(kāi)銷為。考慮到基于λ=1構(gòu)造的FR碼是最優(yōu)的，由文獻(xiàn)[13]可知，M(k)≥CMBR√(n,k,d)， 故可以得出M(k)≥?(k ?1)k/2。因此可以計(jì)算出FR碼的最小修復(fù)帶寬開(kāi)銷為k+3?，可計(jì)算出k=1時(shí)最小，修復(fù)帶寬開(kāi)銷為4，此時(shí)M(k)≥2。

在性能分析部分提前設(shè)定相關(guān)參數(shù)，文件大小恒為M= 1000 Mb ，SRC的子文件數(shù)f=4。單節(jié)點(diǎn)故障時(shí)，SRC的修復(fù)帶寬開(kāi)銷為5M/k，采用例2中構(gòu)造的FR碼的修復(fù)帶寬開(kāi)銷為4M/k，由于文件大小為M= 1000 Mb ，并且基于λ=1構(gòu)造的FR碼是最優(yōu)的，滿足M(k)≥CMBR(n,k,d)，因此k存在最大值，當(dāng)k取最大值時(shí)，修復(fù)帶寬開(kāi)銷最小。單節(jié)點(diǎn)故障修復(fù)帶寬開(kāi)銷如圖2所示。

當(dāng)兩節(jié)點(diǎn)故障時(shí)，傳統(tǒng)的 (n,k)RS碼在修復(fù)過(guò)程中需要下載整個(gè)原文件來(lái)修復(fù)故障節(jié)點(diǎn)，故兩節(jié)點(diǎn)修復(fù)帶寬開(kāi)銷依舊為M；對(duì)于(n,k,f)SRC，其修復(fù)帶寬受兩個(gè)故障節(jié)點(diǎn)之間的節(jié)點(diǎn)數(shù)影響。如果節(jié)點(diǎn)數(shù)大于f?1，那么這兩個(gè)故障節(jié)點(diǎn)可以分別連接f個(gè)存活節(jié)點(diǎn)來(lái)修復(fù)，此時(shí)的修復(fù)帶寬開(kāi)銷為2(f+1)M/k，反之如果節(jié)點(diǎn)數(shù)小于f?1，不能按照單節(jié)點(diǎn)故障修復(fù)方法進(jìn)行修復(fù)，需要先恢復(fù)原文件，進(jìn)一步修復(fù)故障節(jié)點(diǎn)，故修復(fù)帶寬為M。針對(duì)本文基于λ=1差集矩陣構(gòu)造的FR碼，由于一個(gè)平行類含有個(gè)節(jié)點(diǎn)，故兩個(gè)節(jié)點(diǎn)故障時(shí)的修復(fù)帶寬開(kāi)銷依舊為。

兩個(gè)節(jié)點(diǎn)故障時(shí)，采用例2中FR碼的修復(fù)帶寬開(kāi)銷為4M/k， 而RS碼和SRC的修復(fù)帶寬開(kāi)銷為M。兩節(jié)點(diǎn)故障修復(fù)帶寬開(kāi)銷如圖3所示，其中RS碼和SRC的曲線重合。

從圖2和圖3可以看出，不論是單節(jié)點(diǎn)故障還是多節(jié)點(diǎn)故障，基于λ=1差集矩陣構(gòu)造的FR碼的修復(fù)帶寬開(kāi)銷明顯優(yōu)于RS碼和SRC簡(jiǎn)單再生碼。

圖2 λ =1時(shí)單節(jié)點(diǎn)故障修復(fù)帶寬開(kāi)銷性能對(duì)比

圖3 λ =1時(shí)兩節(jié)點(diǎn)故障修復(fù)帶寬開(kāi)銷性能對(duì)比

4.4 修復(fù)局部性

考慮單節(jié)點(diǎn)故障時(shí)，(n,k)RS碼在修復(fù)過(guò)程中，需要連接k個(gè)節(jié)點(diǎn)，修復(fù)局部性為k；而SRC需要連接2f個(gè)節(jié)點(diǎn)，修復(fù)局部性為2f；針對(duì)基于差集矩陣構(gòu)造的FR碼，由構(gòu)造可知一個(gè)平行類中共有λp2個(gè)編碼塊，節(jié)點(diǎn)存儲(chǔ)大小為λp，一個(gè)平行類中包含p個(gè)節(jié)點(diǎn)，故單節(jié)點(diǎn)故障修復(fù)局部性為p。采用系統(tǒng)(k+3,k)MDS碼，故有λp2=k+3，經(jīng)計(jì)算可知，單節(jié)點(diǎn)故障的修復(fù)局部性為p=。

考慮兩節(jié)點(diǎn)故障，SRC和 (n,k)RS碼的修復(fù)局部性均為k。而本文提出的基于差集矩陣的FR碼，一個(gè)平行類含有p個(gè)節(jié)點(diǎn)，故p個(gè)節(jié)點(diǎn)即√可以修復(fù)任意節(jié)點(diǎn)故障，因此修復(fù)局部性恒為p=。

假設(shè)F R 碼外部采用 (k+3,k)M D S 碼中的k=13 ， 則λ=1構(gòu) 造的FR碼外部采用( 16, 13)MDS碼。如圖4所示，考慮單節(jié)點(diǎn)故障，( 16, 13)RS碼的修復(fù)局部性為13；當(dāng)f取4時(shí)，SRC的修復(fù)局部性為8；采用例2中構(gòu)造的FR碼的修復(fù)局部性為4。當(dāng)兩個(gè)節(jié)點(diǎn)故障時(shí)，( 16, 13)RS碼和SRC的修復(fù)局部性均為13，采用例2中FR碼的修復(fù)局部性仍為4，具體如圖4所示。與RS碼和SRC相比，無(wú)論單節(jié)點(diǎn)故障還是兩節(jié)點(diǎn)故障，基于λ=1的差集矩陣構(gòu)造的FR碼都具有較優(yōu)的修復(fù)局部性。

圖4 λ =1時(shí)單節(jié)點(diǎn)故障修復(fù)局部性性能對(duì)比

假設(shè)FR碼外部采用(k+3,k)M DS碼中的k=15，則基于λ=2的差集矩陣構(gòu)造的FR碼外部采用(18, 15)M DS碼。如圖5所示，單節(jié)點(diǎn)故障時(shí)，(18, 15)RS碼的修復(fù)局部性為15；當(dāng)f取4時(shí)，SRC的修復(fù)局部性為8；采用例3中FR碼的修復(fù)局部性為3?？紤]兩節(jié)點(diǎn)故障時(shí)， ( 18, 15)RS碼和SRC的修復(fù)局部性均為15，采用例3中FR碼的修復(fù)局部性仍為3。與RS碼和SRC相比，無(wú)論單節(jié)點(diǎn)故障還是兩節(jié)點(diǎn)故障，基于差集矩陣λ>1的FR碼都具有較小的修復(fù)局部性。

圖5 λ =2時(shí)兩節(jié)點(diǎn)故障修復(fù)局部性性能對(duì)比

5 結(jié)論

針對(duì)目前基于部分圖構(gòu)造的FR碼，構(gòu)造過(guò)程復(fù)雜，本文提出了一種基于差集矩陣的FR碼的構(gòu)造算法，可以容忍多節(jié)點(diǎn)故障，同時(shí)可以任意調(diào)整節(jié)點(diǎn)間的共有編碼塊數(shù)，在參數(shù)選取上比較靈活。進(jìn)一步證明了提出的基于差集矩陣λ=1的FR碼是最優(yōu)的，并給出了基于差集矩陣λ=2構(gòu)造的FR碼的文件大小，且其修復(fù)局部性明顯減小。性能分析和仿真結(jié)果表明，與傳統(tǒng)的RS碼和SRC相比，構(gòu)造的FR碼雖然犧牲了存儲(chǔ)開(kāi)銷，但是可以顯著減少故障節(jié)點(diǎn)的修復(fù)局部性和修復(fù)帶寬開(kāi)銷，降低修復(fù)復(fù)雜度。