分布式系統(tǒng)中數(shù)據(jù)冗余的研究

劉桂華

摘要：隨著數(shù)據(jù)爆炸性的增加，傳統(tǒng)的存儲(chǔ)系統(tǒng)已經(jīng)不能適應(yīng)存儲(chǔ)海量數(shù)據(jù)需要，而分布式系統(tǒng)能夠可靠并且高效地存儲(chǔ)海量數(shù)據(jù)，是存儲(chǔ)系統(tǒng)的發(fā)展方向。為了解決分布式存儲(chǔ)系統(tǒng)中的節(jié)點(diǎn)故障導(dǎo)致的數(shù)據(jù)失效問(wèn)題，該文研究了副本冗余策略和糾刪碼策略兩種用于數(shù)據(jù)維護(hù)的方案，結(jié)合這兩種數(shù)據(jù)冗余方案各自的優(yōu)點(diǎn)，設(shè)計(jì)了一種將兩種策略結(jié)合的數(shù)據(jù)冗余策略，效果良好。

關(guān)鍵詞：分布式存儲(chǔ)系統(tǒng)；數(shù)據(jù)失效；數(shù)據(jù)維護(hù)；數(shù)據(jù)冗余

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）18-0005-02

1數(shù)據(jù)冗余策略

為解決節(jié)點(diǎn)失效導(dǎo)致數(shù)據(jù)損失這個(gè)問(wèn)題，數(shù)據(jù)冗余策略被提出，冗余可以提高數(shù)據(jù)可用性和可靠性，同時(shí)也是容錯(cuò)的前提條件。數(shù)據(jù)冗余方案主要描述重復(fù)數(shù)據(jù)的組織形式[7，8]。數(shù)據(jù)冗余方案可以分為兩類：一類是副本冗余方案，另一類是糾刪碼方案。

1.1副本冗余策略

分布式存儲(chǔ)系統(tǒng)中，冗余副本技術(shù)是一種最常用的分布式數(shù)據(jù)管理機(jī)制[9]。副本冗余方案也稱為數(shù)據(jù)復(fù)制方案，是指將系統(tǒng)中的各個(gè)數(shù)據(jù)塊復(fù)制為多份并保存在不同的地方。這樣當(dāng)某個(gè)節(jié)點(diǎn)失效導(dǎo)致存儲(chǔ)在該節(jié)點(diǎn)上的數(shù)據(jù)不可用時(shí)，仍然可以訪問(wèn)存儲(chǔ)在別處的數(shù)據(jù)塊來(lái)獲取相應(yīng)的信息。副本的數(shù)目越多，整個(gè)系統(tǒng)越可靠，但是副本數(shù)量的增加勢(shì)必增加額外的系統(tǒng)資源消耗如存儲(chǔ)空間[10]，比如一個(gè)原始數(shù)據(jù)塊的大小是1GB，采用數(shù)據(jù)復(fù)制方案，每個(gè)數(shù)據(jù)塊復(fù)制k份，那么存儲(chǔ)系統(tǒng)就需要消耗k GB的存儲(chǔ)空間。一般的存儲(chǔ)系統(tǒng)很難支撐如此大的存儲(chǔ)開(kāi)支。副本冗余策略簡(jiǎn)單易用，因此應(yīng)用廣泛。但是其消耗存儲(chǔ)空間過(guò)大的缺點(diǎn)限制了其的使用。當(dāng)前對(duì)副本冗余方案的研究主要在如何實(shí)現(xiàn)各個(gè)副本一致性方面。

1.2糾刪碼策略

糾刪碼是另一種重要的數(shù)據(jù)冗余方案。糾刪碼方案的基本思想是，首先將原始數(shù)據(jù)分為k份，然后在對(duì)k份數(shù)據(jù)進(jìn)行編碼，得到另外n-k份數(shù)據(jù)，然后將總共為n份的數(shù)據(jù)發(fā)給不同的節(jié)點(diǎn)。在這n份數(shù)據(jù)中，只要其中任意的k份數(shù)據(jù)，就可以解析出原始數(shù)據(jù)。

從糾刪碼基本的形態(tài)來(lái)看，它是k個(gè)數(shù)據(jù)塊加上m個(gè)校驗(yàn)塊的結(jié)構(gòu)，其中數(shù)據(jù)和校驗(yàn)的k和m值都能夠按照一定的規(guī)則設(shè)定。在1～m個(gè)數(shù)據(jù)塊（無(wú)論數(shù)據(jù)或校驗(yàn)塊）損壞的情況下，整體數(shù)據(jù)仍然可以通過(guò)剩余數(shù)據(jù)塊上的數(shù)據(jù)進(jìn)行解析，得到整體數(shù)據(jù)，從而使整體數(shù)據(jù)不會(huì)丟失，存儲(chǔ)系統(tǒng)仍然可以使用。也就是說(shuō)一定數(shù)量的節(jié)點(diǎn)失效并不會(huì)造成用戶數(shù)據(jù)的丟失[12]。

從數(shù)學(xué)的角度上，可以描述為：將文件F看作（F1，F(xiàn)2，.....Fk）的一個(gè)集合，ai（ai1，ai2，...，aik）是一個(gè)由n個(gè)線性無(wú)關(guān)的向量組成的向量組，令

Ci=ai1*F1+ai2*F2+...+aik*Fk

用A表示aij（1<=i<=n，1<=j<=k），則有

A*F=C，即公式（1）：

其中C就是編碼后的冗余數(shù)據(jù)集合，其中的m=n-k個(gè)數(shù)據(jù)塊為冗余數(shù)據(jù)。只要C中剩余的數(shù)據(jù)塊大于等于k個(gè)，即使損失了一部分?jǐn)?shù)據(jù)塊，那么通過(guò)剩下的數(shù)據(jù)塊仍然可以恢復(fù)出原文件。令C中丟失了ci行，則在A中刪除對(duì)應(yīng)的ai行，得到A1，由于A中的向量線性無(wú)關(guān)，所以A1可逆，解析過(guò)程如公式（2）。

糾刪碼具有隨意k份文件就能解析出原文件的特性，在分布式存儲(chǔ)系統(tǒng)中，糾刪碼的功能主要有兩個(gè)，分別是數(shù)據(jù)重構(gòu)和數(shù)據(jù)維護(hù)。數(shù)據(jù)重構(gòu)是對(duì)冗余數(shù)據(jù)進(jìn)行解碼，從而獲得原始數(shù)據(jù)。數(shù)據(jù)維護(hù)是對(duì)失效的數(shù)據(jù)進(jìn)行修復(fù)。

糾刪碼是一種保護(hù)存儲(chǔ)系統(tǒng)中數(shù)據(jù)的一種機(jī)制，能夠容忍系統(tǒng)內(nèi)一定存儲(chǔ)節(jié)點(diǎn)的失效而不影響系統(tǒng)數(shù)據(jù)的完整性。采用糾刪碼方案的存儲(chǔ)系統(tǒng)有一定的容錯(cuò)能力，但是當(dāng)失效的數(shù)據(jù)塊達(dá)到一定的數(shù)量時(shí)，數(shù)據(jù)將無(wú)法恢復(fù)。因此系統(tǒng)需要及時(shí)地對(duì)失效的數(shù)據(jù)進(jìn)行恢復(fù)。傳統(tǒng)的糾刪碼維護(hù)方案是先恢復(fù)原始數(shù)據(jù)，再通過(guò)對(duì)原始數(shù)據(jù)的線性組合得到失效的冗余數(shù)據(jù)。因此，每一個(gè)數(shù)據(jù)塊的失效，就需要下載k份數(shù)據(jù)塊進(jìn)行恢復(fù)，那么系統(tǒng)的維護(hù)通信開(kāi)銷就將非常巨大，對(duì)某些低速網(wǎng)絡(luò)而言，這種開(kāi)銷可能是無(wú)法容忍的。糾刪碼機(jī)制雖然能夠節(jié)省存儲(chǔ)開(kāi)銷，但造成了讀數(shù)據(jù)性能的下降[13]，在使用糾刪碼維護(hù)策略的系統(tǒng)中會(huì)經(jīng)常出現(xiàn)用戶訪問(wèn)延遲的現(xiàn)象。

1.3副本冗余策略和糾刪碼策略的比較

從圖1可以看出，數(shù)據(jù)復(fù)制策略把原始數(shù)據(jù)復(fù)制為3份，分配到不同的節(jié)點(diǎn)中，當(dāng)其中任意兩個(gè)節(jié)點(diǎn)失效時(shí)，可以從別的存儲(chǔ)節(jié)點(diǎn)獲取響應(yīng)的數(shù)據(jù)。而糾刪碼策略則在原始數(shù)據(jù)的基礎(chǔ)上編碼出不同的數(shù)據(jù)塊，在圖1的糾刪碼策略中，任意兩個(gè)節(jié)點(diǎn)失效時(shí)，系統(tǒng)也可以根據(jù)其他兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)還原出原始數(shù)據(jù)。

由圖1可知，在同等可靠性的情況下，相比副本方案，糾刪碼方案將極大地減少數(shù)據(jù)的存儲(chǔ)空間。尤其是在大量數(shù)據(jù)時(shí)，采用糾刪碼策略所節(jié)省的存儲(chǔ)空間是很可觀的。但是，存儲(chǔ)系統(tǒng)需要花費(fèi)極大開(kāi)銷對(duì)失效的數(shù)據(jù)進(jìn)行及時(shí)修復(fù)，而采用副本冗余策略的存儲(chǔ)系統(tǒng)在修復(fù)時(shí)所需要的資源遠(yuǎn)遠(yuǎn)小于采用糾刪碼策略的存儲(chǔ)系統(tǒng)。兩種策略都有各自的優(yōu)缺點(diǎn)，副本冗余策略需要更多的存儲(chǔ)空間，而糾刪碼策略需要更大的通信維護(hù)量和計(jì)算量。如何解決這兩種策略所存在的問(wèn)題，成立當(dāng)下的難點(diǎn)。

2 改進(jìn)數(shù)據(jù)冗余策略方案

2.1副本冗余與糾刪碼結(jié)合策略

原始數(shù)據(jù)中并不是所有數(shù)據(jù)被訪問(wèn)的可能性都是相同的，實(shí)際情況中往往大部分的訪問(wèn)都集中在一部分?jǐn)?shù)據(jù)中，稱這部分?jǐn)?shù)據(jù)為熱門(mén)數(shù)據(jù)，而其余的數(shù)據(jù)被訪問(wèn)的機(jī)會(huì)則比較少，稱此部分?jǐn)?shù)據(jù)為冷門(mén)數(shù)據(jù)。熱門(mén)數(shù)據(jù)所在的存儲(chǔ)節(jié)點(diǎn)會(huì)因?yàn)轭l繁地被訪問(wèn)而更加容易失效，而冷門(mén)數(shù)據(jù)所在的存儲(chǔ)節(jié)點(diǎn)失效的概率則相對(duì)小很多。

結(jié)合前文中提到的問(wèn)題，本文結(jié)合副本冗余策略和糾刪碼策略的優(yōu)勢(shì)，提出了一種副本與糾刪碼結(jié)合的策略。基本思想是首先將原始數(shù)據(jù)進(jìn)行分組，將其中的熱門(mén)數(shù)據(jù)塊使用副本策略進(jìn)行存儲(chǔ)，即將它們復(fù)制為多份并分配到各個(gè)節(jié)點(diǎn)上；同時(shí)，將其中的冷門(mén)數(shù)據(jù)塊進(jìn)行編碼，以糾刪碼的方式進(jìn)行存儲(chǔ)。本策略的工作示意如圖2。

2.2數(shù)據(jù)熱度的判斷方法

在實(shí)際的應(yīng)用中，各數(shù)據(jù)塊的被訪問(wèn)次數(shù)，即數(shù)據(jù)的熱度，與預(yù)期值會(huì)有差別，并且會(huì)隨時(shí)間變化。本策略設(shè)計(jì)了判斷數(shù)據(jù)熱度的算法，監(jiān)測(cè)各個(gè)數(shù)據(jù)塊的熱度，如果數(shù)據(jù)塊的實(shí)際熱度與預(yù)期不符合，就對(duì)其進(jìn)行轉(zhuǎn)換。

熱度監(jiān)測(cè)的實(shí)現(xiàn)方法：選取時(shí)間段T為一個(gè)周期，在Tn+1時(shí)刻對(duì)之前的n個(gè)周期各個(gè)數(shù)據(jù)塊的被訪問(wèn)次數(shù)作統(tǒng)計(jì)，若是發(fā)現(xiàn)某些熱門(mén)數(shù)據(jù)的訪問(wèn)量很少或是某些冷門(mén)數(shù)據(jù)的訪問(wèn)量很多，則對(duì)熱門(mén)數(shù)據(jù)和冷門(mén)數(shù)據(jù)作必要的變換。這種方法缺點(diǎn)是只從n個(gè)周期的訪問(wèn)熱度角度考慮而忽略了最近時(shí)間的訪問(wèn)熱度，不夠全面。比如有某個(gè)數(shù)據(jù)塊，在前（n-3）個(gè)周期內(nèi)都沒(méi)有被訪問(wèn)，但在最近3個(gè)周期內(nèi)訪問(wèn)次數(shù)突然增多，從總體上判斷應(yīng)歸為冷門(mén)數(shù)據(jù)，但實(shí)際上該數(shù)據(jù)塊并不算冷門(mén)數(shù)據(jù)。針對(duì)這個(gè)問(wèn)題，本策略除了對(duì)前n個(gè)周期的被訪問(wèn)次數(shù)進(jìn)行統(tǒng)計(jì)外，還對(duì)各數(shù)據(jù)塊最近三個(gè)周期的被訪問(wèn)次數(shù)進(jìn)行統(tǒng)計(jì)，最后將兩者進(jìn)行加權(quán)平均，將結(jié)果視為判斷是否為熱門(mén)數(shù)據(jù)的依據(jù)。本策略將前n個(gè)周期和最近三個(gè)周期的權(quán)值比設(shè)為4：6。例如某個(gè)數(shù)據(jù)塊在前n個(gè)周期被訪問(wèn)20次，最近三個(gè)周期被訪問(wèn)10次，則可以將m=20*0.4+10*0.6=14作為該數(shù)據(jù)塊的熱度。此外，頻繁地對(duì)熱門(mén)數(shù)據(jù)或冷門(mén)數(shù)據(jù)進(jìn)行轉(zhuǎn)換也會(huì)對(duì)系統(tǒng)造成極大的開(kāi)銷，因此所得到的結(jié)果如果現(xiàn)狀差別不是很大，不作調(diào)整。

與糾刪碼策略相比，本策略的優(yōu)點(diǎn)有：1）由于熱門(mén)數(shù)據(jù)采用副本策略，用戶可以從多個(gè)地方獲得所需數(shù)據(jù)，因此很大程度上解決了用戶訪問(wèn)數(shù)據(jù)延遲的問(wèn)題。2）當(dāng)熱門(mén)數(shù)據(jù)失效時(shí)，系統(tǒng)可以找到相應(yīng)的副本，然后直接進(jìn)行復(fù)制恢復(fù)。不用下載k個(gè)數(shù)據(jù)塊進(jìn)行解析，極大地節(jié)省了網(wǎng)絡(luò)資源和CPU資源；與副本冗余策略相比，本策略避免了為冷門(mén)資源分配大量存儲(chǔ)空間的情況，使得存儲(chǔ)空間的利用率得到很大的提升。

本策略比副本冗余策略更節(jié)省存儲(chǔ)空間，比糾刪碼冗余策略則消耗更少的通信維護(hù)量和計(jì)算量。在實(shí)際應(yīng)用中做到了資源更充分更有效率的利用，取得了比兩者都更令人滿意的效果。

3總結(jié)與展望

本文在仔細(xì)研究了副本冗余策略和糾刪碼策略的基礎(chǔ)上，結(jié)合了副本冗余策略和糾刪碼策略的優(yōu)點(diǎn)，提出了兩者相結(jié)合的數(shù)據(jù)冗余策略，并給出了判斷數(shù)據(jù)熱度的算法。解決了其他冗余存儲(chǔ)系統(tǒng)中的存儲(chǔ)量大，通信維護(hù)量大，計(jì)算量重等問(wèn)題，為數(shù)據(jù)冗余策略提供了很有意義的參考。

與此同時(shí)，本文所提出的策略還存在一些不足，比如所采用的糾刪碼算法還可以繼續(xù)優(yōu)化，判斷數(shù)據(jù)熱度的算法也存在改進(jìn)的空間。在未來(lái)的研究中，將針對(duì)這些不足之處作進(jìn)一步的改進(jìn)。

參考文獻(xiàn)：

[1]王禹.分布式存儲(chǔ)系統(tǒng)中的數(shù)據(jù)冗余與維護(hù)技術(shù)研究[D].華南理工大學(xué)，2011.

[2]黃震.大規(guī)模分布式存儲(chǔ)系統(tǒng)中數(shù)據(jù)冗余技術(shù)研究[D].國(guó)防科學(xué)技術(shù)大學(xué)，2012.