應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造方案

李晨卉

(復(fù)旦大學(xué)上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室,上海200433)

應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造方案

李晨卉

(復(fù)旦大學(xué)上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室,上海200433)

傳統(tǒng)糾錯(cuò)碼編碼方案能夠提高系統(tǒng)容錯(cuò)能力,但在數(shù)據(jù)修復(fù)時(shí)會(huì)占用大量帶寬。為此,基于循環(huán)結(jié)構(gòu),構(gòu)造一種面向分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)最小存儲(chǔ)再生碼。根據(jù)該準(zhǔn)循環(huán)再生碼的冗余系數(shù)向量權(quán)重和修復(fù)帶寬邊界,設(shè)計(jì)一種改進(jìn)的節(jié)點(diǎn)修復(fù)算法,證明其修復(fù)帶寬在最好情況能達(dá)到最小割下界,在最壞情況下也優(yōu)于最大距離可分碼的修復(fù)帶寬。實(shí)驗(yàn)結(jié)果表明,該再碼構(gòu)造方案不僅節(jié)省存儲(chǔ)空間,而且具有構(gòu)造簡單、運(yùn)算代價(jià)低和修復(fù)帶寬小等特點(diǎn)。

網(wǎng)絡(luò)編碼;分布式存儲(chǔ)系統(tǒng);準(zhǔn)循環(huán);再生碼;最小存儲(chǔ)再生碼;數(shù)據(jù)修復(fù)

1 概述

隨著數(shù)字信息從文本到多媒體的轉(zhuǎn)變以及社會(huì)信息化進(jìn)程的加快,信息量開始呈幾何級(jí)數(shù)爆炸性地增長,海量數(shù)據(jù)的存儲(chǔ)和處理受到社會(huì)各界越來越廣泛的關(guān)注。如今,海量數(shù)據(jù)存儲(chǔ)已成為一個(gè)備受矚目的研究熱點(diǎn)。分布式存儲(chǔ)系統(tǒng)(Distributed Storage System,DSS)是一種結(jié)合了互聯(lián)網(wǎng)和存儲(chǔ)技術(shù)的、面向海量數(shù)據(jù)的存儲(chǔ)解決方案。然而,由于網(wǎng)絡(luò)不穩(wěn)定,分布式存儲(chǔ)系統(tǒng)中很容易發(fā)生因節(jié)點(diǎn)失效導(dǎo)致數(shù)據(jù)無法取回的情況,因此通常需要采取某種冗余機(jī)制來提高可靠性。同時(shí),系統(tǒng)需要具有對(duì)失效節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)進(jìn)行修復(fù)的能力以維持其容錯(cuò)性能,但這一過程可能會(huì)造成大量數(shù)據(jù)傳輸。

復(fù)制是最簡單并常見的冗余方案,通過保存2個(gè)或2個(gè)以上原數(shù)據(jù)的副本,保證某處硬盤故障或網(wǎng)絡(luò)中斷不影響該部分?jǐn)?shù)據(jù)的取用,然而這種方案消耗太多額外存儲(chǔ)空間。相比之下,傳統(tǒng)的糾刪碼方案在很大程度上提高了數(shù)據(jù)的存儲(chǔ)效率(在保證系統(tǒng)容錯(cuò)等級(jí)的同時(shí)減少了冗余占用的額外存儲(chǔ)空間),其中最著名的一類糾錯(cuò)碼稱為最大距離可分(Maximum Distance Separable,MDS)碼,但這種編

碼策略在數(shù)據(jù)修復(fù)時(shí)會(huì)產(chǎn)生很大的帶寬消耗和計(jì)算負(fù)載。

針對(duì)該問題,文獻(xiàn)［1］將網(wǎng)絡(luò)編碼技術(shù)與分布式存儲(chǔ)碼技術(shù)相結(jié)合,提出一種新型再生碼編碼方案。利用網(wǎng)絡(luò)編碼技術(shù),再生碼策略能夠在保證系統(tǒng)容錯(cuò)性能(與MDS碼具有相同的容錯(cuò)性能)的同時(shí),優(yōu)化數(shù)據(jù)修復(fù)過程的帶寬消耗。然而,網(wǎng)絡(luò)編碼技術(shù)是一種使網(wǎng)絡(luò)中的中繼節(jié)點(diǎn)具有編碼能力以達(dá)到信息論中多播網(wǎng)絡(luò)的理論最大流界的通信領(lǐng)域新概念,以此為基礎(chǔ)改進(jìn)的再生碼在數(shù)據(jù)修復(fù)時(shí)通常具有復(fù)雜的節(jié)點(diǎn)內(nèi)運(yùn)算,以及為達(dá)到低修復(fù)帶寬而增加的存儲(chǔ)消耗。為此,本文提出一種適用于分布式存儲(chǔ)系統(tǒng)的新型準(zhǔn)循環(huán)再生碼構(gòu)造方案。

2 數(shù)據(jù)修復(fù)與再生碼

在介紹數(shù)據(jù)修復(fù)以及再生碼前,以最具代表性之一的MDS碼為例,介紹糾錯(cuò)碼編碼策略。假設(shè)原數(shù)據(jù)大小為B,編碼基域?yàn)橛邢抻騀q(q是有限域的大小),分布式存儲(chǔ)系統(tǒng)一共有n個(gè)節(jié)點(diǎn)。一個(gè)［n,k］MDS碼的基本思想是:將大小為B的數(shù)據(jù)分成k個(gè)數(shù)據(jù)分組,并編碼為n個(gè)分組的數(shù)據(jù)(n＞k,且每個(gè)新分組的大小與原分組相等),其中,任意k個(gè)分組都可完整恢復(fù)原數(shù)據(jù),該過程稱為數(shù)據(jù)重建。這種編碼系統(tǒng)可以容忍n-k個(gè)分組丟失,如圖1所示。

圖1 糾錯(cuò)碼原理

本文稱這種由任意k個(gè)分組完整重建原數(shù)據(jù)的性質(zhì)為MDS性質(zhì)。當(dāng)存儲(chǔ)節(jié)點(diǎn)失效后,MDS碼的節(jié)點(diǎn)修復(fù)策略是先連接有效節(jié)點(diǎn)中的任意k個(gè)節(jié)點(diǎn),進(jìn)行數(shù)據(jù)重建,然后再根據(jù)編碼規(guī)則重新生成失效節(jié)點(diǎn)的數(shù)據(jù)。這種方案為修復(fù)一個(gè)大小為B/k的數(shù)據(jù)分組同時(shí)傳輸大小為B的數(shù)據(jù)量,傳輸帶寬消耗遠(yuǎn)大于節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)量,尤其是在節(jié)點(diǎn)分布較分散的DSS中,節(jié)點(diǎn)修復(fù)所消耗的額外網(wǎng)絡(luò)帶寬更加明顯。

根據(jù)節(jié)點(diǎn)修復(fù)的定義,無需大量數(shù)據(jù)傳輸就能實(shí)現(xiàn)節(jié)點(diǎn)修復(fù)。如圖2所示,原數(shù)據(jù)被分成4塊,分別用A1,A2,B1,B2表示,并編碼為一個(gè)［4,2］MDS碼,每個(gè)節(jié)點(diǎn)存儲(chǔ)2塊數(shù)據(jù)。節(jié)點(diǎn)2先線性運(yùn)算B1⊕B2,然后再上傳給數(shù)據(jù)收集器(Data Collector, DC),同時(shí)連接節(jié)點(diǎn)1、節(jié)點(diǎn)3分別下載A1,A2+B2,在新節(jié)點(diǎn)通過一定線性運(yùn)算完成數(shù)據(jù)修復(fù)。這樣修復(fù)過程只需消耗3塊數(shù)據(jù)大小的帶寬,而且實(shí)現(xiàn)了節(jié)點(diǎn)的精確修復(fù)。其實(shí),節(jié)點(diǎn)修復(fù)只定義修復(fù)得到的新節(jié)點(diǎn)加入后系統(tǒng)仍滿足MDS性質(zhì),因此新節(jié)點(diǎn)可以是不同于原失效節(jié)點(diǎn)的數(shù)據(jù)分組的線性組合。基于該定義,得到另外2種數(shù)據(jù)修復(fù)模型:功能性修復(fù)和系統(tǒng)部分精確修復(fù)。

圖2 精確修復(fù)[4,2]MDS碼的節(jié)點(diǎn)4

精確修復(fù)是指修復(fù)操作所生成的新節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)與原失效節(jié)點(diǎn)完全一致。功能性修復(fù)［1］要求低一些,只需修復(fù)操作所生成的新節(jié)點(diǎn)加入后系統(tǒng)依然保持MDS性質(zhì),因此新節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)可以與原失效節(jié)點(diǎn)不同。系統(tǒng)部分精確修復(fù)是指對(duì)于失效節(jié)點(diǎn)存儲(chǔ)的系統(tǒng)碼(即未編碼的數(shù)據(jù)分塊)部分采取精確修復(fù)原則,而非系統(tǒng)碼部分依照功能性修復(fù)原則。

在功能性修復(fù)模型下,文獻(xiàn)［2］通過采用修復(fù)過程的信息流圖建模得到的修復(fù)帶寬能夠達(dá)到理論上的最小割下界,利用圖2中的［4,2］MDS碼為例展示這一過程,如圖3所示。虛擬源節(jié)點(diǎn)S代表原數(shù)據(jù)B=4,將每個(gè)存儲(chǔ)節(jié)點(diǎn)表示成一對(duì)節(jié)點(diǎn)并通過一條有權(quán)邊相連,邊的權(quán)值就是該節(jié)點(diǎn)的存儲(chǔ)容量α=2。將DC作為虛擬匯節(jié)點(diǎn),并使它連接任意k=2個(gè)節(jié)點(diǎn),d表示連接的節(jié)點(diǎn)數(shù),b表示修復(fù)時(shí)從每個(gè)連接節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量。

圖3 功能性修復(fù)[4,2]MDS碼的信息流

圖3顯示了節(jié)點(diǎn)X4(虛線橢圓部分)失效時(shí),系統(tǒng)重新構(gòu)建一個(gè)與其具有相同存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)X5來替代它的過程。根據(jù)最大流最小割定理［3］,最小割值必須大于等于S發(fā)送的數(shù)據(jù)量,DC才能重建原數(shù)據(jù)。顯然,圖3中的最小割為α+2β=B=4(虛線表

示),意味著βmin=l,修復(fù)帶寬γmin=dβ=3。根據(jù)信息流圖的最小割分析,參數(shù)必須滿足以下條件才能構(gòu)成再生碼［4］:

顯然,當(dāng)α和β達(dá)到最小值時(shí)就會(huì)得到修復(fù)過程的最低資源消耗。不過由于α和β無法同時(shí)達(dá)到最小,因此在B,k,d確定時(shí),可以得到當(dāng)α取最小得到最小存儲(chǔ)方案或β取最小得到最小帶寬方案的一個(gè)折衷曲線,稱取得該曲線上點(diǎn)的α和β時(shí)對(duì)應(yīng)的編碼方案為再生碼,并從中得到2個(gè)極值情況:最小存儲(chǔ)再生(Minimum Storage Regeneration,MSR)碼和最小帶寬再生(Minimum Bandwidth Regenerating, MBR)碼。其中,MSR碼滿足以下性質(zhì):

MBR碼滿足以下性質(zhì):

功能性修復(fù)雖然對(duì)系統(tǒng)修復(fù)操作的要求更低,修復(fù)實(shí)現(xiàn)的難度更小,但存在3點(diǎn)不足:(1)節(jié)點(diǎn)修復(fù)后需要更新系統(tǒng)的數(shù)據(jù)重建和修復(fù)算法;(2)功能性修復(fù)的實(shí)現(xiàn)需要很大的有限域來滿足動(dòng)態(tài)增大的有向無環(huán)圖,導(dǎo)致編解碼的計(jì)算復(fù)雜度較高;(3)動(dòng)態(tài)的修復(fù)和解碼過程容易發(fā)生信息泄露,因此安全性較差。所以,功能性修復(fù)具有局限性。

精確修復(fù)不僅沒有功能性修復(fù)帶來的上述缺陷,而且還能夠保證進(jìn)行節(jié)點(diǎn)修復(fù)后系統(tǒng)內(nèi)始終保存一份完整的系統(tǒng)碼,這樣用戶讀取數(shù)據(jù)時(shí)系統(tǒng)無需運(yùn)算就可以快速并行地傳輸全部原數(shù)據(jù),這使得精確修復(fù)成為當(dāng)前的首選策略。通過干擾對(duì)齊技術(shù),可以找出可精確修復(fù)的MSR碼［4-5］,并推導(dǎo)出以下2個(gè)定理。

定理1(Exact-MSR碼) 假設(shè)MDS碼率［6］不大于1/2,即(k/n)≤1/2,并且d≥2k-1,那么通過干擾對(duì)齊可以達(dá)到式(2)所示的MSR碼邊界。同時(shí),修復(fù)機(jī)制是可確定的,并且需要的有限域不大于2(n-k)。

定理2 在不使用符號(hào)擴(kuò)展且b=1的情況下,達(dá)到割集邊界的線性精確修復(fù)MSR碼在d＜2k-3時(shí)不存在［7］。

3 應(yīng)用于分布式系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造

準(zhǔn)循環(huán)再生碼是一種基于循環(huán)結(jié)構(gòu)的線性編碼,構(gòu)造簡單,且通過預(yù)定義的節(jié)點(diǎn)修復(fù)系數(shù)向量和修復(fù)算法大大降低了修復(fù)產(chǎn)生的運(yùn)算代價(jià)。

假設(shè)在一個(gè)［n,k,d］再生碼中,原信息被分隔成B個(gè)數(shù)據(jù)塊,并編碼成n個(gè)節(jié)點(diǎn),其中,每個(gè)節(jié)點(diǎn)包含α個(gè)分塊。DC可以通過任意k個(gè)節(jié)點(diǎn)完整恢復(fù)出原數(shù)據(jù)。對(duì)于一個(gè)失效節(jié)點(diǎn),新節(jié)點(diǎn)能通過連接任意d個(gè)可用節(jié)點(diǎn)并從每個(gè)節(jié)點(diǎn)下載β個(gè)分塊重建該節(jié)點(diǎn),節(jié)點(diǎn)修復(fù)所消耗的帶寬稱為修復(fù)帶寬,用γ表示,且有γ=dβ。

3.1 準(zhǔn)循環(huán)再生碼的定義

在準(zhǔn)循環(huán)再生碼中,定義α=2,即每個(gè)存儲(chǔ)節(jié)點(diǎn)包含2個(gè)分塊,并規(guī)定每個(gè)節(jié)點(diǎn)的第1個(gè)分塊存儲(chǔ)原數(shù)據(jù)(即系統(tǒng)碼),第2個(gè)分塊存儲(chǔ)冗余碼(用于數(shù)據(jù)修復(fù)和可靠性保護(hù))。由此可知,在準(zhǔn)循環(huán)再生碼中,有B=n。由于準(zhǔn)循環(huán)再生碼也是一種線性網(wǎng)絡(luò)編碼,因此其第2個(gè)分塊的冗余數(shù)據(jù)均為系統(tǒng)碼的線性組合,并且其冗余系數(shù)向量滿足循環(huán)結(jié)構(gòu)。

用G表示一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼的編碼矩陣,則G滿足如下公式:

存儲(chǔ)系統(tǒng)能夠并行地提取數(shù)據(jù)且不需要譯碼。除非特殊聲明,本文中。

定義如果一個(gè)［n,k,d］存儲(chǔ)碼的編碼向量c=［c1|c2］滿足以下2個(gè)性質(zhì),則稱其為準(zhǔn)循環(huán)再生碼:

(2)節(jié)點(diǎn)修復(fù)性質(zhì):假如節(jié)點(diǎn)n失效,存在一組{i1,i2,…,id}∈{1,2,…,n-1},使能夠通過［h1,h2,…,hd］計(jì)算得到,其中,hj(1≤j≤d)是c1,ij和c2,ij的線性組合。

3.2 準(zhǔn)循環(huán)再生碼的構(gòu)造

應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼的構(gòu)造過程如圖4所示,用S={1,2,…,n}代表存儲(chǔ)節(jié)點(diǎn)的集合,用向量υ=(υ1,υ2,…,υn)表示n個(gè)分塊的系統(tǒng)碼,用向量ρ=(ρ1,ρ2,…,ρn)表示相應(yīng)的n個(gè)冗余碼,稱ρ為冗余向量。

圖4 準(zhǔn)循環(huán)再生碼的構(gòu)造過程

由式(4)準(zhǔn)循環(huán)碼的構(gòu)造矩陣可知,節(jié)點(diǎn)中第2塊存儲(chǔ)的冗余碼與行向量c2,i相關(guān),又由于c2具有循環(huán)結(jié)構(gòu),定義c2如式(5)所示:

其中,λt∈GF(p),t=1,2,…,n,λn+i=λi=λi-n;c2,i為冗余系數(shù)向量,同時(shí)可以用ωt(c)表示c2,i的權(quán)重,因?yàn)橛笑豻(c2,1)=ωt(c2,2)=…=ωt(c2,n)。

根據(jù)式(6)定義冗余向量ρ:

編碼矩陣G可以表示為:

顯然,G是一個(gè)n×2n的矩陣,可以簡單地將G的第n+i列移到第i列右邊(1≤i≤n)構(gòu)建一個(gè)新的編碼矩陣G^:其中,G^與G共軛,G用于表示分布式存儲(chǔ)系統(tǒng)的存儲(chǔ)結(jié)構(gòu),而G^用于后文對(duì)其性質(zhì)的推導(dǎo)。

4 準(zhǔn)循環(huán)再生碼的性質(zhì)及節(jié)點(diǎn)修復(fù)

4.1 準(zhǔn)循環(huán)再生碼的性質(zhì)分析

令s={i1,i2,…,ik}∈S,且|s|=k。將矩陣G^的列序號(hào)表示成以下形式:{2×1-1,2×1,…,2i-1, 2i,…,2n-1,2n},假設(shè)M［s］是一個(gè)任取G^中k組2i-1列和2i(i∈s)列構(gòu)造的矩陣。

命題在一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼中,如果滿足式(9),任意k個(gè)節(jié)點(diǎn)都能完整恢復(fù)原數(shù)據(jù):

定理3 設(shè)Q(x1,x2,…,xn)∈F［x1,x2,…,xn］是一個(gè)多元多項(xiàng)式［8］,總度數(shù)為d0(總度數(shù)是加和表達(dá)式中所有項(xiàng)的最大度數(shù),其中一個(gè)項(xiàng)的度是指變量的冪指數(shù))。對(duì)有限集合S∈F,從中隨機(jī)選取n個(gè)互不相同的數(shù)r1,r2,…,rn,如果Q(x1,x2,…,xn)不為0,則:

通過命題和定理3可以得到以下推論:

定理4 如果存在［n,k,d］準(zhǔn)循環(huán)再生碼,其冗余系數(shù)向量c2,i=［λn-i+2,λn-i+3,…,λn,λ1,λ2,…,λn-i+1］且λ1≠0,則存在相應(yīng)的［n,k,d］準(zhǔn)循環(huán)再生碼,且有冗余向量c′2,i=［λn-i+2,λn-i+3,…,λn,0,λ2,…,λn-i+1］。

證明:不失一般性地,假設(shè)節(jié)點(diǎn)n失效。對(duì)任意的［n,k,d］準(zhǔn)循環(huán)再生碼,且其冗余系數(shù)向量c2,i為上述準(zhǔn)循環(huán)結(jié)構(gòu),令λ1=0得到相應(yīng)的c′2,i。對(duì)一個(gè)由c′2,i構(gòu)造的［n’=n,k’=k,d’=d］存儲(chǔ)碼,只需證明它是一個(gè)準(zhǔn)循環(huán)再生碼,就可證明定理成立。

(1)數(shù)據(jù)重建性質(zhì)的符合性驗(yàn)證

因?yàn)椋踤,k,d］存儲(chǔ)碼是一個(gè)準(zhǔn)循環(huán)再生碼,根據(jù)數(shù)據(jù)重建性質(zhì),有:

其中,i1,i2,…,ik∈{1,2,…,n}。值得注意的是,在c2,ij(j∈{1,2,…,k})修改后(令λ1=0),矩陣的秩并沒有改變,即:

這說明［n’,k’,d’］存儲(chǔ)碼滿足數(shù)據(jù)重建性質(zhì)。

(2)節(jié)點(diǎn)修復(fù)性質(zhì)的符合性驗(yàn)證

在一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼的節(jié)點(diǎn)修復(fù)過程中,可以不失一般性地假設(shè)存儲(chǔ)節(jié)點(diǎn)n失效,則編碼向量［en,c2,n］能夠通過下列公式修復(fù):

其中,l1,l2,…,ld∈{1,2,…,n-1};ρli,αli,βli∈GF(p),i∈{1,2,…,d}。根據(jù)式(11)可以得到:

根據(jù)式(12)可以得到:

根據(jù)式(13)、式(14)可以得出,［n′,k′,d′］存儲(chǔ)碼滿足節(jié)點(diǎn)修復(fù)性質(zhì),因此由［n,k,d］推導(dǎo)出的［n′,k′,d′］存儲(chǔ)碼是準(zhǔn)循環(huán)可再生碼,且ωt(c′)=ωt(c)+1。

4.2 數(shù)據(jù)修復(fù)與算法分析

根據(jù)定理4得知,如果存在λ1≠0的準(zhǔn)循環(huán)再生碼,則可以推出相應(yīng)λ1=0的準(zhǔn)循環(huán)再生碼。在研究性質(zhì)的過程中,均假設(shè)λ1=0。

假設(shè)λ1=0且λn=0,則編碼矩陣G為:

文獻(xiàn)［9-10］提出一種彈性的準(zhǔn)循環(huán)MSR (Quasi-cyclic Flexible MSR,QCFMSR)碼,它的構(gòu)造與本文構(gòu)造類似,只是在參數(shù)設(shè)置和定義上做了更嚴(yán)格的限定,是本文所描述的準(zhǔn)循環(huán)再生碼的一種特例。令β=1,i∈{2,3,…,k+1}時(shí),λi≠0;i∈{1,k+2,k+3,…,n}時(shí),λi=0;得到QCFMSR碼。文獻(xiàn)［10］給出一種節(jié)點(diǎn)修復(fù)算法,這種算法通過一定的擴(kuò)展可以用于本文所定義的編碼結(jié)構(gòu),但其修復(fù)帶寬較大,為n-1,且僅能容忍1個(gè)節(jié)點(diǎn)失效。

下文將討論本文所定義的準(zhǔn)循環(huán)再生碼在節(jié)點(diǎn)修復(fù)方面的性質(zhì),并給出改進(jìn)的節(jié)點(diǎn)修復(fù)算法。

定理5對(duì)一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼,如果有α=2,β=1,則:

為保持?jǐn)?shù)據(jù)重建性質(zhì),從任意k個(gè)節(jié)點(diǎn)傳輸?shù)木幋a系數(shù)向量必須線性獨(dú)立,所以有:

因此,可以得到:

定理6對(duì)一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼,冗余系數(shù)向量的權(quán)重ωt(c)滿足:

(1)因?yàn)棣裮=λn-m+2υ1+λn-m+3υ2+…+λ2n-m+1υn,用{1,2,…,n}標(biāo)記c2,m=［λn-m+2,λn-m+3,…,λ2n-m+1］中各項(xiàng)的位置坐標(biāo),選其中不為0的項(xiàng)的坐標(biāo){l1,l2,…,lw},其中,w≤n,則ωt(c)=w。同時(shí),ρm可以通過坐標(biāo)對(duì)應(yīng)的系統(tǒng)碼集{υl1,υl2,…,υlw}的線性組合計(jì)算得到。

(2)在除了節(jié)點(diǎn)m外的其他節(jié)點(diǎn)中找到一個(gè)c2,k,它坐標(biāo)位m上項(xiàng)的值不為0。類似步驟(1),取節(jié)點(diǎn)c2,k中所有不為0的項(xiàng)對(duì)應(yīng)的系統(tǒng)碼集(節(jié)點(diǎn)m除外)v={υk1,υk2,…,υkw-1},如果其還未被連接,則連接該節(jié)點(diǎn)并下載其第一分塊,則υm能夠通過v= {υk1,υk2,…,υkw-1}和c2,k的線性運(yùn)算得到,其中, |v|=ωt(c)-1。

通過以上步驟,能夠修復(fù)節(jié)點(diǎn)m。過程中消耗的帶寬為γ≤ωt(c)+(ωt(c)-1)+1=2ωt(c)。根

推論2 對(duì)一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼,冗余系數(shù)向量的權(quán)重ωt(c)滿足:

下文給出一種節(jié)點(diǎn)修復(fù)算法,該算法不僅可以精確修復(fù)失效節(jié)點(diǎn),而且能保證在最好情況下修復(fù)帶寬達(dá)到最小割下界。如果令i∈{k+1,k+2,…,n}時(shí),λi≠ 0;且i∈{1,2,…,k}時(shí),λi=0;當(dāng)k為奇數(shù)時(shí),采用修復(fù)算法可以達(dá)到修復(fù)帶寬的下界k+1。

算法當(dāng)λ1=0且λn=0時(shí)的準(zhǔn)循環(huán)再生碼修復(fù)算法

輸入編碼矩陣和失效節(jié)點(diǎn)標(biāo)號(hào)i

輸出節(jié)點(diǎn)i存儲(chǔ)的2塊數(shù)據(jù)

(1)在c2,i中找到所有值非零的項(xiàng),根據(jù)標(biāo)記坐標(biāo){1,2,…,n}對(duì)應(yīng)得到非零項(xiàng)的坐標(biāo)集{l1,l2,…,lw},并連接S中相應(yīng)位置的節(jié)點(diǎn),下載其第一分塊,根據(jù)冗余系數(shù)向量c2,i可以通過線性運(yùn)算得到節(jié)點(diǎn)i的第二分塊。

(2)在所有c2,i,j≠i中找到一個(gè)其位置i的值非零的冗余系數(shù)向量c2,j,尋找方法是將c2,i反置,從節(jié)點(diǎn)i+1處為起始位一一對(duì)應(yīng),第1個(gè)非零位對(duì)應(yīng)的節(jié)點(diǎn)即所求節(jié)點(diǎn)。然后,下載節(jié)點(diǎn)j的第二分塊,并對(duì)節(jié)點(diǎn)j進(jìn)行與第(1)步類似的操作,取節(jié)點(diǎn)c2,j中所有不為0的項(xiàng)對(duì)應(yīng)的系統(tǒng)碼集(節(jié)點(diǎn)m除外)v= {υj1,υj2,…,υjw-1},如果對(duì)應(yīng)的節(jié)點(diǎn)未被連接,則連接該節(jié)點(diǎn)并下載其第一分塊,則vj能夠通過v={υj1,υj2,…,υjw-1}和c2,j的線性運(yùn)算得到。

算法的第(1)步傳輸?shù)臄?shù)據(jù)帶寬為w=ωt(c),第(2)步傳輸?shù)臄?shù)據(jù)帶寬為|v|+1≤(ωt(c)-1)+ 1=ωt(c)。因此一次修復(fù)過程消耗的帶寬為γ≤2ωt(c)。

推論3 對(duì)一個(gè)［n,k,d］準(zhǔn)循環(huán)再生碼,使用修復(fù)算法進(jìn)行節(jié)點(diǎn)修復(fù)時(shí),修復(fù)帶寬γ滿足:k+1≤γ≤n-1。

根據(jù)該修復(fù)性質(zhì),可以給出一種準(zhǔn)循環(huán)MSR (QCMSR)碼的構(gòu)造方法,使α=2,β=1,令?={j1,j2,…,jk}?{2,3,…,n},其中,j1,j2,…,jk是連續(xù)的自然數(shù),且j∈J時(shí),λi≠0;j∈{2,3,…,n}?時(shí),λi= 0;得到QCMSR碼,具有以下性質(zhì):

(1)當(dāng)d=k+1時(shí),根據(jù)MSR碼滿足的條件,即式(2),有α=d-k+1,從而得到d=k+1;

(2)當(dāng)B=n=2k時(shí),根據(jù)式(2)有B=k(d-k+ 1),將性質(zhì)(1)代入等式即可得到。

下面給出一個(gè)采用修復(fù)算法進(jìn)行節(jié)點(diǎn)修復(fù)并達(dá)到帶寬最小割下界的示例,一個(gè)［6,3,4］QCMSR碼,冗余系數(shù)向量c2,1=(0,0,0,1,1,1),根據(jù)循環(huán)結(jié)構(gòu)可以得到其他節(jié)點(diǎn)的冗余系數(shù)向量,假設(shè)第2個(gè)節(jié)點(diǎn)S2失效,則修復(fù)過程如圖5所示。

圖5 算法對(duì)[6,3,4]QCMSR碼失效節(jié)點(diǎn)S2的修復(fù)情況

在圖5中,用1和2表示修復(fù)步驟(1)、步驟(2),點(diǎn)線箭頭指明了反置后的冗余系數(shù)向量c2,2=(1,0,0,0,1,1)的第1個(gè)非零位所匹配到的節(jié)點(diǎn),計(jì)算過程如修復(fù)算法所述。可以看出,步驟(1)、步驟(2)共消耗的帶寬為γ=k+1=4,參與修復(fù)的節(jié)點(diǎn)只進(jìn)行數(shù)據(jù)傳輸,然后在新節(jié)點(diǎn)通過2次線性運(yùn)算最終完成對(duì)節(jié)點(diǎn)的精確修復(fù)。修復(fù)算法具有“傳遞并修復(fù)”的性質(zhì),即節(jié)點(diǎn)中不需要對(duì)其2個(gè)分塊進(jìn)行線性運(yùn)算,運(yùn)算復(fù)雜性較低。

5 結(jié)束語

本文將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于分布式存儲(chǔ)系統(tǒng)的編碼方案中,利用中間節(jié)點(diǎn)編碼優(yōu)化修復(fù)過程的帶寬消耗。在研究再生碼及不同數(shù)據(jù)模型,并與傳統(tǒng)糾錯(cuò)碼的性能進(jìn)行比較后,提出一種適用于分布式存儲(chǔ)系統(tǒng)的新型準(zhǔn)循環(huán)再生碼編碼方案,闡述了其定義和構(gòu)造方法,并對(duì)其構(gòu)造條件和性質(zhì)進(jìn)行分析和證明。同時(shí),針對(duì)該編碼方案的節(jié)點(diǎn)修復(fù)性質(zhì)進(jìn)行分析,給出一種改進(jìn)的節(jié)點(diǎn)修復(fù)算法,并證明算法修復(fù)帶寬在最好情況能夠達(dá)到最小割下界,在最壞情況下也優(yōu)于MDS碼,并通過對(duì)參數(shù)的設(shè)置給出一種準(zhǔn)循環(huán)MSR碼構(gòu)造方案,不僅存儲(chǔ)消耗小而且能夠達(dá)到修復(fù)帶寬的最小割下界。

在接下來的工作中將進(jìn)一步優(yōu)化該修復(fù)算法,以及討論在α＞2的情況下第2個(gè)分塊為循環(huán)結(jié)構(gòu)的準(zhǔn)循環(huán)結(jié)構(gòu)再生碼的性質(zhì)。因?yàn)樾迯?fù)算法在一些情況下并不是最優(yōu)化的修復(fù)策略,即修復(fù)一個(gè)節(jié)點(diǎn)所消耗的帶寬并不一定達(dá)到最小帶寬,所以可以針對(duì)算法繼續(xù)進(jìn)行優(yōu)化,使得當(dāng)編碼結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)的第2個(gè)分塊都用循環(huán)結(jié)構(gòu)時(shí),修復(fù)帶寬盡可能為最小［11］。此外,本文只討論了α=2下的情況,未討

論此參數(shù)推廣到更大范圍的情況。現(xiàn)有研究結(jié)果表明［12-13］,當(dāng)α=3且k≥4時(shí),使每個(gè)節(jié)點(diǎn)的第2個(gè)分塊用循環(huán)結(jié)構(gòu)的構(gòu)造方式不存在精確修復(fù)。對(duì)于α推廣到更大范圍時(shí)準(zhǔn)循環(huán)再生碼的節(jié)點(diǎn)修復(fù)還沒有相關(guān)結(jié)論,是下一步需要深入研究的問題。

［1]Dimakis A G,Ramchandran K,Wu Y,et al.A Survey onNetworkCodesforDistributedStorage［J］.Proceedings of the IEEE,2011,99(3):476-489.

［2]Dimakis A G,Godfrey P G,Wu Y,et al.Network Coding for Distributed Storage Systems［J］.IEEE Transactions on Information Theory,2010,56(9): 4539-4551.

［3]盧開澄,盧華明.圖論及其應(yīng)用［M］.北京:清華大學(xué)出版社,2005.

［4]Wu Y,DimakisA G,RamchandranK.Deterministic Regenerating Codes for Distributed Storage［C］//Proceedings of the 45th Annual Allenton Conference on Communication,Control,and Computing.Washington D.C., USA:IEEE Press,2007:2276-2280.

［5]Wu Y,Dimakis A G.Reducing Repair Traffic for Erasure Coding-based Storage via Interference Alignment［C］// Proceedings of IEEE International Symposium on Information Theory.Washington D.C.,USA:IEEE Press,2009: 2267-2280.

［6]Suh C,Ramchandran K.Exact Regeneration Codes for DistributedStorageRepairUsingInterferenceAlignment［C］//Proceedings of IEEE International Symposium on Information Theory Proceedings.Washington D.C., USA:IEEE Press,2010.

［7]Shah N B,Rashmi K V,Kumar P V,et al.Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions［J］.IEEE Transactions on Information Theory,2012,58(4):2134-2158.

［8]Yeung R W,Li Y R,Cai N,et al.Network Coding Theory［M］.Boston,USA:Now Publishers Inc.,2006.

［9]Gaston B,Pujol J,Villanueva M.Quasi-cyclic Minimum StorageRegeneratingCodesforDistributedData Compression［C］//Proceedings of Data Compression Conference.Washington D.C.,USA:IEEE Press,2011: 33-42.

［10]Gaston B,Pujol J,Villanueva M.Quasi-cyclic Flexible Regenerating Codes［EB/OL］.(2012-12-13).http:// arxiv.org/licenses/nonexclusive-distrib/1.0/.

［11]Kan Haibin,Shen Hong.Lower Bounds of the Minimal Delays of Complex Orthogonal Designs with Maximal Rates［J］.IEEE Transactions on Communications,2006, 54(3):383-388.

［12]Kan Haibin,Shen Hong.A Relation Between the Characteristic Generators of a Linear Code and Its Dual［J］.IEEE Transactions on Information Theory,2005,51(3): 1199-1202.

［13]Yuan C,Kan Haibin.A Characterization of Solvability for a Kind of Networks［J］.Science China Information Sciences,2012,55(4):747-754.

編輯 陸燕菲

Construction Scheme of Quasi-cyclic Regenerating Code for Distributed Storage System

LI Chenhui
(Shanghai Key Laboratory of Intelligent Information Processing,Fudan University,Shanghai 200433,China)

Traditional erasure coding scheme is universally adopted to enhance the fault tolerance,which produces too much data transmission in a repair process.A new construction scheme of quasi-cyclic Minimum Storage Regenerating (MSR)regenerating codes is proposed in this paper.According to its property of exact repair about the weight of encoding vector and the bound of repair bandwidth,it proposes an improved node repairing algorithm which optimizes the repair bandwidth to the cut-set bound,and it is also better than Maximum Distance Separable(MDS)codes in the worst case.Experimental result shows that the construction scheme not only can save the storage space but also has simple structure,low operation cost and low repair bandwidth,etc.

network coding;Distributed Storage System(DSS);quasi-cyclic;regenerating code;Minimum Storage Regenerating(MSR)code;data recovery

李晨卉.應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造方案［J］.計(jì)算機(jī)工程,2015,41(3):81-87.

英文引用格式:Li Chenhui.Construction Scheme of Quasi-cyclic Regenerating Code for Distributed Storage System［J］.Computer Engineering,2015,41(3):81-87.

1000-3428(2015)03-0081-07

A

TP393

10.3969/j.issn.1000-3428.2015.03.015

上海市科委基礎(chǔ)研究基金資助重點(diǎn)項(xiàng)目(12JC1401400)。

李晨卉(1989-),女,碩士研究生,主研方向:網(wǎng)絡(luò)編碼,信息安全,密碼學(xué)。

2014-04-18

:2014-05-16E-mail:chenhuili11@fudan.edu.cn