“雙碼”架構下的云存儲多節點修復協作編碼

謝顯中，黃倩,2，王柳蘇

(1. 重慶郵電大學 寬帶接入網絡研究所，重慶 400065；2. 重慶郵電大學 移通學院 計算機科學系，重慶 401520)

1 引言

隨著大數據的迅猛發展，如何在云存儲/分布式存儲的可靠性與帶寬消耗之間找到一個平衡點至關重要。2007年，Dimakis等[1]第一次將網絡編碼思想應用于云存儲/分布式存儲，并提出了基于網絡編碼思想的再生碼方案。再生碼（regenerating codes）是指在云存儲（cloud storage）系統中，將網絡編碼（network codes）技術和失效節點修復技術相結合的編碼方案[2,3]。利用再生碼技術可以在提高云存儲可靠性的同時，減少修復需要的網絡流量和帶寬，進一步降低存儲和修復代價。因此，各類再生碼和失效節點修復方案受到廣泛重視。Suh等[4]提出了一種滿足最優存儲容量-修復帶寬折衷曲線的極大距離可分（MDS, maximum distance separable）碼，并通過對偶變換的形式將該修復方案同時應用于系統節點和冗余節點的修復。但文獻[4]的精確修復MDS（E-MDS, exact MDS）碼只能解決單節點失效的問題，而未涉及多節點失效的情況。

對于多節點失效修復問題，多節點協作修復是有效的解決方案[5～12]。文獻[5]給出了聯合再生節點方案，但需要更多的傳輸信道，這使修復過程更加繁瑣，導致修復的不穩定。文獻[6,7]所闡述的多節點靈活再生方案主要是指在修復過程中，中間節點下載所需數據的靈活性，即可同時選擇從原健康節點和其他再生節點下載數據并通過干擾對齊來修復失效節點，雖然有效地降低了修復帶寬，但仍有修復時間不同步、修復過程復雜等問題。文獻[8]在多節點聯合修復時把干擾對齊獨立地運用其中，提高了修復效率，但在精確修復時這個方案只在k=2時有效，為了使其有更大的適應性，還有很多問題需要解決。文獻[9,10]分別將其擴展到其他k值組合時的最小帶寬再生碼（MBRC, minimum-bandwidth regenerating codes）和最小存儲再生碼（MSRC, minimum-storage regenerating codes），但在 MBRC 和 MSRC 無法取得折中平衡。Shum等[11]通過改變部分中間節點選取的幫助節點，提出了一種多節點聯合修復（MCR, multi-node cooperative regenerating）碼。MCR碼雖然可以減少修復帶寬，但也使修復過程更加繁瑣，需要更多的傳輸信道，導致修復的不穩定。具有健康節點協作的多節點修復模型[12]在進行多節點修復時，幫助節點把用來修復失效節點的數據直接傳輸到從健康節點中選取的中間節點處。然后在此中間節點上進行相關計算和處理，在保證最低修復帶寬的前提下，同步節點修復過程，減少修復鏈路數目，簡化修復過程，減少對網絡資源的浪費和依賴，以此增加系統可靠性，從而達到安全高效修復節點的目的。但由于此模型將主要的計算和處理工作放在中間節點上，所以中間節點的存儲容量和運算負荷較大，系統穩定性差。

為解決上述多節點協作修復問題，本文首先根據文獻[13]的MDS雙碼(twin-MDS codes)架構模型結合具有健康節點協作的多節點修復模型，給出了一種具有健康節點協作的MDS雙碼架構模型；這不但能解決具有健康節點協作的多節點修復方案[12]中的存儲容量和運算負荷較大的問題，而且具有數據傳輸鏈路少、修復帶寬小、多節點同步修復的優勢。進一步，本文對文獻[4]中的E-MDS碼進行擴展，給出了一種適用于多個系統節點和冗余節點同時修復的多節點協作的精確修復（MER, multi-node exact repair）編碼方案，并證明了其存在性。最后，通過數值仿真對比表明，本文的模型與方案在修復帶寬、數據傳輸鏈路具有較大改進，且隨著云存儲中節點數量的增多優勢更加明顯。

2 MDS雙碼架構下健康節點協作的多節點修復模型

2.1 健康節點協作的多節點修復模型簡介

具有健康節點協作的多節點修復模型的基本思想是在修復r個節點失效時，d個健康節點互相協作，并從d個健康節點中選擇一個健康節點作為節點m代替再生節點，失效節點的修復過程就直接在節點m上進行，以此省掉修復過程中的中間節點環節。具有健康節點協作的多節點修復過程如圖 1所示。

圖1 具有健康節點協作的多節點修復過程

設原始用戶文件可分為 4個大小相同的數據塊（A1，A2，B1，B2），并存儲在2個系統節點（節點1、節點2）中，然后運用具有MDS性質的再生碼對原始文件進行網絡編碼，再生成與系統節點同等大小的2個冗余節點（節點3、節點4）。假設節點1和節點3失效，選擇節點4為節點m，節點2直接將其存儲的數據塊A1和A2傳輸給節點m，然后節點m將接收到的數據再與其自身存儲的數據進行運算，則可以同時得到 2個失效節點的全部數據，并分別輸出從而修復出失效節點1和失效節點3。

在具有健康節點協作的多節點修復模型中，其他健康節點傳送自己存儲的數據到節點m，則需要傳送d-1次大小為β的數據，然后再通過線性運算并輸出r個大小為α的數據，因此，成功修復所有失效節點所需的總修復帶寬為γ=(d-1)β+rα。因此，可以看出圖1中的數據傳輸量為6個數據塊，傳輸次數（傳輸線路）為 3，并且在一個修復過程就達到了同時修復2個失效節點的目的。

因此在云存儲環境中，當存儲節點相隔距離非常大的情況下，具有健康節點協作的多節點修復模型能使整個修復過程更加安全、簡便。該模型在修復失效節點時下載數據是同步的，且修復步驟簡便、安全易實施，有效地減少了所需的數據傳輸鏈路數，保證了高效率的修復節點，減少了對資源的浪費。雖然具有健康節點協作的多節點修復模型的優勢明顯，但仍然有中間節點m存儲容量、運算負荷較大的問題。因此，下一節將引入MDS雙碼架構模型及其編碼過程。

2.2 MDS雙碼架構簡介

在MDS雙碼架構下，云存儲系統中的存儲節點（n個）被分成類型1（n1個）和類型2（n2個），如圖2所示。

圖2 MDS雙碼架構下節點修復和源文件重建的數據下載方式

如果想從類型1的節點下載數據，則該數據可以運用線性碼C1進行編碼解碼操作；而想從類型2的節點下載數據，則數據先通過簡單的移位操作改變順序，然后運用線性碼C2進行編碼解碼操作，并且這2種線性碼（C1、C2）可以相同。另外，當一種類型的存儲節點失效時，需要從另一種類型的健康存儲節點子集下載數據以修復這個失效節點；而如果想要重建出整個原始用戶文件，則需要從同一種類型節點子集下載數據。因為MDS雙碼架構下的兩種線性碼都滿足 MDS特性，因此任意選擇k個同類型節點就可以恢復出整個原始用戶文件。

假設原始用戶文件為在Fq的有限域里的M個信息符號，每個存儲節點存儲k個信息字符，對于類型i=0，1，令Ci為區間[ni,k]中在有限域Fq中任意的線性碼（具有MDS特性），生成矩陣為Gi，把矩陣Gi的第l列表示為g(i,l)(1≤l≤ni)。

首先，用戶數據被分為k2個數據片段，然后對于每一個數據片段進行編碼。把這k2個數據符號排列在k×k階信息矩陣A1中，且A2=A1t，其中，上標t表示矩陣的置換。通過編碼Ci和信息矩陣Ai來獲取這些信息數據，存儲在類型i的每一個節點中的k個信息符號對應到k×ni階矩陣AiGi中的每一列，類型i的節點l(1≤l≤ni)存儲的數據字符在對應在矩陣的第l列，表示為Aig(i,l)(1≤l≤ni)。易知，每個類型i的節點l與矩陣Gi中列g(i,l)一一對應，因此稱g(i,l)為所對應存儲節點的編碼向量。如圖3所示。

圖3 MDS雙碼架構下2種類型碼的編碼過程

為更加具體地描述MDS雙碼架構下的節點修復過程，下面給出一個簡單的修復過程示例。假設類型1的節點1和節點4同時失效，除了類型2的節點2、3、4把所需數據傳輸給修復g(1,1)的中間節點外，類型2的節點1、2、3也要將數據傳輸到修復g(2,4)的中間節點處，最終修復出這2個失效節點的數據，如圖4所示。

圖4 MDS雙碼架構的多節點修復

2.3 具有健康節點協作的MDS雙碼架構模型

為了進一步提高對失效節點的修復效率、系統可靠性，同時降低成本，可將MER碼運用于MDS雙碼架構模型中，對多節點失效進行修復。利用MDS雙碼架構模型與具有健康節點協作的多節點修復模型相結合，不僅達到更優的修復效果，而且還可以克服文獻[12,13]中存在的諸多問題。

具有健康節點協作的MDS雙碼架構模型如圖5所示。將存儲節點根據雙碼結構進行布局，用戶原始文件被存放在2種類型的節點中，并分別用C1碼和C2碼為類型1和類型2的存儲節點編碼。然后在兩部分各選擇一個健康節點作為修復對方失效節點的中間節點m1和m2。假設類型2的r2個節點損壞，則屬于類型1的用來修復這些節點的健康節點的個數為d1，傳輸到m1的鏈路數為d1-1；同樣的，若是類型1的r1個節點損壞，則傳輸到m2的鏈路數為d2-1，然后在中間節點進行線性運算，得到失效節點中的數據，輸出再生節點。

圖5 具有健康節點協作的MDS雙碼架構模型

假設云存儲系統中有總共有r個節點失效，其中，屬于C1碼和C2碼這2種類型的失效節點個數分別為r1和r2。本文分別從d1和d2個節點下載數據來修復所有失效節點，系統管理員從2個類型的健康節點中分別選擇 2個節點作為中間節點m1和m2，其他健康節點分別傳送數據到與自身同類型的接收端m1或者m2，則需要傳送di-1次大小為βi的數據，再通過線性運算并輸出ri個α大小的數據。因此，修復全部失效節點所需的修復帶寬為γ=γ1+γ2，其中，γi=(di-1)βi+riα。

從上面的分析可以看出，與簡單的具有健康節點協作的多節點修復模型相比，只增加了少量的存儲節點，但中間節點的數據存儲量少了一半，明顯地減小了中間節點m的存儲及運算負擔。同時，在同樣的修復條件下，當2種類型的節點中都存在多節點失效的情況時，在傳輸鏈路方面，傳輸鏈路數減少了1條。因為多了1個中間節點就少了1次健康節點傳輸數據的過程，在這個方案中d=d1-1+d2-1=d1+d2-2，而具有健康節點協作的多節點修復模型中d=d1+d2-1。在修復帶寬方面，每條鏈路傳輸的數據量為α沒變，但傳輸鏈路減少了一條，也就是減少了β大小的修復帶寬，這里β=α。

綜上所述，整個系統的可靠性、靈活性都大大增加，既保留、甚至優化了具有健康節點協作的多節點修復方案的數據傳輸鏈路少、修復帶寬小、多節點同步修復的優勢；也解決了這個方案中間節點存儲、運算負擔大的問題，在大量存儲節點的網絡中，此優勢會更加明顯。在下一節中，本文將給出一種運用于具有健康節點協作的MDS雙碼架構模型中的，能適用于多個系統節點或冗余節點的MER碼，并證明其存在性。

3 MDS雙碼架構下具有健康節點協作的MER修復方案

Suh等[4]給出了一種(n,k,d)=(2k,k, 2k-1)的E-MDS碼。對于該 E-MDS碼，可以計算M=kβ(d-k+1)，β=1，則有這里進一步將E-MDS碼再進行簡要地概括，并為了強調 E-MDS碼的對偶性，將使用與文獻[4]不同的符號表述。

設k階非奇異矩陣X=[xij],Y=[yij],Ψ=[ψij],Φ=Ψ-1=[φij]滿足

其中，矩陣Ψ、Φ為初等變換矩陣，矩陣X的列向量為x1,…,xk，矩陣Y的列向量為y1,…,yk。設K={1,…,k}，則對于?i∈K，式(1)可以表示為

設矩陣X～=(XT)-1，Y～ =(YT)-1。其中，對矩陣X（或Y）的列向量進行轉置和求逆操作后得到矩陣X～（或Y～）的列向量x～1,…,x～k（或～y1,…,～yk）。設k×k階矩陣Θ=[θ1…θk]，D=[δ1…δk]。其中，θi表示節點i中存儲的長度為k的列向量，δi表示節點k+i中存儲長度為k的列向量。

文獻[4]中給出了E-MDS編碼方案的兩種構造方法：一種方法是將節點1到節點k設為系統節點，節點k+1到節點2k設為冗余節點；另一種方法是將節點k+1到節點2k設為系統節點，節點1到節點k設為冗余節點。首先對于第一種構造方法，系統節點i中存儲的是未編碼的原始數據分塊，而冗余節點k+i中存儲的是對系統節點中的數據分塊進行線性變換后的編碼數據塊，其中，?i∈K。因此，k個冗余節點中的數據可以表示為

但是，該 E-MDS碼并不適合多節點修復。為了給具有健康節點協作的MDS雙碼架構模型構造一種適合的再生碼，這里對 E-MDS碼進行擴展，從而得到一種適用于多個系統節點或冗余節點的多節點修復網絡編碼方案——多節點精確修復（MER, multi-node exact repair）碼。該修復碼不僅保持了 E-MDS碼的最小修復帶寬，而且可以適用于多節點同時失效的精確修復情況。

定理1若E-MDS碼的參數矩陣Y、Ψ和編碼系數ω、σ、ω′和σ′滿足。

1) 矩陣Y是有限域GF(q)上k×k階的非奇異矩陣。

2) 矩陣Ψ是有限域GF(q)上k×k階的柯西矩陣。

3) 系數ω、σ、ω′和σ′是滿足式（7）的非零變量。

4) 對于?i，j∈K有ψijφij≠1。

則存在能同時修復r個失效節點的，并滿足再生碼割集邊界值的MER碼。

證明選取 E-MDS碼的第一種構造方法。即對于?i∈K，矩陣Θ的列向量對應于系統節點i的數據，矩陣D的列向量對應于冗余節點k+i的數據。因為MER碼至多允許r個節點失效，所以MER碼的幫助節點數量d=n-r。

在節點修復過程中，若系統節點i失效，則幫助節點將各自存儲的向量與列向量yi做內積操作，然后傳給再生節點i′；若冗余節點k+i失效，則幫助節點將各自存儲的向量與列向量xi做內積操作，然后傳給再生節點(k+i)′。

首先證明當r≥2時，且r個失效節點全為系統節點或r個失效節點全為冗余節點的情況。由于矩陣Θ和矩陣D的對稱性，所以這2種情況可以等效處理。

這樣完成定理1的證明。

根據以上的證明過程可以看出，MER碼作為E-MDS碼的擴展，不但保持了E-MDS碼在節點修復過程中滿足再生碼的割集邊界的性質，而且可以實現對r個系統節點（冗余節點），或2個節點（單個系統節點和單個冗余節點）的精確修復。

4 架構模型的數值仿真分析對比

在多節點修復問題中，前面本文已經理論上分析了具有健康節點協作的MDS雙碼架構模型與文獻[12,13]中的架構模型比較，本文提出的架構模型在修復帶寬、數據傳輸鏈路、中間節點存儲量運算量、系統可靠靈活性等方面都有一定的改進。

接下來，本文進行數值仿真對比。把幾種多節點修復模型（原始修復[1]、依次修復[15]、聯合修復[11]、健康節點協作修復[12]）與本文修復方案進行對比。為方便，當k=d,r=n-k，且n＜2k時，把相關參數用集合的形式表示為(n,k,d)(α,B)。

4.1 修復帶寬比較

在多節點失效的環境下，MDS雙碼架構模型的節點的修復過程中用來修復失效節點的每一個健康節點的信息字符都是相互獨立的。因此，每個健康節點只需識別中間節點的編碼向量。并且在此架構中，整個修復過程是以一種分布式方式完成的。這種方式可以使整個修復系統更容易實現，并進一步減少節點之間的修復帶寬消耗。用表示平均每個失效節點所消耗修復帶寬的大小，各修復模型的平均修復帶寬分析結果如表1所示。可以明顯地看出，本文修復模型每個節點平均的修復帶寬最優。并且隨著云存儲中節點數量的增多，優勢更加明顯。

表1 修復帶寬比較

4.2 數據傳輸鏈路數比較

在多節點修復過程中，在網絡上傳輸數據所用傳輸鏈路數f越小，系統可靠性越大。各修復模型所用的傳輸鏈路數結果如表2所示。可以明顯地看出，本方案不僅減少了修復帶寬，也有效地減少了修復傳輸鏈路數目，簡化修復過程，增加可靠性，減少對網絡資源的浪費，達到了安全高效地修復節點的目的。

表2 數據傳輸鏈路數比較

具有健康節點協作的多節點修復方案雖然傳輸鏈路數已經大大減少，但是本方案在同等參數下比它的傳輸鏈路數少 1，在減少中間節點存儲運算負擔的同時，減少了數據傳輸鏈路數，從而減少鏈路傳輸數據失敗的幾率，使系統更加可靠。

4.3 中間節點上的數據量比較

由于在MDS雙碼架構下健康節點協作的多節點修復方案中，2種編碼均會選擇一個健康節點作為修復對方編碼中失效節點的中間節點m1和m2，并分別將修復所需的數據傳輸給相應的中間節點（m1或m2）。因此相比健康節點協作修復方案[12]，分散了當修復多個失效節點時，單個中間節點上的數據量。

各修復模型中，單個中間節點上的最大數據量如表3所示。雖然中間節點的總數據量并沒有明顯減少，但本文的修復模型通過增加中間節點個數，使得單個中間節點的處理數據量減少，從而分散了中間節點的處理壓力。

表3 單個中間節點上的數據量比較

除了以上3個方面的優勢外，MDS雙碼架構模型的另一個主要優勢在與它適用于任意的線性糾刪碼，而MER編碼方案即是一種適用于多個系統節點和冗余節點的多節點修復線性網絡編碼方案。因此只要在E-MDS碼的基礎上使各參數滿足定理1中的約束條件，存在一種 MER碼可適用于具有健康節點協作的 MDS雙碼架構模型，使系統性能更優。

5 結束語

本文首先根據 MDS雙碼架構模型結合具有健康節點協作的多節點修復模型，給出了一種具有健康節點協作的MDS雙碼架構模型。該模型在具有健康節點協作的多節點修復方案的基礎上，解決了中間節點存儲、運算負擔大的問題，尤其在海量存儲節點的網絡中，此優勢會更加明顯。其次，本文通過約束參數條件，將適用于單節點修復的E-MDS碼擴展成了適用于多個系統節點或冗余節點同時修復的MER碼，并證明了其存在性。并在理論意義上將MER碼與具有健康節點協作的MDS雙碼架構模型相結合，以達到對多節點修復的同時，降低修復帶寬、修復鏈路數和單個中間節點需要處理的數據量。最后本文將具有健康節點協作的 MDS雙碼架構模型與現有的幾種架構模型進行數值仿真對比。結果表明，在進行多節點修復時，本文給出的架構模型減少了修復帶寬和數據傳輸鏈路數，降低了中間節點的數據處理量，進一步提高系統可靠性。對于下一步工作，將從MER碼的具體構造和雙碼架構下的MER碼在現實網絡中的實現進行研究。

[1] DIMAKIS A G, GODFREY P B, WAINWRIGHT M J,et al. Network coding for distributed storage systems[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2007. 2000-2008.

[2] DIMAKIS A G, RAMCHANDRAN K, WU Y,et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE,2011, 99(3): 476-489.

[3] RASHMI K V, SHAH N B, KUMAR P V. Optimal exact regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J]. IEEE Transactions on Information Theory,2011, 57(8): 5227-5239.

[4] SUH C, RAMCHANDRAN K. Exact-repair MDS code construction using interference alignment[J]. IEEE Transactions on Information Theory, 2011, 57(3): 1425-1442.

[5] HU Y, XU Y, WANG X,et al. Cooperative recovery of distributed storage systems from multiple losses with network coding[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 268-275.

[6] WANG X, XU Y, HU Y,et al. MFR: multi-loss flexible recovery in distributed storage systems[A]. IEEE International Conference on Communications (ICC)[C]. 2010. 1-5.

[7] 謝顯中, 黃倩, 王柳蘇, 等. 一種云存儲中基于干擾對齊的多節點精確修復方法[J]. 電子學報，2014, 42 (10): 1873-1881.XIE X Z, HUANG Q, WANG L S,et al. A multi-node exact repair method in cloud storage based on interference alignment[J], Acta Electronica Sinica, 2014, 42 (10): 1873-1881.

[8] LE S N. Exact scalar minimum storage coordinated regenerating codes[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. 2012. 1197-1201.

[9] WANG A, ZHANG Z. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C].2013. 400-404.

[10] LI J, LI B. Cooperative repair with minimum-storage regenerating codes for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2014. 316-324.

[11] SHUM K W, HU Y. Cooperative regenerating codes[J]. IEEE Transactions on Information Theory, 2013, 59(11): 7229-7258.

[12] 謝顯中, 王柳蘇, 黃倩, 等. 具有健康節點協作的高效多節點修復方案[J]. 北京郵電大學學報. 2014, 37(1):52-56.XIE X Z, WANG L S, HUANG Q,et al. Efficient multi-node regenerating program with healthy nodes collaboration in distributed storage systems[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(1):52-56.

[13] RASHMI K V, SHAH N B, KUMAR P V. Enabling node repair in any erasure code for distributed storage[A]. IEEE International Symposium on Information Theory(ISIT)[C]. Saint Petersburg, Russia, 2011.1235-1239.

[14] LI X, ZHENG Q, QIAN H,et al. Toward optimizing cauchy matrix for cauchy reed-solomon code[J]. IEEE Communications Letters, 2009,13(8): 603-605.

[15] WU Y, DIMAKIS A G. Reducing repair traffic for erasure coding-based storage via interference alignment[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. Seoul,2009. 2276-2280.