沈克勤,孫 偉,何亞錦,張鑫楠

(長安大學 信息工程學院,西安 710064)

隨著大數(shù)據(jù)時代的到來,數(shù)據(jù)資源呈現(xiàn)出快速增長的趨勢,數(shù)據(jù)的存儲容量也隨之不斷增加.傳統(tǒng)的數(shù)據(jù)存儲系統(tǒng)已經不能適應當前海量數(shù)據(jù)存儲,分布式存儲系統(tǒng)逐漸成為主流存儲方式.通過將海量數(shù)據(jù)分散的存儲在多臺互相獨立物理設備上,分布式存儲系統(tǒng)不僅很好的分擔了存儲負載,而且成本低廉,可擴展性能好,但是分布式存儲系統(tǒng)中的這些物理存儲設備容易發(fā)生故障,可造成大量數(shù)據(jù)丟失.因此,如何提高數(shù)據(jù)存儲的可靠性就成為了分布式存儲亟需解決的問題[1-3].

為保證數(shù)據(jù)存儲時的高可靠性和高可用性,傳統(tǒng)的分布式存儲系統(tǒng)中生成冗余數(shù)據(jù)的策略通常有“復制”和“糾刪碼”策略[4,5].谷歌文件系統(tǒng)和Hadoop 系統(tǒng)運用了三副本復制策略,將原始數(shù)據(jù)塊復制成三個副本然后存儲在系統(tǒng)中來保證存儲的可靠性,這樣會導致存儲開銷過大；為了減小存儲開銷,在實際系統(tǒng)中引入糾刪碼的冗余策略,但該策略在修復故障節(jié)點時會帶來巨大的帶寬開銷.針對上述問題,Dimakis 等將網(wǎng)絡編碼的思想運用到分布式存儲中,提出了再生碼的概念[6],有效減少了存儲開銷和修復帶寬開銷.目前對再生碼的研究表明,主要表現(xiàn)在存儲和帶寬均衡曲線上的兩個極值點,一個極值點對應最小存儲再生碼

MSRC (Minimum Storage Regenerating Code),另一個極值點對應最小帶寬再生碼MBRC (Minimum Bandwidth Regenerating Code).文獻[7-9]給出了一些好的再生碼的構造方法.

但是,再生碼的缺陷在于,在進行故障節(jié)點修復時,需要大量基于有限域上的計算,計算復雜度高,修復局部性復雜.為解決上述問題,EI Rouayheb 和Ram chan dram 在MBRC 的研究基礎上提出了一種新型碼——部分重復碼(Fractional Repetition Codes,FRC)[10],該碼可以進行精確無編碼有效的修復.一般意義上的FRC由兩部分組成：外部的編碼是最大距離可分碼 (Maximum Distance Sparable,MDS)和內部是重復碼,該碼修復故障節(jié)點無需任何編碼操作,可以很好地降低故障修復時所需的帶寬和磁盤I/O 開銷.目前對FRC 的研究主要有基于組合設計構造的FRC[11],基于圖構造的FRC[12],基于偏序集構造的FRC[13],基于二分圖構造的局部修復的FRC[14],這些構造算法復雜,并且大多只能構造同構的FRC,不能得到異構的FRC.

為此,本文提出了兩種構造方法,一種是基于矩陣變換構造的異構FRC,該構造用于構造重復度為2,節(jié)點存儲容量異構的FRC,該方法計算復雜度低,只需進行簡單的異或運算就可得到節(jié)點存儲容量異構的FRC,相比現(xiàn)有的運用正則圖構造的同構FRC,該構造在節(jié)點存儲容量上更符合現(xiàn)實的存儲系統(tǒng)；另外,本文還提出了運用可調節(jié)環(huán)構造的FRC,該方法根據(jù)一定的存放規(guī)則能得到不同重復度的FRC,主要構造重復度 的情況,因為大部分對部分重復碼的研究中重復度都是2 或3,同時該方法也可靈活的調節(jié)節(jié)點存儲容量,即可得到節(jié)點存儲容量同構的FRC 也可得到節(jié)點存儲容量異構的FRC,可大范圍選擇參數(shù),構造結構簡單直觀.同時本文上最大的應用價值在于能無編碼的修復節(jié)點存儲容量異構的分布式存儲系統(tǒng)中的故障節(jié)點,應用前景好,具有很好的實用價值.

1 基礎知識

目前研究表明,對MDS 碼的研究已經十分成熟了,各種參數(shù)的MDS 碼都可得到.所以對部分重復碼的研究主要體現(xiàn)在內部重復碼的構造上.FRC 實際上是復制倍數(shù)為ρ 的 θ 個數(shù)據(jù)塊在節(jié)點上的一種排列組合,復制生成的數(shù)據(jù)塊都分別存儲在不同的系統(tǒng)節(jié)點上.內部的重復碼可用 (n,k,d,θ,ρ,α)FRC 表示,其中n表示存儲系統(tǒng)的節(jié)點數(shù),θ表示存儲在節(jié)點中的數(shù)據(jù)塊個數(shù),ρ表示數(shù)據(jù)塊的復制次數(shù),α表示每個節(jié)點的存儲容量,d表示修復一個失效節(jié)點需連接的存活節(jié)點數(shù),一般認為α=d.數(shù)學上的定義如下：

定義1[15].參數(shù)為(n,k,d)分布式存儲系統(tǒng)的部分重復碼C=(M,U),復制倍數(shù)為ρ,是指特定的n個子集的集合U={U1,U2,···,Un},每個子集的元素均來自于符號集M={1,2,···,θ}.并且節(jié)點存儲容量同構的FRC 還需要滿足下面條件：

1)每個子集的大小均為d；

2)M中的每一個元素都屬于U中的子集,每個子集數(shù)大小為ρ；

3)同構的FRC 滿足nα=ρθ.

定義2[16].(d1,d2,···,dm)正 則圖G(V,E)是一個無向圖,其中 |V|=n,V1,V2,···,Vm?V,并且Vi∩Vj=? .頂點Vi的度為di(1 ≤i≤m),若G(V,E)所有頂點的度都等于d,則該G(V,E)叫 作d-正則圖,若G(V,E)頂點的度不相等分別為d1,d2,···,dm,則稱該G(V,E)為(d1,d2,···,dm)-正則圖,也叫部分正則圖.

2 基于矩陣變換的異構部分重復碼構造

本節(jié)運用矩陣變換的思想,結合部分正則圖提出了一種新的節(jié)點存儲容量異構的部分重復碼,相比文獻[10]和文獻[16]中運用正則圖和部分正則圖構造的部分重復碼,本構造能得到節(jié)點存儲容量更加多樣的FRC,和傳統(tǒng)RS 碼相比,在修復單節(jié)點故障時,修復局部性更好,修復復雜度更優(yōu),無需任何編碼操作,計算復雜低.具體構造算法如下：

該構造主要用于構造節(jié)點存儲容量異構的FRC,適用于分布式存儲系統(tǒng)節(jié)點數(shù)n為奇數(shù)的情況,且構造的FRC 中數(shù)據(jù)塊的重復度ρ 等于2；具體步驟如下：

步驟1.定義一個n階的二進制循環(huán)置換矩陣Cn(d?1),其中n代 表節(jié)點數(shù),d?1表示每個節(jié)點存儲容量同時也表示矩陣中每一行1 的個數(shù),且需滿足的條件為d＞3,d為奇數(shù)；同時我們設定Cn(d?1)矩陣的第一行在數(shù)學上滿足的表達式為：c(t)=t+t2+···+t(d?1)/2+tn?(d?1)/2+···+tn?1.

在矩陣的第一行確定后,矩陣后面的每一行依次向右移動一位,共移動n?1次,最后生成Cn(d?1)矩陣；

步驟2.為得到節(jié)點存儲容量異構的FRC,在步驟1 的基礎上引入矩陣Sn去 調節(jié)步驟1 中的Cn(d?1)矩陣,Sn矩 陣生成方法為：在(n?1)階副對角線都為1,其他元素全為0 的方陣后面加一行0 和一列0,生成n×n階的Sn矩陣；

步驟3.將步驟1 中的矩陣Cn(d?1)和步驟2 中的矩陣Sn進 行模2 運算,得到二進制矩陣P=Cn(d?1)+Sn(mod 2),矩陣P和部分正則圖存在相關聯(lián)的關系,用P=(mij)n×n,1 ≤i,j≤n表示部分正則圖的關聯(lián)矩陣,關聯(lián)規(guī)則如下：

由上面關系可知,部分正則圖的每一個頂點的度和矩陣的每一行中1 的個數(shù)是相等的,經過算法的驗證,發(fā)現(xiàn)矩陣P的不同行中會出現(xiàn)有d,d?1,d?2個1 的情況,因此對應的部分正則圖的度有d,d?1,d?2三種情況,記作(d,d?1,d?2)-部分正則圖,也就對應著構造的FRC 的節(jié)點存儲容量有d,d?1,d?2三種情況.

對構造的FRC 的故障節(jié)點修復進行分析可知,因為該FRC 的重復度 ρ=2,所以本構造能容忍單個節(jié)點出現(xiàn)故障,又由于異構FRC 的節(jié)點容量有d,d?1,d?2三種情況,所以分以下3 種情況討論：

1)若存儲容量為d的節(jié)點出現(xiàn)故障,那么只需要從另外的d個節(jié)點分別下載一個數(shù)據(jù)塊即可直接修復；

2)若存儲容量為d?1的節(jié)點出現(xiàn)故障,那么只需要從另外的d?1個節(jié)點分別下載一個數(shù)據(jù)塊即可直接修復；

3)若存儲容量為d?2的節(jié)點出現(xiàn)故障,那么只需要從另外的d?2個節(jié)點分別下載一個數(shù)據(jù)塊即可直接修復.

當系統(tǒng)中出現(xiàn)故障節(jié)點,只需直接從其他存活的節(jié)點下載數(shù)據(jù)塊修復,修復選擇性高,無編碼操作,計算復雜度低.根據(jù)上述構造算法給出如下具體實例.

例1.給定n=7,d=5,根據(jù)構造方法步驟1 得到矩陣C7(4),其中C7(4)是一個7 ×7的二進制矩陣且第一行表示為c(t)=t+t2+t5+t6,第一行確定后,后面的每一行依次向右移動一位,最后生成C7(4)矩陣,如下所示：

進一步運用矩陣S7調節(jié)矩陣C7(4),S7矩陣是在6 階副對角線都為1,其他元素全為0 的矩陣后面加一行0 和一列0 生成的,如下所示：

得到S7矩 陣后,通過P=C7(4)+S7(mod 2)算得矩陣P,如下所示：

根據(jù)矩陣P能得到 (3,4,5)-部分正則圖,即部分正則圖的度有5,4,3 這三種情況,也就對應節(jié)點存儲容量有5,4,3 三種情況,如圖1所示.

若節(jié)點U1發(fā)生故障,需連接U2,U3,U7這3 個節(jié)點進行修復,即從U2,U3,U7這3 個節(jié)點下載1,6,7數(shù)據(jù)塊進行修復,修復過程如圖2所示.同理,其他節(jié)點發(fā)生故障也可用相同的方法進行修復.

圖1 (3,4,5)-部分正則圖和對應FRC 數(shù)據(jù)塊存儲結構圖

圖2 故障節(jié)點修復圖

3 基于可調節(jié)環(huán)的FRC 構造

本節(jié)運用可調節(jié)環(huán)結構構造FRC,根據(jù)一定的存放規(guī)則去調節(jié)重復度的大小和節(jié)點存儲容量,規(guī)則是將數(shù)據(jù)元素放入相鄰的節(jié)點所在環(huán)的邊之間,規(guī)定當每一個數(shù)據(jù)塊依次放在兩個相鄰的節(jié)點之間時,此時FRC 的重復度為 ρ=2；當每一個數(shù)據(jù)塊都放在3 個相鄰的節(jié)點之間,此時FRC 的重復度為 ρ=3,同理可用相同的存放規(guī)則去調節(jié)重復度.由同構FRC 參數(shù)滿足的條件nα=ρθ可知,當給定的參數(shù)滿足該條件時,可得到同構的FRC,若該等式不成立,則可用可調節(jié)環(huán)構造節(jié)點存儲容量異構的FRC,根據(jù)已有的對FRC 的研究中發(fā)現(xiàn),大部分只考慮重復度為2,3 的情況,具體構造算法如下.

3.1 用可調節(jié)環(huán)去構造重復度ρ=2的FRC

假設系統(tǒng)中節(jié)點用U1,U2,···,Un表示,節(jié)點中的數(shù)據(jù)塊用θ 表示,且[θ]={1,2,···,θ},將數(shù)據(jù)塊按一定規(guī)則放入環(huán)中,即從節(jié)點U1開 始,將數(shù)據(jù)塊1 放在U1和U2所在的邊上,將數(shù)據(jù)塊2 放在U2和U3所在的邊上,數(shù)據(jù)塊3 放到U3和U4所 在邊上,以此類推,直到將θ 個數(shù)據(jù)塊放完為止.

根據(jù)上述算法可以得到重復度 ρ=2的FRC.因為每一個數(shù)據(jù)塊存在于相鄰的2 個節(jié)點所在環(huán)的邊上,每個數(shù)據(jù)塊都會被兩個節(jié)點所共有,即得到的是重復度 ρ=2 的FRC.若所給參數(shù)滿足nα=ρθ,用可調節(jié)環(huán)可以構造節(jié)點存儲容量同構的FRC,否則用可調節(jié)環(huán)可以構造節(jié)點存儲容量異構的FRC.具體實例如下,其中,例2 給定的是用可調節(jié)環(huán)構造的重復度 ρ=2的同構FRC,例3 給定的是用可調節(jié)環(huán)構造的重復度ρ=2的異構FRC.

例2.給定n=6,θ=12,用可調節(jié)環(huán)去構造FRC,環(huán)結構和節(jié)點存儲結構,如圖3所示.

圖3 可調節(jié)環(huán)結構和節(jié)點存儲結構

由節(jié)點存儲結構圖可知該FRC 滿足nα=ρθ,是同構的FRC,重復度ρ=2,節(jié)點儲存容量為α=4,若節(jié)點U1故障,需要從U2下載數(shù)塊1,7,從U6下載數(shù)據(jù)塊6 和12 修復U1,其他節(jié)點故障也可用相同的修復方式進行修復,無需編碼操作.

例3.給定n=8,θ=21,用可調節(jié)環(huán)去構造FRC,環(huán)結構和節(jié)點存儲結構圖,如圖4.

圖4 可調節(jié)環(huán)結構和節(jié)點存儲結構圖

由節(jié)點存儲結構圖可知,該FRC 不滿足nα=ρθ,是異構的FRC,且重復度 ρ=2,節(jié)點存儲容量有4,5,6 三種情況,可修復單節(jié)點故障,修復方式是直接從存活節(jié)點下載相應數(shù)據(jù)塊進行修復.

3.2 用可調節(jié)環(huán)去構造重復度ρ=3的FRC

若分布式存儲系統(tǒng)的節(jié)點用U1,U2,···,Un表示,θ表示存儲在節(jié)點中的數(shù)據(jù)塊,且[θ]={1,2,···,θ},將θ個數(shù)據(jù)塊按一定的規(guī)則放入環(huán)中,即從U1節(jié)點開始,將數(shù)據(jù)塊1 分別放到U1U2和U2U3所在的邊上,將數(shù)據(jù)塊2 分別放到U2U3和U3U4所在邊上,數(shù)據(jù)塊3 放到U3U4和U4U5所 在邊上,以此類推,直到將θ 個數(shù)據(jù)塊放完為止.

根據(jù)上述算法可得到重復度ρ=3的FRC.因為每一個數(shù)據(jù)塊存在于相鄰的3 個節(jié)點所在的環(huán)之間,即每個數(shù)據(jù)塊都會被3 個節(jié)點共有,則得到的是重復度ρ=3的FRC.若所給參數(shù)滿足nα=ρθ,用可調節(jié)環(huán)可以構造節(jié)點存儲容量同構的FRC,否則可以構造節(jié)點存儲容量異構的FRC.具體實例如下,其中,例4 給定的是用可調節(jié)環(huán)構造的重復度ρ=3的同構FRC,如圖5所示,例5 給定的是用可調節(jié)環(huán)構造的重復度 ρ=3的異構FRC,如圖6所示.

例4.給定θ=n=4,則用可調節(jié)環(huán)去構造FRC,結構如下.

由上面的可調節(jié)環(huán)結構圖和節(jié)點存儲圖可知,構造得到的碼是重復度 ρ=3,節(jié)點存儲容量為3 的同構FRC.該FRC 的故障節(jié)點修復方式為,當U1發(fā)生故障,可以直接重U3中下載1,3 兩個數(shù)據(jù)塊,再從U2或U4中下載4 這個數(shù)據(jù)塊；當U1和U2同時發(fā)生故障時,可以直接從U3和U4節(jié)點中下載數(shù)據(jù)塊進行修復,修復方式簡單,無需任何編碼.

圖5 可調節(jié)環(huán)結構和節(jié)點存儲結構圖

圖6 可調節(jié)環(huán)結構和節(jié)點存儲結構圖

例5.給定 θ=16,n=8,用可調節(jié)環(huán)去構造FRC,結構如下.

由上面的可調節(jié)環(huán)結構圖和節(jié)點存儲圖可知,構造得到的FRC 是重復度 ρ=3,節(jié)點存儲容量異構的FRC,節(jié)點容量出現(xiàn)7,6,5 三種情況.該FRC 的故障節(jié)點修復方式為,直接從存活節(jié)點下載數(shù)據(jù)塊,可最多修復兩個故障節(jié)點.

4 性能分析

對本文提出的兩種新的構造進行性能分析,主要與現(xiàn)有的FRC 對比分析,發(fā)現(xiàn)本文構造的FRC 在節(jié)點存儲容量上具有異構的特點,修復局部性好,同時在構造算法運算復雜度低,可以大范圍的選擇參數(shù),構造結構簡單直觀.

4.1 節(jié)點存儲容量對比分析

對矩陣變換構造的異構FRC 和已有的用正則圖和部分正則圖構造的FRC 進行對比分析,主要分析節(jié)點存儲容量,如表1.

表1 節(jié)點存儲容量對比分析

表1只列舉了部分情況,可以發(fā)現(xiàn)本文提出的基于矩陣構造的異構FRC 相比于正則圖構造的FRC 在節(jié)點存儲容量上是異構的,并且本文提出的構造方法在節(jié)點修復選擇度上更優(yōu).

對基于可調節(jié)環(huán)構造的FRC 進行對比分析,相比于文獻[10]提出的運用正則圖構造的FRC 本構造在重復度上的選擇性更靈活,正則圖只能構造 ρ=2的同構FRC,用可環(huán)結構可以得到重復度多樣的同構或異構的FRC,構造算法更簡單直觀.

4.2 參數(shù)選擇對比分析

根據(jù)已有研究表明,大多數(shù)構造FRC 的方法都對參數(shù)有明顯的限制,對比分析得本文提出的基于可調節(jié)環(huán)構造的FRC,在參數(shù)選擇上更具有靈活性,對比分析結果,如表2.分析結果.表2中各參數(shù)含義解釋如下：α是FRC 的節(jié)點存儲容量,d表示修復單個節(jié)點時需要連接的節(jié)點數(shù),一般意義上 α=d,ρ表示FRC 的數(shù)據(jù)重復度,θ表示系統(tǒng)中數(shù)據(jù)塊,n表示系統(tǒng)中的節(jié)點數(shù),q是 素數(shù),h是Hadamard 矩陣的階數(shù).

4.3 修復局部性對比分析

修復局部性是指在修復故障節(jié)點時需要連接的存活節(jié)點數(shù).當單節(jié)點出現(xiàn)故障時,運用正則圖構造的FRC 需要連接的節(jié)點數(shù)為d,即修復局部性為d,運用基于矩陣變換構造的異構FRC 需要連接的節(jié)點數(shù)有d,d?1,d?2 三 種情況,即修復局部性為d,d?1,d?2三種情況,修復局部性更好.另外,當出現(xiàn)單節(jié)點故障時,(n,k)RS 碼需要連接k個節(jié)點先恢復原始文件來修復出現(xiàn)故障的節(jié)點,修復局部性為k；基于矩陣變換構造的異構FRC 需要連接的節(jié)點數(shù)有d,d?1,d?2三種情況,修復局部性為d,d?1,d?2三種情況,又由于研究的FRC 都是d＜k,所以可知和(n,k)RS 對比,基于矩陣變換構造的異構FRC 具有更好的修復局部性.

表2 不同構造方法參數(shù)對比分析圖

圖7給定的實例是基于矩陣變換構造的異構FRC和(n,k)RS 碼的在修復局部性方面的對比情況,當修復節(jié)點存儲容量為d(d＜k)的節(jié)點時,可知基于矩陣變換構造的異構FRC 的修復局部性恒為d(d＜k),但RS 碼的修復局部性與k(正整數(shù))是一次線性關系.

圖7 修復局部性與數(shù)據(jù)塊k 的關系圖

4.4 構造算法運算復雜度

衡量一個算法的優(yōu)劣,通常需要考慮算法構造時涉及的運算復雜度,即將算法寫成程序在實際的計算機系統(tǒng)中運行時,涉及的計算量.本文基于矩陣變換的異構FRC,由構造算法可知,構造一個異構的FRC 需要進行d?1次 加法運算和n2次模2 加運算；運用可調節(jié)環(huán)構造的FRC,構造時不需要任何計算量,只需在環(huán)上直接進行調節(jié)即可,相比于基于矩陣變換的異構FRC,用可調節(jié)環(huán)得到的FRC,在構造算法運算復雜度表現(xiàn)的更優(yōu).

將基于矩陣變換的異構FRC 和運用偏序集構造的FRC[10]在構造算法運算復雜度進行對比分析,在文獻[10]中,構造算法時運用到了加法,乘法運算和基于集合上的運算,明顯可知本文算法運算復雜度更低.

5 結論

考慮實際的分布式存儲系統(tǒng)大多需要滿足異構的特性.為此,本文提出了兩種構造方法,一種是基于矩陣變換構造的異構FRC,該構造主要用于構造重復度為2,節(jié)點存儲容量異構的FRC,相比用正則圖構造的同構FRC,該構造更符合現(xiàn)實的存儲系統(tǒng)；另外,本文還提出了運用可調節(jié)環(huán)構造的FRC,構造得到了重復度為2 或3 的FRC,該方法即可得到節(jié)點存儲容量同構的FRC 也可得到節(jié)點存儲容量異構的FRC.與現(xiàn)有的FRC 對比分析,發(fā)現(xiàn)本文構造的FRC 在節(jié)點存儲容量上具有異構的特點,修復局部性好,同時在構造算法運算復雜度低,可以大范圍的選擇參數(shù),構造結構簡單直觀.將來如何去構造更多樣的異構FRC 是研究的熱點.