基于多斜率碼鏈的陣列糾刪碼

唐 聃,楊昊澎,王福超

成都信息工程大學(xué) 軟件工程學(xué)院,成都 610225)(*通信作者電子郵箱tangdan@foxmail.com)

基于多斜率碼鏈的陣列糾刪碼

唐 聃*,楊昊澎,王福超

成都信息工程大學(xué) 軟件工程學(xué)院,成都 610225)(*通信作者電子郵箱tangdan@foxmail.com)

針對當(dāng)前大多陣列糾刪碼容錯能力偏低以及構(gòu)造時需要滿足的約束條件較強(qiáng)的問題,提出一類基于碼鏈構(gòu)造的陣列糾刪碼。該陣列糾刪碼使用不同斜率碼鏈組織數(shù)據(jù)元素和校驗(yàn)元素間的關(guān)系,從而能達(dá)到理論上不受限制的容錯能力；而在構(gòu)造時避開了類似素數(shù)約束的強(qiáng)約束條件,易于實(shí)用和擴(kuò)展。仿真實(shí)驗(yàn)結(jié)果表明,相對于RS(Reed-Solomon)碼,基于多斜率碼鏈陣列糾刪碼在運(yùn)算效率上的提升超過了2個數(shù)量級；在固定的容錯能力下,存儲效率能隨著條塊尺寸的增加而提高。此外,該類陣列碼的修復(fù)代價和更新代價為一個固定常量,不會隨著系統(tǒng)規(guī)模的擴(kuò)大或容錯能力的提高而增加。

陣列糾刪碼;容錯;碼鏈;條塊尺寸

0 引言

當(dāng)前,我們已經(jīng)跨入到了大數(shù)據(jù)的時代,各個行業(yè)領(lǐng)域產(chǎn)生的數(shù)據(jù)正爆炸式地持續(xù)增長,與之伴隨的是越來越多的數(shù)據(jù)成為了社會正常運(yùn)行不可或缺的部分。為應(yīng)對由數(shù)據(jù)量的快速增長而帶來的數(shù)據(jù)存儲可靠性問題,不斷提高單個存儲節(jié)點(diǎn)的穩(wěn)定性當(dāng)然是一種理論可行的方法；但更加有效的做法是使用多個存儲節(jié)點(diǎn)共同構(gòu)建一個存儲系統(tǒng),這樣做除了能充分利用既有設(shè)備、增加存儲容量、提高數(shù)據(jù)并行訪問效率外,結(jié)合一定的容錯策略后還能有效增強(qiáng)存儲系統(tǒng)的整體可靠性。在這種情況下,通常使用存儲節(jié)點(diǎn)的數(shù)量來表示存儲系統(tǒng)的規(guī)模。目前節(jié)點(diǎn)數(shù)目超過100的大規(guī)模存儲系統(tǒng)已經(jīng)日益普遍,而谷歌等公司甚至已經(jīng)擁有了多個節(jié)點(diǎn)數(shù)目超過3 000的PB級存儲系統(tǒng)[1]。與過去相比,盡管當(dāng)前單個存儲節(jié)點(diǎn)的可靠性已經(jīng)很高,但是在擁有眾多節(jié)點(diǎn)的大規(guī)模存儲系統(tǒng)中,一個時間段內(nèi)多個節(jié)點(diǎn)失效的概率依然很高。據(jù)卡內(nèi)基梅隆大學(xué)的統(tǒng)計數(shù)據(jù)顯示,節(jié)點(diǎn)數(shù)超過300的大規(guī)模存儲系統(tǒng)中存儲節(jié)點(diǎn)每年的失效替換率約為5.1%[2]。當(dāng)然,這還是存儲系統(tǒng)在正常使用狀況下的節(jié)點(diǎn)失效概率,如果再將洪水、泥石流、地震等自然災(zāi)害和黑客攻擊等人為因素考慮在內(nèi)的話,存儲系統(tǒng)的容錯及可靠性增強(qiáng)就更是一個值得關(guān)注的問題。

副本技術(shù)是目前在存儲系統(tǒng)可靠性增強(qiáng)領(lǐng)域中最為成熟的容錯技術(shù)。采用副本技術(shù)的容錯方案將多個相同的數(shù)據(jù)副本存儲到系統(tǒng)的不同節(jié)點(diǎn)上,由于每個節(jié)點(diǎn)的副本完全相同,通常可不嚴(yán)格區(qū)分校驗(yàn)數(shù)據(jù)(冗余數(shù)據(jù))和原始數(shù)據(jù),當(dāng)有節(jié)點(diǎn)失效時,由任意一個未失效節(jié)點(diǎn)中的副本都能恢復(fù)出丟失數(shù)據(jù)。使用副本技術(shù)的容錯方法簡單直觀、易于實(shí)現(xiàn)及動態(tài)擴(kuò)展,但是存儲效率過低卻是其巨大的缺陷。假設(shè)使用副本技術(shù)構(gòu)造一個t容錯的存儲系統(tǒng),則需要將原始數(shù)據(jù)復(fù)制成t+1份副本分別存放到不同的節(jié)點(diǎn)上,即存儲效率僅為1/(t+1)。顯然,這種極低的存儲空間有效利用率是大規(guī)模存儲系統(tǒng)難以接受的。因?yàn)榇鎯ο到y(tǒng)作為一個整體,不能僅僅考慮某一項性能參數(shù),而應(yīng)根據(jù)應(yīng)用環(huán)境兼顧大多重要性能指標(biāo)。糾刪碼可以在一定程度上平衡存儲系統(tǒng)中的多種主要性能,是一種日益受到重視的存儲系統(tǒng)容錯方法。目前,用于存儲系統(tǒng)容錯的糾刪碼主要包括了RS類糾刪碼(Reed-SolomonErasureCodes)、LDPC(Low-DensityParity-CheckCodes)類糾刪碼，以及陣列糾刪碼。RS類糾刪碼是目前唯一一類容錯能力不受限制且具備MDS(MaximumDistanceSeparable)性質(zhì)的糾刪碼,但其編譯碼等運(yùn)算均在多元有限域上進(jìn)行,計算復(fù)雜度非常高,特別是多元域上的乘法和求逆。因此,以RS類糾刪碼為核心構(gòu)建存儲系統(tǒng)的容錯方法需要解決的主要問題不是優(yōu)化編碼,而是如何大幅提高有限域的計算效率。當(dāng)然,目前也有一些研究者針對這一問題進(jìn)行了卓有成效的工作,其中最具代表性的工作為Plank等[3]提出的RS碼有限域降階運(yùn)算方案,以及有限域運(yùn)算庫GF-Complete[4]。盡管如此,目前RS碼的運(yùn)算效率仍然很難滿足存儲系統(tǒng)整體運(yùn)行性能的需要,特別是大規(guī)模存儲系統(tǒng)。LDPC碼是源于通信領(lǐng)域的一類糾刪碼,其編碼和譯碼過程完全基于異或運(yùn)算,與RS碼相比,其糾刪能力不受限且運(yùn)算效率還要高出幾個數(shù)量級。但是,LDPC碼的碼字結(jié)構(gòu)不規(guī)則和成功譯碼的概率性卻增加了根據(jù)應(yīng)用環(huán)境需求設(shè)計出與之適應(yīng)編碼的難度。目前基于LDPC碼的容錯方法在實(shí)際存儲系統(tǒng)中的應(yīng)用很少,已有方法多是以理論研究或?qū)嶒?yàn)為主[5]。

陣列糾刪碼(通常簡稱為陣列碼)是編譯碼運(yùn)算均使用二元域上異或運(yùn)算的一類糾刪碼,運(yùn)算效率很高,具有的二維編碼結(jié)構(gòu)可完全對應(yīng)當(dāng)前多節(jié)點(diǎn)存儲系統(tǒng)的數(shù)據(jù)布局結(jié)構(gòu),因此很適合在存儲系統(tǒng)中使用。但陣列碼在商用存儲系統(tǒng)中的使用卻非常少,究其原因可以歸納為如下。一是當(dāng)前陣列碼容錯能力普遍偏低,具備MDS性質(zhì)的陣列碼的最大容錯能力通常為2和3[6-9];即使是非MDS的陣列碼,在付出了不少的其他性能代價后,最大容錯能力也大多沒有超過20[10-13]。此外,當(dāng)前大多陣列碼在構(gòu)造時還對存儲陣列尺寸有較強(qiáng)的限制條件,最典型的是素數(shù)限制,即要求存儲系統(tǒng)的條帶或條帶尺寸為一個素數(shù)或者和素數(shù)嚴(yán)格地保持某種線性關(guān)系,EVENODD碼[6]、X碼[7]、Star碼[8]和擴(kuò)展X碼[9]等陣列碼在構(gòu)造時都存在素數(shù)限制。其他一些陣列碼在構(gòu)造時的沒有這么強(qiáng)的限制條件[10-11],但卻付出了很大的其他性能代價而降低了實(shí)用性。比如容錯能力達(dá)12以上的Weaver碼[10],該碼在構(gòu)造時就無需滿足素數(shù)限制,但其存儲效率始終低于50%,且還會隨著容錯能力的提升而迅速下降。文獻(xiàn)[14]提出的陣列碼構(gòu)造方法可以構(gòu)造出容錯能力在理論上沒有限制的陣列碼,構(gòu)造時也無需滿足很強(qiáng)的限制條件,但具體構(gòu)造步驟卻沒有明確指出。

針對陣列碼存在的這些問題,本文提出了一類新的陣列糾刪碼,該碼基于不同斜率的碼鏈構(gòu)造,能根據(jù)應(yīng)用環(huán)境需求預(yù)先設(shè)置容錯數(shù)量,且容錯能力在理論上不受限制。雖然不具備MDS性質(zhì),但該陣列碼的存儲效率能在不影響容錯能力等重要性能的前提下,隨著條塊尺寸的增加而不斷提高。此外,該碼在構(gòu)造時也無需滿足素數(shù)限制這樣的強(qiáng)約束條件,已基本具備在存儲系統(tǒng)中使用的條件。

1 基本概念和定義

在存儲編碼領(lǐng)域的常用基本概念,如數(shù)據(jù)、校驗(yàn)、冗余、元素、條帶、條塊、水平陣列碼、垂直陣列碼、編碼、譯碼、數(shù)據(jù)重構(gòu)等,本文將繼續(xù)沿用這些概念的定義而不再贅述[10-13]。下面給出的一些符號和概念的定義則是為了配合說明本文方法而提出的。

碼鏈 陣列碼是一類線性碼,因此在陣列碼中,任意一個校驗(yàn)元素均由t個數(shù)據(jù)元素的異或相加得到,換句話說,一個校驗(yàn)元素與生成它的所有數(shù)據(jù)元素的異或和為0。而上述元素像一個鏈條一樣分布于存儲陣列中,為敘述方便而簡稱為碼鏈,也可稱為編碼鏈或校驗(yàn)鏈。而部署碼鏈則是將碼鏈上所有的數(shù)據(jù)元素進(jìn)行異或求和,得到對應(yīng)校驗(yàn)元素并存儲于相應(yīng)位置的過程。

斜率 將存儲系統(tǒng)的數(shù)據(jù)陣列部分(假設(shè)尺寸為m×n,其中m和n均為大于1 的正整數(shù))看作一個二維坐標(biāo)系,以向右的水平軸作為坐標(biāo)系的正向X軸,以向下的垂直軸作為坐標(biāo)系的正向Y軸,則所有數(shù)據(jù)陣列中的元素成為了該坐標(biāo)系上擁有固定坐標(biāo)的一個點(diǎn),假設(shè)一條碼鏈上所有存在于數(shù)據(jù)陣列部分的元素坐標(biāo)為(x1,y1),(x2,y2),…,(xt,yt),若這些元素的坐標(biāo)滿足條件(1)則稱該碼鏈存在斜率,且將斜率定義為s=((y2-y1)%n)/(x2-x1)。

(y2-y1)%n=(y3-y2)%n=…=(yt-yt-1)%n

(1)

圖1展示了如何部署一條斜率為1的碼鏈。其中,所有背景色相同的元素異或和為0,共同構(gòu)成一條完整碼鏈。

圖1 斜率為1的碼鏈

El(i,j):該符號用于標(biāo)識存儲陣列中第i行第j列的元素,當(dāng)有多個元素需要表示時,可以使用符號“:”表示出一個范圍區(qū)間,如El(i,2:5)表示存儲陣列第i行上的第2到5個元素集合,El(:,j)則用于表示陣列中第j列的所有元素。

2 基于多斜率碼鏈的陣列碼

垂直陣列碼的數(shù)據(jù)布局結(jié)構(gòu)中,同一條塊中既存儲有數(shù)據(jù)元素又存儲有冗余元素,具有很好的負(fù)載平衡性,但節(jié)點(diǎn)間數(shù)據(jù)的相互依賴性很強(qiáng),不便于擴(kuò)展,因此本文的新方法采用了典型的水平陣列布局。關(guān)于陣列碼的構(gòu)造方法有很多,常見的包括圖論構(gòu)造法、RS糾刪碼映射法、代數(shù)模型構(gòu)造方法和幾何構(gòu)造法等。這幾種陣列糾刪碼的構(gòu)造方法各有優(yōu)點(diǎn),其中使用幾何形式的構(gòu)造方法具有最高的計算效率且更加易于計算機(jī)軟硬件實(shí)現(xiàn)。而本文采用的基于不同斜率碼鏈來組織數(shù)據(jù)元素和校驗(yàn)元素間關(guān)系的方法就是最典型的一種幾何構(gòu)造法。

2.1 編碼及數(shù)據(jù)重構(gòu)方法

如前所述,為了減少數(shù)據(jù)及冗余元素間的相互依賴性,文章采用了典型的水平式陣列結(jié)構(gòu)布局。假設(shè)存儲系統(tǒng)節(jié)點(diǎn)的容錯數(shù)量為f,陣列的行數(shù)為m,數(shù)據(jù)陣列部分的列數(shù)為n,冗余陣列部分的列數(shù)為r,顯然f、m、r為正整數(shù),且m≥2。整個存儲陣列的尺寸為m×(n+r)。若無特別說明,下文在敘述過程中的符號f、m、n、r具有和本段描述相同的含義。

在構(gòu)造一個f容錯的水平陣列碼時,可在數(shù)據(jù)陣列部分部署斜率從1開始,并從正負(fù)雙向漸進(jìn)擴(kuò)大的碼鏈f條,顯然所有碼鏈部署完成后將產(chǎn)生冗余元素f·n個,然后將這些冗余元素按照列優(yōu)先原則順序放置于各校驗(yàn)節(jié)點(diǎn)上。使用符號d(i,j)來表示數(shù)據(jù)陣列部分中第i行第j列所對應(yīng)的元素,而直接使用c(t)表示校驗(yàn)陣列部分的第t個元素,則存儲陣列各元素的標(biāo)識如圖2所示。其中：i、j、t為正整數(shù),且1≤i≤m,1≤j≤n,1≤t≤f·n。

圖2 存儲陣列的元素標(biāo)識

在上述數(shù)據(jù)元素和冗余元素的標(biāo)識體系下,任意一個校驗(yàn)元素均可使用式(2)計算得出：

(2)

其中：運(yùn)算符“「?”表示向上取整；“%”表示取模;lr表示產(chǎn)生當(dāng)前校驗(yàn)元素使用的是第lr條碼鏈；lc則表示該條碼鏈?zhǔn)堑趌c次被使用。lr和lc的計算公式如下：

lr=[(t-1)/n]+1

(3)

lc=(t-1)%n+1

(4)

例1 對一個最大容錯能力為3,且條塊尺寸為3的存儲陣列部署碼鏈,其中該存儲陣列的數(shù)據(jù)陣列部分有7列。

如前所述,最大容錯能力f為3,數(shù)據(jù)陣列部分的尺寸為3×7,則校驗(yàn)元素的數(shù)目為21個,因此校驗(yàn)陣列部分的列數(shù)也為7。最大容錯能力為3,因此需要部署斜率為1、-1、2的碼鏈各一條,具體部署過程如圖3所示,其中背景色相同的元素異或和為0。

圖3 斜率為1、-1、2的碼鏈部署

用本文方法可以很容易地根據(jù)應(yīng)用環(huán)境需求構(gòu)造出任意容錯能力的陣列碼。而接下來將簡要介紹當(dāng)有節(jié)點(diǎn)失效后如何進(jìn)行恢復(fù)重構(gòu)。需要說明的是,本文僅考慮節(jié)點(diǎn)錯誤的情況,即整個存儲節(jié)點(diǎn)失效而導(dǎo)致該節(jié)點(diǎn)上所有數(shù)據(jù)元素的丟失,這也對應(yīng)存儲陣列中整列的數(shù)據(jù)失效。失效節(jié)點(diǎn)上數(shù)據(jù)恢復(fù)的基本思想可以歸結(jié)為一句話,即尋找只存在唯一一個失效元素的碼鏈,顯然該碼鏈上的失效元素可由其他有效元素計算恢復(fù)。不斷重復(fù)這一過程,直到所有失效元素被恢復(fù)。

例2 假設(shè)在例1所示的存儲系統(tǒng)中節(jié)點(diǎn)1、3、5失效,即在將失效節(jié)點(diǎn)替換更新后,存儲陣列中數(shù)據(jù)陣列部分的1、3、5列上的元素數(shù)值變得未知,整個數(shù)據(jù)恢復(fù)過程如圖4所示。其中有“X”標(biāo)識的元素表示數(shù)值未知的失效元素,而具有相同背景色的元素為僅有一個失效元素的碼鏈,將該碼鏈上其他元素進(jìn)行異或相加可恢復(fù)失效元素。

圖4 失效數(shù)據(jù)的成功恢復(fù)過程

繼續(xù)擴(kuò)展例2,假設(shè)數(shù)據(jù)陣列部分的尺寸為,仍然是1、3、5列上的元素失效。然而,如圖5所示,此時卻無法找出任何一條僅包含一個失效元素的碼鏈。在此情況下,該存儲系統(tǒng)中所有的數(shù)據(jù)丟失。

1.2.1 觀察組和對照組在院期間均進(jìn)行常規(guī)的術(shù)后自我護(hù)理知識宣教、免費(fèi)發(fā)放宣教資料等進(jìn)行造口護(hù)理指導(dǎo)。

圖5 失敗的數(shù)據(jù)恢復(fù)

2.2 約束條件及容錯能力保證

從例2可以得出如下結(jié)論,如果需要使得條塊尺寸為3的存儲陣列容錯能力達(dá)到3,除了需要部署3條斜率不同的碼鏈外,數(shù)據(jù)陣列部分的列數(shù)至少不能小于7,否則將無法保證容錯能力。將這一結(jié)論進(jìn)一步擴(kuò)展,即僅僅使用不同斜率的f條碼鏈來構(gòu)造陣列碼不能保證容錯能力一定是f,容錯數(shù)量和陣列尺寸還需要滿足某種條件。在此,首先給出容錯能力f、條塊尺寸m和數(shù)據(jù)陣列部分列數(shù)n應(yīng)滿足的條件:n≥m·f-f+1。下面將證明在滿足該約束條件的情況下,容錯能力就可以得到保證。

對于水平布局的陣列碼,節(jié)點(diǎn)級錯誤的發(fā)生情況可以分為如下三種:一是全部失效節(jié)點(diǎn)在校驗(yàn)陣列部分,二是校驗(yàn)陣列部分和數(shù)據(jù)陣列部分均有失效節(jié)點(diǎn),三是失效節(jié)點(diǎn)全部在數(shù)據(jù)陣列部分。當(dāng)所有失效節(jié)點(diǎn)都發(fā)生于校驗(yàn)陣列部分時,僅僅需要在替換失效節(jié)點(diǎn)后重新做一次編碼操作即可,這是數(shù)據(jù)重構(gòu)最簡單的情況。當(dāng)數(shù)據(jù)陣列部分和校驗(yàn)陣列部分都有失效節(jié)點(diǎn)出現(xiàn)時,也相對容易處理。在f容錯的陣列碼中,每個數(shù)據(jù)元素均有f條碼鏈通過,因此一個數(shù)據(jù)元素與f個校驗(yàn)元素相關(guān)。根據(jù)約束條件可知,n>m,所以兩個與同一數(shù)據(jù)元素相關(guān)的校驗(yàn)元素一定不會出現(xiàn)在同一列。由此,所有數(shù)據(jù)陣列部分的失效元素可以被全部恢復(fù),之后再根據(jù)編碼方法就可以將校驗(yàn)陣列部分的全部失效元素恢復(fù)。而對于f個失效節(jié)點(diǎn)全部存在于數(shù)據(jù)陣列部分的情況,下面將采用數(shù)學(xué)歸納法進(jìn)行證明。

首先,不妨將數(shù)據(jù)陣列部分f個失效列記作E1,E2,…,Ef,其中di記為錯誤列Ei與其右鄰失效列之間的距離, 不妨假設(shè)max(d1,d2,…,df)=df,其中i=1,2,…,f。因此,由鴿籠原理可知,df≥m成立。當(dāng)f=1時,即僅有一個失效列時,將該列記作E1。由碼鏈部署方法可知,每一個數(shù)據(jù)元素均有一條碼鏈通過,顯然該列上的所有失效元素可以成功恢復(fù)。假設(shè)當(dāng)f=k時所有失效元素可以被成功恢復(fù),其中k為正整數(shù)。下面討論f=k+1的情況。由前提條件可知,max(d1,d2,…,dk)=dk≥m。因此,若不等式d1≥「m/2?成立,則顯然第一個失效列E1上的所有元素均可由斜率為1或-1的碼鏈恢復(fù)。同理,若dk≥「m/2?成立,則最后一個失效列Ek+1上的所有元素均可由斜率為1或-1的碼鏈恢復(fù)。至此,上述兩種情況均可化為f=k的情況,而根據(jù)前述假設(shè)可知,所有失效數(shù)據(jù)能得到恢復(fù)。而當(dāng)d1<「m/2?且dk<「m/2?時,顯然所有失效列上的第一個失效元素可以被斜率為±1,±2,…,±k,k+1的碼鏈恢復(fù)。而所有失效列上第一行的失效元素被成功恢復(fù)后,只需不斷重復(fù)上述相同的步驟,剩余失效元素可被有效恢復(fù)。

因此,不等式n≥m·f-f+1即是構(gòu)造陣列碼時需要滿足的約束條件,不難看出,與前文所述的素數(shù)約束相比,本文方法的約束條件非常容易滿足,也有根據(jù)實(shí)用環(huán)境需求動態(tài)擴(kuò)展的空間,與大多已有陣列碼相比,本文方法的限制條件強(qiáng)度已經(jīng)有了很大幅度的降低。

3 實(shí)驗(yàn)與分析

3.1 運(yùn)算工作量

由于大多陣列碼的碼字結(jié)構(gòu)不規(guī)則而很難用一個確切的公式來表達(dá)編碼或數(shù)據(jù)重構(gòu)的總體工作量,因此,通常使用生成單個校驗(yàn)位所需要經(jīng)過異或運(yùn)算的次數(shù)來衡量其編碼的復(fù)雜度,采用恢復(fù)單個丟失數(shù)據(jù)位需要經(jīng)過的異或運(yùn)算的次數(shù)來衡量其數(shù)據(jù)恢復(fù)的復(fù)雜度。由前文可知,每條碼鏈的長度均為m+1,所以生成單個校驗(yàn)位或者恢復(fù)單個失效元素所需的計算工作量均為m-1。然而,條帶尺寸會隨著條塊尺寸m或容錯能力f的擴(kuò)大而增加,這就意味著校驗(yàn)位的數(shù)量也將增加,即總體運(yùn)算量加大。因此,存儲陣列的條塊尺寸以及容錯能力的變化對編碼和數(shù)據(jù)恢復(fù)運(yùn)算量的影響是需要考慮的一個因素。假設(shè)條塊尺寸200,容錯能力為50的情況下,以存儲1 GB的數(shù)據(jù)為例,生成所有校驗(yàn)位或恢復(fù)50個節(jié)點(diǎn)的失效數(shù)據(jù)所需要的異或運(yùn)算次數(shù)約為4.2×109,這些運(yùn)算量用一臺主頻為3.2 GHz的普通個人電腦大概也只需要16 s就能完成。圖6顯示了條塊尺寸對陣列碼編碼和數(shù)據(jù)恢復(fù)運(yùn)算量的影響情況,而圖7則顯示了容錯能力對編碼和數(shù)據(jù)恢復(fù)運(yùn)算量的影響情況。

圖6 條塊尺寸對運(yùn)算量的影響

圖7 容錯能力對運(yùn)算量的影響

如前所述,以存儲效率為標(biāo)準(zhǔn),目前的陣列碼可以劃分為MDS編碼和非MDS編碼。MDS編碼在存儲效率上具有理論上的最優(yōu)值,其典型代表包括以EVENODD碼[6]、X碼[7]、Star碼[8]和擴(kuò)展X碼[9]等。但是具有MDS性質(zhì)的陣列碼通常的容錯能力僅為2或3, 這顯然不能滿足現(xiàn)代大規(guī)模存儲系統(tǒng)的可靠性增強(qiáng)需求。而為了提高陣列碼的容錯能力, 研究者們則設(shè)計出一些不具備MDS性質(zhì)的陣列碼,其容錯能力與具有MDS性質(zhì)的陣列碼相比有較大提升(通常在10個以上),即通過降低存儲效率(在不小于復(fù)制冗余策略的前提下)以換取更高的容錯能力,這類編碼的典型代表包括Weaver碼[10]、Hover碼[11]和Grid碼[12]等。但大多對于存儲效率的犧牲很大,比如Weaver碼在容錯能力為10時,其存儲效率還不足20%。而本文提出的編碼也是一種典型的非MDS陣列編碼,因此也不具有最優(yōu)的存儲效率,但可以在保證較高容錯能力的前提下,達(dá)到較高的存儲效率。如圖8所示,在具有較高容錯能力時,本文提出的陣列碼依然可以達(dá)到較高的存儲效率。

圖8 存儲效率的變化

3.3 修復(fù)代價和更新代價

修復(fù)代價通常是指重構(gòu)一個失效的數(shù)據(jù)元素所需要涉及到讀操作的存儲節(jié)點(diǎn)總數(shù)。修復(fù)代價是存儲系統(tǒng)中一個重要的性能指標(biāo),與數(shù)據(jù)重構(gòu)、數(shù)據(jù)更新、降低讀寫等均有密切的關(guān)系。由前述碼鏈的部署方法可得,每條碼鏈上均有m+1(m個數(shù)據(jù)元素和1個校驗(yàn)元素)個元素,因此,重構(gòu)一個失效數(shù)據(jù)元素需要涉及的節(jié)點(diǎn)數(shù)總是m,且不會隨著存儲系統(tǒng)規(guī)模和容錯能力的增加而增大。

更新代價是水平布局陣列碼中的一個特有指標(biāo),它是指一個最小的數(shù)據(jù)位改變時所需要涉及到的校驗(yàn)節(jié)點(diǎn)數(shù)。數(shù)據(jù)更新比較頻繁時,更新代價過高會導(dǎo)致校驗(yàn)節(jié)點(diǎn)的訪問過熱而降低存儲系統(tǒng)的整體I/O性能。由本文陣列碼構(gòu)造方法可知,每個數(shù)據(jù)元素均剛好有f條不同碼鏈通過,即每個數(shù)據(jù)元素均有f個不同的校驗(yàn)元素與之相關(guān)。換句話說,當(dāng)任意一個數(shù)據(jù)元素改變時,總是會涉及到f個校驗(yàn)節(jié)點(diǎn),即更新代價恒為f,而這也已經(jīng)達(dá)到了f容錯陣列碼更新代價的理論最優(yōu)值。

4 結(jié)語

本文使用不同斜率碼鏈構(gòu)造出了一類容錯能力理論上不受限制的陣列糾刪碼,其結(jié)構(gòu)簡潔,有利于計算機(jī)軟硬件實(shí)現(xiàn)。該碼涉及的所有計算均使用二進(jìn)制的異或運(yùn)算,具有極高的運(yùn)算效率;而構(gòu)造時也無需滿足素數(shù)約束等強(qiáng)約束條件,易于實(shí)用且便于擴(kuò)展。雖然該碼不具備MDS性質(zhì),但存儲效率可以通過條塊尺寸的增加而不斷提高。此外,該碼的修復(fù)代價和更新代價均為一個常量,不會隨著系統(tǒng)規(guī)模或容錯能力的提高而增加。

)

[1]SATHIAMOORTHYM,ASTERISM,PAPAILIOPOULOSD,etal.XORingelephants:novelerasurecodesforbigdata[J].ProceedingsoftheVLDBEndowment, 2013, 6(5): 325-336.

[2]SCHROEDERB,GIBSONGA.Diskfailuresintherealworld:whatdoesanMTTFof1 000 000hoursmeantoyou?[C]//FAST2007:Proceedingsofthe5thUSENIXConferenceonFileandStorageTechnologies.Berkeley,CA:USENIXAssociation, 2007:1-16.

[3]PLANKJS,XUL.OptimizingCauchyReed-Solomoncodesforfault-tolerantnetworkstorageapplications[C]//NCA2006:ProceedingsoftheFifthIEEEInternationalSymposiumonNetworkComputingandApplications.Washington,DC:IEEEComputerSociety, 2006:173-180.

[4]PLANKJS,GREENANKM,MILLEREL.ScreamingfastGaloisfieldarithmeticusingIntelSIMDinstructions[C]//FAST2013:Proceedingsofthe11thUSENIXConferenceonFileandStorageTechnologies.Berkeley,CA:USENIXAssociation, 2013: 299-306.

[5]JANAKIRAMB,CHANDRAMG,ARAVINDKG,etal.SpreadStore:aLDPCerasurecodeschemefordistributedstoragesystem[C]//Proceedingsofthe2010InternationalConferenceonDataStorageandDataEngineering.Piscataway,NJ:IEEE, 2010: 154-158.

[6]BLAUMM,BRADYJ,BRUCKJ,etal.EVENODD:anefficientschemefortoleratingdoublediskfailuresinRAIDarchitectures[J].IEEETransactionsonComputers, 1995, 44(2): 192-202.

[7]XUL,BRUCKJ.X-code:MDSarraycodeswithoptimalencoding[J].IEEETransactionsonInformationTheory, 1999, 45(1): 272-276.

[8]HUANGC,XUL.STAR:anefficientcodingschemeforcorrectingtriplestoragenodefailures[J].IEEETransactionsonComputers, 2008, 57(7): 889-901.

[9] 孟慶春. 應(yīng)用于分布式存儲系統(tǒng)上的糾刪碼技術(shù)研究[D]. 北京: 中國科學(xué)院研究生院, 2007.(MENGQC.Researchoferasurecodesappliedindistributedstoragesystem[D].Beijing:GraduateUniversityoftheChineseAcademyofSciences, 2007.)

[10]HAFNERJL.WEAVERcodes:highlyfaulttoleranterasurecodesforstoragesystems[C]//FAST2005:Proceedingsofthe4thConferenceonUSENIXConferenceonFileandStorageTechnologies.Berkeley,CA:USENIXAssociation, 2005, 4: 211-224.

[11]HAFNERJL.HoVererasurecodesfordiskarrays[C]//DSN2006:Proceedingsofthe2006InternationalConferenceonDependableSystemsandNetworks.Washington,DC:IEEEComputerSociety, 2006: 217-226.

[12]LIM,SHUJ,ZHENGW.GRIDcodes:strip-basederasurecodeswithhighfaulttoleranceforstoragesystems[J].ACMTransactionsonStorage, 2009, 4(4):ArticleNo. 15.

[13] 陳崢. 一類新的陣列糾刪碼理論及應(yīng)用研究[D]. 北京: 中國科學(xué)院研究生院, 2009.(CHENZ.Aclassofarrayerasurecodesandtheirapplications[D].Beijing:GraduateUniversityoftheChineseAcademyofSciences, 2009.)

[14] 唐聃, 舒紅平. 一類多容錯的陣列糾刪碼[J]. 中國科學(xué): 信息科學(xué), 2016, 46(4): 523-538.(TANGD,SHUHP.Aclassofarrayerasurecodeswithhighfault-tolerance[J].ScienceChina:InformationSciences, 2016, 46(4): 523-538.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61501064, 61501063),theYouthScienceandTechnologyFundofSichuanProvince(2017JQ0057).

TANG Dan, born in 1982, Ph. D., associate professor. His research interests include big data, cloud computing, coding theory.

Array erasure codes based on coding chains with multiple slopes

TANG Dan*, YANG Haopeng, WANG Fuchao

(College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China)

In view of the problem that the fault tolerance capability is low and strong constraint conditions need to be satisfied in the construction of most array erasure codes at present, a new type of array erasure codes based on coding chains was proposed. In the new array erasure codes, coding chains with different slopes were used to organize the relationship among data elements and check elements, so as to achieve infinite fault tolerance capability in theory; the strong constraint conditions like the prime number limitation was avoided in construction, which is easy to be practical and extensible. Simulation results show that, compared with Reed-Solomon codes (RS codes), the efficiency of the proposed array erasure codes based on coding chains is more than 2 orders of magnitude; under the condition of fixed fault tolerance, its storage efficiency can be improved with the increase of the strip size. In addition, the update penalty and repair cost of the array codes is a fixed constant, which will not increase with the expansion of the storage system scale or the increase of fault tolerance capability.

array erasure code; fault tolerance; coding chain; strip size

2016- 10- 08;

2016- 11- 25。

國家自然科學(xué)基金資助項目(61501064, 61501063);四川省青年科技基金資助項目(2017JQ0057)。

唐聃(1982—),男,四川成都人,副教授,博士,CCF會員,主要研究方向:大數(shù)據(jù)、云計算、編碼理論。

1001- 9081(2017)04- 0936- 05

10.11772/j.issn.1001- 9081.2017.04.0936

TP302.8

A