一種基于分布式存儲(chǔ)系統(tǒng)的Piggyback碼
發(fā)布時(shí)間:2021-01-11 23:18
隨著大數(shù)據(jù)時(shí)代的來臨,糾刪碼在分布式存儲(chǔ)系統(tǒng)中有著越來越重要的應(yīng)用.Piggyback碼作為糾刪碼的一種,因其同時(shí)具有高效率存儲(chǔ)和低修復(fù)帶寬的優(yōu)點(diǎn)而成為近年來的研究熱點(diǎn),RSR-Ⅱ碼作為Piggyback碼中在減少修復(fù)帶寬方面最典型的碼,因其修復(fù)過程中需要進(jìn)行有限域上方程組的求解,使得編碼復(fù)雜度和修復(fù)復(fù)雜度過高.針對這個(gè)問題,提出了一種新的Piggyback碼,并給出了其一般性構(gòu)造和修復(fù)算法,該碼基于分布式存儲(chǔ)系統(tǒng)中廣泛使用的系統(tǒng)型M DS碼,通過結(jié)合Piggybacking框架的核心思想,構(gòu)造了新的piggybacks添加規(guī)則,有效避免了有限域上的方程組求解問題.對比分析表明,新的Piggyback碼既保持了RSR-Ⅱ碼較低的平均修復(fù)帶寬率,還具有更低的編碼復(fù)雜度和修復(fù)復(fù)雜度.
【文章來源】:小型微型計(jì)算機(jī)系統(tǒng). 2020,41(05)北大核心
【文章頁數(shù)】:7 頁
【部分圖文】:
系統(tǒng)型(6,4)-MDS碼
在本文中,將以系統(tǒng)型(n,k)-MDS碼作為基礎(chǔ)碼,用{aj=(a1,j,a2,j,…,ak,j)T}jm=1表示包含m個(gè)實(shí)例的原始數(shù)據(jù),并且以未被編碼的形式存儲(chǔ)在k個(gè)系統(tǒng)節(jié)點(diǎn)上,根據(jù)圖2(a)中介紹的Piggybacking框架,則具有Piggybacking框架的系統(tǒng)型MDS碼如圖2(b)所示.2.3 RSR-II碼
由于篇幅所限,RSR-II碼的編碼構(gòu)造及修復(fù)算法詳見文獻(xiàn)[13].下面給出RSR-II碼的例子,該例子以系統(tǒng)型(13,9)-M DS碼作為基礎(chǔ)碼,校驗(yàn)節(jié)點(diǎn)的個(gè)數(shù)為r=4,因此實(shí)例數(shù)為2r-3=5.首先,對基礎(chǔ)碼添加piggybacks后如圖3(a)所示,然后,在同一節(jié)點(diǎn)的不同實(shí)例間進(jìn)行可逆線性變換,得到最終的編碼結(jié)果如圖3(b)所示.由系統(tǒng)節(jié)點(diǎn)數(shù)為k,校驗(yàn)節(jié)點(diǎn)數(shù)為r的RSR-II碼修復(fù)算法可知,為修復(fù)一個(gè)系統(tǒng)節(jié)點(diǎn),需要在有限域上求解r-1個(gè)方程,而RSR-II碼添加piggybacks的規(guī)則導(dǎo)致了其中r-2個(gè)方程為屬于同一個(gè)方程組的方程,為使得方程組總是有解的,便在編碼過程中引入了長度為k的向量.但是,隨著校驗(yàn)節(jié)點(diǎn)數(shù)r的不斷增大,不僅由公式(1)公式(2)計(jì)算向量的乘法計(jì)算量會(huì)隨之增大,而且所解方程組中方程的數(shù)量也會(huì)隨之增大,這顯然會(huì)增加編碼復(fù)雜度和修復(fù)復(fù)雜度.
【參考文獻(xiàn)】:
期刊論文
[1]分布式存儲(chǔ)系統(tǒng)中的糾刪碼容錯(cuò)方法研究[J]. 孫黎,蘇宇,張弛,張濤. 計(jì)算機(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]分布式存儲(chǔ)中的糾刪碼容錯(cuò)技術(shù)研究[J]. 王意潔,許方亮,裴曉強(qiáng). 計(jì)算機(jī)學(xué)報(bào). 2017(01)
本文編號(hào):2971667
【文章來源】:小型微型計(jì)算機(jī)系統(tǒng). 2020,41(05)北大核心
【文章頁數(shù)】:7 頁
【部分圖文】:
系統(tǒng)型(6,4)-MDS碼
在本文中,將以系統(tǒng)型(n,k)-MDS碼作為基礎(chǔ)碼,用{aj=(a1,j,a2,j,…,ak,j)T}jm=1表示包含m個(gè)實(shí)例的原始數(shù)據(jù),并且以未被編碼的形式存儲(chǔ)在k個(gè)系統(tǒng)節(jié)點(diǎn)上,根據(jù)圖2(a)中介紹的Piggybacking框架,則具有Piggybacking框架的系統(tǒng)型MDS碼如圖2(b)所示.2.3 RSR-II碼
由于篇幅所限,RSR-II碼的編碼構(gòu)造及修復(fù)算法詳見文獻(xiàn)[13].下面給出RSR-II碼的例子,該例子以系統(tǒng)型(13,9)-M DS碼作為基礎(chǔ)碼,校驗(yàn)節(jié)點(diǎn)的個(gè)數(shù)為r=4,因此實(shí)例數(shù)為2r-3=5.首先,對基礎(chǔ)碼添加piggybacks后如圖3(a)所示,然后,在同一節(jié)點(diǎn)的不同實(shí)例間進(jìn)行可逆線性變換,得到最終的編碼結(jié)果如圖3(b)所示.由系統(tǒng)節(jié)點(diǎn)數(shù)為k,校驗(yàn)節(jié)點(diǎn)數(shù)為r的RSR-II碼修復(fù)算法可知,為修復(fù)一個(gè)系統(tǒng)節(jié)點(diǎn),需要在有限域上求解r-1個(gè)方程,而RSR-II碼添加piggybacks的規(guī)則導(dǎo)致了其中r-2個(gè)方程為屬于同一個(gè)方程組的方程,為使得方程組總是有解的,便在編碼過程中引入了長度為k的向量.但是,隨著校驗(yàn)節(jié)點(diǎn)數(shù)r的不斷增大,不僅由公式(1)公式(2)計(jì)算向量的乘法計(jì)算量會(huì)隨之增大,而且所解方程組中方程的數(shù)量也會(huì)隨之增大,這顯然會(huì)增加編碼復(fù)雜度和修復(fù)復(fù)雜度.
【參考文獻(xiàn)】:
期刊論文
[1]分布式存儲(chǔ)系統(tǒng)中的糾刪碼容錯(cuò)方法研究[J]. 孫黎,蘇宇,張弛,張濤. 計(jì)算機(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]分布式存儲(chǔ)中的糾刪碼容錯(cuò)技術(shù)研究[J]. 王意潔,許方亮,裴曉強(qiáng). 計(jì)算機(jī)學(xué)報(bào). 2017(01)
本文編號(hào):2971667
本文鏈接:http://www.wukwdryxk.cn/kejilunwen/jisuanjikexuelunwen/2971667.html
最近更新
教材專著