包 涵 王意潔 許方亮

1(并行與分布處理國家重點(diǎn)實(shí)驗(yàn)室(國防科技大學(xué)) 長沙 410073)2(國防科技大學(xué)計(jì)算機(jī)學(xué)院 長沙 410073)

近年來，數(shù)據(jù)中心(datacenter, DC)故障屢見不鮮[1-8].因此，存放在單數(shù)據(jù)中心存儲(chǔ)系統(tǒng)里的數(shù)據(jù)面臨著永久丟失的風(fēng)險(xiǎn).為了確保在數(shù)據(jù)中心故障時(shí)仍能恢復(fù)其中的數(shù)據(jù)，各大機(jī)構(gòu)通常選擇采用容錯(cuò)技術(shù)(糾刪碼和多副本)將數(shù)據(jù)存儲(chǔ)在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中.

在單數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中，糾刪碼因其高容錯(cuò)性和低冗余度而得到了廣泛應(yīng)用[9-12].然而，在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中，由于下列原因，糾刪碼的寫入速度較低以至于難以適應(yīng)于大數(shù)據(jù)時(shí)代日益增長的數(shù)據(jù)產(chǎn)生速度[13-14]：

1) 糾刪碼寫入數(shù)據(jù)時(shí)，源節(jié)點(diǎn)需要向若干節(jié)點(diǎn)傳輸大量的數(shù)據(jù)塊或編碼塊，因此數(shù)據(jù)傳輸量較大.此外，在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中，糾刪碼寫入數(shù)據(jù)時(shí)需要頻繁地在數(shù)據(jù)中心間進(jìn)行數(shù)據(jù)傳輸，因而數(shù)據(jù)的平均傳輸距離(跳數(shù))較長[15-16].因此，跨數(shù)據(jù)中心糾刪碼寫入數(shù)據(jù)時(shí)的網(wǎng)絡(luò)資源消耗量(數(shù)據(jù)傳輸量與平均傳輸距離之積)較大.當(dāng)網(wǎng)絡(luò)資源消耗量較大時(shí)，有較大概率需要在低帶寬的物理鏈路上傳輸較多的數(shù)據(jù)，這將形成傳輸瓶頸，導(dǎo)致寫入速度低的問題[17].

2) 糾刪碼寫入數(shù)據(jù)的過程中涉及較多的編碼操作，并需要在位于多個(gè)數(shù)據(jù)中心的多個(gè)節(jié)點(diǎn)間進(jìn)行頻繁的數(shù)據(jù)傳輸操作，若無法有效保證編碼效率和傳輸效率，極易造成編碼計(jì)算瓶頸或傳輸瓶頸，進(jìn)而導(dǎo)致寫入速度低的問題.

由于跨數(shù)據(jù)中心糾刪碼較低的寫入速度大大限制了其可用性，本文聚焦于提高跨數(shù)據(jù)中心糾刪碼的寫入速度.

現(xiàn)有的糾刪碼寫入方法分為集中式寫入方法[18-19]和分布式寫入方法[20-22]2類：

已有的集中式寫入方法主要是面向單數(shù)據(jù)中心糾刪碼的.在這類寫入方法中，中心編碼節(jié)點(diǎn)將單獨(dú)負(fù)責(zé)完成一個(gè)條帶中所有編碼塊的編碼生成任務(wù)，這將形成嚴(yán)重的編碼瓶頸.如圖1(a)所示，在我們的實(shí)際測試中，集中式寫入方法Trad[19]的單個(gè)節(jié)點(diǎn)最大計(jì)算復(fù)雜度是2種分布式寫入方法D2CP[22]和IncEncoding[23]的4.3～8.8倍.因此，集中式寫入方法的整體編碼效率較低，這會(huì)對寫入速度產(chǎn)生不利影響.

為了提高糾刪碼寫入數(shù)據(jù)時(shí)的編碼效率，研究者們提出了分布式寫入方法(包括面向單數(shù)據(jù)中心糾刪碼的分布式寫入方法[20-22]的和面向跨數(shù)據(jù)中心糾刪碼的分布式寫入方法[23]).通過將編碼操作分散到多個(gè)編碼節(jié)點(diǎn)上并行執(zhí)行，分布式寫入方法能夠提高編碼效率.然而，這類方法通常會(huì)引入較大的網(wǎng)絡(luò)資源消耗量，從而對寫入速度產(chǎn)生不利影響.尤其是在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中，這一問題更加突出.如圖1(b)所示，2種分布式寫入方法D2CP和IncEncoding的網(wǎng)絡(luò)資源消耗量是集中式寫入方法Trad的2.1～2.5倍.此外，在涉及節(jié)點(diǎn)較多時(shí)，分布式寫入方法需要在多個(gè)節(jié)點(diǎn)間多次轉(zhuǎn)發(fā)同一數(shù)據(jù)塊.如圖1(c)所示，2種分布式寫入方法D2CP和IncEncoding的單個(gè)數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)為集中式寫入方法Trad的6～11倍.由于數(shù)據(jù)塊在節(jié)點(diǎn)間進(jìn)行轉(zhuǎn)發(fā)時(shí)需要進(jìn)行額外的磁盤讀寫操作和排隊(duì)等待操作[23]，因而數(shù)據(jù)塊的轉(zhuǎn)發(fā)次數(shù)越多，傳輸效率越低，這將對寫入速度產(chǎn)生不利影響.

Fig. 1 Comparison between the centralized writing method of erasure code and the distributed writing method of erasure code圖1 分布式糾刪碼寫入方法和集中式糾刪碼寫入方法的對比

總而言之，在跨數(shù)據(jù)中心存儲(chǔ)中，現(xiàn)有糾刪碼寫入方法由于無法兼顧網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率，使得它們難以達(dá)到較高的寫入速度.為此，本文提出了一種基于生成矩陣變換的跨數(shù)據(jù)中心糾刪碼寫入方法(cross-datacenter erasure code writing method based on generator matrix trans-formation, CREW).具體而言，CREW包含以下3個(gè)算法:

1) 一種基于貪心策略的傳輸拓?fù)錁?gòu)造算法(greedy strategy-based transmission topology con-struction algorithm, GBTC).可構(gòu)造一種自頂向下邊權(quán)(網(wǎng)絡(luò)距離)遞增的數(shù)據(jù)中心級傳輸樹來組織數(shù)據(jù)中心間的數(shù)據(jù)傳輸.同時(shí)，GBTC還將構(gòu)造一種星型拓?fù)鋪斫M織各數(shù)據(jù)中心內(nèi)部的數(shù)據(jù)傳輸.

2) 一種生成矩陣變形算法(generator matrix transformation algorithm, GMT).可在不改變各編碼塊間的線性關(guān)系的前提下對編碼塊生成矩陣進(jìn)行變形，使得需要存儲(chǔ)在位于GBTC構(gòu)造的傳輸樹下端的數(shù)據(jù)中心里的編碼塊的生成過程依賴于盡可能少的數(shù)據(jù)塊.因?yàn)镚BTC構(gòu)造的傳輸樹自頂向下邊權(quán)遞增，所以使用GMT對生成矩陣進(jìn)行變形可使寫入過程中需要長距離傳輸?shù)臄?shù)據(jù)塊盡可能地少，進(jìn)而可以降低網(wǎng)絡(luò)資源消耗量.

3) 一種分布式流水線寫入算法(distributed pipelined writing algorithm, DPW).可協(xié)調(diào)各節(jié)點(diǎn)間的數(shù)據(jù)傳輸操作和編碼操作.為了避免節(jié)點(diǎn)的計(jì)算能力成為編碼瓶頸， DPW在數(shù)據(jù)中心間進(jìn)行分布式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸.為了避免因數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)過多造成傳輸瓶頸，DPW在數(shù)據(jù)中心內(nèi)部進(jìn)行集中式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸.

1 相關(guān)工作

在采用編碼參數(shù)為(n,k,d)的糾刪碼的存儲(chǔ)系統(tǒng)中寫入數(shù)據(jù)時(shí)，原始數(shù)據(jù)首先將被源節(jié)點(diǎn)Src拆分為多個(gè)數(shù)據(jù)塊，每k個(gè)數(shù)據(jù)塊組成一個(gè)條帶.接著每個(gè)條帶的k個(gè)數(shù)據(jù)塊X=(x1,x2,…,xk)將被編碼節(jié)點(diǎn)編碼為n個(gè)編碼塊Y=(y1,y2,…,yn)，編碼過程如式(1)所示：

Y=XG,

(1)

其中滿秩矩陣G被稱為糾刪碼的生成矩陣.對應(yīng)于每個(gè)生成矩陣，存在一個(gè)(n-k)×n的滿秩矩陣H，使得GHT=0,H被稱為糾刪碼的校驗(yàn)矩陣[24-26].

當(dāng)編碼節(jié)點(diǎn)完成編碼后，n個(gè)編碼塊將被存儲(chǔ)在n個(gè)不同的存儲(chǔ)節(jié)點(diǎn)中，以確保在一個(gè)條帶中任意d-1個(gè)編碼塊所在的存儲(chǔ)節(jié)點(diǎn)失效時(shí)，系統(tǒng)可以通過其他n-k-d+1個(gè)存儲(chǔ)節(jié)點(diǎn)的編碼塊來恢復(fù)原始數(shù)據(jù).

糾刪碼的寫入模式可以分為2類：先副本后編碼模式和直接編碼模式.與先副本后編碼模式相比，直接編碼模式對系統(tǒng)的計(jì)算資源和存儲(chǔ)資源的消耗更低，但對糾刪碼寫入速度的要求更高.因此，本文主要關(guān)注于如何提高直接寫入模式下的糾刪碼寫入速度.在直接寫入模式下，糾刪碼的寫入方法可分為集中式寫入方法和分布式寫入方法2類.

1.1 集中式寫入方法

已有的集中式寫入方法Trad主要是面向單數(shù)據(jù)中心存儲(chǔ)的.Trad寫入數(shù)據(jù)時(shí)，源節(jié)點(diǎn)首先將所有的數(shù)據(jù)塊傳送給中心編碼節(jié)點(diǎn)，然后由中心編碼節(jié)點(diǎn)將這些數(shù)據(jù)塊編碼為若干編碼塊后分發(fā)到若干個(gè)存儲(chǔ)節(jié)點(diǎn)中.由于集中式寫入方法簡單易實(shí)現(xiàn)且便于維護(hù)，WAS[27]和Atlas[28]等分布式存儲(chǔ)系統(tǒng)均采用集中式寫入方法.但是，由于集中式寫入方法將所有編碼計(jì)算負(fù)載集中在中心編碼節(jié)點(diǎn)上，這種方法的編碼效率較低，極易造成性能瓶頸.

此外，F(xiàn)an等人[19]提出了一種新的集中式數(shù)據(jù)寫入方法Trad-MR.在寫入數(shù)據(jù)時(shí)，Trad-MR首先會(huì)將不同的數(shù)據(jù)對象發(fā)送到不同的MapReduce節(jié)點(diǎn)中，然后由不同的MapReduce節(jié)點(diǎn)來負(fù)責(zé)不同數(shù)據(jù)對象的編碼和分發(fā).這種方法可以在一定程度上緩解糾刪碼寫入數(shù)據(jù)時(shí)的性能瓶頸問題，但隨著寫入數(shù)據(jù)量的不斷增加，MapReduce節(jié)點(diǎn)的計(jì)算能力仍然可能成為寫入過程的瓶頸.

總而言之，集中式寫入方法的優(yōu)點(diǎn)是簡單易實(shí)現(xiàn)，其缺點(diǎn)是編碼效率較低，從而對糾刪碼寫入速度造成不利影響.

1.2 分布式寫入方法

分布式寫入方法在進(jìn)行數(shù)據(jù)寫入時(shí)，會(huì)將數(shù)據(jù)編碼任務(wù)分散到多個(gè)編碼節(jié)點(diǎn)上并行執(zhí)行以提高編碼效率.已有的分布式寫入方法分為面向單數(shù)據(jù)中心糾刪碼的分布式寫入方法和面向跨數(shù)據(jù)中心糾刪碼的分布式寫入方法2類.

1) 面向單數(shù)據(jù)中心糾刪碼的分布式寫入方法

Lluis等人[21]提出一種網(wǎng)內(nèi)分布式寫入方法In-Network.In-Network在寫入數(shù)據(jù)時(shí)首先由源節(jié)點(diǎn)將原始數(shù)據(jù)條帶劃分為k個(gè)數(shù)據(jù)塊.然后，源節(jié)點(diǎn)將劃分好的k個(gè)數(shù)據(jù)塊分發(fā)到k個(gè)存儲(chǔ)節(jié)點(diǎn)中.這些存儲(chǔ)節(jié)點(diǎn)在接收到數(shù)據(jù)塊后將同時(shí)進(jìn)行數(shù)據(jù)塊的存儲(chǔ)操作和轉(zhuǎn)發(fā)操作.接收到這些存儲(chǔ)節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)塊的編碼節(jié)點(diǎn)將使用這些數(shù)據(jù)塊完成編碼塊的編碼生成任務(wù)，同時(shí)將一部分編碼塊(中間編碼塊)發(fā)送到其編碼節(jié)點(diǎn)中參與其他編碼塊的編碼生成過程.最后，所有編碼節(jié)點(diǎn)都將接收到編碼所需的中間編碼塊或數(shù)據(jù)塊.總而言之，In-Network通過將數(shù)據(jù)寫入時(shí)的編碼任務(wù)分散到多個(gè)節(jié)點(diǎn)來提高編碼效率.然而，In-Network僅僅適用于局部性碼并且對編碼參數(shù)具有較為嚴(yán)格的要求.因此，In-Network的通用性較差.

針對In-Network通用性差的問題，我們在文獻(xiàn)[22]中提出了一種通用性更高的分布式寫入方法D2CP，適用于所有的局部性碼.在D2CP中，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后先完成部分的編碼操作，然后將編碼生成的中間編碼塊發(fā)送到相應(yīng)的編碼節(jié)點(diǎn)中，這些編碼節(jié)點(diǎn)在接收到源節(jié)點(diǎn)發(fā)送的中間編碼塊后通過相互協(xié)作的方式完成剩余的編碼操作以得到最終的編碼塊.與In-Network類似，D2CP通過將編碼操作分散到多個(gè)節(jié)點(diǎn)并行執(zhí)行的方式提高了編碼效率，并且具有比In-Network更高的通用性.

2) 面向跨數(shù)據(jù)中心糾刪碼的寫入方法

我們在文獻(xiàn)[23]中提出了一種面向跨數(shù)據(jù)中心糾刪碼的分布式寫入方法IncEncoding.在IncEncoding中，所有存儲(chǔ)節(jié)點(diǎn)都是編碼節(jié)點(diǎn)，源節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)以線性拓?fù)浣M織，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后沿著線性拓?fù)湟粤魉姆绞揭来伟l(fā)送各個(gè)數(shù)據(jù)塊，各個(gè)存儲(chǔ)節(jié)點(diǎn)接收到一個(gè)數(shù)據(jù)塊后就使用其進(jìn)行編碼得到中間編碼塊，同時(shí)將該數(shù)據(jù)塊轉(zhuǎn)發(fā)給下一存儲(chǔ)節(jié)點(diǎn).最終，每個(gè)存儲(chǔ)節(jié)點(diǎn)都將收到自己所需的所有數(shù)據(jù)塊，并編碼生成最終的編碼塊.

以上分布式寫入方法都能夠?qū)⒕幋a操作分散到多個(gè)節(jié)點(diǎn)上并行執(zhí)行，因而能夠有效提高寫入時(shí)的編碼效率.但是，由于通常需要在多個(gè)節(jié)點(diǎn)間傳輸數(shù)據(jù)塊和中間編碼塊，分布式寫入方法也帶來了較大的網(wǎng)絡(luò)資源消耗量.此外，在涉及節(jié)點(diǎn)較多時(shí)，已有的分布式寫入方法中數(shù)據(jù)塊在存儲(chǔ)節(jié)點(diǎn)間的轉(zhuǎn)發(fā)次數(shù)較多.由于存儲(chǔ)節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)通常會(huì)帶來額外的磁盤讀寫耗時(shí)和排隊(duì)耗時(shí)[23]，因而數(shù)據(jù)塊的轉(zhuǎn)發(fā)次數(shù)越多，傳輸效率較低，進(jìn)而導(dǎo)致寫入速度越低.

2 基于生成矩陣變換的跨數(shù)據(jù)中心糾刪碼寫入方法(CREW)

已有糾刪碼寫入方法在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中寫入數(shù)據(jù)時(shí)面臨著寫入速度較低的問題.在本節(jié)中，我們提出了一種基于生成矩陣變換的分布式流水線跨數(shù)據(jù)中心糾刪碼寫入方法，可以通過降低數(shù)據(jù)寫入時(shí)的網(wǎng)絡(luò)資源消耗量、提高編碼效率和傳輸效率來提高寫入速度，其主要思想是：通過對傳輸拓?fù)浜蜕删仃囃瑫r(shí)進(jìn)行優(yōu)化達(dá)到降低網(wǎng)絡(luò)資源消耗量的目的；同時(shí)，通過將編碼操作和傳輸操作分散到多個(gè)節(jié)點(diǎn)上并行執(zhí)行并控制數(shù)據(jù)塊的轉(zhuǎn)發(fā)次數(shù)達(dá)到提高編碼效率和傳輸效率的目的.

在本節(jié)中，我們首先通過一個(gè)實(shí)例來介紹CREW的主要思想.接著，分別介紹CREW包含的3個(gè)主要算法：一種基于貪心策略的傳輸拓?fù)錁?gòu)造算法GBTC、一種生成矩陣變形算法GMT和一種分布式流水線寫入算法DPW.最后給出CREW的整體算法流程.

2.1 主要思想

首先,我們通過一個(gè)實(shí)例來介紹CREW的主要思想.假設(shè)某編碼參數(shù)為(6,4,2)的糾刪碼的原始生成矩陣為式(2)中的G.

(2)

存儲(chǔ)節(jié)點(diǎn)和源節(jié)點(diǎn)位于UCloud[29]的6個(gè)數(shù)據(jù)中心中(分別用TPE,PEK1,PEK2,SHA,CAN,LA表示)，這6個(gè)數(shù)據(jù)中心間的網(wǎng)絡(luò)距離如表1所示.詳細(xì)數(shù)據(jù)放置方案為：源節(jié)點(diǎn)位于PEK1，存放編碼塊y4，y5，y6的存儲(chǔ)節(jié)點(diǎn)位于PEK2，存放編碼塊y2和y3的存儲(chǔ)節(jié)點(diǎn)位于TPE， 存放編碼塊y1的存儲(chǔ)節(jié)點(diǎn)位于SHA.

Table 1 Network Distances Between 6 DCs of UCloud表1 UCloud的6個(gè)數(shù)據(jù)中心間的網(wǎng)絡(luò)距離 hop

CREW首先使用GBTC構(gòu)造一個(gè)如圖2所示的數(shù)據(jù)傳輸拓?fù)?，其中：各個(gè)數(shù)據(jù)中心由一個(gè)樹形拓?fù)鋪斫M織，該樹形拓?fù)渲凶皂斚蛳逻叺臋?quán)值(網(wǎng)絡(luò)距離，即跳數(shù))遞增；數(shù)據(jù)中心內(nèi)部的各節(jié)點(diǎn)由一個(gè)星型拓?fù)鋪斫M織.

Fig. 2 Transmission topology of CREW圖2 CREW的傳輸拓?fù)?/p>

接著，CREW使用GMT對原生成矩陣G進(jìn)行初等行變換得到式(3)中的實(shí)際生成矩陣G′.

(3)

使用G′對數(shù)據(jù)進(jìn)行編碼后，樹形拓?fù)渲性较露说臄?shù)據(jù)中心要存儲(chǔ)的編碼塊與越少的數(shù)據(jù)塊線性相關(guān)(即G′中相應(yīng)列的非零行越少).

最后，如圖2所示，CREW使用DPW按以下方式組織各條帶中數(shù)據(jù)的編碼和傳輸：1)源節(jié)點(diǎn)Src先將原數(shù)據(jù)拆分為4個(gè)數(shù)據(jù)塊x1,x2,x3,x4；2)源節(jié)點(diǎn)向PEK2中的一個(gè)節(jié)點(diǎn)(編碼節(jié)點(diǎn))發(fā)送x1,x2,x3,x4，并向SHA中的一個(gè)節(jié)點(diǎn)(編碼節(jié)點(diǎn))發(fā)送x3；3)PEK2中的編碼節(jié)點(diǎn)收到4個(gè)數(shù)據(jù)塊后使用G′對其進(jìn)行編碼得到y(tǒng)6，y5，y4，將y6存儲(chǔ)在本地，并將y5和y4發(fā)送到PEK2中的另外2個(gè)節(jié)點(diǎn)中存儲(chǔ)；4)SHA中的編碼節(jié)點(diǎn)接收到x3后使用G′對其進(jìn)行編碼得到y(tǒng)3=x3并將y3存儲(chǔ)到本地；5)PEK2在使用x1，x2，x3，x4編碼生成y6，y5，y4的同時(shí)，將x1，x2轉(zhuǎn)發(fā)到TPE中的一個(gè)節(jié)點(diǎn)(編碼節(jié)點(diǎn))中；6)TPE中的編碼節(jié)點(diǎn)收到x1，x2后使用G′對其進(jìn)行編碼得到y(tǒng)1=x1和y2=x2，將y2存儲(chǔ)到本地并將y1發(fā)送到TPE中的另一個(gè)節(jié)點(diǎn)中存儲(chǔ).需要強(qiáng)調(diào)的是，各個(gè)節(jié)點(diǎn)是按流水并行的方式執(zhí)行各項(xiàng)編碼、傳輸任務(wù)的，即同一時(shí)間內(nèi)有多個(gè)條帶的數(shù)據(jù)在這些節(jié)點(diǎn)中進(jìn)行編碼和傳輸.

在CREW寫入數(shù)據(jù)的過程中，由于需要長距離傳輸?shù)臄?shù)據(jù)塊較少，所以網(wǎng)絡(luò)資源消耗量較低.與面向跨數(shù)據(jù)中心糾刪碼的分布式寫入方法IncEncoding相比，CREW可將寫入數(shù)據(jù)時(shí)的網(wǎng)絡(luò)資源消耗量降低59.4%.此外，由于在數(shù)據(jù)中心內(nèi)部采用了集中式的數(shù)據(jù)編碼和傳輸，CREW的傳輸效率較高，可將數(shù)據(jù)塊的最大轉(zhuǎn)發(fā)次數(shù)降低50%.

與集中式寫入方法Trad相比，CREW的網(wǎng)絡(luò)資源消耗量高了12.5%.但由于CREW的數(shù)據(jù)編碼任務(wù)是分散到多個(gè)節(jié)點(diǎn)上以流水并行的方式進(jìn)行的，與Trad相比CREW的編碼效率較高，可將單個(gè)節(jié)點(diǎn)的最大乘法運(yùn)算次數(shù)降低50%.此外，在集中式寫入方法Trad中，中心編碼節(jié)點(diǎn)除了要負(fù)責(zé)完成所有的編碼操作外，還需要負(fù)責(zé)完成所有的編碼塊分發(fā)操作，進(jìn)一步降低了其編碼效率.因此，CREW的編碼效率遠(yuǎn)高于Trad.

此外，在計(jì)算實(shí)際生成矩陣G′時(shí)，我們僅僅對原始生成矩陣G進(jìn)行了初等行變換，所以使用G′編碼得到的各編碼塊間的線性關(guān)系與使用G進(jìn)行編碼時(shí)相同.也就是說，對生成矩陣進(jìn)行變換并不改變糾刪碼原有的修復(fù)過程.

2.2 基于貪心策略的傳輸拓?fù)錁?gòu)造算法(GBTC)

糾刪碼數(shù)據(jù)寫入時(shí)的傳輸拓?fù)淇梢杂靡粋€(gè)有向圖D=V,E表示.其中，點(diǎn)集合V包含源節(jié)點(diǎn)和所有用于存儲(chǔ)編碼塊的存儲(chǔ)節(jié)點(diǎn)，邊集合E中的邊e=v1,v2∈E表示寫入過程中節(jié)點(diǎn)v1將向節(jié)點(diǎn)v2傳輸編碼塊或數(shù)據(jù)塊.e=v1,v2的權(quán)值weight(e)設(shè)為節(jié)點(diǎn)v1和節(jié)點(diǎn)v2之間的網(wǎng)絡(luò)距離.因此，傳輸拓?fù)銬的總網(wǎng)絡(luò)距離為其中，傳輸拓?fù)銬的數(shù)據(jù)中心間網(wǎng)絡(luò)距離定義為為E中連接屬于不同數(shù)據(jù)中心的節(jié)點(diǎn)的邊的集合).

由于糾刪碼寫入過程中既涉及數(shù)據(jù)中心間的數(shù)據(jù)傳輸又涉及數(shù)據(jù)中心內(nèi)的數(shù)據(jù)傳輸，因此傳輸拓?fù)淇梢苑譃?部分：

1) 數(shù)據(jù)中心間傳輸拓?fù)?在CREW構(gòu)建數(shù)據(jù)中心間傳輸拓?fù)鋾r(shí)，首先要求使用一種樹形傳輸拓?fù)浣M織數(shù)據(jù)傳輸以分散數(shù)據(jù)的編碼任務(wù)，從而保證編碼效率.其次，要求NDDin盡可能小以降低網(wǎng)絡(luò)資源消耗量.此外，因?yàn)樵贑REW中越靠近源節(jié)點(diǎn)的邊上需要傳輸?shù)臄?shù)據(jù)塊數(shù)越多，所以要求越靠近源節(jié)點(diǎn)的邊的權(quán)值越小，從而達(dá)到充分降低網(wǎng)絡(luò)資源消耗量的目的.

2) 數(shù)據(jù)中心內(nèi)傳輸拓?fù)?由于在各個(gè)數(shù)據(jù)中心內(nèi)只需編碼并存儲(chǔ)部分編碼塊，所以在數(shù)據(jù)中心內(nèi)編碼時(shí)的計(jì)算量較小.因此，在構(gòu)建數(shù)據(jù)中心內(nèi)傳輸拓?fù)鋾r(shí)，出于控制數(shù)據(jù)塊的轉(zhuǎn)發(fā)次數(shù)的目的，CREW將在數(shù)據(jù)中心內(nèi)采用集中式編碼方法進(jìn)行編碼并使用一種以編碼節(jié)點(diǎn)為中心的星型拓?fù)浣Y(jié)構(gòu)來組織數(shù)據(jù)傳輸.

為了構(gòu)造滿足以上要求的傳輸拓?fù)?，我們提出了一種基于貪心策略的傳輸拓?fù)錁?gòu)造算法(GBTC)，如算法1所示：

算法1.基于貪心策略的傳輸拓?fù)錁?gòu)造算法GBTC.

輸入：源節(jié)點(diǎn)Src、 存放編碼塊的存儲(chǔ)節(jié)點(diǎn)集合N、N中節(jié)點(diǎn)所在的數(shù)據(jù)中心的集合DC、各節(jié)點(diǎn)間的網(wǎng)絡(luò)距離矩陣DIS；

輸出：傳輸拓?fù)銬=V,E.

① for eachDCiinDC

②Venc,i←selectRandomly(N,DCi)；*從

N中隨機(jī)選擇一個(gè)屬于DCi的節(jié)點(diǎn)*

③ for eachvjinDCi

④ ifvj≠Venc,i

⑤E.add(vj,Venc,i)；

⑥ end if

⑦ end for

⑧ end for

⑨Vt.add(Src)；

⑩Venc.add(Src)；

Nenc-Venc)；*Nenc-Venc中選出2個(gè)離nd最近的節(jié)點(diǎn)*

第1步. GBTC從每個(gè)數(shù)據(jù)中心中隨機(jī)選擇一個(gè)存儲(chǔ)節(jié)點(diǎn)作為該數(shù)據(jù)中心的編碼節(jié)點(diǎn)(算法1第①②行).同時(shí)，GBTC以各數(shù)據(jù)中心的編碼節(jié)點(diǎn)為中心，以星型拓?fù)浣Y(jié)構(gòu)(數(shù)據(jù)中心內(nèi)傳輸拓?fù)?組織各個(gè)中心的所有節(jié)點(diǎn)，具體步驟為：GBTC將各數(shù)據(jù)中心編碼節(jié)點(diǎn)與該數(shù)據(jù)中心的所有非編碼節(jié)點(diǎn)相連產(chǎn)生若干條邊，并將這些邊添加到傳輸拓?fù)涞倪吋疎中(算法1第③～⑦行).

第2步. GBTC將源節(jié)點(diǎn)Src添加到一個(gè)臨時(shí)點(diǎn)集Vt和數(shù)據(jù)中心間傳輸拓?fù)涞狞c(diǎn)集Venc中(算法1第⑨⑩行).

第3步. GBTC構(gòu)造一個(gè)以源節(jié)點(diǎn)Src為根、自頂向下邊權(quán)遞增的樹形拓?fù)?數(shù)據(jù)中心間傳輸拓?fù)?來組織所有的編碼節(jié)點(diǎn)和源節(jié)點(diǎn)Src.具體步驟如下：對于Vt中的每個(gè)節(jié)點(diǎn)vt，首先選中所有不在Venc中的2個(gè)距離vt最近的2個(gè)編碼節(jié)點(diǎn)tmpN1和tmpN2；然后將tmpN1和tmpN2加入Venc和Vt中；接著將vt與tmpN1和tmpN2分別相連產(chǎn)生2條邊，并將這2條邊添加到傳輸拓?fù)涞倪吋疎中；最后將vt從Vt中刪除.當(dāng)Vt中不含有任何節(jié)點(diǎn)時(shí)，E為傳輸拓?fù)涞倪吋垂?jié)點(diǎn)Src與所有存儲(chǔ)節(jié)點(diǎn)的集合N的并集為傳輸拓?fù)涞狞c(diǎn)集V(算法1第～行).

第4步. GBTC將返回傳輸拓?fù)銬=V,E(算法1第行).

在GBTC構(gòu)造數(shù)據(jù)中心間傳輸拓?fù)鋾r(shí)，由于每次向E中添加邊時(shí)都是選擇權(quán)值最小的2條邊，所以構(gòu)造的樹形拓?fù)淠軌驖M足NDDin較小且自頂向下邊權(quán)遞減的要求.此外，GBTC的計(jì)算復(fù)雜度為O(|DC|2).

2.3 生成矩陣變形算法(GMT)

在2.2節(jié)中，我們提出一種基于貪心策略的傳輸拓?fù)錁?gòu)造算法GBTC.在GBTC構(gòu)造的數(shù)據(jù)中心間傳輸拓?fù)渲校竭h(yuǎn)離源節(jié)點(diǎn)的邊的權(quán)值越大(網(wǎng)絡(luò)距離越長).與之相適應(yīng)地，本節(jié)將提出一種生成矩陣變形算法GMT，通過對任意線性糾刪碼的生成矩陣進(jìn)行變形使得寫入過程中需要在遠(yuǎn)離源節(jié)點(diǎn)的邊上傳輸?shù)臄?shù)據(jù)塊數(shù)盡可能地少，從而達(dá)到降低網(wǎng)絡(luò)資源消耗量的目標(biāo).與此同時(shí)，GMT可以保持各編碼塊的線性關(guān)系，因而對糾刪碼原有的修復(fù)過程沒有任何影響.此外，GMT可以保持編碼的系統(tǒng)性，因而不會(huì)降低讀取效率.

GMT對生成矩陣進(jìn)行變形的過程如算法2：

算法2.生成矩陣變形算法GMT.

輸入：原始生成矩陣G、傳輸拓?fù)銬、放置方案P=Y,N；

輸出：變形后的生成矩陣G′.

①Y←sortY(D,P)；*根據(jù)放置方案P和傳輸拓?fù)銬對所有的編碼塊進(jìn)行排序*

②EX←exchangeScheme(Y,G)；

③G1←columnExchange(G,EX)；*對G進(jìn)行列交換操作，得到G1*

④G2←RREF(G1)；*使用RREF算法對將G1化為行最簡形矩陣G2*

⑤EX′←revert(EX)；

⑥G′←columnExchange(G2,EX′).*對G2進(jìn)行列交換操作，得到G′*

第1步. GMT按各編碼塊所在數(shù)據(jù)中心在GBTC構(gòu)建的傳輸拓?fù)渲信c源節(jié)點(diǎn)Src的距離對這些編碼塊進(jìn)行排序(算法2第①行).編碼塊所在數(shù)據(jù)中心與源節(jié)點(diǎn)Src的距離越遠(yuǎn)，相應(yīng)的編碼塊排序越靠前.

第2步. 設(shè)編碼塊的排序?yàn)閥i1,yi2,…,yin，GMT將接著對生成矩陣G=(g*1,g*2,…,g*n)進(jìn)行列交換操作(g*i表示G的第i個(gè)列向量)，得到如下矩陣G1=(g*i1,g*i2,…,g*in)(算法2第②③行).

定理1.在GMT算法中，G與G′的校驗(yàn)矩陣相同，即用它們編碼得到的編碼塊之間的線性關(guān)系相同.

假設(shè)G的校驗(yàn)矩陣為H.若將G轉(zhuǎn)換為G1的列交換操作為EX={e1,e2,e2,e3,…,ex,ex+1}，其中e1,e2表示交換矩陣的第e1列和第e2列.那么，我們定義對H進(jìn)行EX列交換操作得到的矩陣為H1.因?yàn)镚HT=0，所以G1H1T=0.

因?yàn)镚′是通過對G2進(jìn)行EX′={ex,ex+1,…,e1,e2}操作得到，H是通過對H1進(jìn)行EX′={ex,ex+1,…,e1,e2}操作得到,所以有G′HT=0,H也是G′的校驗(yàn)矩陣.因此用G′編碼得到的編碼塊之間的線性關(guān)系與用G編碼得到的編碼塊之間的線性關(guān)系相同.

證畢.

定理2.在GMT算法中，若G為系統(tǒng)碼的生成矩陣，則G′也為系統(tǒng)碼的生成矩陣.

證明. 因?yàn)榫仃嘒是行滿秩的，所以G1也是行滿秩的.由于矩陣的秩等于其行最簡形矩陣非零行的數(shù)量，所以G1的行最簡形(G2)一定可以通過列交換操作轉(zhuǎn)化為

[EA],

(4)

其中E為單位矩陣.

所以，G2為系統(tǒng)碼的生成矩陣，進(jìn)而有G′為系統(tǒng)碼的生成矩陣.

證畢.

由定理1有，GMT并不會(huì)改變糾刪碼原有的修復(fù)過程.由定理2有，若G為系統(tǒng)碼的生成矩陣，則G′也為系統(tǒng)碼的生成矩陣，所以GMT不會(huì)改變原有糾刪碼的讀取性能.此外，由于GMT的輸入可以是任意線性糾刪碼的生成矩陣，所以GMT的適用范圍較廣.最后，GMT中的主要計(jì)算任務(wù)為執(zhí)行RREF算法，其復(fù)雜度為O(k2).由于實(shí)際應(yīng)用中k的值較小，因此GMT的計(jì)算用時(shí)較低.

2.4 分布式流水線寫入算法(DPW)

在2.2節(jié)和2.3節(jié)中，我們分別提出了基于貪心策略的傳輸拓?fù)錁?gòu)造算法GBTC和生成矩陣轉(zhuǎn)換算法GMT，對傳輸拓?fù)浜蜕删仃囘M(jìn)行了優(yōu)化，從而達(dá)到效降低寫入數(shù)據(jù)時(shí)的網(wǎng)絡(luò)資源消耗量的目的，進(jìn)而提高了寫入速度.

然而，寫入速度不僅受到網(wǎng)絡(luò)資源消耗量的影響，也受到寫入過程中的傳輸效率和編碼效率的影響.傳統(tǒng)的集中式寫入方法將所有編碼操作都集中到了中心編碼節(jié)點(diǎn)上，導(dǎo)致編碼效率低下，進(jìn)而導(dǎo)致寫入速度較低的問題.而在已有的分布式寫入方法中，數(shù)據(jù)塊往往需要被多次轉(zhuǎn)發(fā)，帶來額外的磁盤讀寫耗時(shí)和排隊(duì)耗時(shí)，使得傳輸效率低下，同樣導(dǎo)致了寫入速度較低的問題.因此，為了兼顧糾刪碼寫入數(shù)據(jù)時(shí)的編碼效率和傳輸效率，我們在本節(jié)提出了一種分布式流水線寫入算法DPW.

算法3.分布式流水線寫入算法DPM.

輸入：數(shù)據(jù)塊向量X、生成矩陣G′、傳輸拓?fù)銬.

①Src.send(X,D)；

② for eachvtinD.V

③ ifvt.isEncodingNode()

④codedblocks←vt.enc(receivedBlocks)；*使用G′對接收到的數(shù)據(jù)塊進(jìn)行編碼，得到編碼塊*

⑤vt.storing(codedblocks)；*將編碼塊存儲(chǔ)到本地*

⑥vo←vt.getOffspring；

⑦vt.send(vo,codedblocks)；*將編碼塊轉(zhuǎn)發(fā)到下一級節(jié)點(diǎn)*

⑧ else

⑨vt.storing(receivedBlocks)；

⑩ end if

為了避免節(jié)點(diǎn)的計(jì)算能力成為編碼瓶頸，DPW在數(shù)據(jù)中心間進(jìn)行分布式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸以將計(jì)算任務(wù)分散到多個(gè)節(jié)點(diǎn)并行執(zhí)行.因?yàn)閷?shí)際應(yīng)用中用來存儲(chǔ)一個(gè)條帶的數(shù)據(jù)中心數(shù)較小，所以數(shù)據(jù)中心間的傳輸拓?fù)涞倪x擇對數(shù)據(jù)在存儲(chǔ)節(jié)點(diǎn)間轉(zhuǎn)發(fā)的次數(shù)的影響較小.因此，在數(shù)據(jù)中心間進(jìn)行分布式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼既可以提高編碼效率又不會(huì)對傳輸效率造成過大影響.

此外，為了避免因數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)過多造成的傳輸瓶頸，DPW在數(shù)據(jù)中心內(nèi)部進(jìn)行集中式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸以降低數(shù)據(jù)塊的轉(zhuǎn)發(fā)次數(shù).因?yàn)镈PW在數(shù)據(jù)中心間采用的是分布式的數(shù)據(jù)編碼，各個(gè)數(shù)據(jù)中心只負(fù)責(zé)條帶中一部分編碼塊的編碼任務(wù)，所以各數(shù)據(jù)中心中需要進(jìn)行的編碼運(yùn)算量較小.因此，在數(shù)據(jù)中心內(nèi)部采用集中式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸既可以提高傳輸效率，又不會(huì)導(dǎo)致編碼瓶頸.

DPW中涉及的節(jié)點(diǎn)有3類：源節(jié)點(diǎn)Src、編碼節(jié)點(diǎn)和普通存儲(chǔ)節(jié)點(diǎn).DPW根據(jù)GBTC構(gòu)造的數(shù)據(jù)中心間傳輸拓?fù)湎蚋鱾€(gè)編碼節(jié)點(diǎn)發(fā)送該編碼節(jié)點(diǎn)所需的數(shù)據(jù)塊(算法3第①行).各個(gè)編碼節(jié)點(diǎn)在接收到其所需的數(shù)據(jù)塊后將同時(shí)進(jìn)行2個(gè)操作.一方面，各編碼節(jié)點(diǎn)向它在數(shù)據(jù)中心間傳輸拓?fù)渲械淖庸?jié)點(diǎn)(子數(shù)據(jù)中心)里的編碼節(jié)點(diǎn)發(fā)送這些子節(jié)點(diǎn)需要的數(shù)據(jù)塊.由于越遠(yuǎn)離源節(jié)點(diǎn)Src的數(shù)據(jù)中心需要的數(shù)據(jù)塊越少，傳輸?shù)臄?shù)據(jù)量是遞減的.另一方面，編碼節(jié)點(diǎn)用自己收到的數(shù)據(jù)塊編碼生成本數(shù)據(jù)中心各個(gè)存儲(chǔ)節(jié)點(diǎn)所需存儲(chǔ)的編碼塊，并以星型拓?fù)鋵⑦@些編碼塊發(fā)送到相應(yīng)的存儲(chǔ)節(jié)點(diǎn)中(算法3第③～⑦行).由于編碼操作對網(wǎng)絡(luò)資源占用少，而傳輸操作對計(jì)算資源占用小，編碼節(jié)點(diǎn)能夠以較高的效率同時(shí)進(jìn)行這2項(xiàng)操作.為了提高寫入效率，以上過程中的數(shù)據(jù)傳輸和編碼過程都以流水并行的方式進(jìn)行的.顯然，GMT的計(jì)算復(fù)雜度為O(kn).

2.5 CREW的算法描述

基于生成矩陣變換的分布式流水線跨數(shù)據(jù)中心糾刪碼寫入方法的算法描述如算法4所示:

算法4.基于生成矩陣變換的跨數(shù)據(jù)中心糾刪碼寫入方法CREW.

輸入：原始數(shù)據(jù)O、原始生成矩陣G、源節(jié)點(diǎn)Src、Src所在的數(shù)據(jù)中心dcc、數(shù)據(jù)塊數(shù)k、數(shù)據(jù)塊大小Sb、存放編碼塊的存儲(chǔ)節(jié)點(diǎn)集合N、N中節(jié)點(diǎn)所在的數(shù)據(jù)中心的集合DC、節(jié)點(diǎn)間的網(wǎng)絡(luò)距離矩陣DIS.

①m←O.size()kSb；

②D←Src.GBTC(dcc,N,DC,DIS)；

③G′←Src.GMT(G)；

④ fori

⑤X←Src.splite(O)；

⑥Src.DPW(X,D,G′)；

⑦i←i+1；

⑧ end for

首先，源節(jié)點(diǎn)Src調(diào)用GBTC得到傳輸拓?fù)銬并調(diào)用GMT對生成矩陣進(jìn)行變形得到G′(算法4第①～③行)；接著，源節(jié)點(diǎn)Src將原始數(shù)據(jù)劃分為若干個(gè)條帶，每個(gè)條帶含有k個(gè)數(shù)據(jù)塊(算法4第⑤行)；最后，源節(jié)點(diǎn)Src不斷調(diào)用DPW以并行流水的方式完成所有條帶的寫入任務(wù)(算法4第⑥行).

在CREW中，GBTC的計(jì)算復(fù)雜度為O(|DC|2)，GMT的計(jì)算復(fù)雜度為O(k2)，DPW的計(jì)算復(fù)雜度O(kn).其中，GBTC與CMT只執(zhí)行2次，DPW的執(zhí)行次數(shù)由原始數(shù)據(jù)的大小決定.所以，CREW的計(jì)算復(fù)雜度為O(knm).實(shí)際應(yīng)用中，k和n較小，因此CREW的計(jì)算復(fù)雜度為O(m).

3 實(shí)驗(yàn)與結(jié)果

為了評估CREW的性能，我們基于Hadoop 3.0.3的HDFS實(shí)現(xiàn)了CREW.Hadoop 3.0.3的HDFS中主要有3類節(jié)點(diǎn)：Client(即源節(jié)點(diǎn))、NameNode和DataNode.其中，Client負(fù)責(zé)數(shù)據(jù)的寫入；NameNode負(fù)責(zé)存儲(chǔ)源節(jié)點(diǎn)Client寫入的元數(shù)據(jù)、檢測編碼塊失效、選擇DataNode來完成失效編碼塊的修復(fù)工作；DataNode則負(fù)責(zé)存儲(chǔ)Client寫入的數(shù)據(jù)并運(yùn)行ECWorker任務(wù)對失效的編碼塊進(jìn)行修復(fù).

在實(shí)現(xiàn)CREW時(shí)，我們主要對Client和Data-Node進(jìn)行了修改：在Client中添加了拓?fù)錁?gòu)造模塊和生成矩陣變形模塊，使其在寫入數(shù)據(jù)前可以運(yùn)行GBTC來確定傳輸拓?fù)洳⒖梢赃\(yùn)行GMT來對生成矩陣進(jìn)行變形操作；在DataNode添加了編碼模塊，使其在寫入數(shù)據(jù)過程中可以進(jìn)行部分編碼操作，從而能夠支持DPW的運(yùn)行.

此外，我們同樣基于Hadoop 3.0.3的HDFS實(shí)現(xiàn)了一種集中式寫入方法Trad[19]、一種分布式寫入方法D2CP[22]、一種面向跨數(shù)據(jù)中心糾刪碼的分布式寫入方法IncEncoding[23]、CREW的2種變形CREW-Star和CREW-Tree.

在Trad中，源節(jié)點(diǎn)即為中心編碼節(jié)點(diǎn)，源節(jié)點(diǎn)先將數(shù)據(jù)對象分塊，然后對數(shù)據(jù)塊進(jìn)行編碼得到編碼塊，最后將編碼塊分發(fā)到各個(gè)存儲(chǔ)節(jié)點(diǎn)中.

在D2CP中，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后完成部分的數(shù)據(jù)編碼操作，然后將編碼生成的中間編碼塊發(fā)送到相應(yīng)的存儲(chǔ)節(jié)點(diǎn)中，存儲(chǔ)節(jié)點(diǎn)在接收到源節(jié)點(diǎn)的數(shù)據(jù)后通過相互協(xié)作的方式完成剩余的編碼操作.

在CREW-Star中，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后以星型拓?fù)浒l(fā)送給各個(gè)數(shù)據(jù)中心中的編碼節(jié)點(diǎn)，編碼節(jié)點(diǎn)在接收到所有需要的數(shù)據(jù)塊后對其進(jìn)行編碼，然后將編碼得到的編碼塊以星型拓?fù)浒l(fā)送給同數(shù)據(jù)中心里的其他存儲(chǔ)節(jié)點(diǎn).

在CREW-Tree中，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后以樹型拓?fù)?最小網(wǎng)絡(luò)距離生成樹)發(fā)送給各個(gè)數(shù)據(jù)中心中的編碼節(jié)點(diǎn)，編碼節(jié)點(diǎn)在接收到所有需要的數(shù)據(jù)塊后對其進(jìn)行編碼，然后將編碼后的編碼塊以星型拓?fù)浒l(fā)送給同數(shù)據(jù)中心里的其他存儲(chǔ)節(jié)點(diǎn).

在IncEncoding中，所有源節(jié)點(diǎn)和存儲(chǔ)節(jié)點(diǎn)以線性拓?fù)浣M織，源節(jié)點(diǎn)將數(shù)據(jù)對象分塊后沿著線性拓?fù)湟粤魉姆绞揭来伟l(fā)送各個(gè)數(shù)據(jù)塊，各個(gè)存儲(chǔ)節(jié)點(diǎn)接收到一個(gè)數(shù)據(jù)塊就使用其進(jìn)行編碼得到中間編碼塊，同時(shí)將該數(shù)據(jù)塊轉(zhuǎn)發(fā)給下一存儲(chǔ)節(jié)點(diǎn).最終，每個(gè)存儲(chǔ)節(jié)點(diǎn)都將接收到自己所需的所有數(shù)據(jù)塊，并編碼生成最終的編碼塊.

3.1 實(shí)驗(yàn)設(shè)置

我們的實(shí)驗(yàn)環(huán)境為UCloud[29]的6個(gè)數(shù)據(jù)中心，其中2個(gè)位于北京(記為PEK1和PEK2)、一個(gè)位于上海(記為SHA)、一個(gè)位于廣州(記為CAN)、一個(gè)位于洛杉磯(記為LA)、一個(gè)位于臺北(記為TPE).我們測試了這6個(gè)數(shù)據(jù)中心間的網(wǎng)絡(luò)距離，如表1所示.實(shí)驗(yàn)用到了每個(gè)數(shù)據(jù)中心的10個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)配備了2個(gè)6核Intel Xeon-2640 2.5 GHz處理器、6 GB內(nèi)存和20 GB磁盤.

在實(shí)驗(yàn)中，我們首先使用Hadoop源碼中提供的ErasureCodeBenchmarkThroughput類來生成不同大小的文件，然后比較了不同寫入方法在不同參數(shù)下寫入這些文件時(shí)的各項(xiàng)性能指標(biāo).實(shí)驗(yàn)中的參數(shù)如表2所示.其中，第1列為表示參數(shù)的符號，第2列為參數(shù)的定義，第3列為參數(shù)的取值范圍，第4列為參數(shù)的默認(rèn)值.

Table 2 Parameters in Experiments表2 實(shí)驗(yàn)參數(shù)

3.2 評價(jià)指標(biāo)

由于糾刪碼寫入方法的寫入速度受到網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率的影響.因此，我們首先比較了不同寫入方法的網(wǎng)絡(luò)資源消耗量；然后，我們分別用數(shù)據(jù)塊的最大轉(zhuǎn)發(fā)次數(shù)和節(jié)點(diǎn)的最大編碼復(fù)雜度來量化對比不同寫入方法的傳輸效率和編碼效率；最后，我們還直接比較了不同寫入方法的寫入速度.

1) 平均網(wǎng)絡(luò)資源消耗量.平均網(wǎng)絡(luò)資源消耗量定義為M·NavgSd(單位為hop).其中，M為數(shù)據(jù)寫入過程中的各節(jié)點(diǎn)間的數(shù)據(jù)傳輸總量，Navg為數(shù)據(jù)的平均傳輸網(wǎng)絡(luò)距離，Sd為數(shù)據(jù)對象的大小.

2) 數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù).由于數(shù)據(jù)的傳輸是流水并行的，理想情況下總傳輸時(shí)間由所有數(shù)據(jù)塊的最長傳輸時(shí)間決定.又因?yàn)閿?shù)據(jù)塊在存儲(chǔ)節(jié)點(diǎn)上進(jìn)行轉(zhuǎn)發(fā)時(shí)會(huì)帶來額外的磁盤讀寫耗時(shí)和排隊(duì)等待耗時(shí)，所以數(shù)據(jù)塊的最長傳輸時(shí)間受最長轉(zhuǎn)發(fā)次數(shù)的影響較大.因此可以使用數(shù)據(jù)塊的最大轉(zhuǎn)發(fā)次數(shù)來衡量傳輸效率.最大轉(zhuǎn)發(fā)次數(shù)越短，傳輸效率越高.

3) 節(jié)點(diǎn)最大計(jì)算復(fù)雜度.各個(gè)節(jié)點(diǎn)的編碼復(fù)雜度定義為該節(jié)點(diǎn)需要完成的乘法運(yùn)算次數(shù).由于數(shù)據(jù)的編碼可以分散到不同的節(jié)點(diǎn)同步進(jìn)行，理想情況下總的編碼用時(shí)由所有節(jié)點(diǎn)的最長編碼用時(shí)決定，而節(jié)點(diǎn)的最長編碼用時(shí)受節(jié)點(diǎn)最大計(jì)算復(fù)雜度的影響較大.因此，節(jié)點(diǎn)最大計(jì)算復(fù)雜度決定了編碼效率.節(jié)點(diǎn)最大計(jì)算復(fù)雜度越小，編碼效率越高.

4) 寫入速度.寫入速度定義為SdT(單位為MBps)，其中，T為寫入用時(shí)，Sd為數(shù)據(jù)對象的大小.寫入速度受到網(wǎng)絡(luò)資源消耗量、編碼效率、傳輸效率的共同影響，能夠綜合評估寫入方法的優(yōu)劣.

3.3 平均網(wǎng)絡(luò)資源消耗量

3.3.1 平均網(wǎng)絡(luò)資源消耗量與編碼參數(shù)的關(guān)系

圖3顯示了使用不同編碼參數(shù)和不同寫入方法時(shí)的平均網(wǎng)絡(luò)資源消耗量.隨著編碼塊數(shù)n的增加，所有寫入方法的平均資源消耗量都增加了，這是由于數(shù)據(jù)傳輸量會(huì)隨著n的增加而增加.在所有寫入方法中，由于Trad在中心編碼節(jié)點(diǎn)中完成全部編碼塊的編碼后只需直接將編碼塊傳輸?shù)綄?yīng)的存儲(chǔ)節(jié)點(diǎn)中即可，所以其網(wǎng)絡(luò)資源銷量最小.但是，Trad的低網(wǎng)絡(luò)資源消耗量是通過犧牲編碼效率獲得的.由于Trad將全部的編碼負(fù)載集中到了中心編碼節(jié)點(diǎn)上，其編碼效率明顯低于其他寫入方法.在其他5種寫入方法中，CREW具有最小的平均網(wǎng)絡(luò)資源消耗量，這是因?yàn)镃REW可以通過同時(shí)對傳輸拓?fù)浜蜕删仃囘M(jìn)行優(yōu)化充分減少寫入過程中需要遠(yuǎn)距離傳輸?shù)臄?shù)據(jù)塊.

Fig. 3 Comparison of the average network resource consumption under different encoding parameters圖3 不同的編碼參數(shù)下的平均網(wǎng)絡(luò)資源消耗量對比

3.3.2 平均網(wǎng)絡(luò)資源消耗量與數(shù)據(jù)中心數(shù)的關(guān)系

圖4表明所有寫入方法的平均網(wǎng)絡(luò)資源消耗量都會(huì)隨著使用的數(shù)據(jù)中心數(shù)的增加而增加.這是由于使用的數(shù)據(jù)中心數(shù)越多，需要跨數(shù)據(jù)中心傳輸?shù)臄?shù)據(jù)越多.此外，在只使用3個(gè)數(shù)據(jù)中心進(jìn)行數(shù)據(jù)存儲(chǔ)時(shí)，CREW的平均網(wǎng)絡(luò)資源消耗量甚至少于Trad，這是因?yàn)镃REW此時(shí)將需要使用較多數(shù)據(jù)塊編碼得到的編碼塊存放在源節(jié)點(diǎn)所在的數(shù)據(jù)中心中，從而大大減少了需要跨數(shù)據(jù)中心傳輸?shù)臄?shù)據(jù)塊的數(shù)目.

Fig. 4 Comparison of the average network resource consumption when different numbers of DCs are used圖4 不同的數(shù)據(jù)中心數(shù)下的平均網(wǎng)絡(luò)資源消耗量對比

3.4 數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)

3.4.1 數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)與編碼參數(shù)的關(guān)系

Fig. 5 Comparison of the maximum number of forwards of data blocks under different encoding parameters圖5 不同的編碼參數(shù)下的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)對比

圖5顯示了選擇不同的編碼參數(shù)時(shí)CREW,CREW-Tree,CREW-Star,Trad的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)沒有明顯變化.這是由于這些寫入方法在數(shù)據(jù)中心內(nèi)采用的是集中式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼，因而其數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)只受到數(shù)據(jù)中心間傳輸拓?fù)涞挠绊?，而?shù)據(jù)中心間傳輸拓?fù)渲皇艿绞褂玫臄?shù)據(jù)中心數(shù)的影響.此外，由于D2CP和IncEncoding在數(shù)據(jù)中心間和數(shù)據(jù)中心內(nèi)部均采用分布式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼，因而它們的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)隨著編碼塊數(shù)n的增加而增加，并且明顯高于其他方法.最后，由于Trad和CREW-Star在數(shù)據(jù)中心間使用了無需轉(zhuǎn)發(fā)數(shù)據(jù)的星型傳輸拓?fù)洌鼈兊臄?shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)最小.但是，由于實(shí)際應(yīng)用中數(shù)據(jù)中心的數(shù)目通常較小，所以數(shù)據(jù)中心間傳輸拓?fù)鋵?shù)據(jù)塊的最大轉(zhuǎn)發(fā)次數(shù)影響較小.因此，CREW和CREW-Star的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)在各種編碼參數(shù)下均只比Trad和CREW-Star多1～2次.

3.4.2 數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)與數(shù)據(jù)中心數(shù)的關(guān)系

圖6顯示了使用不同糾刪碼寫入方法時(shí)，數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)隨著數(shù)據(jù)中心數(shù)的增長而緩慢增長.這是由于隨著數(shù)據(jù)中心數(shù)的增多，各種方法的傳輸拓?fù)涞纳疃染饾u加深.此外，由于D2CP和IncEncoding在數(shù)據(jù)中心間和數(shù)據(jù)中心內(nèi)部均采用分布式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼，因而它們的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)明顯高于其他方法.最后，由于Trad和CREW-Star在數(shù)據(jù)中心間使用了無需轉(zhuǎn)發(fā)數(shù)據(jù)的星型傳輸拓?fù)洌运鼈兊臄?shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)最小.但是，由于數(shù)據(jù)中心的數(shù)目通常較小，所以數(shù)據(jù)中心間傳輸拓?fù)鋵?shù)據(jù)塊的最大轉(zhuǎn)發(fā)次數(shù)影響較小.因此，實(shí)驗(yàn)中CREW和CREW-Star的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)僅比Trad和CREW-Star多1～2次.

Fig. 6 Comparison of the maximum number of forwards of data blocks when different numbers of DCs are used圖6 不同的數(shù)據(jù)中心數(shù)下的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)對比

3.5 節(jié)點(diǎn)最大計(jì)算復(fù)雜度

3.5.1 節(jié)點(diǎn)最大計(jì)算復(fù)雜度與編碼參數(shù)的關(guān)系

圖7顯示了不同編碼參數(shù)對節(jié)點(diǎn)最大計(jì)算復(fù)雜度的影響.可以看到，隨著編碼塊數(shù)和數(shù)據(jù)塊數(shù)的增加，節(jié)點(diǎn)最大計(jì)算復(fù)雜度逐漸增加.這是由于越多的編碼塊和數(shù)據(jù)塊意味著越多的乘法計(jì)算.此外，由于IncEncoding和D2CP在數(shù)據(jù)中心間和數(shù)據(jù)中心內(nèi)部均采用分布式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼，所以它們的節(jié)點(diǎn)最大計(jì)算復(fù)雜度最低.但是，這2種方法的低節(jié)點(diǎn)最大計(jì)算復(fù)雜度是通過犧牲傳輸效率獲得的.如圖5所示，在不同的編碼參數(shù)下，IncEncoding和D2CP的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)均明顯多于其他方法，因而它們傳輸效率明顯低于其他方法.在其他寫入方法中，CREW具有最低的節(jié)點(diǎn)最大計(jì)算復(fù)雜度，這是由于CREW在數(shù)據(jù)中心間采用分布式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸，起到了分散計(jì)算負(fù)載的作用.

Fig. 7 Comparison of the maximum computational complexity of encoding nodes under different encoding parameters圖7 不同的編碼參數(shù)下的節(jié)點(diǎn)最大計(jì)算復(fù)雜度對比

3.5.2 節(jié)點(diǎn)最大計(jì)算復(fù)雜度與數(shù)據(jù)中心數(shù)的關(guān)系

Fig. 8 Comparison of the maximum computational complexity of encoding nodes when different numbers of DCs are used圖8 不同的數(shù)據(jù)中心數(shù)下的節(jié)點(diǎn)最大計(jì)算復(fù)雜度對比

圖8顯示了不同數(shù)據(jù)中心數(shù)對節(jié)點(diǎn)最大計(jì)算復(fù)雜度的影響.可以看到，隨著數(shù)據(jù)中心數(shù)的增加，節(jié)點(diǎn)最大計(jì)算復(fù)雜度逐漸降低.這是由于越多的數(shù)據(jù)中心意味著編碼計(jì)算越分散.此外，由于IncEncoding和D2CP在數(shù)據(jù)中心間和數(shù)據(jù)中心內(nèi)部均采用分布式的數(shù)據(jù)傳輸和數(shù)據(jù)編碼，所以它們的節(jié)點(diǎn)最大計(jì)算復(fù)雜度最低.但是，這2種方法的低節(jié)點(diǎn)最大計(jì)算復(fù)雜度是通過犧牲傳輸效率獲得的.如圖6所示，在不同的數(shù)據(jù)中心數(shù)下，IncEncoding和D2CP的數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)明顯多于其他方法，因而它們傳輸效率明顯低于其他方法.在其他寫入方法中，CREW具有最低的節(jié)點(diǎn)最大計(jì)算復(fù)雜度，這是由于CREW在數(shù)據(jù)中心間采用分布式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸，起到了分散計(jì)算負(fù)載的作用.

3.6 寫入速度

3.6.1 寫入速度與數(shù)據(jù)包大小的關(guān)系

如圖9所示，隨著數(shù)據(jù)包大小的不斷增大，6種寫入方法的寫入速度都在不斷提高.這是因?yàn)楦蟮臄?shù)據(jù)包能夠減少數(shù)據(jù)包的數(shù)量，從而提高傳輸速度.值得注意的是，當(dāng)數(shù)據(jù)包大小從48 KB增大到64 KB時(shí)，數(shù)據(jù)傳輸速度又略微降低.這是由于超過一定大小的數(shù)據(jù)包在通過TCP傳輸時(shí)會(huì)被分為多個(gè)包，從而增加了數(shù)據(jù)包的數(shù)據(jù)量.此外，在不同的數(shù)據(jù)包大小下，CREW均能取得最高的寫入速度，這是因?yàn)镃REW可在網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率之間取得較好的權(quán)衡.

Fig. 9 Comparison of the writing rate when different data package sizes are used圖9 不同的數(shù)據(jù)包大小下的寫入速度對比

3.6.2 寫入速度與線程數(shù)目的關(guān)系

如圖10所示，隨著線程數(shù)目的增加，6種寫入方法的寫入速度都得到提高.這是由于線程的增加提高了編碼的效率.特別的是，隨著線程數(shù)的增加，Trad的寫入速度的增加較為明顯.這是因?yàn)門rad的寫入瓶頸在于編碼效率，而提高線程數(shù)能夠有效提高編碼效率.此外，在不同的線程數(shù)目下，CREW均能取得最高的寫入速度，這是因?yàn)镃REW可在網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率之間取得較好的權(quán)衡.

3.6.3 寫入速度與編碼參數(shù)的關(guān)系

圖11顯示了不同編碼參數(shù)對寫入速度的影響.可以看到，隨著編碼塊數(shù)的增加，編碼速度降低.這是因?yàn)榫幋a塊數(shù)的增加同時(shí)增大了網(wǎng)絡(luò)資源消耗量和節(jié)點(diǎn)最大計(jì)算復(fù)雜度.此外，在不同的編碼參數(shù)下，CREW均能取得最高的寫入速度，這是因?yàn)镃REW可在網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率之間取得較好的權(quán)衡.

3.6.4 寫入速度與數(shù)據(jù)中心數(shù)的關(guān)系

圖12顯示了數(shù)據(jù)中心數(shù)對寫入速度的影響.可以看到，隨著數(shù)據(jù)中心數(shù)的增加，寫入速度降低.這是因?yàn)閿?shù)據(jù)中心數(shù)的增加同時(shí)增大了網(wǎng)絡(luò)資源消耗量和數(shù)據(jù)塊最大傳輸距離.此外，在不同的數(shù)據(jù)中心數(shù)下，CREW均能取得最高的寫入速度，這是因?yàn)镃REW可在網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率之間取得較好的權(quán)衡.

總體而言，Trad的網(wǎng)絡(luò)資源消耗量少且數(shù)據(jù)塊最長傳輸網(wǎng)絡(luò)距離短，但其節(jié)點(diǎn)最大計(jì)算復(fù)雜度最高.D2CP和IncEncoding的節(jié)點(diǎn)最大計(jì)算復(fù)雜度低，但其數(shù)據(jù)塊最長傳輸網(wǎng)絡(luò)距離長且網(wǎng)絡(luò)資源消耗量大.CREW-Star的網(wǎng)絡(luò)資源消耗量大，CREW-Tree的數(shù)據(jù)塊最長傳輸網(wǎng)絡(luò)距離長.而CREW能在網(wǎng)絡(luò)資源消耗量、數(shù)據(jù)塊最大轉(zhuǎn)發(fā)次數(shù)(傳輸效率)和節(jié)點(diǎn)最大計(jì)算復(fù)雜度(編碼效率)間取得較好的權(quán)衡.因此，平均而言，CREW的寫入速度比IncEncoding,Trad,D2CP,CREW-Tree,CREW-Star分別提高了32.4%， 57.9%,36.3%,33.3%,35.2%.

4 總 結(jié)

在跨數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中，已有糾刪碼寫入方法面臨網(wǎng)絡(luò)資源消耗量較大、編碼效率和傳輸效率低等問題，使得跨數(shù)據(jù)中心糾刪碼的寫入速度較低以至于難以適應(yīng)于日益增長的數(shù)據(jù)生成速度.為此，本文提出了一種基于生成矩陣變換的跨數(shù)據(jù)中心糾刪碼寫入方法CREW.具體而言，CREW包含以下3個(gè)主要算法：基于貪心策略的傳輸拓?fù)錁?gòu)造算法GBTC和生成矩陣變形算法GMT，二者相互協(xié)作可降低數(shù)據(jù)寫入時(shí)需要遠(yuǎn)距離傳輸?shù)臄?shù)據(jù)量，從而達(dá)到降低網(wǎng)絡(luò)資源消耗量的目的.以及分布式流水線寫入算法DPW來協(xié)調(diào)各節(jié)點(diǎn)間的數(shù)據(jù)傳輸操作和編碼操作.為了避免節(jié)點(diǎn)的計(jì)算能力成為編碼瓶頸， DPW在數(shù)據(jù)中心間進(jìn)行分布式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸.為了避免因數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)過多造成的傳輸瓶頸，DPW在數(shù)據(jù)中心內(nèi)部進(jìn)行集中式的數(shù)據(jù)編碼和數(shù)據(jù)傳輸.在跨數(shù)據(jù)中心環(huán)境下的實(shí)驗(yàn)表明，CREW能在網(wǎng)絡(luò)資源消耗量、編碼效率和傳輸效率之間取得較好的權(quán)衡，從而能夠有效提高寫入速度.