基于分布式存儲(chǔ)系統(tǒng)的Reed—Solomon算法優(yōu)化

陳浩

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

關(guān)鍵詞：分布式存儲(chǔ)系統(tǒng) 糾刪碼 RS碼 冗余數(shù)據(jù)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）08（c）-0020-02

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

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

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

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

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

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

2 測(cè)試結(jié)果

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

[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.