沈洪敏，周功建

(廈門大學(xué)嘉庚學(xué)院，福建 漳州 363105)

1 引言

隨著信息、網(wǎng)絡(luò)、電子技術(shù)的迅速發(fā)展，以及大數(shù)據(jù)時代的來臨，不斷催生信息數(shù)據(jù)越來越呈現(xiàn)爆炸性的增長，同時數(shù)據(jù)規(guī)模也呈現(xiàn)指數(shù)級上升的現(xiàn)象[1]。與此同時，使得當(dāng)前信息技術(shù)的發(fā)展方向越來越變?yōu)橐詳?shù)據(jù)存儲為核心的計算機(jī)信息技術(shù)發(fā)展?；诜植际降臄?shù)據(jù)存儲系統(tǒng)作為當(dāng)前數(shù)據(jù)存儲的主要應(yīng)用技術(shù)之一，充分結(jié)合了數(shù)據(jù)存儲系統(tǒng)、計算機(jī)技術(shù)、集成電路技術(shù)以及計算機(jī)網(wǎng)絡(luò)技術(shù)發(fā)展的結(jié)晶。同時，構(gòu)建基于分布式的數(shù)據(jù)存儲系統(tǒng)其目的就在于充分利用當(dāng)前相對廉價的數(shù)據(jù)存儲軟硬件資源、網(wǎng)絡(luò)軟硬件資源，從而構(gòu)建超大規(guī)模、可靠性高以及具有強(qiáng)擴(kuò)展性的數(shù)據(jù)存儲與應(yīng)用系統(tǒng)。然而，當(dāng)前隨著數(shù)據(jù)獲取方式不斷增多、數(shù)據(jù)類型日趨復(fù)雜、以及數(shù)據(jù)增長方式呈現(xiàn)前所未有的數(shù)據(jù)變化，從而造成數(shù)據(jù)在進(jìn)行分布式存儲的過程中，呈現(xiàn)存儲節(jié)點數(shù)量逐步上升、節(jié)點的分散性高、異構(gòu)性以及易失效性等問題，給傳統(tǒng)的數(shù)據(jù)存儲方式以及數(shù)據(jù)存儲過程中的可靠性帶來嚴(yán)峻的挑戰(zhàn)[2][3]。

因此，在進(jìn)行分布式數(shù)據(jù)存儲系統(tǒng)研究的過程中，如何進(jìn)一步提高系統(tǒng)的可靠性、容錯性以及數(shù)據(jù)恢復(fù)精度等內(nèi)容，同時進(jìn)一步降低軟硬件數(shù)據(jù)修復(fù)開銷成為當(dāng)前分布式數(shù)據(jù)存儲系統(tǒng)的研究熱點。

通常來講，分布式存系統(tǒng)在進(jìn)行提高數(shù)據(jù)容錯的方法主要從以下兩個方面進(jìn)行研究，即多副本數(shù)據(jù)存儲技術(shù)以及數(shù)據(jù)存儲糾刪碼技術(shù)[4]。顧名思義，多副本數(shù)據(jù)存儲技術(shù)就是將需要保護(hù)的原始數(shù)據(jù)以多個數(shù)據(jù)副本存儲在不同的數(shù)據(jù)節(jié)點上，在進(jìn)行數(shù)據(jù)恢復(fù)的過程中出現(xiàn)無效節(jié)點時，可以將其它未失效的節(jié)點副本數(shù)據(jù)復(fù)制覆蓋掉失效節(jié)點上，從而實現(xiàn)對失效節(jié)點上的數(shù)據(jù)進(jìn)行恢復(fù)。很明顯，多副本數(shù)據(jù)存儲技術(shù)在進(jìn)行數(shù)據(jù)存儲與恢復(fù)的過程中修復(fù)原理簡單直觀，而且更有利于實現(xiàn)，因此該方法是目前應(yīng)用最為廣泛的數(shù)據(jù)存儲與容錯技術(shù)。很明顯可以看出，輕量級數(shù)據(jù)采用此方法極為有利[5]。但是，當(dāng)遇到海量數(shù)據(jù)存儲與修復(fù)的過程中，為了保證數(shù)據(jù)的可靠性和容錯性，需要消耗大量存儲空間，會極大的耗費人力物力和財力。

為了解決多副本容錯技術(shù)帶來的缺點，數(shù)據(jù)糾刪碼技術(shù)應(yīng)運而生，該方法通過將原始存儲數(shù)據(jù)按照一定編碼規(guī)則對原始數(shù)據(jù)進(jìn)行編碼，將編碼得到的具有冗余信息的冗余數(shù)據(jù)按照一定規(guī)則一并存儲到對應(yīng)的數(shù)據(jù)節(jié)點上，從而達(dá)到存儲數(shù)據(jù)容錯的目的[6]。在進(jìn)行數(shù)據(jù)恢復(fù)的過程中，如果數(shù)據(jù)出現(xiàn)異常，通過對剩余有效數(shù)據(jù)進(jìn)行讀取，然后按照數(shù)據(jù)存儲過程中的數(shù)據(jù)編碼規(guī)則，采用對應(yīng)的譯碼算法完成對異常故障節(jié)點的數(shù)據(jù)進(jìn)行恢復(fù)。由于該方法無論在存儲資源消耗、數(shù)據(jù)存儲節(jié)點結(jié)構(gòu)等方面很多優(yōu)勢，因此該方法越來越成為當(dāng)前分布式數(shù)據(jù)存儲與糾刪技術(shù)的研究熱點。其中比較典型的數(shù)據(jù)糾刪碼算法有，EvenOdd糾刪碼算法，F(xiàn)ree Codes，RDP算法以及HRCSD等糾刪碼數(shù)據(jù)容錯算法。同時在此算法的基礎(chǔ)上，很多研究學(xué)者提出了新的數(shù)據(jù)糾刪容錯算法。其中，文獻(xiàn)[7]根據(jù)EvenOdd算法的特點，提出了同時針對多列誤碼的G-EvenOdd數(shù)據(jù)糾刪算法。與此同時，文獻(xiàn)[8]同樣基于EvenOdd基礎(chǔ)算法，提出了基于擴(kuò)展EvenOdd的存儲數(shù)據(jù)糾刪模型，該模型描述了一種新的星形編碼方案，用于糾正三重存儲節(jié)點故障(擦除)。星型碼是雙糾擦偶奇碼的擴(kuò)展，是廣義三糾擦偶奇碼的改進(jìn)，然后詳細(xì)介紹了星型碼解碼算法，同時應(yīng)用于糾正各種三節(jié)點故障。最后通過實驗表明，該方法在針對任意三點故障星型碼的有效性，驗證了該模型在應(yīng)對需要更高可靠性的存儲系統(tǒng)具有很好的實際意義。文獻(xiàn)[9]在研究糾刪碼的過程中，作者將網(wǎng)絡(luò)編碼的思想引入其中，同時結(jié)合網(wǎng)絡(luò)中的信息流圖來進(jìn)行對存儲數(shù)據(jù)的修復(fù)問題進(jìn)行數(shù)學(xué)建模，通過分析沒此修復(fù)數(shù)據(jù)的修復(fù)帶寬的大小來進(jìn)行評判該方法的優(yōu)越性。文獻(xiàn)[10]提出采用建立在可用帶寬的存儲數(shù)據(jù)修復(fù)模型，這種模型通過分析優(yōu)化對應(yīng)的線性網(wǎng)絡(luò)編碼的數(shù)據(jù)修復(fù)速度。從實際使用角度可已看出，該方法的局限性主要在于除了要維護(hù)現(xiàn)有的數(shù)據(jù)，同時還可以有效維護(hù)大量的節(jié)點信息，很難解決整個系統(tǒng)的負(fù)載均衡問題。于此同時，文獻(xiàn)[11]于2005年經(jīng)由IBM實驗室提出了關(guān)于針對多磁盤故障的糾刪算法，比如HoVer碼以及R5X0碼等方法。

綜合以上可以看出，在關(guān)于糾刪碼算法的研究過程中，主要集中于糾刪碼的以下的問題。首先，糾刪算法的冗余度問題，即系統(tǒng)在滿足一定糾刪性能的情況下產(chǎn)生多少冗余編碼才可以滿足整個系統(tǒng)的性能；其次，糾刪算法編碼的復(fù)雜度問題；因為糾刪算法的復(fù)雜度不僅直接影響文件的存儲時間，同時也是衡量糾刪算法優(yōu)劣的一個性能指標(biāo)；最后，糾刪算法的譯碼復(fù)雜度問題，該問題類似于是編碼算法逆，同時也直接影響整個數(shù)據(jù)塊文件重構(gòu)的修復(fù)速度，因此在研究糾刪算法時，必須考慮以上三個問題。同時，還要關(guān)注整個糾刪算法的數(shù)據(jù)修復(fù)的成功率問題以及數(shù)據(jù)結(jié)構(gòu)、節(jié)點的優(yōu)化問題。

因此，本論文利用決策樹模型在數(shù)據(jù)決策時的優(yōu)越性，建立了基于決策樹模型的分布式存儲數(shù)據(jù)糾刪碼修復(fù)算法。該方法通過采用決策樹模型對原始數(shù)據(jù)進(jìn)行分類編碼，同時將得到的決策樹模型帶來的冗余數(shù)據(jù)存儲于模型中不同節(jié)點上，從而滿足超大規(guī)模數(shù)據(jù)并行存儲與修復(fù)的需求。

2 糾刪碼算法原理

糾刪碼算法作為當(dāng)前比較典型的數(shù)據(jù)存儲與修復(fù)算法，由于其占用資源少、可靠性高以及修復(fù)速度快的優(yōu)點引起了國內(nèi)外眾多研究學(xué)者進(jìn)行算法研究。在進(jìn)行研究糾刪碼之前，首先對以下幾個基本概念進(jìn)行解釋；首先，將數(shù)據(jù)塊定義為分布式數(shù)據(jù)存儲的過程中，將數(shù)據(jù)按照設(shè)定大小形式來進(jìn)行存儲；其次，在進(jìn)行編碼存儲的過程中將存儲冗余信息(校驗信息)所占用的存儲塊成為冗余塊，同時在進(jìn)行糾刪碼存儲的過程中也將該內(nèi)容稱為校驗塊；然后將存放數(shù)據(jù)塊的節(jié)點以及校驗數(shù)據(jù)的節(jié)點分別成為數(shù)據(jù)節(jié)點和校驗節(jié)點。典型糾刪碼技術(shù)的基本原理如圖1所示。

圖1 糾刪碼原理結(jié)構(gòu)示意圖

如圖1所示可以看出，假設(shè)利用經(jīng)典的三元組數(shù)據(jù)(n，k，k′)來表述糾刪碼。首先，將原始的存儲數(shù)據(jù)Data，分別存儲與對應(yīng)的分解為大小恒定的k個數(shù)據(jù)塊中。因此，可以得到需要的數(shù)據(jù)塊個數(shù)為

Nblock=Size(Data)/k

(1)

在對原始數(shù)據(jù)進(jìn)行編碼的過程中，一般都會采用特定的數(shù)據(jù)編碼算法，對所有k個數(shù)據(jù)塊進(jìn)行編碼，然后可以得到Nblock數(shù)據(jù)塊。在對Nblock個編碼數(shù)據(jù)塊進(jìn)行存儲的過程中，分別將Nblock數(shù)據(jù)塊存儲在N個不同的存儲節(jié)點上，這些節(jié)點之間相互獨立，在進(jìn)行恢復(fù)數(shù)據(jù)的時候，如果其中某些節(jié)點出現(xiàn)問題或者丟失，可利用其它存活的節(jié)點來完成對數(shù)據(jù)的恢復(fù)。

由于本文主要描述糾刪碼在數(shù)據(jù)恢復(fù)中的作用，因此在進(jìn)行數(shù)據(jù)恢復(fù)過程中，首先以4數(shù)據(jù)塊與2冗余數(shù)據(jù)塊為例，建立對應(yīng)的數(shù)據(jù)編碼方法：

(2)

其中，MC表示編碼系數(shù)矩陣，C為編碼矩陣元素；Data需要存儲的編碼數(shù)據(jù)；Ek表示與存儲數(shù)據(jù)行列數(shù)大小對應(yīng)的單位陣。利用公式(2)完成對數(shù)據(jù)編碼存儲。在進(jìn)行解碼的過程中，如果對應(yīng)的編碼塊節(jié)點出現(xiàn)錯誤，如公式(3)所示

(3)

根據(jù)公式(2)和(3)可進(jìn)行恢復(fù)損失的數(shù)據(jù)，在進(jìn)行恢復(fù)的過程中首先構(gòu)造對應(yīng)的數(shù)據(jù)恢復(fù)矩陣

(4)

2.1 基于決策樹模型的糾刪碼數(shù)據(jù)恢復(fù)算法

在進(jìn)行數(shù)據(jù)存儲恢復(fù)的過程中，雖然傳統(tǒng)經(jīng)典的糾刪碼數(shù)據(jù)恢復(fù)算法已經(jīng)得到廣泛的應(yīng)用，但是依然存在數(shù)據(jù)恢復(fù)效率低，構(gòu)建繁瑣等處理問題。為了解決以上問題，本文集合決策樹在數(shù)據(jù)處理中的應(yīng)用，建立基于決策樹模型的糾刪碼數(shù)據(jù)恢復(fù)算法。

(5)

(6)

(7)

(8)

進(jìn)一步得

(9)

其次，為了描述確實節(jié)點數(shù)據(jù)的純度，文章采用決策樹模型中的基尼數(shù)值來進(jìn)行描述?；嶂刀x如下

(10)

其中，K為描述存儲數(shù)據(jù)的分類級別數(shù)；pk表示數(shù)據(jù)中的樣本點屬于第K階分類的概率；可以清楚的發(fā)現(xiàn)，如果樣本點數(shù)據(jù)屬于上述定義的1類的概率p，這樣可以得到對應(yīng)的概率密度的基尼指數(shù)為

Gini(Data)=2p(1-p)

(11)

同時，對于節(jié)點數(shù)據(jù)AData的基尼指數(shù)為

(12)

因此，結(jié)合公式(11)-(12)可以看出，在對確實數(shù)據(jù)進(jìn)行分類的過程中Gini(Data)對的數(shù)值越小，則存儲數(shù)據(jù)缺失的節(jié)點數(shù)據(jù)越小。

在結(jié)合糾刪碼建模的過程中，具體結(jié)構(gòu)流程示意圖如圖2所示。其中，首先將對應(yīng)的原始數(shù)據(jù)進(jìn)行數(shù)據(jù)遍歷，通過遍歷獲得對應(yīng)的樣本點數(shù)據(jù)，以及樣本數(shù)據(jù)對應(yīng)的存儲節(jié)點集。在進(jìn)行數(shù)據(jù)恢復(fù)的過程中不斷去驗證對應(yīng)恢復(fù)數(shù)據(jù)的基尼指數(shù)，看是否基尼指數(shù)到達(dá)滿意的程度。

圖2 決策樹糾刪流程示意圖

3 數(shù)字仿真與數(shù)據(jù)分析

為了驗證本文提出算法在數(shù)據(jù)恢復(fù)過程中的有效性，分別采用不同的方法來進(jìn)行對比，同時在不同角度來進(jìn)行分析本文算法的優(yōu)越性。

首先，分析存儲開銷方面。在進(jìn)行數(shù)據(jù)存儲的過程中，數(shù)據(jù)存儲的開銷與數(shù)據(jù)效率通常定義為實際數(shù)據(jù)大小空間M與數(shù)據(jù)在存儲系統(tǒng)中所占有的實際存儲空間S的比值。為了說明本文有效性，本文將三副本技術(shù)、HRCSD碼、S2-RAID碼以及本文提出的方法分析存儲開銷。4種策略所占用的存儲空間開銷如圖3所示。

圖3 存儲數(shù)據(jù)開銷對比

如圖3所示，可以看出在對同類數(shù)據(jù)進(jìn)行存儲的過程中，本文提出的算法的存儲開銷相對較低，同時采用S2-RAID方法所占用的存儲空間最大，另外兩種方法分別處于兩種方法的中間。所以采用本文提出的方法相對來說更好一些。

其次，在進(jìn)行數(shù)據(jù)恢復(fù)過程中，數(shù)據(jù)恢復(fù)的效率是考核所有數(shù)據(jù)恢復(fù)算法重要的衡量指標(biāo)。接下來通過不同的方法來對比數(shù)據(jù)恢復(fù)效率，恢復(fù)效率對比表格如表1所示。

表1 不同方法的數(shù)據(jù)恢復(fù)效率

如表1中的數(shù)據(jù)可以看，由于在進(jìn)行建模的過程中引入了對應(yīng)的決策樹模型以及算法流程在基尼指數(shù)的介入，大大提高了數(shù)據(jù)修復(fù)的準(zhǔn)確性。因此可以看出，在進(jìn)行數(shù)據(jù)恢復(fù)的過程中，采用本文提出的數(shù)據(jù)恢復(fù)的方法數(shù)據(jù)恢復(fù)效率更高，這也就意味著在進(jìn)行數(shù)據(jù)恢復(fù)的過程中恢復(fù)的數(shù)據(jù)精確度更高。

最后，分析采用不同方法進(jìn)行數(shù)據(jù)恢復(fù)過程中修復(fù)時間變化。同樣采用不同方法來對相同的存儲數(shù)據(jù)量進(jìn)行修復(fù)，修復(fù)時間曲線如圖4所示。

圖4 不同方法下的數(shù)據(jù)修復(fù)時間

如圖4所示，可以看出采用本文提出的方法在數(shù)據(jù)修復(fù)時所需要的修復(fù)時間相對較低，側(cè)面反映出本文提出的方法可以有效縮短對應(yīng)的數(shù)據(jù)修復(fù)時間。

4 結(jié)論

由于分布式數(shù)據(jù)存儲系統(tǒng)作為經(jīng)典數(shù)據(jù)容錯技術(shù)，因此基于分布式存儲數(shù)據(jù)糾刪碼技術(shù)研究一直是近些年數(shù)據(jù)修復(fù)過程中的研究熱點。在進(jìn)行數(shù)據(jù)備份與修復(fù)的過程中，糾刪碼技術(shù)以其數(shù)據(jù)存儲過程中資源消耗低、可靠性高等優(yōu)點在數(shù)據(jù)糾刪存儲領(lǐng)域得到了廣泛應(yīng)用。但是，隨著應(yīng)用數(shù)據(jù)的深入，以及大量數(shù)據(jù)在不斷地更新產(chǎn)生，傳統(tǒng)糾刪碼數(shù)據(jù)修復(fù)技術(shù)依然存在數(shù)據(jù)修復(fù)速度低、修復(fù)率低等缺點。因此，本文結(jié)合數(shù)據(jù)決策模型提出基于決策樹模型的分布式數(shù)據(jù)糾刪碼修復(fù)算法，該算法通過引入決策樹模型在數(shù)據(jù)決策上的優(yōu)勢，建立的基于決策樹的分布式存儲數(shù)據(jù)糾刪碼算法。最后，為了驗證本文算法在存儲效率，數(shù)據(jù)恢復(fù)效率以及對應(yīng)的修復(fù)時間方面的優(yōu)越性，本文給出了對應(yīng)的數(shù)據(jù)仿真。通過對比仿真可以看出本文提出的方法在修復(fù)速度、數(shù)據(jù)修復(fù)率等方面有很好的提升。