鄭杰輝

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

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

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

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

圖1 層次碼的編碼圖

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

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

2 旋轉交織碼

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

A組

B組

C組

圖3旋轉交織碼的編碼圖

Fig.3 Coding diagram of rotary interleaved code

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

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

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

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

圖6 單節(jié)點故障時修復帶寬開銷的變化

圖7 兩節(jié)點故障時修復帶寬開銷的變化

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

圖8 單節(jié)點故障時修復局部性的變化

圖9 兩節(jié)點故障時修復修復局部性的變化

3 故障節(jié)點快速修復性能

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

表1 不同編碼方案下節(jié)點修復性能的對比分析結果

4 結論

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

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

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