劉桂華

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

關鍵詞：分布式存儲系統；數據失效；數據維護；數據冗余

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）18-0005-02

1數據冗余策略

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

1.1副本冗余策略

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

1.2糾刪碼策略

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

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

從數學的角度上，可以描述為：將文件F看作（F1，F2，.....Fk）的一個集合，ai（ai1，ai2，...，aik）是一個由n個線性無關的向量組成的向量組，令

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

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

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

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

糾刪碼具有隨意k份文件就能解析出原文件的特性，在分布式存儲系統中，糾刪碼的功能主要有兩個，分別是數據重構和數據維護。數據重構是對冗余數據進行解碼，從而獲得原始數據。數據維護是對失效的數據進行修復。

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

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

從圖1可以看出，數據復制策略把原始數據復制為3份，分配到不同的節(jié)點中，當其中任意兩個節(jié)點失效時，可以從別的存儲節(jié)點獲取響應的數據。而糾刪碼策略則在原始數據的基礎上編碼出不同的數據塊，在圖1的糾刪碼策略中，任意兩個節(jié)點失效時，系統也可以根據其他兩個節(jié)點的數據還原出原始數據。

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

2 改進數據冗余策略方案

2.1副本冗余與糾刪碼結合策略

原始數據中并不是所有數據被訪問的可能性都是相同的，實際情況中往往大部分的訪問都集中在一部分數據中，稱這部分數據為熱門數據，而其余的數據被訪問的機會則比較少，稱此部分數據為冷門數據。熱門數據所在的存儲節(jié)點會因為頻繁地被訪問而更加容易失效，而冷門數據所在的存儲節(jié)點失效的概率則相對小很多。

結合前文中提到的問題，本文結合副本冗余策略和糾刪碼策略的優(yōu)勢，提出了一種副本與糾刪碼結合的策略?；舅枷胧鞘紫葘⒃紨祿M行分組，將其中的熱門數據塊使用副本策略進行存儲，即將它們復制為多份并分配到各個節(jié)點上；同時，將其中的冷門數據塊進行編碼，以糾刪碼的方式進行存儲。本策略的工作示意如圖2。

2.2數據熱度的判斷方法

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

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

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

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

3總結與展望

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

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

參考文獻：

[1]王禹.分布式存儲系統中的數據冗余與維護技術研究[D].華南理工大學，2011.

[2]黃震.大規(guī)模分布式存儲系統中數據冗余技術研究[D].國防科學技術大學，2012.