陳浩

摘 要：隨著存儲規(guī)模的增大和信息節(jié)點的增多，基于分布式存儲系統的磁盤發(fā)生故障的概率越來越高。為了增強系統的可靠性，我們通過RS算法引入冗余數據。隨后該研究針對傳統RS碼的生成矩陣做出了一些改進，使得生成矩陣1的數目減少，優(yōu)化了編碼解碼的速度。

關鍵詞：分布式存儲系統 糾刪碼 RS碼 冗余數據

中圖分類號：TP393 文獻標識碼：A 文章編號：1672-3791（2014）08（c）-0020-02

1 Cauchy RS編碼矩陣優(yōu)化

原來的Cauchy矩陣被認為是無差異的，算法復雜度一樣。該研究給出了一種構建Cauchy編碼矩陣的算法。我們把編譯結果和原來的CRS碼[1]和其他一些陣列奇偶校驗碼做以比較。

假設o表示每一個編碼矩陣中“1”的平均數目。那么在計算每一個冗余包所需要進行的異或運算次數為。舉例來說，對于圖1的編碼矩陣來說，“1”的總數目為47個。剩余編碼矩陣一共有6行，o為7.83，則需要進行的異或運算次數平均為6.83次。

考慮另外一種構造Cauchy矩陣的方法：集合X取域中的前m個元素，Y取后n個元素。在我們給出的例子中，這個編碼矩陣有54個“1”。這種隨機產生矩陣比原來的編碼矩陣的復雜度要高17%。

考慮三個參數n，m和w，把域中個元素分到集合X和Y中的方法總數為。我們列舉了所有可能組合的情況，縱坐標表示的是編碼算法復雜度，如圖1所示：

首先，我們可以觀察到當n的值越小影響就越大，這是因為n和m的選擇受制于不等式，而n越小，在域上可供m選擇的值越多，所以產生的差距也就越大；當n的值增大，矩陣選擇所造成的差異逐漸減小。然后當n值增大時，CRS算法性能逐漸下降，這是因為當Cauchy矩陣的維度不斷增大時，編碼矩陣從域中所包含的元素越多。對于域中的每一個元素，它所包含的“1”的數目的變化范圍在和之間。維度較小的矩陣可以盡可能多的包含“1”的數目為的元素，維度較大的矩陣則必須包含“1”的數目為的元素，所以它的計算復雜度較高。

2 測試結果

隨后我們把通過上一章得到的編碼矩陣和其他類型的編碼算法進行比較：Cauchy RS（Original），Cauchy RS（GC），Cauchy RS（BC）和Star-Code[2]。

所有CRS類型的碼中，CRS（GC）的表現最好，盡管它的編碼復雜度也會隨著n的增大而降低，和其他兩個類型的CRS表現趨向一致。并且每次當為整數時，CRS（Original）和CRS（BC）的編碼復雜度都會發(fā)生跳躍性變化，而CRS（GC）一直是平滑增長。

3 結語

該研究通過改善Cauchy矩陣的生成方式提高了編碼效率。在用C語言實現CRS算法時只用了橫向校驗，這樣每次在進行解碼時都需要占據過多的帶寬去下載所需要的數據塊或者冗余塊，如果我們考慮使用對角線校驗，那么就可以進行混合修復，這樣可以節(jié)約帶寬。

參考文獻

[1] Plank JS. A Tutorial on Reed-Solomon Coding for Fault-tolerance in Raid-like Systems [J]. Software ？Practice & Experience，1997，27（9）：995-1012.

[2] Blomer J， Kalfane M， Karpinski M， et al. An XOR-based Erasure-resilient Coding Scheme [J]. California， UC Berkeley， International Computer Science Institute Technical Reporttr-95-048，1995：1-19.