隨著大數(shù)據(jù)時代的來臨,糾刪碼在分布式存儲系統(tǒng)中有著越來越重要的應用.Piggyback碼作為糾刪碼的一種,因其同時具有高效率存儲和低修復帶寬的優(yōu)點而成為近年來的研究熱點,RSR-Ⅱ碼作為Piggyback碼中在減少修復帶寬方面最典型的碼,因其修復過程中需要進行有限域上方程組的求解,使得編碼復雜度和修復復雜度過高.針對這個問題,提出了一種新的Piggyback碼,并給出了其一般性構造和修復算法,該碼基于分布式存儲系統(tǒng)中廣泛使用的系統(tǒng)型M DS碼,通過結合Piggybacking框架的核心思想,構造了新的piggybacks添加規(guī)則,有效避免了有限域上的方程組求解問題.對比分析表明,新的Piggyback碼既保持了RSR-Ⅱ碼較低的平均修復帶寬率,還具有更低的編碼復雜度和修復復雜度. 

【文章來源】：小型微型計算機系統(tǒng). 2020,41(05)北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

系統(tǒng)型(6,4)-MDS碼

在本文中，將以系統(tǒng)型(n,k)-MDS碼作為基礎碼，用{aj=(a1,j,a2,j，…，ak,j)T}jm=1表示包含m個實例的原始數(shù)據(jù)，并且以未被編碼的形式存儲在k個系統(tǒng)節(jié)點上，根據(jù)圖2(a)中介紹的Piggybacking框架，則具有Piggybacking框架的系統(tǒng)型MDS碼如圖2(b)所示．2.3 RSR-II碼

由于篇幅所限，RSR-II碼的編碼構造及修復算法詳見文獻[13]．下面給出RSR-II碼的例子，該例子以系統(tǒng)型(13,9)-M DS碼作為基礎碼，校驗節(jié)點的個數(shù)為r=4，因此實例數(shù)為2r-3=5．首先，對基礎碼添加piggybacks后如圖3(a)所示，然后，在同一節(jié)點的不同實例間進行可逆線性變換，得到最終的編碼結果如圖3(b)所示．由系統(tǒng)節(jié)點數(shù)為k，校驗節(jié)點數(shù)為r的RSR-II碼修復算法可知，為修復一個系統(tǒng)節(jié)點，需要在有限域上求解r-1個方程，而RSR-II碼添加piggybacks的規(guī)則導致了其中r-2個方程為屬于同一個方程組的方程，為使得方程組總是有解的，便在編碼過程中引入了長度為k的向量．但是，隨著校驗節(jié)點數(shù)r的不斷增大，不僅由公式(1)公式(2)計算向量的乘法計算量會隨之增大，而且所解方程組中方程的數(shù)量也會隨之增大，這顯然會增加編碼復雜度和修復復雜度．

【參考文獻】：
期刊論文
[1]分布式存儲系統(tǒng)中的糾刪碼容錯方法研究[J]. 孫黎,蘇宇,張弛,張濤.  計算機工程. 2019(11)
[2]Erasure coding for distributed storage: an overview[J]. S.B.BALAJI,M.Nikhil KRISHNAN,Myna VAJHA,Vinayak RAMKUMAR,Birenjith SASIDHARAN,P.Vijay KUMAR.  Science China（Information Sciences）. 2018(10)
[3]分布式存儲中的糾刪碼容錯技術研究[J]. 王意潔,許方亮,裴曉強.  計算機學報. 2017(01)



本文編號：2971667