異構去中心化存儲中的LRC-RS混合編碼

胡金平，李貴洋，李 慧，江小玉，韓鴻宇

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

Inkwood研究表示，全球云存儲市場規模在2019-2027期間預計將以20.31%的復合年均增長率增長[1]。目前存儲系統可按網絡結構分為中心化存儲和去中心化存儲[2,3]。前者數據易泄露、價格相對昂貴；后者利用區塊鏈[4]等技術解決了安全、可信、可控的存儲要求。在這些系統內，糾刪碼[5,6]得到了應用。

常用的糾刪碼有RS碼[7,8]、局部修復編碼(LRC)[9,10]等。RS編碼滿足MDS[11]性質，能達到最高容錯能力；LRC通過減少磁盤I/O來降低修復帶寬。它們都運用在了中心化存儲系統中，然而去中心化環境中僅使用了低碼率的RS碼，如Storj中RS(40,20)[12]、Sia中RS(30,10)[13]。其原因在于兩者環境的差異：中心化存儲內是性能優、穩定且可信的節點；而去中心化存儲中卻是性能和可靠不定的節點(拜占庭攻擊[14])。

在去中心化存儲中，RS碼的可靠性基于所有節點不可信。然而實際的環境中，存在部分節點可信，這些節點將RS碼可靠性提升到了規定之上，側面體現出低碼率編碼浪費了可靠節點的資源。為合理利用可信節點的資源，可適當降低編碼的可靠性，讓改變后的編碼可靠性處于在采用RS編碼時所有節點不可信和部分節點可信的可靠性之間。基于此，提出了去中心化存儲中基于可信度的LRC-RS混合編碼。實驗結果表明，在同等的冗余度下，LRC-RS能有效地降低修復帶寬。

1 相關理論基礎

1.1 定 義

首先是相關性質定義：

性質1 將原始數據分為等大小的k份，進行編碼產生n-k個校驗，將數據擴大到n份并存儲到不同的n個節點上。任何k份數據都能恢復全部的n個節點中的數據。稱這種性質為MDS性質。

定義1 糾刪碼(Erasure coding，EC)：起源于通信傳輸領域，后逐漸應用到存儲系統中。它把數據分割成片段并對這些片段進行編碼，然后編碼后的數據存儲到不同位置的節點中。具有高磁盤利用率和高數據可靠性的優點。

定義2 一個碼的第i位具有局部性r(localityr)，則說明該位上的值可以通過讀取碼的其它不超過r個位上的值來修復。

定義4 失效率(LR)是對數據編碼后，數據失效的概率。

其次給出參數列表，方便后續討論。見表1。

表1 參數

1.2 RS碼

RS碼[15]是經典的MDS碼。一個(n,k)的RS線性碼，在給定的有限域中，能糾正n-k=2t個已知錯誤。其中k是原始數據的總數，t代表糾正未知錯誤的個數。

MT=(m1,m2,…,mk)、GT= [gj,i](0

(1)

解碼時，因RS的MDS性質，W中任意的k行都能恢復所有原始數據。若wf失效，應有

(2)

(3)

校驗節點丟失后下載原始數據，重新計算校驗。

1.3 LRC

為了減少糾刪碼中的磁盤I/O開銷，由Papailiopoulos等[16]分別提出局部修復編碼(locally repairable codes)，簡稱LRC，具體定義如定義1所示，使用符號集(n,k,r)表示。當r較小時，幫助節點的訪問量也較小，從而修復帶寬和磁盤I/O也較小。LRC碼是構建在RS之上來減少節點訪問量的編碼。Gopalan等指出C Huang等[17]提出的金字塔碼達到了其界限(定義3)。2012年，C Huang將金字塔碼大規模運用于微軟的Azure 云中[18]，節省了大量的帶寬資源。文中使用(n,k,l)的符號集來表示LRC。

圖1為一般的局部修復碼LRC(12,8,2)的結構。將8個數據塊用RS編碼得到2個校驗p1,p2，稱其為全局校驗塊(global parity block)，分別包含了所有8個原始數據塊的信息。接著將數據分為m1,…,m4和m5,…,m8兩組，由分組m1～4的數據節點產生校驗塊lp1,1，由分組m5～8的數據節點產生校驗塊lp1,2，稱由部分原始數據產生的校驗為局部校驗塊(local parity block)。在生成lp1,1時，將m5～8前的系數置為0，得到的校驗就是關于m1～4的；lp1,2同理。按照上訴方法，得到LRC(12,8,2)。易看出局部校驗只添加在數據節點之上。

圖1 Locally Repairable Codes的結構

1.4 編碼的可靠性

文獻[19]中給出了利用馬爾科夫模型計算編碼可靠性的方法。通過計算編碼的平均失效時間(MTTF)，從而知道該參數下編碼的可靠性。該文章指出節點的失效和修復均服從指數分布，與此同時又給出了利用馬爾科夫模型來計算編碼的可靠性的方法。該模型規定可用節點的數量由馬爾科夫鏈中的每個狀態決定，其中λ為單個節點失效的概率，ρ為單個節點被修復的概率，得到編碼的可靠性為

(4)

式中：n1,j為矩陣N中的元素，其中N=(I-Q)-1。I為單位矩陣、Q為轉移矩陣P去掉吸收狀態的行和列后的子矩陣。轉移矩陣P是關于λ和ρ的矩陣

式中：εi=iλ+ρi。

2 去中心化存儲中的LRC-RS碼

2.1 節點分類

2.1.1 節點特征

去中心化存儲系統因環境的異構性，將節點分為高可信節點和低可信節點。其特點是：高可信節點能夠提供高效服務；低可信節點不能提供穩定的服務。去中心化存儲系統中的每個節點都有自身的信用元數據信息，如通過歷史數據分析節點的在線時長、能提供的網絡帶寬大小、惡意攻擊次數、節點的提供方等。系統根據這些特點綜合考慮，給予不同的權重，求出編碼的可信度，根據這個值，將節點分為低可信節點和高可信節點。為適應所有節點，立即修復和延遲修復是常用的兩種修復方式[21]。其中立即修復用于高可信度節點，因為其可信任，需要馬上修復；延遲修復適用于低可信度節點，因為該類節點具有不確定性。特別是低可靠節點，在不影響系統冗余度的情況下，只要在規定的閾值期間能重新上線，都認為該節點上的數據沒有丟失。

2.1.2 可信節點數量

在RS碼的某個可靠性下，去中心化存儲系統中存在部分高可信節點和部分低可信節點。混合編碼是對高可信節點使用LRC，低可信度節點使用RS編碼，因此需要找到高可信度節點和低可信度節點的數量。

(5)

圖2 可信節點彈性變化的編碼架構

2.2 LRC-RS混合編碼

2.2.1 編碼結構

2.2.2 編碼過程

(6)

(7)

例子：LRC-RS(40,20,23,14,2)。其包含23個高可信節點和17個低可信節點。形成了LRC(23,14,2)和RS(17,6)的混合編碼。LRC中有23個節點，其中有14個系統節點{m1,m2,…,m14}，2個局部校驗{lp1,2,lp2,1}、7個全局校驗{p1～7}，按照式(6)和式(1)編碼，其中lpi,j=ci,j。剩下的17個低可信節點使用RS(17,6)編碼，將6個數據節點進行RS編碼得到17個數據。如圖3所示。對于高可信節點而言，需先按照RS(21,14)編碼產生全局校驗。然后將全局校驗p1和p2拆分，即p1=lp1,1+lp1,2、p2=lp2,1+lp2,2。

圖3 混合編碼LRC-RS(40,20,23,14,2)的編碼過程

局部校驗lpi,j的產生如圖4所示。每一組中有2個局部校驗，產生lp1,1,lp2,1將m8～14的系數置為0，產生lp1,2,lp2,2將m1～7置為0。按照這種變化后，局部編碼實際上就是RS(9,7)，每一組用于編碼的子生成矩陣為原生成矩陣對應行，并且lp1,1,lp2,2不存儲。

圖4 混合編碼中LRC(23,14,2)生成局部校驗

2.2.3 解碼過程

當節點丟失后，系統會指定替代節點利用網絡向幫助節點請求所需的數據，并利用其修復。若有低可信節點丟失，就利用RS的解碼算法進行解碼。若有高可信節點的節點丟失，解碼前需要衡量丟失的位置，并將丟失的節點分配到局部校驗或者全局校驗中，最后利用局部校驗或全局校驗修復失效的節點。分配方式分為3步：一是利用丟失的節點數量和位置來判斷能否解碼；第二步給有丟失節點的組中分得局部校驗可以解碼的數量；第三步將剩下的節點分攤到全局校驗節點上。如算法1所示。發生數據丟失后，有兩種情況不能解碼，分別是：一是丟失節點數量大于校驗節點的數量；二是某一組丟失節點的數量比全局校驗數量與組內局部校驗之和還大，如圖5(a)、圖5(b)所示。

算法1: LRC失效節點分配到校驗節點算法

輸入： 丟失節點數量sumL, 每組丟失的數量gloArr, 全局校驗數量glbP, 每組的局部校驗數量grPArr, 全局和局部校驗節點之和sumPX。

輸出： 解碼方式。

步驟1 判斷是否能夠解碼。

IF sumL > sumP THEN exit(0)

For gloArr i in gloArr

IF gloArr i > glbp THEN exit(0)

步驟2 分配局部校驗節點。 定義每組中需要全局校驗修復的數量globRepairArr

For gloArr i in grPArr

globRepairArri = gloArri-grPArri

步驟3 分配全局校驗節點。

For globRepairArri in globRepairArr

IF globRepairArri > 0 THEN

tempsum = tempsum+ globRepairArri

IF tempsum > ∑glbpiTHEN exit(0)

步驟4 返回丟失節點對應的解碼校驗集合。

圖5 丟失節點后不能修復的情況

同樣以LRC-RS(40,20,23,14,2)為例，LRC編碼中丟失m2,m3,m4,m7,m8,m9,m11,m12這8個節點。按照算法1的恢復方式進行分配失效節點。根據圖6可知，丟失的8個節點小于9個校驗節點且8個節點分布在不同的組，因此可以解碼。

修復第一組的m2,m3,m4,m7分兩步：先下載p1,lp1,2得到lp1,1，然后下載m1,m5,m6,p3,p4,lp2,1。利用lp1,1與lp2,1得到關于節點m1～7的兩個方程，利用p3,p4得到關于節點m1～14的兩個方程。同理修復第二組m8,m9,m11,m12也分為兩步：先下載p2,lp2,1得到lp2,2，再下載m10,m13,m14,p5,p6,lp1,2。利用lp1,2與lp2,2得到關于節點m8～14的兩個方程，利用p5,p6得到關于節點m1～14的兩個方程。綜上一共有8個線性無關的方程和8個未知數，解方程得到8個丟失節點。如圖7所示。

3 分 析

3.1 理論可靠性分析

混合編碼在減少下載帶寬的同時需要保證數據的可靠性。在2.1節中，根據節點的特征，驗證了高低可靠性節點分布在去中心化環境中。其中高可信節點的不易失效；低可信節點的失效的概率較高。在1.4節中，給出了根據節點失效概率計算整個編碼的可靠性的方法。將RS和LRC編碼通過馬爾科夫模型來模擬。假設使用RS和LRC編碼節點的失效概率λ和修復概率ρ相同，每個小時間片內只丟失或修復一個節點。現給出RS(10,6)和LRC(10,6,2)的馬爾科夫模型。根據參數可知RS能容忍任意4個節點失效，LRC能容忍任意的3個節點和86%[17]的任意4個節點失效。兩種編碼的馬爾科夫的狀態轉移圖分別如圖8(a)、圖8(b)所示，其中Pd=86%。

圖6 失效節點分配到校驗節點

圖7 混合編碼中LRC(23,14,2)恢復失效的8個節點的解碼過程

圖8 LRC和RS的馬爾科夫模型

在RS與LRC的n,k取值相同的情況下，來分析節點失效概率對可靠性的影響。現用rs_λ和lrc_λ分別表示RS和LRC的節點失效概率。分兩種情況：①當rs_λ=lrc_λ時，因RS能修復任意k個節點，而LRC只能修復任意k-1個節點和部分任意k個節點(l=2)，所以RS的可靠性高于LRC的可靠性；②當rs_λ>lrc_λ時，RS的節點失效概率變大，而LRC節點的失效概率減小或不變，當rs_λ增加到一個臨界值，RS的可靠性將會低于LRC的可靠性。

3.2 實驗可靠性分析

保證與RS(40,20)具有相同的n，k參數結構，來比較RS碼與混合編碼的可靠性。參數見文獻[20]，RS編碼中λ=0.03；LRC-RS混合編碼中的LRC碼的節點失效概率lrc_λ=0.03，RS碼的節點失效概率rs_λ=0.034。如表2所示。從表中可以看出，利用LRC-RS(40,20,23,14,2)混合編碼的MTTF值均大于RS編碼的MTTF值，可以得出混合編碼的可靠性更高，滿足目前工程上所能容忍的失效率。

表2 LRC-RS(40,20,23,14,2)與RS(40,20)可靠性對比

3.3 總修復下載量

LRC-RS混合編碼通過減少節點訪問量來降低數據修復的總下載帶寬。現以例子來對比在相同的節點數量、冗余度和失效節點數量下兩種編碼的修復帶寬。由于混合編碼的失效節點數量會分布在兩種編碼中，因此將所有分布的情況進行排列組合，選取下載量最大的作為比較對象。如圖9所示，LRC-RS(40,20,23,14,2)的總修復下載量處于[7,192]的范圍以內，最小的下載量為丟失一個節點，需要下載7個節點；最大下載量是一共丟失20個節點，需要下載192個節點。RS(40,20)編碼的總修復下載量處于[20,400]的范圍以內，最少的下載量是丟失一個節，需要下載20個節點；最多是丟失20個節點，需要下載400個節點。

圖9 混合編碼LRC-RS與RS碼的總修復下載量對比

4 結束語

針對去中心化存儲中節點的異構性，給出了LRC碼在去中心化環境中詳細的編解碼的算法，并對LRC碼中節點如何存儲進行了詳細的闡述[21]。通過使用LRC編碼，改善了RS中修復一塊數據需要下載k倍數量級的數據的問題。雖然兩種編碼同時運用在同一個去中心化系統會增加少量的編解碼的復雜度，但是LRC-RS混合編碼在數據的下載量(修復帶寬)上的明顯優勢讓其非常值得。最后，它不僅能夠降低網絡中的修復帶寬，同時帶來了可觀的經濟效益。