唐 聃,楊昊澎,王福超

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

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

唐 聃*,楊昊澎,王福超

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

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

陣列糾刪碼;容錯(cuò);碼鏈;條塊尺寸

0 引言

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

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

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

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

1 基本概念和定義

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

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

斜率 將存儲(chǔ)系統(tǒng)的數(shù)據(jù)陣列部分(假設(shè)尺寸為m×n,其中m和n均為大于1 的正整數(shù))看作一個(gè)二維坐標(biāo)系,以向右的水平軸作為坐標(biāo)系的正向X軸,以向下的垂直軸作為坐標(biāo)系的正向Y軸,則所有數(shù)據(jù)陣列中的元素成為了該坐標(biāo)系上擁有固定坐標(biāo)的一個(gè)點(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):該符號(hào)用于標(biāo)識(shí)存儲(chǔ)陣列中第i行第j列的元素,當(dāng)有多個(gè)元素需要表示時(shí),可以使用符號(hào)“:”表示出一個(gè)范圍區(qū)間,如El(i,2:5)表示存儲(chǔ)陣列第i行上的第2到5個(gè)元素集合,El(:,j)則用于表示陣列中第j列的所有元素。

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

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

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

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

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

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

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

(2)

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

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

(3)

lc=(t-1)%n+1

(4)

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

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

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

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

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

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

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

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

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

2.2 約束條件及容錯(cuò)能力保證

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

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

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

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

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

3.1 運(yùn)算工作量

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

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

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

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

圖8 存儲(chǔ)效率的變化

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

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

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

4 結(jié)語(yǔ)

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

)

[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)用于分布式存儲(chǔ)系統(tǒng)上的糾刪碼技術(shù)研究[D]. 北京: 中國(guó)科學(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]. 北京: 中國(guó)科學(xué)院研究生院, 2009.(CHENZ.Aclassofarrayerasurecodesandtheirapplications[D].Beijing:GraduateUniversityoftheChineseAcademyofSciences, 2009.)

[14] 唐聃, 舒紅平. 一類多容錯(cuò)的陣列糾刪碼[J]. 中國(guó)科學(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。

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

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

1001- 9081(2017)04- 0936- 05

10.11772/j.issn.1001- 9081.2017.04.0936

TP302.8

A