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

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


本文編號(hào)：2971911