應用于分布式存儲系統的準循環再生碼構造方案

李晨卉

(復旦大學上海市智能信息處理重點實驗室,上海200433)

應用于分布式存儲系統的準循環再生碼構造方案

李晨卉

(復旦大學上海市智能信息處理重點實驗室,上海200433)

傳統糾錯碼編碼方案能夠提高系統容錯能力,但在數據修復時會占用大量帶寬。為此,基于循環結構,構造一種面向分布式存儲系統的準循環最小存儲再生碼。根據該準循環再生碼的冗余系數向量權重和修復帶寬邊界,設計一種改進的節點修復算法,證明其修復帶寬在最好情況能達到最小割下界,在最壞情況下也優于最大距離可分碼的修復帶寬。實驗結果表明,該再碼構造方案不僅節省存儲空間,而且具有構造簡單、運算代價低和修復帶寬小等特點。

網絡編碼;分布式存儲系統;準循環;再生碼;最小存儲再生碼;數據修復

1 概述

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

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

碼策略在數據修復時會產生很大的帶寬消耗和計算負載。

針對該問題,文獻［1］將網絡編碼技術與分布式存儲碼技術相結合,提出一種新型再生碼編碼方案。利用網絡編碼技術,再生碼策略能夠在保證系統容錯性能(與MDS碼具有相同的容錯性能)的同時,優化數據修復過程的帶寬消耗。然而,網絡編碼技術是一種使網絡中的中繼節點具有編碼能力以達到信息論中多播網絡的理論最大流界的通信領域新概念,以此為基礎改進的再生碼在數據修復時通常具有復雜的節點內運算,以及為達到低修復帶寬而增加的存儲消耗。為此,本文提出一種適用于分布式存儲系統的新型準循環再生碼構造方案。

2 數據修復與再生碼

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

圖1 糾錯碼原理

本文稱這種由任意k個分組完整重建原數據的性質為MDS性質。當存儲節點失效后,MDS碼的節點修復策略是先連接有效節點中的任意k個節點,進行數據重建,然后再根據編碼規則重新生成失效節點的數據。這種方案為修復一個大小為B/k的數據分組同時傳輸大小為B的數據量,傳輸帶寬消耗遠大于節點存儲的數據量,尤其是在節點分布較分散的DSS中,節點修復所消耗的額外網絡帶寬更加明顯。

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

圖2 精確修復[4,2]MDS碼的節點4

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

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

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

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

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

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

MBR碼滿足以下性質:

功能性修復雖然對系統修復操作的要求更低,修復實現的難度更小,但存在3點不足:(1)節點修復后需要更新系統的數據重建和修復算法;(2)功能性修復的實現需要很大的有限域來滿足動態增大的有向無環圖,導致編解碼的計算復雜度較高;(3)動態的修復和解碼過程容易發生信息泄露,因此安全性較差。所以,功能性修復具有局限性。

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

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

定理2 在不使用符號擴展且b=1的情況下,達到割集邊界的線性精確修復MSR碼在d＜2k-3時不存在［7］。

3 應用于分布式系統的準循環再生碼構造

準循環再生碼是一種基于循環結構的線性編碼,構造簡單,且通過預定義的節點修復系數向量和修復算法大大降低了修復產生的運算代價。

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

3.1 準循環再生碼的定義

在準循環再生碼中,定義α=2,即每個存儲節點包含2個分塊,并規定每個節點的第1個分塊存儲原數據(即系統碼),第2個分塊存儲冗余碼(用于數據修復和可靠性保護)。由此可知,在準循環再生碼中,有B=n。由于準循環再生碼也是一種線性網絡編碼,因此其第2個分塊的冗余數據均為系統碼的線性組合,并且其冗余系數向量滿足循環結構。

用G表示一個［n,k,d］準循環再生碼的編碼矩陣,則G滿足如下公式:

存儲系統能夠并行地提取數據且不需要譯碼。除非特殊聲明,本文中。

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

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

3.2 準循環再生碼的構造

應用于分布式存儲系統的準循環再生碼的構造過程如圖4所示,用S={1,2,…,n}代表存儲節點的集合,用向量υ=(υ1,υ2,…,υn)表示n個分塊的系統碼,用向量ρ=(ρ1,ρ2,…,ρn)表示相應的n個冗余碼,稱ρ為冗余向量。

圖4 準循環再生碼的構造過程

由式(4)準循環碼的構造矩陣可知,節點中第2塊存儲的冗余碼與行向量c2,i相關,又由于c2具有循環結構,定義c2如式(5)所示:

其中,λt∈GF(p),t=1,2,…,n,λn+i=λi=λi-n;c2,i為冗余系數向量,同時可以用ωt(c)表示c2,i的權重,因為有ωt(c2,1)=ωt(c2,2)=…=ωt(c2,n)。

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

編碼矩陣G可以表示為:

顯然,G是一個n×2n的矩陣,可以簡單地將G的第n+i列移到第i列右邊(1≤i≤n)構建一個新的編碼矩陣G^:其中,G^與G共軛,G用于表示分布式存儲系統的存儲結構,而G^用于后文對其性質的推導。

4 準循環再生碼的性質及節點修復

4.1 準循環再生碼的性質分析

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

命題在一個［n,k,d］準循環再生碼中,如果滿足式(9),任意k個節點都能完整恢復原數據:

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

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

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

證明:不失一般性地,假設節點n失效。對任意的［n,k,d］準循環再生碼,且其冗余系數向量c2,i為上述準循環結構,令λ1=0得到相應的c′2,i。對一個由c′2,i構造的［n’=n,k’=k,d’=d］存儲碼,只需證明它是一個準循環再生碼,就可證明定理成立。

(1)數據重建性質的符合性驗證

因為［n,k,d］存儲碼是一個準循環再生碼,根據數據重建性質,有:

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

這說明［n’,k’,d’］存儲碼滿足數據重建性質。

(2)節點修復性質的符合性驗證

在一個［n,k,d］準循環再生碼的節點修復過程中,可以不失一般性地假設存儲節點n失效,則編碼向量［en,c2,n］能夠通過下列公式修復:

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

根據式(12)可以得到:

根據式(13)、式(14)可以得出,［n′,k′,d′］存儲碼滿足節點修復性質,因此由［n,k,d］推導出的［n′,k′,d′］存儲碼是準循環可再生碼,且ωt(c′)=ωt(c)+1。

4.2 數據修復與算法分析

根據定理4得知,如果存在λ1≠0的準循環再生碼,則可以推出相應λ1=0的準循環再生碼。在研究性質的過程中,均假設λ1=0。

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

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

下文將討論本文所定義的準循環再生碼在節點修復方面的性質,并給出改進的節點修復算法。

定理5對一個［n,k,d］準循環再生碼,如果有α=2,β=1,則:

為保持數據重建性質,從任意k個節點傳輸的編碼系數向量必須線性獨立,所以有:

因此,可以得到:

定理6對一個［n,k,d］準循環再生碼,冗余系數向量的權重ωt(c)滿足:

(1)因為ρm=λn-m+2υ1+λn-m+3υ2+…+λ2n-m+1υn,用{1,2,…,n}標記c2,m=［λn-m+2,λn-m+3,…,λ2n-m+1］中各項的位置坐標,選其中不為0的項的坐標{l1,l2,…,lw},其中,w≤n,則ωt(c)=w。同時,ρm可以通過坐標對應的系統碼集{υl1,υl2,…,υlw}的線性組合計算得到。

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

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

推論2 對一個［n,k,d］準循環再生碼,冗余系數向量的權重ωt(c)滿足:

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

算法當λ1=0且λn=0時的準循環再生碼修復算法

輸入編碼矩陣和失效節點標號i

輸出節點i存儲的2塊數據

(1)在c2,i中找到所有值非零的項,根據標記坐標{1,2,…,n}對應得到非零項的坐標集{l1,l2,…,lw},并連接S中相應位置的節點,下載其第一分塊,根據冗余系數向量c2,i可以通過線性運算得到節點i的第二分塊。

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

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

推論3 對一個［n,k,d］準循環再生碼,使用修復算法進行節點修復時,修復帶寬γ滿足:k+1≤γ≤n-1。

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

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

(2)當B=n=2k時,根據式(2)有B=k(d-k+ 1),將性質(1)代入等式即可得到。

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

圖5 算法對[6,3,4]QCMSR碼失效節點S2的修復情況

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

5 結束語

本文將網絡編碼技術應用于分布式存儲系統的編碼方案中,利用中間節點編碼優化修復過程的帶寬消耗。在研究再生碼及不同數據模型,并與傳統糾錯碼的性能進行比較后,提出一種適用于分布式存儲系統的新型準循環再生碼編碼方案,闡述了其定義和構造方法,并對其構造條件和性質進行分析和證明。同時,針對該編碼方案的節點修復性質進行分析,給出一種改進的節點修復算法,并證明算法修復帶寬在最好情況能夠達到最小割下界,在最壞情況下也優于MDS碼,并通過對參數的設置給出一種準循環MSR碼構造方案,不僅存儲消耗小而且能夠達到修復帶寬的最小割下界。

在接下來的工作中將進一步優化該修復算法,以及討論在α＞2的情況下第2個分塊為循環結構的準循環結構再生碼的性質。因為修復算法在一些情況下并不是最優化的修復策略,即修復一個節點所消耗的帶寬并不一定達到最小帶寬,所以可以針對算法繼續進行優化,使得當編碼結構中每個節點的第2個分塊都用循環結構時,修復帶寬盡可能為最?。?1］。此外,本文只討論了α=2下的情況,未討

論此參數推廣到更大范圍的情況?，F有研究結果表明［12-13］,當α=3且k≥4時,使每個節點的第2個分塊用循環結構的構造方式不存在精確修復。對于α推廣到更大范圍時準循環再生碼的節點修復還沒有相關結論,是下一步需要深入研究的問題。

［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]盧開澄,盧華明.圖論及其應用［M］.北京:清華大學出版社,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

李晨卉.應用于分布式存儲系統的準循環再生碼構造方案［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

上海市科委基礎研究基金資助重點項目(12JC1401400)。

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

2014-04-18

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