NTar基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法

1、ntar:基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法許方亮，王意潔，裴曉強(qiáng)510152025303540（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院并行與分布處理國(guó)家重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410073）摘要：大規(guī)模分布式容錯(cuò)存儲(chǔ)系統(tǒng),采用糾刪碼作為數(shù)據(jù)冗余技術(shù)能夠比多副本技術(shù)以更低的額外存儲(chǔ)空間開(kāi)銷(xiāo)獲得相同的數(shù)據(jù)可靠性。然而，基于糾刪碼的數(shù)據(jù)冗余技術(shù)在修復(fù)一個(gè)失效編碼塊時(shí)需要從其他節(jié)點(diǎn)下載多個(gè)編碼塊，不僅占用了大量網(wǎng)絡(luò)資源，也嚴(yán)重降低了修復(fù)速度?，F(xiàn)有的修復(fù)方法都沒(méi)有考慮網(wǎng)絡(luò)拓?fù)涞挠绊憽榇?，提出并?shí)現(xiàn)了一種基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法 ntar。ntar 依據(jù)網(wǎng)絡(luò)拓?fù)鋵⑴c修復(fù)的節(jié)點(diǎn)組織成網(wǎng)絡(luò)距離最小的樹(shù)型結(jié)構(gòu)，縮短修

2、復(fù)期間數(shù)據(jù)的傳輸距離，從而減少占用的網(wǎng)絡(luò)資源并縮短修復(fù)時(shí)間。此外，提出了節(jié)點(diǎn)選擇算法 optree。optree 可快速地從所有可用節(jié)點(diǎn)中選出最優(yōu)的參與修復(fù)的節(jié)點(diǎn)組合，并同時(shí)生成最優(yōu)的樹(shù)型修復(fù)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)的星型修復(fù)，ntar可將修復(fù)占用的網(wǎng)絡(luò)資源降低 30%-45%，修復(fù)時(shí)間減少 50%-70%。關(guān)鍵詞： 計(jì)算機(jī)應(yīng)用；分布式存儲(chǔ)系統(tǒng)；網(wǎng)絡(luò)拓?fù)?；糾刪碼；數(shù)據(jù)修復(fù)中圖分類(lèi)號(hào)：tp393ntar:network topology-based tree-structured datareconstruction scheme for erasure codesxu fangliang

3、, wang yijie, pei xiaoqiang(national key laboratory for parallel and distributed processing, college of computer, nationaluniversity of defense technology, changsha 410073)abstract: distributed storage systems are employing erasure codes instead of replicatioin as dataredundant scheme, since the for

4、mer consume much less storage space than the latter over the samedata reliability. however, erasure codes require multiple blocks to be transmitted from survivingnodes to reconstruct a new block after a node failure, which occupies more network resource andlowers the reconstruction efficiency. previ

5、ous work mainly concerned about how to reduce thedata volume downloaded during repair, and neglected the influence of network topology. for that,a network topology based tree-structured data reconstruction scheme called ntar for erasurecodes is proposed and implemented. ntar builds a regeneration tr

6、ee with minimum total distanceaccording to the network topology to reduce the path length, which reduces network resourcesconsumption, and improves the reconstruction efficiency. moreover, an algorithm named optreeis also proposed to select the nodes which participate the reconstruction. optree can

7、quickly makean optimal selection and generate the optimal reconstruction tree at the same time. the results ofthorough experiments in a real cluster show that, compared with conventional reconstructionscheme, ntar can reduce network resource consumption by 30%-45%, and reduce thereconstruction time

8、by 50%-70%.key words: computer applications; disstributed storage system; network topology; erasurecodes; data reconstruction基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973)項(xiàng)目(2011cb302601)；國(guó)家自然科學(xué)基金項(xiàng)目(61379052)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863 計(jì)劃)項(xiàng)目(2013aa01a213)；湖南省自然科學(xué)杰出青年基金項(xiàng)目(s2010j5050)；高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助課題(20124307110015)作者簡(jiǎn)介：許方亮(1989-)，

9、男，碩士研究生，主要研究方向：分布式容錯(cuò)存儲(chǔ)系統(tǒng)，糾刪碼通信聯(lián)系人：王意潔(1971-)，女，教授，博士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)計(jì)算，數(shù)據(jù)庫(kù)，并行與分布處理. e-mail: -1-0 引言4550556065707580在云計(jì)算等領(lǐng)域應(yīng)用廣泛的大型分布式存儲(chǔ)系統(tǒng)，如 gfs1等，往往包含幾千甚至幾萬(wàn)個(gè)存儲(chǔ)節(jié)點(diǎn)。龐大的規(guī)模使節(jié)點(diǎn)失效成為了常態(tài)。為了保證數(shù)據(jù)的可靠性，即在部分存儲(chǔ)節(jié)點(diǎn)失效時(shí)仍然能夠訪問(wèn)系統(tǒng)中的所有數(shù)據(jù)，必須對(duì)進(jìn)入系統(tǒng)的所有數(shù)據(jù)進(jìn)行冗余存儲(chǔ)。常用的數(shù)據(jù)冗余技術(shù)包括多副本技術(shù)2和糾刪碼技術(shù)3。多副本技術(shù)因其簡(jiǎn)單和較高的數(shù)據(jù)訪問(wèn)帶寬等優(yōu)點(diǎn)已在現(xiàn)

10、有存儲(chǔ)系統(tǒng)中得到了廣泛應(yīng)用。然而，多副本極高的存儲(chǔ)成本，極大地增加了系統(tǒng)構(gòu)建和運(yùn)行成本。隨著近年來(lái)數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，過(guò)高的存儲(chǔ)成本使多副本技術(shù)越來(lái)越不適合用在大型的存儲(chǔ)系統(tǒng)中。相比于多副本技術(shù)，糾刪碼技術(shù)能以極低的額外存儲(chǔ)空間開(kāi)銷(xiāo)獲得相同或更高的數(shù)據(jù)可靠性4。因此，近年來(lái)糾刪碼技術(shù)在分布式存儲(chǔ)領(lǐng)域受到了廣泛關(guān)注。然而，糾刪碼極高的修復(fù)成本嚴(yán)重阻礙了它的大規(guī)模應(yīng)用。當(dāng)某個(gè)節(jié)點(diǎn)失效時(shí)，為了維持原有的數(shù)據(jù)可靠性，系統(tǒng)需要修復(fù)失效節(jié)點(diǎn)上的數(shù)據(jù)塊并將其放到其他可用節(jié)點(diǎn)中(稱(chēng)為新生節(jié)點(diǎn))。修復(fù)一個(gè)數(shù)據(jù)塊時(shí)，新生節(jié)點(diǎn)需要從多個(gè)可用數(shù)據(jù)節(jié)點(diǎn)(稱(chēng)為提供者節(jié)點(diǎn))分別下載一個(gè)數(shù)據(jù)塊才能修復(fù)出丟失的數(shù)據(jù)塊。這不僅

11、占用了大量的網(wǎng)絡(luò)資源，也極大地降低了數(shù)據(jù)修復(fù)速度。因此，研究如何降低糾刪碼修復(fù)所占用的網(wǎng)絡(luò)資源和耗費(fèi)的時(shí)間對(duì)促進(jìn)糾刪碼的廣泛應(yīng)用具有重要意義。在傳統(tǒng)的糾刪碼修復(fù)方法中，所有提供者節(jié)點(diǎn)都直接將數(shù)據(jù)塊傳送給新生節(jié)點(diǎn)，提供者節(jié)點(diǎn)與新生節(jié)點(diǎn)之間形成一個(gè)星型結(jié)構(gòu)。顯然，這種結(jié)構(gòu)所占用的網(wǎng)絡(luò)資源為提供者節(jié)點(diǎn)到新生節(jié)點(diǎn)的網(wǎng)絡(luò)資源之和，修復(fù)的速度也受限于新生節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬。為了降低糾刪碼的修復(fù)時(shí)間，li jun 等人提出了一種基于節(jié)點(diǎn)間可用帶寬的樹(shù)型修復(fù)方法5。此方法根據(jù)修復(fù)時(shí)節(jié)點(diǎn)間可用帶寬來(lái)建立樹(shù)型修復(fù)結(jié)構(gòu)，以提高修復(fù)速度。然而，此方法是基于一個(gè)節(jié)點(diǎn)可從多個(gè)節(jié)點(diǎn)同時(shí)接收數(shù)據(jù)的假設(shè)。這與實(shí)際情況不符，目前無(wú)法

12、實(shí)現(xiàn)。因?yàn)楝F(xiàn)有網(wǎng)絡(luò)接口只能采用分時(shí)的方法輪流從不同節(jié)點(diǎn)接收數(shù)據(jù)。傳統(tǒng)的星型修復(fù)方法和上述基于節(jié)點(diǎn)間可用帶寬的樹(shù)型修復(fù)方法都沒(méi)有考慮到網(wǎng)絡(luò)拓?fù)鋵?duì)修復(fù)占用網(wǎng)絡(luò)資源的影響。為此，本文提出了一種基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法ntar。它根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建最優(yōu)的樹(shù)型修復(fù)結(jié)構(gòu)(稱(chēng)為修復(fù)樹(shù))，以縮短修復(fù)時(shí)數(shù)據(jù)傳輸?shù)木嚯x，從而減少修復(fù)占用的網(wǎng)絡(luò)資源。ntar 與上述基于節(jié)點(diǎn)間可用帶寬的樹(shù)型修復(fù)方法是不同的。首先，ntar 的首要目標(biāo)是優(yōu)化修復(fù)占用的網(wǎng)絡(luò)資源，這是阻礙糾刪碼在實(shí)際中廣泛應(yīng)用的首要因素6；其次，ntar根據(jù)網(wǎng)絡(luò)拓?fù)鋪?lái)構(gòu)建修復(fù)樹(shù)而非節(jié)點(diǎn)間可用帶寬，在數(shù)據(jù)中心中，前者比后者更穩(wěn)定且非常容易獲得；

13、最后，ntar 的修復(fù)速度分析和優(yōu)化基于一個(gè)節(jié)點(diǎn)在某一時(shí)刻只能從一個(gè)節(jié)點(diǎn)接收數(shù)據(jù)的假設(shè)，完全可以實(shí)現(xiàn)。本文的貢獻(xiàn)有以下幾點(diǎn)。第一，針對(duì)現(xiàn)有糾刪碼修復(fù)方法沒(méi)有考慮網(wǎng)絡(luò)拓?fù)溆绊懙牟蛔?，提出了基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法 ntar，證明了最小生成樹(shù)是最優(yōu)的修復(fù)樹(shù)，并且分析了其修復(fù)時(shí)間；第二，提出了從多個(gè)可用節(jié)點(diǎn)中快速選出最優(yōu)提供者節(jié)點(diǎn)組合并同時(shí)生成最優(yōu)修復(fù)樹(shù)的算法 optree；第三，基于 hdfs-raid 實(shí)現(xiàn)了 ntar，對(duì)其進(jìn)行了較全面的測(cè)試，并將其與星型修復(fù)方法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，相比于星型修復(fù)方法，ntar可以有效降低修復(fù)占用的網(wǎng)絡(luò)資源并提高修復(fù)速度。本文剩余部分組織結(jié)構(gòu)如下。

14、第 1 節(jié)介紹了降低糾刪碼修復(fù)成本的相關(guān)工作；第 2 節(jié)介紹了糾刪碼的編解碼與修復(fù)原理；第 3 節(jié)提出了一種基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法-2-ntar，包括快速選取最優(yōu)提供者節(jié)點(diǎn)組合并構(gòu)建出最優(yōu)修復(fù)樹(shù)的算法 optree；第 4 節(jié)通過(guò)實(shí)859095100105110115際實(shí)驗(yàn)對(duì) ntar 進(jìn)行了全面的測(cè)試；第 5 節(jié)總結(jié)全文。1 相關(guān)工作根據(jù)所用方法的不同，現(xiàn)有優(yōu)化糾刪碼的工作主要可分為以下三類(lèi)。第一，基于節(jié)點(diǎn)間可用網(wǎng)絡(luò)帶寬的糾刪碼樹(shù)型修復(fù)方法，由 li jun 等人最先提出5。此方法根據(jù)節(jié)點(diǎn)間可用帶寬構(gòu)建一棵以新生節(jié)點(diǎn)為根，并覆蓋所有提供者節(jié)點(diǎn)的最大生成樹(shù)作為修復(fù)樹(shù)。修復(fù)時(shí)，樹(shù)中子節(jié)

15、點(diǎn)向其父節(jié)點(diǎn)發(fā)送數(shù)據(jù)，節(jié)點(diǎn)接收到其子節(jié)點(diǎn)的數(shù)據(jù)后，將這些數(shù)據(jù)與自身存儲(chǔ)的數(shù)據(jù)進(jìn)行組合，然后再發(fā)送給自己的父節(jié)點(diǎn)，依次類(lèi)推，直至到達(dá)根節(jié)點(diǎn)。相比于星型結(jié)構(gòu)的修復(fù)策略，這種樹(shù)型修復(fù)方法能夠充分利用網(wǎng)絡(luò)中的空閑鏈路，提高修復(fù)速度。sun weidong 等人擴(kuò)展了這一做法，將其應(yīng)用于多節(jié)點(diǎn)失效時(shí)的并行修復(fù)7。然而，上述方法存在以下三個(gè)方面的不足。首先，它只有在一個(gè)節(jié)點(diǎn)可以從多個(gè)節(jié)點(diǎn)同時(shí)接收數(shù)據(jù)時(shí)才有效，這與目前實(shí)際情況不符；其次，節(jié)點(diǎn)間可用帶寬是動(dòng)態(tài)的，很難精確測(cè)量；最后，每次修復(fù)時(shí)都需要測(cè)量提供者節(jié)點(diǎn)和新生節(jié)點(diǎn)間的所有可用帶寬。這將耗費(fèi)很長(zhǎng)時(shí)間，并會(huì)增加大量額外的數(shù)據(jù)傳輸。第二，可用于所有基于異或

16、操作糾刪碼特殊修復(fù)方法。最早由 xiang liping 等人8提出，以?xún)?yōu)化 rdp9陣列碼修復(fù)時(shí)下載的數(shù)據(jù)量，osama khan 等人10將其一般化，使其適用于任何基于異或操作(xor)的糾刪碼。此方法通過(guò)盡量使用那些可以修復(fù)多個(gè)失效塊的可用塊，來(lái)達(dá)到降低下載數(shù)據(jù)量的目的。然而，這種基于 xor 的編碼大部分為陣列型編碼，容錯(cuò)能力有限，不適合于分布式容錯(cuò)存儲(chǔ)系統(tǒng)。第三，新型的糾刪碼。大部分都是從編碼本身來(lái)降低修復(fù)成本，如 lrcs(locallyrepairable codes)6、pyramid 碼11、expyramid 碼12、weaver 碼13等。這些編碼大都是通過(guò)分組編碼的方法

17、來(lái)減少修復(fù)時(shí)下載的數(shù)據(jù)量，都是對(duì)傳統(tǒng) rs 碼14的改進(jìn)，會(huì)增加存儲(chǔ)空間開(kāi)銷(xiāo)。另外，ntar 完全可與上述后兩類(lèi)工作結(jié)合在一起使用，進(jìn)一步降低其修復(fù)代價(jià)。2 糾刪碼的編碼與修復(fù)原理通常，糾刪碼可以用三元組 (n, k, k ) 來(lái)表示。(n, k, k ) 糾刪碼的基本思想是將數(shù)據(jù)對(duì)象 d分成 k 個(gè)大小相等的數(shù)據(jù)塊 d1, d2,l, dk ，通過(guò)特定的編碼算法對(duì)這 k 個(gè)數(shù)據(jù)塊進(jìn)行運(yùn)算，產(chǎn)生 n 個(gè)大小不變的編碼塊 c1,c2 ,l,cn ( n k )，使得其中任意 k 個(gè)塊都能通過(guò)相應(yīng)的解碼算法得到原數(shù)據(jù) d 對(duì)應(yīng)的 k 個(gè)數(shù)據(jù)塊( k k )。2.1 糾刪碼的編解碼原理目前用于分布式

18、存儲(chǔ)系統(tǒng)中的糾刪碼基本上都是線性的，即每個(gè)編碼塊 ci 都是數(shù)據(jù)塊d1, d2,l, dk 的線性組合，如式(1)所示，其中 gij fq ， i = 1,2,l, n ， j = 1,2,l, k ， fq 是大小為 q 的有限域(galois field)。( gi1 d1 d2 m dk -3-(1)gi 2 l gik ) = ci , i = 1, 2,l, n 2.2 糾刪碼的修復(fù)原理與編碼相同，修復(fù)時(shí)失效編碼塊也是用來(lái)修復(fù)這個(gè)塊的編碼的線性組合。哪些塊可以用120125來(lái)修復(fù)失效塊以及組合系數(shù)的計(jì)算方法取決于具體的糾刪碼，一般都需要對(duì)編碼時(shí)的系數(shù)矩陣求逆5。對(duì)于 rs 碼14，修

19、復(fù)時(shí)需要下載 k 個(gè)編碼塊。而對(duì)于改進(jìn)型糾刪碼，需要下載的編碼塊數(shù)在大部分情況都小于 k ，只有少數(shù)情況下會(huì)大于 k。本文以后統(tǒng)一以 r 表示任意線性糾刪碼在修復(fù)一個(gè)失效塊時(shí)需要下載的編碼塊數(shù)。記要修復(fù)的失效塊為 c0 ，用以修復(fù) c0 的所有編碼塊為 c1 ,c2 ,l,cr ，c0 與這些編碼塊的組合系數(shù)為 (b1 b2 l b r ) ， b j fq ， j = 1,2,l, r 。則糾刪碼的修復(fù)可統(tǒng)一表示成公式(2)。ri =1(2)3 基于網(wǎng)絡(luò)拓?fù)涞臉?shù)型修復(fù)方法在傳統(tǒng)的星型修復(fù)方法中，所有提供者節(jié)點(diǎn)都將自己的數(shù)據(jù)直接發(fā)送給新生節(jié)點(diǎn)，公式(2)的計(jì)算工作全部由新生節(jié)點(diǎn)完成。在圖 1(

20、a)中顯示了一個(gè)星型修復(fù)實(shí)例中的數(shù)據(jù)傳輸情130況。其中，節(jié)點(diǎn) n1、n2、n3 和 n4 為提供者節(jié)點(diǎn)，節(jié)點(diǎn) n6 為新生節(jié)點(diǎn)。從圖 1(a)可以看出，這種方法中所有編碼塊的傳輸距離都很長(zhǎng)，給鏈路 s2-s1-s3-n6 造成了很大壓力，而在數(shù)據(jù)中心中如 s2-s1 和 s1-s3 這樣的高層鏈路往往已經(jīng)是整個(gè)網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)钠款i。此外，這種方法也在節(jié)點(diǎn) n6 處形成了嚴(yán)重的網(wǎng)絡(luò)堵塞，嚴(yán)重降低了修復(fù)速度。s1s1s2s3s2s3n1n2n3n4n5n6n1n2n3n4n5n6(a) 星型修復(fù)時(shí)的數(shù)據(jù)流(b) ntar修復(fù)時(shí)的數(shù)據(jù)流135140145150圖 1 星型修復(fù)與基于網(wǎng)絡(luò)拓?fù)涞臉?shù)型修

21、復(fù)的數(shù)據(jù)流fig.1 data streams of star-structured reconstruction and ntar實(shí)際上，沒(méi)有必要將 c1 ,c2 ,l,cr 全部直接發(fā)送給新生節(jié)點(diǎn)，再由新生節(jié)點(diǎn)來(lái)完成所有的計(jì)算。根據(jù)有限域上運(yùn)算的交換律和結(jié)合律，可以利用分層匯聚的方式分布式并行化這個(gè)數(shù)據(jù)傳輸和計(jì)算過(guò)程。另外，在大規(guī)模數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)洚?dāng)中，不同節(jié)點(diǎn)之間的距離是不同的，即不同節(jié)點(diǎn)之間的鏈路長(zhǎng)度是不同的。在修復(fù)過(guò)程中，如果能先把相距較近的提供者節(jié)點(diǎn)上的編碼塊組合到一起，然后再發(fā)送到距離更遠(yuǎn)的提供者節(jié)點(diǎn)上與其數(shù)據(jù)進(jìn)行進(jìn)一步的組合，就可以縮短數(shù)據(jù)的傳輸距離，從而降低占用的網(wǎng)絡(luò)資源，

22、并提高修復(fù)速度。圖 1(b)顯示了用 ntar 對(duì)圖 1(a)中實(shí)例進(jìn)行修復(fù)時(shí)的數(shù)據(jù)傳輸情況?？梢钥闯?，ntar 有效縮短了節(jié)點(diǎn) n1 和節(jié)點(diǎn) n2 中編碼塊的傳輸距離，極大地減輕了鏈路 s2-s1-s3-n6 的負(fù)載，并且使節(jié)點(diǎn) n6 需要接收的編碼塊從 4 個(gè)減少到了 2 個(gè)，這有利于提高修復(fù)的速度。另外，在沒(méi)有增加任何交換機(jī)負(fù)載的情況下，極大地減輕了交換機(jī) s1 的負(fù)載。3.1 ntar基于網(wǎng)絡(luò)拓?fù)涞募m刪碼樹(shù)型修復(fù)方法 ntar 的具體修復(fù)過(guò)程可以分為兩大步。第一步，構(gòu)建修復(fù)樹(shù)。具體步驟如下。1)根據(jù)所采用的糾刪碼確定可用來(lái)修復(fù)失效塊 c0 的編碼塊 c1 ,c2 ,l,cr 并計(jì)算出相

23、應(yīng)的修復(fù)系數(shù)向量 (b1 b2 l b r ) ；2)從系統(tǒng)中獲得用以修復(fù)的編碼塊 c1 ,c2 ,l,cr 分別所在節(jié)點(diǎn)，記為v1,v2 ,l,vr ，并根據(jù)系統(tǒng)的數(shù)據(jù)放置策略確-4-c0 = bici 定出新生節(jié)點(diǎn)，記為v0 ；3)根據(jù)系統(tǒng)網(wǎng)絡(luò)拓?fù)湫畔⒊跏蓟硎竟?jié)點(diǎn)v0,v1,l,vr 相互之間網(wǎng)絡(luò)距離的矩陣 adjmatrix。其中，adjmatrixij表示節(jié)點(diǎn) vi 和節(jié)點(diǎn) vj 之間的網(wǎng)絡(luò)距離，0 i, j r ；4)根據(jù)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離矩陣 adjmatrix構(gòu)建出以新生節(jié)點(diǎn)v0 為根的總網(wǎng)絡(luò)155160距離最小的修復(fù)樹(shù)，樹(shù)中節(jié)點(diǎn)為v0,v1,l,vr ；5)將節(jié)點(diǎn) vi 在修

24、復(fù)樹(shù)中的父節(jié)點(diǎn)、子節(jié)點(diǎn)、所存儲(chǔ)的編碼塊 ci 及其對(duì)應(yīng)的系數(shù) b i 等信息發(fā)送給節(jié)點(diǎn) vi， 0 i r 。第二步，數(shù)據(jù)修復(fù)。節(jié)點(diǎn) vi 根據(jù)其在修復(fù)樹(shù)中位置的不同，工作也不同，具體如下。1)vi 如果是葉節(jié)點(diǎn)，則負(fù)責(zé)從本地存儲(chǔ)系統(tǒng)中讀取編碼塊 ci ，計(jì)算出 bici 并將其發(fā)送給自己 的 父 節(jié) 點(diǎn) ； 2)vi 如 果 是 內(nèi) 部 節(jié) 點(diǎn) ， 則 負(fù) 責(zé) 接 收 其 子 節(jié) 點(diǎn) 發(fā) 送 來(lái) 的 數(shù) 據(jù) ， 記 為c1 ,c2 l cn (v ) ，其中 in(v ) 為 vi 的在修復(fù)樹(shù)中的子節(jié)點(diǎn)數(shù)，并從本地存儲(chǔ)系統(tǒng)中讀取編碼塊 ci ，然后計(jì)算出in (vi )j =1j + bic

25、i 并將結(jié)果發(fā)送給自己的父節(jié)點(diǎn)；3)vi 如果是根節(jié)點(diǎn)，則負(fù)責(zé)接收其子節(jié)點(diǎn)發(fā)送來(lái)的數(shù)據(jù)，記為 c1 ,c2 ,l,cin (v j ) ，計(jì)算出in (vi )j =1j ，即 c0 ，然后將結(jié)果寫(xiě)入本地存儲(chǔ)系統(tǒng)。這樣就成功地修復(fù)了失效塊 c0 。圖 2 顯示了用 ntar 修復(fù)圖 1 中實(shí)例時(shí)第二步各節(jié)點(diǎn)計(jì)算的數(shù)據(jù)和節(jié)點(diǎn)之間傳輸?shù)臄?shù)據(jù)。n6c02=c01+c03+2c2c0=c02+c04c04=4c4n2c01=1c1c2c03=3c3c4n4165n1c1c3n3圖 2 糾刪碼的樹(shù)型修復(fù)過(guò)程實(shí)例fig.2 an example of erasure codes tree-structur

26、ed reconstruction3.2 最優(yōu)修復(fù)樹(shù)的構(gòu)建3.2.1網(wǎng)絡(luò)資源度量指標(biāo):網(wǎng)絡(luò)代價(jià)170175180糾刪碼修復(fù)所占用網(wǎng)絡(luò)資源的傳統(tǒng)度量指標(biāo)是修復(fù)時(shí)所需下載的總數(shù)據(jù)量。這一指標(biāo)可以較好地評(píng)價(jià)一種編碼在修復(fù)方面的優(yōu)劣，也在一定程度上反映了修復(fù)過(guò)程所帶來(lái)的網(wǎng)絡(luò)資源開(kāi)銷(xiāo)。然而，它是一個(gè)比較籠統(tǒng)的量，并不能精確反映修復(fù)過(guò)程真正占用網(wǎng)絡(luò)資源的多少。這是因?yàn)樗豢紤]了修復(fù)所需下載的數(shù)據(jù)量，并沒(méi)有考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)數(shù)據(jù)傳輸?shù)挠绊?。顯然，在由一個(gè)交換設(shè)備相連的兩個(gè)節(jié)點(diǎn)之間和在由三個(gè)交換設(shè)備相連的兩個(gè)節(jié)點(diǎn)之間分別傳輸?shù)攘康臄?shù)據(jù)所占用的網(wǎng)絡(luò)資源量是完全不相等的。因此，為了更加精確地描述修復(fù)所占用的網(wǎng)絡(luò)資

27、源，本文用傳輸?shù)臄?shù)據(jù)量和傳輸?shù)木嚯x的乘積，稱(chēng)之為數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)代價(jià)。定義 1.節(jié)點(diǎn) u 和節(jié)點(diǎn) v 之間的網(wǎng)絡(luò)距離 d(u，v)等于它們之間的物理鏈路數(shù)目，其單位為跳(hop)。如果節(jié)點(diǎn) u 和節(jié)點(diǎn) v 之間傳輸數(shù)據(jù)時(shí)經(jīng)過(guò)的交換設(shè)備數(shù)目為 h(u，v)，則 d(u，v) = h(u，v)+1。這里的交換設(shè)備指網(wǎng)絡(luò)中任何具有數(shù)據(jù)轉(zhuǎn)發(fā)功能的設(shè)備，包括集線器、交換機(jī)、路由器以及具有轉(zhuǎn)發(fā)功能的服務(wù)器等。定義 2. 節(jié)點(diǎn) u 和節(jié) v 之間傳輸數(shù)據(jù)量為 a (u,v )時(shí)的網(wǎng)絡(luò)代價(jià)為公式(3)，其單位為bytehop，以 表示。c(u, v) = a(u, v) d (u, v)-5-(3) , i,

28、j i c c185網(wǎng)絡(luò)代價(jià)既包含了傳輸?shù)臄?shù)據(jù)量，也包含了數(shù)據(jù)傳輸?shù)木嚯x。數(shù)據(jù)經(jīng)過(guò)的鏈路數(shù)越多，它占用的網(wǎng)絡(luò)資源，如網(wǎng)絡(luò)端口和鏈路等也就越多。網(wǎng)絡(luò)鏈路和端口負(fù)載的輕重直接影響著網(wǎng)絡(luò)的數(shù)據(jù)傳輸性能，對(duì)上層應(yīng)用性能具有重要影響。因此，網(wǎng)絡(luò)代價(jià)能更精確地反映數(shù)據(jù)傳輸對(duì)網(wǎng)絡(luò)造成的影響。3.2.2問(wèn)題建模190195200不失一般性，以v = v0 ,v1,l,vr表示所有參與修復(fù)失效塊 c0 的節(jié)點(diǎn)組成的集合。其中，v0 為新生節(jié)點(diǎn)，v1,v2 ,l,vr 為提供者節(jié)點(diǎn)。不妨假設(shè)存儲(chǔ)編碼塊 ci 的節(jié)點(diǎn)為 vi，1 i r ，每個(gè)編碼塊的大小為 s 字節(jié)。邊集 e = (vi ,v j ) | i,

29、j = 0,1,l, r,i j表示各個(gè)節(jié)點(diǎn)之間的路徑，函數(shù) w(vi ,v j ) 表示節(jié)點(diǎn)vi 和v j 之間的網(wǎng)絡(luò)距離，即 w(vi ,v j ) = d (vi ,v j ) 。這樣，可以用有權(quán)完全圖 gr = (v , e, w) 來(lái)表示用編碼塊 c1 ,c2 ,l,cr 來(lái)修復(fù)失效塊 c0 時(shí)的網(wǎng)絡(luò)。li jun 等人已經(jīng)證明 gr 的生成樹(shù)可以用來(lái)修復(fù)失效數(shù)據(jù)塊5。定義 3. 糾刪碼的修復(fù)樹(shù)是 gr 的生成樹(shù)。記修復(fù)樹(shù)為 tr = v , e ，gr 中的邊 (vi ,v j ) e 當(dāng)且僅當(dāng)在修復(fù)時(shí)節(jié)點(diǎn) vi 向節(jié)點(diǎn) vj 發(fā)送數(shù)據(jù)，其中 0 i, j r ，且 i j 。根據(jù)

30、節(jié)點(diǎn)間傳輸數(shù)據(jù)的網(wǎng)絡(luò)代價(jià)定義可得樹(shù)型修復(fù)的網(wǎng)絡(luò)代價(jià)。定義 4. 在 gr 使用修復(fù)樹(shù) tr = v , e 進(jìn)行數(shù)據(jù)修復(fù)的網(wǎng)絡(luò)代價(jià) c(tr)為公式(4)。c(tr ) =本文的目標(biāo)是使 c(tr)最小。問(wèn)題求解3.2.3 ( w(u, v) a (u, v)( u ,v )e (4)引理 15. 修復(fù)樹(shù) tr 中各邊在修復(fù)過(guò)程中傳輸?shù)臄?shù)據(jù)量都相等且為 s 字節(jié)，即 a(u, v) = s205字節(jié)，其中 (u, v) e 。定理 1. gr 的最小生成樹(shù)是具有最低網(wǎng)絡(luò)代價(jià)的修復(fù)樹(shù)。證明. 根據(jù)引理 1，可以將公式(4)化為 c(tr ) = s( u ,v )e w(u, v) 。因?yàn)樵谛迯?fù)

31、時(shí) s 是常量，所以 c(tr ) 最小當(dāng)且僅當(dāng)( u ,v )e w(u, v) 最小。顯然，其表示的是修復(fù)樹(shù) tr 各邊權(quán)重之和，而修復(fù)樹(shù) tr 是 gr 的生成樹(shù)，又權(quán)重之和最小的生成樹(shù)是最小生成樹(shù)。所以，gr 的最小生成樹(shù)是210215具有最低網(wǎng)絡(luò)代價(jià)的修復(fù)樹(shù)。證畢。定理 1 同時(shí)也說(shuō)明，使用現(xiàn)有的最小生成樹(shù)構(gòu)建算法，如 prime 算法，即可從 gr 構(gòu)建出最優(yōu)的修復(fù)樹(shù)。星型修復(fù)方法和 ntar 的修復(fù)結(jié)構(gòu)分別如圖 3(a)和圖 3(b)所示。由于所有節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)量都為 m 字節(jié)，根據(jù)節(jié)點(diǎn)間網(wǎng)絡(luò)距離，易得星型修復(fù)和 ntar 的網(wǎng)絡(luò)代價(jià)分別為 14s和 10s。可見(jiàn)，ntar 比

32、星型修復(fù)方法占用的網(wǎng)絡(luò)資源減少了約 28.6%。-6-v1v2v04242v0v1v2v344v4v322v4(a)傳統(tǒng)星型修復(fù)結(jié)構(gòu)(b)基于網(wǎng)絡(luò)拓?fù)涞臉?shù)型修復(fù)結(jié)構(gòu)圖 3 星型修復(fù)與 ntar 的修復(fù)結(jié)構(gòu)fig.3 reconstruction structure of star-structured reconstruction and ntar3.3 最優(yōu)提供者節(jié)點(diǎn)組合的選擇算法 optree220225230實(shí)際中，修復(fù)時(shí)可用來(lái)修復(fù)失效塊的存活數(shù)據(jù)塊數(shù)一般都多于 r，假設(shè)其為 a (a r) 。這時(shí)就會(huì)有 car 種提供者節(jié)點(diǎn)組合可供選擇，選用不同的提供者節(jié)點(diǎn)組合會(huì)有不同的最優(yōu)網(wǎng)絡(luò)代價(jià)。

33、如果能夠從中選取最優(yōu)網(wǎng)絡(luò)代價(jià)最小的組合，將進(jìn)一步降低修復(fù)占用的網(wǎng)絡(luò)資源。但是如果窮舉所有選擇，分別計(jì)算它們的最優(yōu)網(wǎng)絡(luò)代價(jià)，再?gòu)闹羞x出最優(yōu)的組合將會(huì)花費(fèi)很長(zhǎng)時(shí)間。為了盡快找到最優(yōu)的提供者節(jié)點(diǎn)組合，本文提出了一種基于 prime 最小生成樹(shù)算法的節(jié)點(diǎn)選擇算法 optree。optree 能快速選出最優(yōu)的提供者節(jié)點(diǎn)組合，并同時(shí)生成修復(fù)時(shí)所需的最優(yōu)修復(fù)樹(shù)。optree 的基本思想和過(guò)程與 prime 算法相同，只是讓新生節(jié)點(diǎn)和所有 a 個(gè)可用節(jié)點(diǎn)都參加生成樹(shù)的構(gòu)建，并且在選取了 r 條邊后就終止算法，而不是像 prime 算法那樣選取 a 條邊后才終止。由于 prime 算法的每一步都是最優(yōu)的，所以

34、optree 能產(chǎn)生最優(yōu)的結(jié)果。optree的具體過(guò)程如算法 1。算法 1. 最優(yōu)提供者節(jié)點(diǎn)組合的選擇算法 optree輸入:root:新生節(jié)點(diǎn);candidateproviders:可選提供者節(jié)點(diǎn)集合;r:需要選擇的提供者節(jié)點(diǎn)個(gè)數(shù);adjmatrix:節(jié)點(diǎn)間網(wǎng)絡(luò)距離矩陣;輸出:reconstructiontree:修復(fù)樹(shù);chosenproviders:最優(yōu)的提供者節(jié)點(diǎn)集合;過(guò)程:1:reconstructiontree:= ;2:chosenproviders:= ;3:chosennumber:=0;4:candidateedges:= ;5:for each provider in c

35、andidateproviders do6:7:linklengthprovider,root: = adjmatrix root, provider ;將 edgeroot,provider 加到 candidateedges 中;8:end for9:while chosennumber r do10:11:12:從 candidateedges 中選出最短的邊 edgefrom,to;將 edgefrom,to 加到 reconstructiontree 中;從 candidateedges 中刪除 edgefrom,to;-7-13:14:15:16:17:18:19:20:21:將

36、from 加入到 chosenproviders 中;chosennumber: = chosennumber+1;for each edgeu,v in candidateedges dolinklengthu,to: =adjmatrix u, to;if linklengthu,to = linklengthu,v then從 candidateedges 中刪除 edgeu,v;將 edgeu,to 加入到 candidateedges 中;end ifend for22:end while23:return reconstructiontree 和 chosenproviders;3

37、.4 修復(fù)時(shí)間分析假設(shè)每個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬都為 b 字節(jié)/秒，網(wǎng)絡(luò)中交換設(shè)備各端口的帶寬都大于 b 字節(jié)/秒。這些在現(xiàn)有數(shù)據(jù)中心中都是比較常見(jiàn)的情況。另外，如果一個(gè)節(jié)點(diǎn)接收了整個(gè)編碼塊后才進(jìn)行合并或?qū)⑵浒l(fā)送給自己的父節(jié)點(diǎn)會(huì)嚴(yán)重地浪費(fèi)時(shí)間，實(shí)現(xiàn)修復(fù)過(guò)程最優(yōu)的方式應(yīng)該是235240245250255流水線。一個(gè)節(jié)點(diǎn)一旦從其各個(gè)子節(jié)點(diǎn)都收到了一個(gè)數(shù)據(jù)包后就立刻開(kāi)始將它們合并，在合并數(shù)據(jù)的同時(shí)繼續(xù)從其各子節(jié)點(diǎn)接收數(shù)據(jù)并將合并好的數(shù)據(jù)包發(fā)送給自己父節(jié)點(diǎn)。顯然，在這種情況下修復(fù)時(shí)間受限于需要接收最多編碼塊的節(jié)點(diǎn)。若以 y(tr ) 表示修復(fù)樹(shù) tr 所有節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)，則可得其最短修復(fù)時(shí)間 t(tr)為

38、y(tr ) s(5)b其中t (tr ) 是從修復(fù)開(kāi)始到新生節(jié)點(diǎn)從其各子節(jié)點(diǎn)都收到第一個(gè)數(shù)據(jù)包的時(shí)間。一般情況下，編碼塊的大小都在幾十 mb 甚至幾百 mb，遠(yuǎn)遠(yuǎn)大于一個(gè)數(shù)據(jù)包的大小(幾 kb)。因此，t (tr )可以忽略不計(jì)。根據(jù)公式(5)可得圖 3 中星型修復(fù)和 ntar 的最短修復(fù)時(shí)間分別為 4s b 秒和 2s b 秒?？梢?jiàn)，ntar 將修復(fù)時(shí)間縮短了 50%。4 實(shí)驗(yàn)結(jié)果與分析雖然已有一些關(guān)于樹(shù)型修復(fù)的研究，但大都是基于理論分析和模擬實(shí)驗(yàn)的研究方法。本文基于 hdfs-raid 實(shí)現(xiàn)了對(duì) rs 碼14的 ntar(稱(chēng)之為 hdfs-ntar)，其核心機(jī)制可以不加修改地用于其它的線

39、性糾刪碼。在一個(gè)真實(shí)的集群上，對(duì) ntar 修復(fù)樹(shù)的構(gòu)建時(shí)間、網(wǎng)絡(luò)代價(jià)以及修復(fù)時(shí)間等方面進(jìn)行了測(cè)試，并且與傳統(tǒng)的星型修復(fù)方法做了對(duì)比。星型修復(fù)在有多于r 個(gè)節(jié)點(diǎn)可以作為提供者節(jié)點(diǎn)時(shí)，不同的組合也具有不同的網(wǎng)絡(luò)代價(jià)。為了公平，星型修復(fù)時(shí)也選擇了網(wǎng)絡(luò)代價(jià)最小的節(jié)點(diǎn)組合，不妨稱(chēng)之為基于網(wǎng)絡(luò)拓?fù)涞男切托迯?fù) (networktopology based star-structured reconstruction，ntsr)。對(duì)于每一個(gè)測(cè)試，固定每個(gè)條帶產(chǎn)生的校驗(yàn)塊數(shù)目為 4，條帶長(zhǎng)度分別取 4、6、8、10、12 各做一組實(shí)驗(yàn)，以考察條帶長(zhǎng)度對(duì)測(cè)試結(jié)果的影響。ntar 采用的最優(yōu)提供者節(jié)點(diǎn)組合選擇算法

40、和最優(yōu)修復(fù)樹(shù)構(gòu)建算法為 optree。ntsr 的最優(yōu)提供者節(jié)點(diǎn)組合選擇方法是取與新生節(jié)點(diǎn)網(wǎng)絡(luò)距離最小的前 r 個(gè)可用節(jié)點(diǎn)。hdfs 文件塊大小取 64mb。4.1 實(shí)驗(yàn)環(huán)境實(shí)驗(yàn)使用的 hdfs-ntar 集群由 19 個(gè)節(jié)點(diǎn)組成，包含一個(gè) namenode 節(jié)點(diǎn)和 18 個(gè)datanode 節(jié)點(diǎn)。所有 datanode 平均連接在三個(gè)交換機(jī)上。連接在同一交換機(jī)上的節(jié)點(diǎn)之間-8-+t (tr )t(tr ) =260265的網(wǎng)絡(luò)距離為 2，連接于不同交換機(jī)的節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離為 4。hdfs-ntar 集群中所有節(jié)點(diǎn)均為配置相同的寶德服務(wù)器，各配有 4 顆 intel xeon e-2640處

41、理器，64gb 內(nèi)存，1tb 硬盤(pán)和千兆網(wǎng)卡。集群中所有交換機(jī)均具有 48 個(gè) 10/100/1000mbps自適應(yīng)端口。4.2 修復(fù)樹(shù)的構(gòu)建時(shí)間和修復(fù)的網(wǎng)絡(luò)代價(jià)測(cè)試時(shí)，先向 hdfs-ntar 中寫(xiě)入 180 個(gè)大小均為 1gb 的文件，當(dāng)編碼完成后，關(guān)閉其中一個(gè) datanode，分別統(tǒng)計(jì)采用 ntar 和 ntsr 修復(fù)所有失效塊時(shí)獲得節(jié)點(diǎn)間網(wǎng)絡(luò)距離和構(gòu)建各自的修復(fù)結(jié)構(gòu)所花費(fèi)的總時(shí)間和網(wǎng)絡(luò)代價(jià)，然后計(jì)算出平均的構(gòu)建時(shí)間和網(wǎng)絡(luò)代價(jià)。實(shí)驗(yàn)結(jié)果分別如圖 4(a)和圖 4(b)所示。0.10.080.06ntarntsr25002000ntarntsr15000.0410000.024 6 8

42、10 12條帶長(zhǎng)度(塊)(a) 修復(fù)結(jié)構(gòu)的平均建立時(shí)間46 8 10條帶長(zhǎng)度(塊)(b) 平均網(wǎng)絡(luò)代價(jià)12270275280圖 4 ntar 和 ntsr 修復(fù)結(jié)構(gòu)的平均建立時(shí)間和網(wǎng)絡(luò)代價(jià)fig.4 averaged building time and network cost of ntar and ntsr從圖 4(a)可以看出，ntar 和 ntsr 修復(fù)結(jié)構(gòu)的建立時(shí)間都隨著條帶長(zhǎng)度的增大而延長(zhǎng)，且 ntar 修復(fù)樹(shù)的建立時(shí)間比 ntsr 稍長(zhǎng)。然而，即使當(dāng)條帶長(zhǎng)度為 12 時(shí)，建立一個(gè)修復(fù)樹(shù)所需時(shí)間也只有 0.1 毫秒左右。這說(shuō)明，ntar 選擇最優(yōu)提供者節(jié)點(diǎn)組合并建立最優(yōu)修復(fù)樹(shù)的時(shí)間

43、開(kāi)銷(xiāo)非常小，相對(duì)于修復(fù)一個(gè)失效塊所需的時(shí)間，這完全可以忽略不計(jì)。從圖 4(b)可以看出，相比于 ntsr，ntar 將修復(fù)的網(wǎng)絡(luò)代價(jià)減少了 30%-45%，并且 ntar的網(wǎng)絡(luò)代價(jià)隨著條帶長(zhǎng)度的增大而增長(zhǎng)的速度明顯慢于 ntsr。這是因?yàn)殡S著條帶長(zhǎng)度的增大，會(huì)有更多的編碼塊在修復(fù)時(shí)可以就近組合，ntar 相比于 ntsr 產(chǎn)生的網(wǎng)絡(luò)代價(jià)也就更少。這表明，ntar 有效減少網(wǎng)絡(luò)資源占用。4.3 修復(fù)時(shí)間測(cè)試時(shí)，向 hdfs-ntar 中寫(xiě)入了 180 個(gè)大小恰為一個(gè)條帶的文件，當(dāng)編碼完成后關(guān)閉一個(gè) datanode 節(jié)點(diǎn)，然后分別用串行和并行的方法進(jìn)行修復(fù)，并計(jì)算出單塊的平均修復(fù)時(shí)間，結(jié)果分別如

44、圖 5(a)和圖 5(b)所示。并行修復(fù)時(shí)的并行度為 18。2.564ntarntsr21.5ntarntsr120.546 8 10條帶長(zhǎng)度(塊)1246 8 10條帶長(zhǎng)度(塊)12(a)串行修復(fù)(b)并行修復(fù)285圖 5 ntar 和 ntsr 的串行與并行修復(fù)時(shí)間fig.5 averaged sequential and parallel reconstruction time of ntar and ntsr從圖 5(a)可以看出，ntar 的平均串行修復(fù)時(shí)間比 ntsr 縮短了 60%-85%，并且 ntar的平均修復(fù)時(shí)間不隨條帶長(zhǎng)度的增大而變化，而 ntsr 的平均修復(fù)時(shí)間則隨條帶

45、長(zhǎng)度的增大線性增加。這是因?yàn)?，在?shù)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，ntar 產(chǎn)生的最低網(wǎng)絡(luò)代價(jià)修復(fù)樹(shù)中節(jié)點(diǎn)的-9-建立時(shí)間(ms）平均網(wǎng)絡(luò)代價(jià)(ms)修復(fù)時(shí)間(s)修復(fù)時(shí)間(s)290295300305310315320325330335最大孩子數(shù)是固定的?？梢?jiàn)，ntar 分布式并行化的特點(diǎn)明顯提高了修復(fù)速度。從圖 5(b)可以看出，ntar 比 ntsr 并行修復(fù)的時(shí)間短 40%-70%，且前者隨條帶長(zhǎng)度增大而增加的速度遠(yuǎn)慢于 ntsr。這一方面是因?yàn)?ntar 占用的網(wǎng)絡(luò)資源更少，尤其是有效減輕了網(wǎng)絡(luò)中高層鏈路的負(fù)載，從而提高了整個(gè)網(wǎng)絡(luò)的傳輸性能;另一方面是因?yàn)?ntar 將數(shù)據(jù)的發(fā)送和傳輸任務(wù)均勻地分

46、布在了所有參與修復(fù)的節(jié)點(diǎn)上，避免了 ntsr 中的網(wǎng)絡(luò)瓶頸。5 總結(jié)采用糾刪碼作為大規(guī)模分布式容錯(cuò)存儲(chǔ)系統(tǒng)的數(shù)據(jù)冗余技術(shù)，能夠比多副本在相同可靠性的情況下節(jié)省大量的存儲(chǔ)空間。然而，糾刪碼高昂的修復(fù)成本，嚴(yán)重阻礙了其在實(shí)際存儲(chǔ)系統(tǒng)中的廣泛應(yīng)用。本文首先針對(duì)現(xiàn)有糾刪碼修復(fù)方法沒(méi)有考慮網(wǎng)絡(luò)拓?fù)溆绊懙牟蛔悖岢隽嘶诰W(wǎng)絡(luò)拓?fù)涞臉?shù)型修復(fù)方法 ntar。其次，提出了從所有可用節(jié)點(diǎn)中選取最優(yōu)提供者節(jié)點(diǎn)組合的算法optree。它能夠在快速選出最優(yōu)提供者節(jié)點(diǎn)組合的同時(shí)構(gòu)建出最優(yōu)的修復(fù)樹(shù)。最后，基于hdfs-raid 實(shí)現(xiàn)了 ntar 和 optree，并通過(guò)大量實(shí)際實(shí)驗(yàn)驗(yàn)證了 ntar 和 optree 的有效

47、性。實(shí)驗(yàn)結(jié)果表明，ntar 相比于傳統(tǒng)的星型修復(fù)方法，有效地減少了糾刪碼修復(fù)時(shí)占用的網(wǎng)絡(luò)資源，并極大地提高了串行和并行修復(fù)速度。參考文獻(xiàn) (references)1 ghemawat s, gobioff h, leugn s t. the google file systemc. proceedings of the 9th acm symposium onoperating systems principles. new york: acm, 20032 wang yijie, li sijun. research and performance evaluation of data re

48、plication technology in distributedstorage systemsj. international journal of computers and mathematics with applications, 2006,51(11):1625-16323 羅象宏, 舒繼武. 存儲(chǔ)系統(tǒng)中的糾刪碼研究綜述. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(1):1-114 lin w k, chiu d m, lee y b. erasure code replication revisitedc. proceedings of the 4th international

49、conference on peer-to-peer computing. washington, dc: ieee computer society, 20045 li jun, yang shuang, wang xin, et al. tree-structured data regeneration with network coding in distributedstorage systemsc. proceedings of the 17th international workshop on quality of service. 2009:1-96 sathiamoorthy m