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

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

Inkwood研究表示，全球云存儲(chǔ)市場(chǎng)規(guī)模在2019-2027期間預(yù)計(jì)將以20.31%的復(fù)合年均增長(zhǎng)率增長(zhǎng)[1]。目前存儲(chǔ)系統(tǒng)可按網(wǎng)絡(luò)結(jié)構(gòu)分為中心化存儲(chǔ)和去中心化存儲(chǔ)[2,3]。前者數(shù)據(jù)易泄露、價(jià)格相對(duì)昂貴；后者利用區(qū)塊鏈[4]等技術(shù)解決了安全、可信、可控的存儲(chǔ)要求。在這些系統(tǒng)內(nèi)，糾刪碼[5,6]得到了應(yīng)用。

常用的糾刪碼有RS碼[7,8]、局部修復(fù)編碼(LRC)[9,10]等。RS編碼滿足MDS[11]性質(zhì)，能達(dá)到最高容錯(cuò)能力；LRC通過(guò)減少磁盤(pán)I/O來(lái)降低修復(fù)帶寬。它們都運(yùn)用在了中心化存儲(chǔ)系統(tǒng)中，然而去中心化環(huán)境中僅使用了低碼率的RS碼，如Storj中RS(40,20)[12]、Sia中RS(30,10)[13]。其原因在于兩者環(huán)境的差異：中心化存儲(chǔ)內(nèi)是性能優(yōu)、穩(wěn)定且可信的節(jié)點(diǎn)；而去中心化存儲(chǔ)中卻是性能和可靠不定的節(jié)點(diǎn)(拜占庭攻擊[14])。

在去中心化存儲(chǔ)中，RS碼的可靠性基于所有節(jié)點(diǎn)不可信。然而實(shí)際的環(huán)境中，存在部分節(jié)點(diǎn)可信，這些節(jié)點(diǎn)將RS碼可靠性提升到了規(guī)定之上，側(cè)面體現(xiàn)出低碼率編碼浪費(fèi)了可靠節(jié)點(diǎn)的資源。為合理利用可信節(jié)點(diǎn)的資源，可適當(dāng)降低編碼的可靠性，讓改變后的編碼可靠性處于在采用RS編碼時(shí)所有節(jié)點(diǎn)不可信和部分節(jié)點(diǎn)可信的可靠性之間?；诖耍岢隽巳ブ行幕鎯?chǔ)中基于可信度的LRC-RS混合編碼。實(shí)驗(yàn)結(jié)果表明，在同等的冗余度下，LRC-RS能有效地降低修復(fù)帶寬。

1 相關(guān)理論基礎(chǔ)

1.1 定 義

首先是相關(guān)性質(zhì)定義：

性質(zhì)1 將原始數(shù)據(jù)分為等大小的k份，進(jìn)行編碼產(chǎn)生n-k個(gè)校驗(yàn)，將數(shù)據(jù)擴(kuò)大到n份并存儲(chǔ)到不同的n個(gè)節(jié)點(diǎn)上。任何k份數(shù)據(jù)都能恢復(fù)全部的n個(gè)節(jié)點(diǎn)中的數(shù)據(jù)。稱這種性質(zhì)為MDS性質(zhì)。

定義1 糾刪碼(Erasure coding，EC)：起源于通信傳輸領(lǐng)域，后逐漸應(yīng)用到存儲(chǔ)系統(tǒng)中。它把數(shù)據(jù)分割成片段并對(duì)這些片段進(jìn)行編碼，然后編碼后的數(shù)據(jù)存儲(chǔ)到不同位置的節(jié)點(diǎn)中。具有高磁盤(pán)利用率和高數(shù)據(jù)可靠性的優(yōu)點(diǎn)。

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

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

其次給出參數(shù)列表，方便后續(xù)討論。見(jiàn)表1。

表1 參數(shù)

1.2 RS碼

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

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

(1)

解碼時(shí)，因RS的MDS性質(zhì)，W中任意的k行都能恢復(fù)所有原始數(shù)據(jù)。若wf失效，應(yīng)有

(2)

(3)

校驗(yàn)節(jié)點(diǎn)丟失后下載原始數(shù)據(jù)，重新計(jì)算校驗(yàn)。

1.3 LRC

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

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

圖1 Locally Repairable Codes的結(jié)構(gòu)

1.4 編碼的可靠性

文獻(xiàn)[19]中給出了利用馬爾科夫模型計(jì)算編碼可靠性的方法。通過(guò)計(jì)算編碼的平均失效時(shí)間(MTTF)，從而知道該參數(shù)下編碼的可靠性。該文章指出節(jié)點(diǎn)的失效和修復(fù)均服從指數(shù)分布，與此同時(shí)又給出了利用馬爾科夫模型來(lái)計(jì)算編碼的可靠性的方法。該模型規(guī)定可用節(jié)點(diǎn)的數(shù)量由馬爾科夫鏈中的每個(gè)狀態(tài)決定，其中λ為單個(gè)節(jié)點(diǎn)失效的概率，ρ為單個(gè)節(jié)點(diǎn)被修復(fù)的概率，得到編碼的可靠性為

(4)

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

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

2 去中心化存儲(chǔ)中的LRC-RS碼

2.1 節(jié)點(diǎn)分類(lèi)

2.1.1 節(jié)點(diǎn)特征

去中心化存儲(chǔ)系統(tǒng)因環(huán)境的異構(gòu)性，將節(jié)點(diǎn)分為高可信節(jié)點(diǎn)和低可信節(jié)點(diǎn)。其特點(diǎn)是：高可信節(jié)點(diǎn)能夠提供高效服務(wù)；低可信節(jié)點(diǎn)不能提供穩(wěn)定的服務(wù)。去中心化存儲(chǔ)系統(tǒng)中的每個(gè)節(jié)點(diǎn)都有自身的信用元數(shù)據(jù)信息，如通過(guò)歷史數(shù)據(jù)分析節(jié)點(diǎn)的在線時(shí)長(zhǎng)、能提供的網(wǎng)絡(luò)帶寬大小、惡意攻擊次數(shù)、節(jié)點(diǎn)的提供方等。系統(tǒng)根據(jù)這些特點(diǎn)綜合考慮，給予不同的權(quán)重，求出編碼的可信度，根據(jù)這個(gè)值，將節(jié)點(diǎn)分為低可信節(jié)點(diǎn)和高可信節(jié)點(diǎn)。為適應(yīng)所有節(jié)點(diǎn)，立即修復(fù)和延遲修復(fù)是常用的兩種修復(fù)方式[21]。其中立即修復(fù)用于高可信度節(jié)點(diǎn)，因?yàn)槠淇尚湃?，需要馬上修復(fù)；延遲修復(fù)適用于低可信度節(jié)點(diǎn)，因?yàn)樵擃?lèi)節(jié)點(diǎn)具有不確定性。特別是低可靠節(jié)點(diǎn)，在不影響系統(tǒng)冗余度的情況下，只要在規(guī)定的閾值期間能重新上線，都認(rèn)為該節(jié)點(diǎn)上的數(shù)據(jù)沒(méi)有丟失。

2.1.2 可信節(jié)點(diǎn)數(shù)量

在RS碼的某個(gè)可靠性下，去中心化存儲(chǔ)系統(tǒng)中存在部分高可信節(jié)點(diǎn)和部分低可信節(jié)點(diǎn)?；旌暇幋a是對(duì)高可信節(jié)點(diǎn)使用LRC，低可信度節(jié)點(diǎn)使用RS編碼，因此需要找到高可信度節(jié)點(diǎn)和低可信度節(jié)點(diǎn)的數(shù)量。

(5)

圖2 可信節(jié)點(diǎn)彈性變化的編碼架構(gòu)

2.2 LRC-RS混合編碼

2.2.1 編碼結(jié)構(gòu)

2.2.2 編碼過(guò)程

(6)

(7)

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

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

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

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

2.2.3 解碼過(guò)程

當(dāng)節(jié)點(diǎn)丟失后，系統(tǒng)會(huì)指定替代節(jié)點(diǎn)利用網(wǎng)絡(luò)向幫助節(jié)點(diǎn)請(qǐng)求所需的數(shù)據(jù)，并利用其修復(fù)。若有低可信節(jié)點(diǎn)丟失，就利用RS的解碼算法進(jìn)行解碼。若有高可信節(jié)點(diǎn)的節(jié)點(diǎn)丟失，解碼前需要衡量丟失的位置，并將丟失的節(jié)點(diǎn)分配到局部校驗(yàn)或者全局校驗(yàn)中，最后利用局部校驗(yàn)或全局校驗(yàn)修復(fù)失效的節(jié)點(diǎn)。分配方式分為3步：一是利用丟失的節(jié)點(diǎn)數(shù)量和位置來(lái)判斷能否解碼；第二步給有丟失節(jié)點(diǎn)的組中分得局部校驗(yàn)可以解碼的數(shù)量；第三步將剩下的節(jié)點(diǎn)分?jǐn)偟饺中ｒ?yàn)節(jié)點(diǎn)上。如算法1所示。發(fā)生數(shù)據(jù)丟失后，有兩種情況不能解碼，分別是：一是丟失節(jié)點(diǎn)數(shù)量大于校驗(yàn)節(jié)點(diǎn)的數(shù)量；二是某一組丟失節(jié)點(diǎn)的數(shù)量比全局校驗(yàn)數(shù)量與組內(nèi)局部校驗(yàn)之和還大，如圖5(a)、圖5(b)所示。

算法1: LRC失效節(jié)點(diǎn)分配到校驗(yàn)節(jié)點(diǎn)算法

輸入： 丟失節(jié)點(diǎn)數(shù)量sumL, 每組丟失的數(shù)量gloArr, 全局校驗(yàn)數(shù)量glbP, 每組的局部校驗(yàn)數(shù)量grPArr, 全局和局部校驗(yàn)節(jié)點(diǎn)之和sumPX。

輸出： 解碼方式。

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

IF sumL > sumP THEN exit(0)

For gloArr i in gloArr

IF gloArr i > glbp THEN exit(0)

步驟2 分配局部校驗(yàn)節(jié)點(diǎn)。 定義每組中需要全局校驗(yàn)修復(fù)的數(shù)量globRepairArr

For gloArr i in grPArr

globRepairArri = gloArri-grPArri

步驟3 分配全局校驗(yàn)節(jié)點(diǎn)。

For globRepairArri in globRepairArr

IF globRepairArri > 0 THEN

tempsum = tempsum+ globRepairArri

IF tempsum > ∑glbpiTHEN exit(0)

步驟4 返回丟失節(jié)點(diǎn)對(duì)應(yīng)的解碼校驗(yàn)集合。

圖5 丟失節(jié)點(diǎn)后不能修復(fù)的情況

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

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

3 分 析

3.1 理論可靠性分析

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

圖6 失效節(jié)點(diǎn)分配到校驗(yàn)節(jié)點(diǎn)

圖7 混合編碼中LRC(23,14,2)恢復(fù)失效的8個(gè)節(jié)點(diǎn)的解碼過(guò)程

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

在RS與LRC的n,k取值相同的情況下，來(lái)分析節(jié)點(diǎn)失效概率對(duì)可靠性的影響?，F(xiàn)用rs_λ和lrc_λ分別表示RS和LRC的節(jié)點(diǎn)失效概率。分兩種情況：①當(dāng)rs_λ=lrc_λ時(shí)，因RS能修復(fù)任意k個(gè)節(jié)點(diǎn)，而LRC只能修復(fù)任意k-1個(gè)節(jié)點(diǎn)和部分任意k個(gè)節(jié)點(diǎn)(l=2)，所以RS的可靠性高于LRC的可靠性；②當(dāng)rs_λ>lrc_λ時(shí)，RS的節(jié)點(diǎn)失效概率變大，而LRC節(jié)點(diǎn)的失效概率減小或不變，當(dāng)rs_λ增加到一個(gè)臨界值，RS的可靠性將會(huì)低于LRC的可靠性。

3.2 實(shí)驗(yàn)可靠性分析

保證與RS(40,20)具有相同的n，k參數(shù)結(jié)構(gòu)，來(lái)比較RS碼與混合編碼的可靠性。參數(shù)見(jiàn)文獻(xiàn)[20]，RS編碼中λ=0.03；LRC-RS混合編碼中的LRC碼的節(jié)點(diǎn)失效概率lrc_λ=0.03，RS碼的節(jié)點(diǎn)失效概率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)可靠性對(duì)比

3.3 總修復(fù)下載量

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

圖9 混合編碼LRC-RS與RS碼的總修復(fù)下載量對(duì)比

4 結(jié)束語(yǔ)

針對(duì)去中心化存儲(chǔ)中節(jié)點(diǎn)的異構(gòu)性，給出了LRC碼在去中心化環(huán)境中詳細(xì)的編解碼的算法，并對(duì)LRC碼中節(jié)點(diǎn)如何存儲(chǔ)進(jìn)行了詳細(xì)的闡述[21]。通過(guò)使用LRC編碼，改善了RS中修復(fù)一塊數(shù)據(jù)需要下載k倍數(shù)量級(jí)的數(shù)據(jù)的問(wèn)題。雖然兩種編碼同時(shí)運(yùn)用在同一個(gè)去中心化系統(tǒng)會(huì)增加少量的編解碼的復(fù)雜度，但是LRC-RS混合編碼在數(shù)據(jù)的下載量(修復(fù)帶寬)上的明顯優(yōu)勢(shì)讓其非常值得。最后，它不僅能夠降低網(wǎng)絡(luò)中的修復(fù)帶寬，同時(shí)帶來(lái)了可觀的經(jīng)濟(jì)效益。