分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)修復(fù)技術(shù)研究

鄭杰輝

(廈門海洋學(xué)院 信息技術(shù)系,福建 廈門 361000)

分布式存儲(chǔ)系統(tǒng)是大量普通PC服務(wù)器通過(guò)Internet互聯(lián),對(duì)外作為一個(gè)整體提供存儲(chǔ)服務(wù)[1]。分布式存儲(chǔ)系統(tǒng)具備如下幾個(gè)特性:1)可擴(kuò)展。分布式系統(tǒng)可以擴(kuò)展到幾百臺(tái)到幾千臺(tái)的集群規(guī)模,而且,隨著集群規(guī)模的增長(zhǎng),系統(tǒng)整體性能表現(xiàn)為線性增長(zhǎng)。2)低成本。分布式存儲(chǔ)系統(tǒng)的自動(dòng)容錯(cuò)、自動(dòng)負(fù)載均衡機(jī)制使其可以構(gòu)建在普通PC機(jī)之上。另外,線性擴(kuò)展能力也使得增加、減少機(jī)器非常方便,可以使用較低的成本實(shí)現(xiàn)自動(dòng)運(yùn)維。3)高性能。無(wú)論是整個(gè)集群還是單機(jī)服務(wù),都要求分布式系統(tǒng)具備高性能。4)易用。分布式存儲(chǔ)系統(tǒng)需要提供通用的對(duì)外接口,另外也要求具備完善的監(jiān)控、運(yùn)維工具,并能夠方便地與其它系統(tǒng)集成[2]。如 Hadoop云計(jì)算系統(tǒng)導(dǎo)入數(shù)據(jù)。在現(xiàn)代信息技術(shù)和互聯(lián)網(wǎng)技術(shù)不斷發(fā)展的當(dāng)今社會(huì),分布式存儲(chǔ)系統(tǒng)的挑戰(zhàn)主要在于數(shù)據(jù)、狀態(tài)信息的持久化,要求在自動(dòng)遷移、自動(dòng)容錯(cuò)、并發(fā)讀寫的過(guò)程中保證數(shù)據(jù)的一致性[3],所涉及的技術(shù)主要包括分布式系統(tǒng)和數(shù)據(jù)庫(kù)[4]。無(wú)論分布式存儲(chǔ)系統(tǒng)中哪個(gè)節(jié)點(diǎn)發(fā)生故障,如何有效提升存儲(chǔ)系統(tǒng)可靠性和修復(fù)效率都是必須面對(duì)的關(guān)鍵技術(shù)難點(diǎn)。在此基礎(chǔ)上,本文選取目前分布式存儲(chǔ)系統(tǒng)中常見的集中節(jié)點(diǎn)修復(fù)技術(shù)進(jìn)行對(duì)比分析,以期更好地實(shí)現(xiàn)節(jié)點(diǎn)故障修復(fù)效率和質(zhì)量。

1 層次碼與循環(huán)RS碼

在分布式存儲(chǔ)系統(tǒng)中,層次碼(HC)可以實(shí)現(xiàn)糾錯(cuò)/刪除碼和局部修復(fù)碼的結(jié)合,但是如果存儲(chǔ)系統(tǒng)發(fā)生故障時(shí),由于連接節(jié)點(diǎn)的個(gè)數(shù)比原始數(shù)據(jù)節(jié)點(diǎn)數(shù)少,在修復(fù)過(guò)程中如果僅僅連接任意k個(gè)節(jié)點(diǎn)并不能實(shí)現(xiàn)數(shù)據(jù)恢復(fù)[5]。例如對(duì)于包含k個(gè)數(shù)據(jù)塊的文件,基于層次碼的具體編碼規(guī)則主要包括:1)構(gòu)件第0層編碼HC-(k0,r0),即由k0個(gè)原始數(shù)據(jù)塊與r0個(gè)校驗(yàn)塊構(gòu)成;2)構(gòu)件第1層編碼HC-(k1,r1);3)重復(fù)構(gòu)件編碼并增加編碼層數(shù),直至第i層編碼為HC-(ki,ri)[6]。圖1中列出了層次碼的編碼圖,圖1(a)中G2,1為0層編碼組,b1、b2和b3為原始數(shù)據(jù)塊,如果某一數(shù)據(jù)塊發(fā)生丟失的情況下(如b1),編碼圖中可通過(guò)b2和局部校驗(yàn)塊進(jìn)行修復(fù)(如b3),在這個(gè)情況下,要想恢復(fù)b1的數(shù)據(jù)塊,則需要讀取b2和b3數(shù)據(jù)塊信息,此時(shí)的修復(fù)局部性為2;圖1(b)中G4,1為1層編碼組,如果某一數(shù)據(jù)塊發(fā)生丟失的情況下(如b7),需要讀取的數(shù)據(jù)塊包括b1、b2、b4和b5,此時(shí)的修復(fù)局部性為4。綜合而言,在采用層次碼進(jìn)行分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)修復(fù)時(shí),修復(fù)帶寬開銷和局部修復(fù)性都會(huì)發(fā)生不同程度降低。

圖1 層次碼的編碼圖

循環(huán)RS碼是線性循環(huán)編碼,即編碼后的碼組T(X)左移或右移都必然還是有限組碼組中的一組,并且T(X)碼組能夠被g(X)整除,g(X)為生成多項(xiàng)式[7],這種由傳統(tǒng)RS碼衍生而來(lái)的編碼可以通過(guò)調(diào)節(jié)校驗(yàn)塊的生成方式來(lái)降低分布式存儲(chǔ)系統(tǒng)中的節(jié)點(diǎn)故障[8]。圖2為循環(huán)RS碼的編碼圖,其中原始數(shù)據(jù)節(jié)點(diǎn)s、校驗(yàn)節(jié)點(diǎn)數(shù)m和節(jié)點(diǎn)數(shù)t分別為6、2和3,左側(cè)部分的N0、N1、N2、N3、N4和N5為原始數(shù)據(jù)節(jié)點(diǎn),右側(cè)部分的N6、N7為校驗(yàn)節(jié)點(diǎn),左側(cè)部分編碼圖中的圓圈和三角形分別表示N6、N7的生成方式。從圖2中可見,在分布式存儲(chǔ)系統(tǒng)中若發(fā)生某個(gè)節(jié)點(diǎn)故障,編碼圖中讀取15個(gè)數(shù)據(jù)塊即可完成數(shù)據(jù)修復(fù),這種循環(huán)RS碼的方法相對(duì)傳統(tǒng)RS碼方法的數(shù)據(jù)處理量減少了約16%,此外,即使在分布式存儲(chǔ)系統(tǒng)中發(fā)生多個(gè)節(jié)點(diǎn)故障,循環(huán)RS碼也會(huì)相較于傳統(tǒng)RS碼具備更優(yōu)的數(shù)據(jù)處理能力。

圖2 循環(huán)RS碼的編碼圖

2 旋轉(zhuǎn)交織碼

實(shí)際應(yīng)用過(guò)程中的分布式存儲(chǔ)系統(tǒng)通常會(huì)出現(xiàn)較多用戶訪問(wèn)一個(gè)節(jié)點(diǎn)的情況,此時(shí)的節(jié)點(diǎn)超負(fù)荷運(yùn)行會(huì)影響分布式存儲(chǔ)系統(tǒng)的整體運(yùn)行能力[9],尤其是當(dāng)分布式存儲(chǔ)系統(tǒng)中出現(xiàn)某個(gè)節(jié)點(diǎn)故障時(shí),其它節(jié)點(diǎn)的超負(fù)荷會(huì)更加嚴(yán)重,極端情況下還會(huì)發(fā)生系統(tǒng)癱瘓。因此,需要設(shè)計(jì)一種能夠均衡節(jié)點(diǎn)負(fù)載的編碼,旋轉(zhuǎn)交織碼即在這種情況下應(yīng)運(yùn)而生。從圖3的旋轉(zhuǎn)交織碼的編碼圖中可見,該編碼可以對(duì)三組存儲(chǔ)單元進(jìn)行標(biāo)號(hào)并形成位置標(biāo)識(shí),這樣A組、B組和C組中相同位置處的數(shù)據(jù)塊可以實(shí)現(xiàn)旋轉(zhuǎn)交織,即分布式存儲(chǔ)系統(tǒng)中某節(jié)點(diǎn)發(fā)生故障時(shí),可通過(guò)另外兩組標(biāo)號(hào)位置相同的數(shù)據(jù)塊對(duì)節(jié)點(diǎn)實(shí)現(xiàn)修復(fù),并均衡運(yùn)行過(guò)程中節(jié)點(diǎn)負(fù)載狀況;但是,與此同時(shí),由于修復(fù)過(guò)程中參與節(jié)點(diǎn)的數(shù)量較多(約占整個(gè)系統(tǒng)節(jié)點(diǎn)數(shù)的67%),旋轉(zhuǎn)交織碼存在較大的修復(fù)局部性。

A組

B組

C組

圖3旋轉(zhuǎn)交織碼的編碼圖

Fig.3 Coding diagram of rotary interleaved code

進(jìn)一步對(duì)旋轉(zhuǎn)交織碼進(jìn)行層次構(gòu)造,以降低分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)故障的修復(fù)局部性,具體包括將旋轉(zhuǎn)交織碼中的層次碼按照層次化進(jìn)行擴(kuò)展,從而降低殘余節(jié)點(diǎn)修復(fù)的數(shù)據(jù)塊,值得注意的是,雖然重新層次構(gòu)造的旋轉(zhuǎn)交織碼的節(jié)點(diǎn)修復(fù)數(shù)據(jù)塊會(huì)減小,但是不會(huì)影響到節(jié)點(diǎn)負(fù)載均衡。

圖4為分布式存儲(chǔ)系統(tǒng)中單節(jié)點(diǎn)故障的修復(fù)示意圖,其中,故障節(jié)點(diǎn)位于節(jié)點(diǎn)p1,0處,用灰色陰影標(biāo)識(shí),相應(yīng)的單元數(shù)據(jù)片也用陰影標(biāo)識(shí)(1,9,5)。從圖中可見,如果運(yùn)行過(guò)程中節(jié)點(diǎn)p1,0處發(fā)生故障,則可以通過(guò)下一層p0,0處和p0,1處節(jié)點(diǎn)進(jìn)行修復(fù),也可以通過(guò)上一層p2,0處節(jié)點(diǎn)和同層p1,1處節(jié)點(diǎn)進(jìn)行修復(fù)。相應(yīng)地,如果陰影標(biāo)識(shí)處位置標(biāo)號(hào)為1,9,5處的數(shù)據(jù)塊發(fā)生故障或者丟失,可用前述的旋轉(zhuǎn)交織碼的方法找到相同位置標(biāo)號(hào)處的數(shù)據(jù)進(jìn)行修復(fù)。此外,如果單元數(shù)據(jù)片中同時(shí)出現(xiàn)了幾個(gè)或者多個(gè)節(jié)點(diǎn)故障,參照旋轉(zhuǎn)交織碼的修復(fù)處理方法,相應(yīng)地通過(guò)其他單元數(shù)據(jù)片相同位置編號(hào)處的數(shù)據(jù)來(lái)進(jìn)行修復(fù),修復(fù)過(guò)程中還可以較好地滿足節(jié)點(diǎn)負(fù)載要求。

當(dāng)分布式存儲(chǔ)系統(tǒng)中出現(xiàn)多節(jié)點(diǎn)故障,采用旋轉(zhuǎn)交織碼進(jìn)行節(jié)點(diǎn)故障修復(fù)時(shí)的示意圖如圖5,其中,出現(xiàn)故障的節(jié)點(diǎn)處都用陰影進(jìn)行標(biāo)識(shí)?？梢?該套分布式存儲(chǔ)系統(tǒng)中同時(shí)出現(xiàn)了7處故障,分別位于p3,0處、p2,0處、p1,0處、p0,2處、p1,2處、p0,4處和p0,6處。通過(guò)前述的旋轉(zhuǎn)交織碼修復(fù)方法可知,不同位置處的故障可以通過(guò)其他兩個(gè)單位數(shù)據(jù)片中的數(shù)據(jù)進(jìn)行修復(fù),則可以先通過(guò)p0,0和p0,1修復(fù)p1,0,通過(guò)p1,1和p0,3修復(fù)p0,2,通過(guò)p07和p1,3修復(fù)p0,6,通過(guò)p2,1和p1,3修復(fù)p1,2;再通過(guò)p1,0和p1,1修復(fù)p2,0,通過(guò)p1,2和p0,5修復(fù)p0,4;最后再通過(guò)p2,0和p2,1修復(fù)p3,0,從而實(shí)現(xiàn)了整個(gè)分布式存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)故障的修復(fù),且在整個(gè)過(guò)程中,旋轉(zhuǎn)交織碼的修復(fù)都為均衡修復(fù)。

在分布式存儲(chǔ)系統(tǒng)的多節(jié)點(diǎn)故障修復(fù)過(guò)程中,修復(fù)帶寬開銷、修復(fù)局部性和修復(fù)復(fù)雜度直接決定了編碼的優(yōu)劣,在此基礎(chǔ)上,對(duì)前述的層次碼、循環(huán)RS碼和旋轉(zhuǎn)交織碼的性能進(jìn)行了對(duì)比分析,并設(shè)定層次碼中第0層包括的節(jié)點(diǎn)數(shù)為2m。從圖6和圖7的節(jié)點(diǎn)故障時(shí)修復(fù)帶寬開銷的變化可知,單節(jié)點(diǎn)發(fā)生故障時(shí),旋轉(zhuǎn)交織碼的修復(fù)帶寬最小,而兩節(jié)點(diǎn)發(fā)生故障時(shí),旋轉(zhuǎn)交織碼的層次碼技術(shù)可以發(fā)揮明顯優(yōu)勢(shì),其修復(fù)帶寬開銷明顯要低于層次碼、循環(huán)RS碼。

圖6 單節(jié)點(diǎn)故障時(shí)修復(fù)帶寬開銷的變化

圖7 兩節(jié)點(diǎn)故障時(shí)修復(fù)帶寬開銷的變化

從圖8和圖9的節(jié)點(diǎn)故障時(shí)修復(fù)局部性的變化可知,分布式存儲(chǔ)系統(tǒng)中任意單節(jié)點(diǎn)發(fā)生故障時(shí),旋轉(zhuǎn)交織碼的層次碼技術(shù)的修復(fù)局部性最小,而當(dāng)兩節(jié)點(diǎn)發(fā)生故障時(shí),旋轉(zhuǎn)交織碼的層次碼技術(shù)也可以發(fā)揮明顯優(yōu)勢(shì),其修復(fù)局部性的最大值和最小值都要低于層次碼、循環(huán)RS碼相應(yīng)的修復(fù)局部性的最大值和最小值。

圖8 單節(jié)點(diǎn)故障時(shí)修復(fù)局部性的變化

圖9 兩節(jié)點(diǎn)故障時(shí)修復(fù)修復(fù)局部性的變化

3 故障節(jié)點(diǎn)快速修復(fù)性能

表1為層次碼、循環(huán)RS碼和旋轉(zhuǎn)交織碼在分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)故障修復(fù)時(shí)的性能對(duì)比結(jié)果,其中,k和r分別表示元素?cái)?shù)據(jù)庫(kù)節(jié)點(diǎn)數(shù)和存儲(chǔ)校驗(yàn)塊的節(jié)點(diǎn)數(shù),a和m分別表示節(jié)點(diǎn)數(shù)據(jù)塊和源文件大小。從修復(fù)帶寬開銷、修復(fù)局部性和復(fù)雜度的綜合性能對(duì)比結(jié)果可知,基于旋轉(zhuǎn)交織碼的層次碼技術(shù)在分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)故障修復(fù)中具有明顯的優(yōu)勢(shì),其修復(fù)復(fù)雜度要明顯低于層次碼和循環(huán)RS碼,從而可以提升節(jié)點(diǎn)故障修復(fù)效率。

表1 不同編碼方案下節(jié)點(diǎn)修復(fù)性能的對(duì)比分析結(jié)果

4 結(jié)論

1)在采用層次碼進(jìn)行分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)修復(fù)時(shí),修復(fù)帶寬開銷和局部修復(fù)性都會(huì)發(fā)生不同程度的降低,即使在分布式存儲(chǔ)系統(tǒng)中發(fā)生多個(gè)節(jié)點(diǎn)故障,循環(huán)RS碼也會(huì)相較于傳統(tǒng)RS碼具備更優(yōu)的數(shù)據(jù)處理能力。

2)分布式存儲(chǔ)系統(tǒng)中某節(jié)點(diǎn)發(fā)生故障時(shí),旋轉(zhuǎn)交織碼技術(shù)可通過(guò)另外兩組標(biāo)號(hào)位置相同的數(shù)據(jù)塊對(duì)節(jié)點(diǎn)實(shí)現(xiàn)修復(fù),并均衡運(yùn)行過(guò)程中節(jié)點(diǎn)負(fù)載狀況,但是旋轉(zhuǎn)交織碼存在較大的修復(fù)局部性。

3)基于旋轉(zhuǎn)交織碼的層次碼在修復(fù)帶寬開銷、修復(fù)局部性和復(fù)雜度方面相較于層次碼和循環(huán)RS碼具有明顯優(yōu)勢(shì),可以提升分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)故障的修復(fù)效率。