基于節點共邊的異構部分重復碼構造①

田松濤

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

當今世界互聯網快速發展,數據海量化是互聯網技術發展的必然結果[1].如何快速、高效、可靠地存儲這些數據資源成為研究熱點和面臨的巨大挑戰.傳統的集中式存儲將數據集中存放在專用服務器或者專用磁盤陣列中,存儲海量數據時存在諸多瓶頸,例如系統性能、存儲成本和可擴展性.分布式存儲系統將海量數據存儲在多個廉價存儲設備中,海量存儲能力、高吞吐量、高可用性、高可擴展性和低成本等突出優勢使分布式存儲系統成為海量數據的有效存儲手段.但是實際的分布式存儲系統中不可避免地會出現節點故障,如何高效地修復故障節點來保障分布式存儲系統的高可靠性和高可用性成為目前急需解決的關鍵問題[2,3].

現有的復制和糾刪碼策略能修復分布式存儲系統中的節點故障,但都存在各自的缺陷.隨后,Dimakis 等人將網絡編碼應用到分布式存儲系統中,提出了再生碼的概念[4],顯著降低了故障節點的修復帶寬開銷.再生碼雖然能有效降低故障節點修復時的帶寬開銷,但沒有考慮磁盤I/O 開銷和修復局部性.為了確保修復故障節點較低修復帶寬開銷的同時,需要連接的存活節點數也較少,Papailiopoulos 等人提出了局部修復碼(locally repairable codes,LRC)[5].進一步,Hao 等人和Wang 等人分別研究了局部修復碼的構造以及協作局部修復碼[6,7].

再生碼和局部修復碼在故障節點修復過程中涉及大量有限域運算,計算復雜度較高.為了進一步降低計算復雜度和修復帶寬開銷,El Rouayheb 等人提出一種精確修復的最小帶寬再生碼——部分重復(fractional repetition,FR)碼[8].目前對 FR 碼的研究主要有基于組合設計構造FR 碼[9],基于序列構造FR 碼[10],基于二分圖構造局部修復 FR 碼[11],FR 碼的修復消耗最小化[12].這些構造算法復雜,并且大多只能構造同構的FR 碼,不能得到異構的FR 碼.Silberstein 等人基于組合設計和正則圖,提出了一種達到最大碼率的FR 碼的構造方法[13],但其重復度受 FR 碼結構的約束,不能適用于任意參數.基于Hadamard 矩陣構造的異構部分重復碼[14,15]修復復雜度和修復帶寬開銷都有所降低.基于矩陣變換和可調節環的部分重復碼構造[16]可以大范圍的選擇參數,構造結構簡單直觀.Zhu 等人提出基于組合設計的FR 碼,可以調整存儲節點的數量和節點的存儲容量[17].進一步,Zhu 等人對一般好的部分重復碼的重復度限和重構度限進行了討論[18-21].在實際的分布式存儲系統中,數據存儲的結構多為異構的,并且需要動態存儲,即在增加或減少數據時,自動調節數據的存儲分布.

為了解決上述問題,本文構造了一種基于節點共邊的異構部分重復碼(heterogeneous fractional repetition codes based on node common edge,HFRC-NCE).具體地,結合節點共邊的特性,將熱數據存儲在多點共邊上,將冷數據存儲在兩點共邊上,使得熱數據具有較高的重復度,同時各個節點存儲的數據容量不同,實現數據的動態存儲和異構存儲.性能分析表明,與文獻[8]基于完全圖和文獻[22]基于部分正則圖構造的部分重復碼相比,雖然HFRC-NCE的存儲開銷和修復帶寬開銷略大,但其構造簡單,減小了文件的重構度,節點的修復選擇度更高,節點存儲的數據容量更加多樣性,使得系統能更高效地修復故障節點.

1 點共邊和部分重復碼

1.1 點共邊

圖G通常用G=(V,E) 表示,其中V(G)和E(G)分別為圖G中的節點集和邊集.圖G中節點的個數稱為圖G的階,與節點相關聯的邊的總數稱為節點的度,將ρ 點存在同一條邊上記為Eρ,如圖1所示.如果圖G中任意兩個不同的節點通過邊相互連接,稱圖G為完全圖.當圖G中每個節點都具有相同的度,則稱圖G為正則圖.

圖1 ρ點 共邊的Eρ

n階完全圖的各個節點相連的邊的總和為完全圖可視為由個E2構成的圖,在任意兩點都通過邊相連的前提下,當圖G中邊的總和小于時,說明圖G中的邊不僅有兩點相連的情況,還存在多點共邊的情況.

圖2為ρ點共邊時相對于n階完全圖減少的邊數.當一個3 階完全圖變為3 點共邊E3會減少兩條邊,一個4 階完全圖變為4 點共邊E4會減少5 條邊.以此類推,n階完全圖變為ρ 點共邊Eρ會減少條邊.當圖中邊的總和θ小于時,圖中必然存在3 點及以上多點共邊.將 ρ 點共邊Eρ的個數記為Pρ,則:

圖2 多點共邊時減少的邊數

具體地以圖3中的6 階圖為例,圖中共有9 條邊,n=6,θ=9.根據式(1)和式(2),得到P2=6和P3=3,則圖3存在3 條3 點共邊的邊E3和6 條2 點共邊的邊E2.

圖3 E 2和E3組合圖

1.2 部分重復碼

部分重復碼的實質是由外部的最大距離可分碼(maximum distance separable,MDS)和內部重復碼構成,首先將原始文件分成M個原始數據塊,原始數據塊通過(θ,M)M DS 碼編碼后,生成θ 個編碼數據塊,再將生成的編碼數據塊復制 ρ倍分別存儲到n個節點中,每個節點存儲d個不同的編碼塊,得到一個(n,d,θ,ρ)部分重復碼,滿足nd=θρ.

圖4為基于完全圖構造的部分重復碼,由外部的(15,14)M DS 碼和內部重復度ρ=2的重復碼構成.將MDS碼編碼后的15 個數據塊依次存放在完全圖的不同邊上,每個節點存儲5 個數據塊.每個節點故障時需要連接其他5 個存活節點進行修復,所以d=5.此系統至少需要4 個節點來重構原文件,所以k=4,并且滿足nd=θρ.

圖4 基于完全圖構造的(6,5,15,2)部分重復碼

2 基于節點共邊的異構部分重復碼

2.1 基于節點共邊的異構部分重復碼構造

在實際的分布式存儲系統中,存儲節點的存儲容量大多異構.為了滿足分布式存儲系統存儲容量異構的特點,結合節點共邊的特性,按照熱數據重復度高和冷數據重復度低的原則構造異構部分重復碼.具體步驟如下.

步驟1.首先將原始文件分成M(M=θ-1)個原始數據塊,原始數據塊通過(θ,M) M DS 碼編碼后生成θ 個編碼數據塊,將其存儲到具有n個 節點的n階圖中.

步驟2.設Pρ為一個未知參數,Pρ表示 ρ點共邊Eρ的數目.將MDS 碼編碼后的一個數據塊存放在共邊Eρ上,則該共邊Eρ上的所有 ρ個節點都將存儲該數據塊,相當于將此數據塊重復存儲了ρ 倍.本文中數據塊的重復度 ρ最大取4,所以只會出現P2、P3和P4三個未知參數.

步驟3.通過已知的節點個數n和編碼后的數據塊個數θ,結合式(1)和式(2),可以解出符合條件的未知參數P2、P3和P4.將MDS 碼編碼后的數據塊分為熱數據塊和冷數據塊,將熱數據塊存儲在3 點共邊或者4 點共邊的邊上,將冷數據塊存儲在2 點共邊的邊上,通過以上的編碼過程可以得到一個異構的部分重復碼.

具體地,通過例1 來說明構造的過程.

例1.首先將原始文件分成M=7個原始數據塊,通過(8,7)M DS 碼編碼生成θ=8個編碼數據塊,將這些編碼后的數據塊存儲到n=6個存儲節點中,在滿足參數要求的情況下,將節點數和編碼后的數據塊個數代入式(1)和式(2)中:解得未知參數P3為1,P4為1,表示有1 條3 點共邊的邊和1 條4 點共邊的邊,通過與MDS 碼編碼生成的θ=8個 編碼數據塊做差,得到P2為6,即有6 條兩點共邊的邊,將編碼后的數據塊1,2 看作熱數據塊,將3,4,5,6,7,8 看作冷數據塊,將熱數據塊1 存儲在4 點共邊上,將熱數據塊2 存儲在3 點共邊上,將冷數據塊3,4,5,6,7,8 依次存儲在2 點共邊上,通過此編碼過程可以得到6 個節點的數據塊存儲分布如圖5所示.

圖5 n=6,θ=8的HFRC-NCE

2.2 節點修復

本文異構部分重復碼是基于節點共邊來構造的,因此當節點發生故障時,可以簡單直觀的通過圖中的數據分布來修復節點,當節點故障時只需連接圖中相鄰的存活節點進行修復,下面分單節點故障和多節點故障進行討論.

單節點故障修復:HFRC-NCE 每個數據塊最小的重復度為2,即每條邊的數據塊最少存儲在兩個節點上,故當單個節點發生故障時可從相鄰的存活節點下載數據塊進行修復,并且當故障節點存儲的數據塊位于E3或E4時,故障節點修復將有更多的選擇方案.如圖5中的節點1 發生故障時,節點1 中的3和6 數據塊可連接節點5和6 下載相應的數據塊進行修復,節點1 中的1 數據塊位于E4上,所以可通過連接節點2、3、4 中的任意一個下載數據塊1 進行修復.

多節點故障修復:HFRC-NCE 每個數據塊最大的重復度為4,即每條邊的數據塊最多存放在4 個節點上,故最多能同時修復3 個故障節點,存在以下3 種情況:

(1)當同時修復3 個故障節點時,這3 個節點應在同一個E4上.

(2)當同時修復2 個故障節點時,這2 個節點應在同一個E3上.

(3)當故障節點不在同一個E3或E4時,只能修復單節點故障不能修復多節點故障.

圖5中的節點1、2和3 同時發生故障時,節點1、2和3 中的數據塊1 均可連接節點4 下載數據塊1 進行修復,節點1、2和3 中的其他數據塊可連接相鄰的存活節點下載相應的數據塊進行修復.當節點5和6 同時發生故障時,節點5和6 可以通過連接存活節點1、2、3和4 下載相應的數據塊進行修復.當節點3和6 同時發生故障時,由于節點3和6 不在同一多點共邊上,數據塊8 沒有存活節點可供下載,故不能同時修復節點3和6.

3 性能分析

本節主要分析HFRC-NCE的節點修復選擇度、節點存儲容量、重構度、存儲開銷和修復帶寬開銷,并與完全圖和部分正則圖構造的部分重復碼進行對比.

3.1 節點修復選擇度

修復故障節點可選的方案數,叫做該節點的修復選擇度.基于節點共邊的異構部分重復碼的節點修復選擇度與各個數據塊的重復度 ρ和節點容量d相關.由于每個編碼數據塊存儲到不同的共邊上,故每個數據塊的重復度并不相同,每個節點存儲著不同數量的數據塊.當單節點發生故障時,需要分情況討論:當發生故障的節點在3 點或4 點共邊時,單節點的修復選擇度為ρ-1;當發生的節點存儲在多節點共邊相交的位置時,單節點的修復選擇度為(ρmax-1)×(ρmax-2),當發生故障的節點在2 點共邊時,單節點的修復選擇度為1.當多節點發生故障時,多個節點需位于同一條共邊上否則將無法修復,多故障節點的修復選擇度為ρ-2.圖6所示為3 種構造的部分重復碼,節點故障的最大修復選擇度對比.

圖6 節點故障的最大修復選擇度對比

如圖5當節點1、2、3 中的一個發生故障時,單節點的修復選擇度為3;當節點5、6 中的一個發生故障時,單節點的修復選擇度為2;當節點4 發生故障時,單節點的修復選擇度為6.當節點1和2 同時故障時,節點修復選擇度為2;當節點1和6 同時故障時,由于節點1 在4 點共邊上,節點6 在3 點共邊上,導致數據塊6 沒有存活節點供其下載修復,無法進行多節點修復.

基于完全圖和部分正則圖構造的部分重復碼,單節點的節點修復選擇度為1,并且當2 個及以上節點故障時均不能進行修復.因此HFRC-NCE 提高了單節點及多節點的節點修復選擇度,并增加了故障節點可修復的個數.

3.2 節點存儲容量

節點存儲容量及每個節點存儲的數據塊容量,表1為完全圖和部分正則圖構造的部分重復碼和HFRCNCE 節點存儲容量的對比.

表1 不同構造部分重復碼存儲容量的對比

通過部分節點的存儲容量對比發現HFRC-NCE的節點存儲容量更加多樣化,更適用于實際的分布式存儲系統中.

相對于靜態存儲,動態存儲更適用于實際的分布式存儲系統,HFRC-NCE 在增刪原始文件M時,即更改MDS 碼編碼后的數據塊θ,可以根據式(1)和式(2),快速求得Eρ的邊數,使得數據塊復制的倍數有所變化,進而改變節點的存儲分布,達到動態存儲,同時也體現了HFRC-NCE的節點存儲容量的多樣化.

3.3 重構度

用k表示文件的重構度,k的定義為重構原文件所需的最少節點數.CMBR(n,k,d)=kd-=M,CMBR表示最小帶寬再生碼的存儲容量,等于從系統中任意k個節點所能獲得的文件大小M.n階完全圖構造的部分重復碼原始文件M=θ-1,每個節點存儲的數據塊容量d為n-1,將d和M代入CMBR的公式中可以求得k=n-2,即重構原始文件至少需要n-2個節點.HFRCNCE的各個節點的數據塊容量d不同,當節點位于多點共邊相交的位置時,節點存儲的數據塊容量d最小;當節點位于兩點共邊不位于多點共邊時,節點存儲的數據塊容量d最大.在HFRC-NCE 中,當只存在E2和x個E3時,數據塊容量d最小為n-1-x,最大為n-1;當只存在E2和x個E4時,數據塊容量d最小為n-2-x,最大為n-1.HFRC-NCE的重構度會隨選取節點的不同而變化.下面通過表2不同的節點數和編碼后的數據塊來分析重構度.

通過表2可以得出,在節點個數相同的情況下,HFRC-NCE的最小重構度k為n-4,完全圖構造的部分重復碼的重構度k為n-2,HFRC-NCE的重構度小于基于完全圖構造的部分重復碼的重構度.由于HFRCNCE 增加了部分數據塊的重復度,MDS 碼編碼后的數據塊相對于完全圖構造的部分重復碼的編碼塊較少,所以HFRC-NCE的重構度有所降低.

表2 不同參數下文件的重構度

3.4 存儲開銷和修復帶寬開銷

存儲開銷為各個節點存儲數據塊所需的空間與原始文件M的比值.n階完全圖構造的部分重復碼,將原始文件M經過MDS碼編碼后生成 θ=個編碼塊,每個節點存儲n-1 個數據塊,其存儲開銷為×n×(n-1)=2M.n階部分正則圖構造的部分重復碼的存儲開銷也為2M.HFRC-NCE的原始文件M經過MDS碼編碼后生成 θ＜個編碼塊,編碼塊復制不同的倍數存儲到各個節點中,編碼塊復制的倍數取決于此編碼塊所在的Eρ,存儲的數據塊總和為當HFRCNCE 只存在E2和E3時,結合式(1)式(2)可推導出HFRCNCE的存儲開銷為若HFRC-NCE的存儲開銷等于 2M需滿足但HFRC-NCE的θ＜故HFRC-NCE的存儲開銷大于2M,即大于基于完全圖和部分正則圖構造的部分重復碼的存儲開銷.同理,當HFRC-NCE只存在E2和E4時,結合式(1)式(2)可推導出HFRCNCE的存儲開銷為HFRC-NCE的θ＜故HFRC-NCE的存儲開銷仍大于2M.圖7所示,當原始文件大小M=1000 MB時,3 種構造的部分重復碼存儲開銷的對比.

圖7 存儲開銷對比

修復帶寬開銷為修復故障節點時所需下載的數據量的大小.n階完全圖構造的部分重復碼,原始文件大小為M,經過MDS 碼編碼后生成θ=個編碼塊,每個節點存儲n-1個數據塊,則單故障節點的修復帶寬開銷為n階部分正則圖構造的部分重復碼,原始文件大小為M,經過MDS 碼編碼后生成θ=個編碼塊,其中n-1個節點每個節點存儲n-2 個 數據塊,1 個節點存儲n-3個數據塊,則單故障節點的修復帶寬開銷為(n-3).HFRC-NCE 每個節點存儲的數據塊數量不同,故不同節點故障時的修復帶寬開銷不同.圖8所示,當原始文件大小M=1000 MB時,3 種構造的部分重復碼節點修復帶寬開銷的對比.

圖8 節點修復帶寬開銷對比

3.5 構造算法運算復雜度

衡量一個算法的好壞,其算法運算復雜度是一個重要的指標.本文構造的HFRC-NCE 碼,在構造時只需根據已知的節點數和邊數結合式(1)和式(2)求出兩點共邊和多點共邊的情況,之后將冷數據和熱數據塊分別存儲在邊上,構造出的HFRC-NCE 碼簡單直觀.本文的構造與文獻[13]相比,文獻[13]運用大量組合設計的知識,所需判斷的情況過多,加大運算復雜度,因此本文的算法復雜度更優.

4 結論

當前部分重復碼的構造大多為同構的并且為靜態存儲,不太適用于實際的分布式存儲系統.本文結合節點共邊的特性,并將實際分布式系統的冷熱數據塊相結合,構造的HFRC-NCE 簡單直觀,便于進行快速的節點修復.通過與完全圖和部分正則圖構造的部分重復碼對比,可以發現,HFRC-NCE 雖然具有較高的存儲開銷和修復帶寬開銷,但能實現更多故障節點的修復,降低了文件的重構度,提高了節點的修復選擇度,使節點容量更加多樣化,并且在增刪原始數據時,能快速地調整節點的存儲分布,實現動態存儲.