發(fā)布時間：2021-01-12 02:00

　　為推進糾刪碼在分布式存儲系統(tǒng)中的應(yīng)用,研究提高系統(tǒng)修復(fù)效率的算法。Hitchhiker碼作為一種最新的具有最優(yōu)存儲空間和較低修復(fù)成本的糾刪碼,已在Hadoop等分布式系統(tǒng)中部署實現(xiàn)。針對目前Hitchhiker碼采用均分的數(shù)據(jù)分配模式,存在網(wǎng)絡(luò)帶寬浪費的問題,提出一種最優(yōu)分配的Hitchhiker編碼（optimal allocation of Hitchhiker,OHitchhiker）。通過在編碼的分配環(huán)節(jié)引入一種動態(tài)選擇分配算法,使得OHitchhiker碼可以針對不同（n,k）值選擇具有最小修復(fù)代價的編碼結(jié)構(gòu)。理論分析以及實驗結(jié)果驗證了OHitchhiker碼在保持較低存儲空間的同時,進一步降低了下載帶寬。 

【文章來源】：計算機工程與設(shè)計. 2020,41(07)北大核心

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

【部分圖文】：

（n,k)=(13,10)3種糾刪碼

OHitchhiker碼（n=13,k=10）的編碼結(jié)構(gòu)

以O(shè)Hitchhiker碼（n=13,k=10）為例，當(dāng)節(jié)點Node8失效時，修復(fù)過程如圖3所示。從圖3中可以發(fā)現(xiàn)，當(dāng)節(jié)點Node8失效時，OHitchhiker碼首先通過下載{b1，…，b10,f1(b）}/b8，共10個數(shù)據(jù)，恢復(fù)出b8；然后根據(jù)DSDA算法生成分塊情況S={4,3,3}，發(fā)現(xiàn)失效節(jié)點Node8中數(shù)據(jù)a8∈S3；所以先下載Node12中的第一子條帶然后再下載Node13中的第二子條帶計算得到f2(b）和f3(b），全進行異或操作得到最后通過下載{a9,a10}，異或恢復(fù)出a8，此時下載了4個數(shù)據(jù)。因此，OHitchhiker碼（n=13,k=10）的修復(fù)過程需要下載圖中灰色塊部分，共14個數(shù)據(jù)塊，其平均修復(fù)帶寬βsysOHH=13.7。


本文編號：2971911