具有最優(yōu)負(fù)載均衡性的糾刪碼修復(fù)流水線

江小玉，李貴洋，胡金平，韓鴻宇

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

大數(shù)據(jù)時(shí)代，分布式存儲(chǔ)集群承載的數(shù)據(jù)量規(guī)模日益擴(kuò)大，需要以更加經(jīng)濟(jì)有效的方式保障數(shù)據(jù)的可靠性[1]。糾刪碼(erasure code)[2,3]因具有高容錯(cuò)性和低冗余度的特點(diǎn)，在許多大規(guī)模分布式存儲(chǔ)系統(tǒng)中已得到實(shí)際應(yīng)用，比如 Google[5]、Facebook[6]、Hadoop[7]等互聯(lián)網(wǎng)國際巨頭。但是，糾刪碼的修復(fù)代價(jià)高昂[8]，修復(fù)時(shí)從其它可用節(jié)點(diǎn)上下載數(shù)據(jù)并進(jìn)行譯碼，會(huì)對計(jì)算和網(wǎng)絡(luò)資源造成巨大的壓力。由于互聯(lián)網(wǎng)中的網(wǎng)絡(luò)帶寬資源有限，網(wǎng)絡(luò)帶寬成為了系統(tǒng)的性能瓶頸[9]。

數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時(shí)間占總修復(fù)時(shí)間的94%[10]，數(shù)據(jù)節(jié)點(diǎn)發(fā)生故障后如何實(shí)現(xiàn)快速恢復(fù)是目前糾刪碼研究領(lǐng)域的一個(gè)重點(diǎn)。一方面可以通過減少總的網(wǎng)絡(luò)帶寬從而減少對網(wǎng)絡(luò)資源的占用[11]，另一方面是消除系統(tǒng)中的網(wǎng)絡(luò)性能瓶頸[12]。例如：糾刪碼修復(fù)流水線(RP)[13]通過改變網(wǎng)絡(luò)傳輸結(jié)構(gòu)，消除瓶頸節(jié)點(diǎn)，減少了90%的修復(fù)時(shí)間。但是，現(xiàn)有的糾刪碼修復(fù)流水線中存在修復(fù)工作部署不均，節(jié)點(diǎn)負(fù)載不夠均衡的問題。

為了均衡節(jié)點(diǎn)的負(fù)載，提高糾刪碼的修復(fù)性能，本文提出了一種網(wǎng)絡(luò)結(jié)構(gòu)Optns。Optns中多構(gòu)造了一條流水線路徑。理論分析及實(shí)驗(yàn)結(jié)果表明，與RP原始網(wǎng)絡(luò)結(jié)構(gòu)相比，Optns不僅以O(shè)(1)的時(shí)間完成了故障修復(fù)，而且所有幫助(參與修復(fù)的)節(jié)點(diǎn)均攤了修復(fù)過程中的工作量，具有最優(yōu)的負(fù)載均衡性。

1 相關(guān)理論基礎(chǔ)

1.1 問題定義

首先，將本文的相關(guān)參數(shù)統(tǒng)一羅列成表，具體見表1。

表1 參數(shù)

其次，給出本文相關(guān)的性質(zhì)和術(shù)語定義。

性質(zhì)1 (最大距離可分離碼)：最大距離可分離(maximum distance separable，MDS)碼通常用于通信和存儲(chǔ)系統(tǒng)中的各種應(yīng)用。一個(gè)(k,r)-MDS碼取一個(gè)大小為B的文件，將其分成大小相等的k個(gè)塊后編碼，生成r個(gè)檢驗(yàn)塊，形成一個(gè)糾刪碼組(共包含n個(gè)編碼塊)，分別存放在n個(gè)獨(dú)立的節(jié)點(diǎn)上。讀取其中任意k塊，通過譯碼運(yùn)算可修復(fù)一個(gè)故障數(shù)據(jù)塊，編碼后的系統(tǒng)最多可容忍任意r個(gè)原始數(shù)據(jù)塊或校驗(yàn)塊發(fā)生故障?？芍?/p>

n=k+r

(1)

定義1 數(shù)據(jù)切片：將數(shù)據(jù)文件切分為固定、更小的單位，稱為數(shù)據(jù)切片。

定義2 時(shí)間片段：將修復(fù)過程劃分時(shí)間片段，每個(gè)時(shí)間片段內(nèi)只有一個(gè)數(shù)據(jù)切片可以通過網(wǎng)絡(luò)鏈路傳輸。

定義3 節(jié)點(diǎn)負(fù)載：系統(tǒng)修復(fù)一個(gè)故障時(shí)，節(jié)點(diǎn)所承擔(dān)的工作量。

1.2 糾刪碼修復(fù)流水線原理

修復(fù)流水線基于最典型的糾刪碼算法——里德-所羅門碼(Reed-Solomon，RS)。RS碼是一類MDS編碼，修復(fù)任何一個(gè)故障時(shí)的代價(jià)為k，即需要從其它磁盤上讀取，并在網(wǎng)絡(luò)上傳輸k份數(shù)據(jù)。互聯(lián)網(wǎng)中節(jié)點(diǎn)的網(wǎng)絡(luò)帶寬比較低時(shí)會(huì)造成修復(fù)擁塞，網(wǎng)絡(luò)資源成為了系統(tǒng)的性能瓶頸。

如圖1(a)所示，糾刪碼常規(guī)修復(fù)中，幫助節(jié)點(diǎn)(用集合N={Ni|1≤i≤k}表示)串行將本地的數(shù)據(jù)發(fā)送給代替(代替故障節(jié)點(diǎn)的新)節(jié)點(diǎn)R，R收集齊數(shù)據(jù)后做譯碼運(yùn)算。k個(gè)幫助節(jié)點(diǎn)競爭R的網(wǎng)絡(luò)資源導(dǎo)致鏈路擁塞。并且，R節(jié)點(diǎn)需要做全部的運(yùn)算，工作繁重，容易成為系統(tǒng)的瓶頸節(jié)點(diǎn)。因此，采用糾刪碼修復(fù)流水線分而治之，通過改變傳輸結(jié)構(gòu)的方式重新分配網(wǎng)絡(luò)流量，將譯碼運(yùn)算分散到各個(gè)幫助節(jié)點(diǎn)，RP拓?fù)浣Y(jié)構(gòu)如圖1(b)所示。假設(shè)a={a1，a2,…,ak}為譯碼系數(shù)，b={b1，b2,…,bk}為幫助節(jié)點(diǎn)上的數(shù)據(jù)。則修復(fù)流水線的工作流程為：N1發(fā)送數(shù)據(jù)a1b1，N2將本地的數(shù)據(jù)乘以相應(yīng)的系數(shù)，與從N1接收的數(shù)據(jù)進(jìn)行數(shù)據(jù)組合，然后將計(jì)算后的數(shù)據(jù)(a1b1⊕a2b2)轉(zhuǎn)發(fā)給N3(“⊕”表示二元域上的加運(yùn)算，即異或運(yùn)算)。幫助節(jié)點(diǎn)間發(fā)送的數(shù)據(jù)量大小是相同的，因?yàn)楫惢蜻\(yùn)算不會(huì)改變數(shù)據(jù)塊的大小。以此類推，直到將恢復(fù)后的數(shù)據(jù)發(fā)送給一個(gè)新的節(jié)點(diǎn)R。此時(shí)，系統(tǒng)中不存在瓶頸節(jié)點(diǎn)，可顯著減少修復(fù)時(shí)間。

圖1 常規(guī)修復(fù)vs修復(fù)流水線拓?fù)?/p>

從圖1(b)的拓?fù)鋱D抽象出RP的網(wǎng)絡(luò)結(jié)構(gòu)Cyclic[13]，如圖2(a)所示，Cyclic構(gòu)造了多條不同的流水線路徑，將數(shù)據(jù)文件切分為更小的單位后分組進(jìn)行修復(fù)。Cyclic修復(fù)流程如下：

t1時(shí)刻，第一組流水線啟動(dòng)，N1、N2、N3同時(shí)開始發(fā)送數(shù)據(jù)。

t2、t3時(shí)刻，N1～N4作為中間節(jié)點(diǎn)，接收、計(jì)算并轉(zhuǎn)發(fā)數(shù)據(jù)給下一個(gè)節(jié)點(diǎn)。

t4時(shí)刻，第一組流水線負(fù)責(zé)的數(shù)據(jù)修復(fù)完成。

t5時(shí)刻，第二組流水線啟動(dòng)，同時(shí)N4將第一組中修復(fù)完的第一個(gè)數(shù)據(jù)切片發(fā)送給R。

t6時(shí)刻，第二組的修復(fù)流水線繼續(xù)工作，N1也將在第一組中修復(fù)好的第二個(gè)數(shù)據(jù)切片發(fā)送給R。

圖2 網(wǎng)絡(luò)結(jié)構(gòu)(k=4，m=2，s=6)

在相同的模式下持續(xù)修復(fù)，直到整個(gè)修復(fù)工作完成。分布式存儲(chǔ)系統(tǒng)中，R作為代替節(jié)點(diǎn)比一般的節(jié)點(diǎn)分布的更遠(yuǎn)，常位于網(wǎng)絡(luò)邊緣，因此與R的交互受限更多。幫助節(jié)點(diǎn)循環(huán)參與修復(fù)中的各項(xiàng)工作，例如N1在t1時(shí)刻發(fā)送數(shù)據(jù)；t3時(shí)刻接收、計(jì)算、轉(zhuǎn)發(fā)數(shù)據(jù)；t6時(shí)刻將數(shù)據(jù)發(fā)送給R，參與了每一項(xiàng)修復(fù)任務(wù)。但是可以看出，Cyclic存在缺陷：N3節(jié)點(diǎn)沒有與R交互，即沒有承擔(dān)工作量最大的修復(fù)任務(wù)，這一部分工作由部分幫助節(jié)點(diǎn)承擔(dān)，導(dǎo)致負(fù)載不夠均衡。

2 Optns網(wǎng)絡(luò)結(jié)構(gòu)

在Cyclic的基礎(chǔ)上進(jìn)行改進(jìn)，設(shè)計(jì)了Optns網(wǎng)絡(luò)結(jié)構(gòu)，它能完全均衡幫助節(jié)點(diǎn)間的負(fù)載，使幫助節(jié)點(diǎn)間的負(fù)載相同。Optns仍保持糾刪碼修復(fù)流水線的基本原理，它的核心思想在于：為了讓所有的幫助節(jié)點(diǎn)均攤負(fù)載，每個(gè)幫助節(jié)點(diǎn)都必須參與所有的修復(fù)任務(wù)。因此，在選定k個(gè)幫助節(jié)點(diǎn)后，通過空置時(shí)間片段的方法構(gòu)造更多的流水線修復(fù)路徑。Optns的構(gòu)造步驟如下：

(1)當(dāng)系統(tǒng)發(fā)生故障時(shí)，從剩余的可用節(jié)點(diǎn)中任意選取k個(gè)節(jié)點(diǎn)用于修復(fù)。

(2)將數(shù)據(jù)文件切分為s個(gè)大小相等的數(shù)據(jù)切片。

(3)構(gòu)造不同的修復(fù)流水線路徑。k個(gè)幫助節(jié)點(diǎn)依次排列，每次將幫助節(jié)點(diǎn)循環(huán)左移一位，k個(gè)幫助節(jié)點(diǎn)可以構(gòu)造k條不同的路徑。

(4)分組并行修復(fù)。每一條流水線上有(k-1)個(gè)時(shí)間片段，可供(k-1)個(gè)節(jié)點(diǎn)將數(shù)據(jù)傳輸給R，即每一組修復(fù)中可以并行調(diào)度(k-1)條不同的流水線。假設(shè)修復(fù)完一個(gè)故障所需的時(shí)間為t，則一個(gè)時(shí)間片段耗費(fèi)的時(shí)間為t/s。

(5)空置時(shí)間片段。第一組流水線傳輸修復(fù)完數(shù)據(jù)后，Nk節(jié)點(diǎn)推遲第一個(gè)數(shù)據(jù)切片發(fā)送給R的啟動(dòng)時(shí)間，Nk在tk+1時(shí)刻作為第二組流水線的啟動(dòng)節(jié)點(diǎn)。此時(shí)，k條不同的線性路徑都調(diào)度了，共有k個(gè)節(jié)點(diǎn)與R交互，負(fù)載最重的修復(fù)任務(wù)均勻分配給了所有幫助節(jié)點(diǎn)，其它的工作也隨之均勻分配。

Optns結(jié)構(gòu)如圖2(b)所示，空白區(qū)塊表示空置的時(shí)間片段。Optns的修復(fù)過程與Cyclic類似：

t1時(shí)刻，第一組的流水線啟動(dòng)。

t2、t3時(shí)刻，傳輸數(shù)據(jù)進(jìn)行修復(fù)。

t4時(shí)刻，第一組負(fù)責(zé)的數(shù)據(jù)修復(fù)完成，但還沒有把修復(fù)完成的數(shù)據(jù)傳輸給R。

t5時(shí)刻，第二組啟動(dòng)，N4開始工作，給N1傳輸數(shù)據(jù)。如果N4同時(shí)發(fā)送數(shù)據(jù)給R，節(jié)點(diǎn)將被重載，出口帶寬資源被競爭，可能導(dǎo)致?lián)砣?。因此，空置一個(gè)時(shí)間片段，推遲給R發(fā)送數(shù)據(jù)的時(shí)間。

t6時(shí)刻，N4將數(shù)據(jù)發(fā)送給R。以N4為啟動(dòng)節(jié)點(diǎn)的流水線的終端節(jié)點(diǎn)為N3，因此，所有的幫助節(jié)點(diǎn)都會(huì)參與每一項(xiàng)修復(fù)任務(wù)。

t6時(shí)刻及以后，幫助節(jié)點(diǎn)全部并行，系統(tǒng)中不再有空閑的幫助節(jié)點(diǎn)，修復(fù)效率達(dá)到最高。

對比圖2(a)和圖2(b)，Optns結(jié)構(gòu)與Cyclic結(jié)構(gòu)最大的區(qū)別在于，Cyclic只構(gòu)造了(k-1)條不同的流水線路徑，剩余一個(gè)幫助節(jié)點(diǎn)沒有參與和請求節(jié)點(diǎn)交互的修復(fù)任務(wù)，節(jié)點(diǎn)的負(fù)載不夠均衡。而Optns構(gòu)造了k條不同的流水線，所有幫助節(jié)點(diǎn)都會(huì)循環(huán)參與每一項(xiàng)子任務(wù)，十分均衡。

3 理論分析

為了評價(jià)Optns的性能，以節(jié)點(diǎn)負(fù)載L和修復(fù)時(shí)間T作為評判標(biāo)準(zhǔn)。

3.1 計(jì)算節(jié)點(diǎn)負(fù)載算法

由于與請求節(jié)點(diǎn)的交互工作量最大，節(jié)點(diǎn)負(fù)載不均衡的瓶頸集中在此，因此只分析幫助節(jié)點(diǎn)對這一部分工作量的攤分情況。經(jīng)研究后，提出通用算法1，計(jì)算節(jié)點(diǎn)的負(fù)載，具體步驟如下。

算法1：計(jì)算節(jié)點(diǎn)負(fù)載

輸入：B、C、α； //B表示發(fā)生故障的數(shù)據(jù)塊大小，C表示單位數(shù)據(jù)量，α表示修復(fù)單位數(shù)據(jù)量，與R交互時(shí)的工作量。

輸出：節(jié)點(diǎn)負(fù)載L。

過程：

(1)P=NULL; //P表示與R交互的幫助節(jié)點(diǎn)集合；

(2)FORi=1 tokin N

IFNi與R交互 and Ni不存在P中THEN

把Ni加入集合P

ENDIF

ENDFOR

(3)d=crad(P)；//crad()表示集合元素的個(gè)數(shù)；

(5) 輸出節(jié)點(diǎn)負(fù)載L，算法停止。

3.2 計(jì)算修復(fù)時(shí)間

糾刪碼系統(tǒng)的故障修復(fù)時(shí)間實(shí)際上由幾部分組成，計(jì)算公式如下

Trepair=TI/O+Ttrans+Tcompute

(2)

其中，Trepair表示總的修復(fù)時(shí)間，TI/O表示磁盤I/O時(shí)間，Ttrans表示數(shù)據(jù)傳輸時(shí)間，Tcompute表示譯碼計(jì)算時(shí)間。數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時(shí)間占比高達(dá)94%，為了避免其它因素的干擾，本算法中忽略磁盤的I/O時(shí)間和計(jì)算時(shí)間，令

TI/O=0，Tcompute=0

(3)

根據(jù)式(2)、式(3)，修復(fù)時(shí)間Trepair=Ttrans?；诖耍岢鐾ㄓ盟惴?，計(jì)算修復(fù)時(shí)間，具體步驟如下。

算法2：計(jì)算修復(fù)時(shí)間

輸入：s、k、t; //s表示數(shù)據(jù)切片的個(gè)數(shù)，k表示幫助節(jié)點(diǎn)的個(gè)數(shù)，t表示修復(fù)一個(gè)數(shù)據(jù)塊故障的時(shí)間。

輸出：修復(fù)時(shí)間T。

過程：

(2)FORi=1 to (g-1)

tg=(k-1) // 每一條流水線消耗的時(shí)間片段數(shù)量。

ENDFOR

(3)ttrans=s；//將所有修復(fù)完的數(shù)據(jù)切片依次傳輸給R消耗的時(shí)間片段。

(5) 總的修復(fù)時(shí)間片ttotal=tg+tm=(k-1)+s；

(6) 修復(fù)一個(gè)數(shù)據(jù)塊故障的時(shí)間為t，則一個(gè)時(shí)間片段消耗的時(shí)間為th=t/s；

(7) 輸出總的修復(fù)時(shí)間T=ttotal×th，算法停止。

3.3 理論分析

3.3.1 節(jié)點(diǎn)負(fù)載

Cyclic有(k-1)條不同的流水線路徑，即有(k-1)個(gè)幫助節(jié)點(diǎn)與R交互，根據(jù)算法1，節(jié)點(diǎn)的負(fù)載為LCyclic=αB/(k-1)C。同理，Optns有k個(gè)幫助節(jié)點(diǎn)與R交互，負(fù)載LOptns=αB/kC。顯然LOptns

ΔL=(LCyclic-LOptns)/LCyclic×100%=1/k

(4)

因此，Optns減少了幫助節(jié)點(diǎn)對工作量最大的修復(fù)任務(wù)的分?jǐn)偭?，均衡了?jié)點(diǎn)的負(fù)載。

3.3.2 修復(fù)時(shí)間

根據(jù)通用算法2，原始的網(wǎng)絡(luò)結(jié)構(gòu)Cyclic的修復(fù)時(shí)間TCyclic= (k-1 +s)×(t/s)=[1+(k-1)/s]t。Optns結(jié)構(gòu)中空置了一個(gè)時(shí)間片段，需要加以計(jì)算，修復(fù)時(shí)間TOptns=(ttotal+1)th=(1+k/s)t。Cyclic與Optns的時(shí)間差

ΔT=TOptns-TCyclic=t/s

(5)

相比Cyclic，Optns雖然增加了一個(gè)空閑的時(shí)間片段，但并不會(huì)對整體的修復(fù)時(shí)間造成任何消極影響，時(shí)間復(fù)雜度為O(1)。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)步驟

(1)搭建實(shí)驗(yàn)環(huán)境。在NS-3(network simulator version 3)運(yùn)行環(huán)境中進(jìn)行程序的仿真工作。根據(jù)網(wǎng)絡(luò)拓?fù)淠Ｐ痛罱▽?shí)驗(yàn)環(huán)境，如圖3所示，在NS-3中創(chuàng)建一個(gè)節(jié)點(diǎn)作為路由器，n個(gè)節(jié)點(diǎn)作為實(shí)際的存儲(chǔ)節(jié)點(diǎn)，并在網(wǎng)絡(luò)鏈路上配置帶寬為1 Gb/s、時(shí)延為1 ms，IP地址為10.0.0.x等。這(n+1)個(gè)節(jié)點(diǎn)可以模擬分布式存儲(chǔ)環(huán)境，進(jìn)行實(shí)驗(yàn)測試。

圖3 網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

(2)以節(jié)點(diǎn)負(fù)載和修復(fù)時(shí)間作為實(shí)驗(yàn)指標(biāo)，發(fā)生故障的數(shù)據(jù)塊大小、(k,r)編碼參數(shù)為變化條件，測定Cyclic和Optns相應(yīng)的數(shù)據(jù)并繪圖。

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

圖4(a)、圖4(b)分別表示了節(jié)點(diǎn)負(fù)載和修復(fù)時(shí)間隨數(shù)據(jù)塊大小改變的變化。圖4(c)、圖4(d)分別表示了節(jié)點(diǎn)負(fù)載和修復(fù)時(shí)間隨(k,r)編碼參數(shù)改變的變化。

設(shè)定編碼參數(shù)(k,r)為(6,3)，單位數(shù)據(jù)量為2 MB，切片大小為32 KB，故障數(shù)據(jù)塊的大小從8 MB變化到128 MB。從圖4(a)可以看出，節(jié)點(diǎn)負(fù)載與數(shù)據(jù)塊的大小成正比，修復(fù)的數(shù)據(jù)量越多，節(jié)點(diǎn)的負(fù)載越大。相比Cyclic，Optns的負(fù)載約減少16.7%，并隨著數(shù)據(jù)塊的增大，Optns減少節(jié)點(diǎn)負(fù)載的優(yōu)勢越大。從圖4(b)可以看出，修復(fù)時(shí)間與數(shù)據(jù)塊的大小成正比，修復(fù)的數(shù)據(jù)量越多，修復(fù)時(shí)間越長。數(shù)據(jù)切片的大小固定后，隨著數(shù)據(jù)塊的增大，切片個(gè)數(shù)增加，Optns與Cyclic的修復(fù)時(shí)間趨于相等。

圖4 實(shí)驗(yàn)結(jié)果

設(shè)定故障數(shù)據(jù)塊大小為64 MB，單位數(shù)據(jù)量為2 MB，切片數(shù)s=2048。從圖4(c)可以看出，節(jié)點(diǎn)負(fù)載與k的取值相關(guān)，隨著k的值從4增加到12，Optns減少負(fù)載的比例從25%降低到8%，減少的比例與k的大小成反比。從圖4(d)可以看出，修復(fù)時(shí)間與k的取值相關(guān)，但是k的取值不會(huì)明顯影響修復(fù)時(shí)間，與修復(fù)時(shí)間最直接相關(guān)的是網(wǎng)絡(luò)帶寬。相比Cyclic，Optns設(shè)置空白的時(shí)間片段后，增加的修復(fù)時(shí)間在0.01 s左右，從總的修復(fù)時(shí)間來看，毫秒級的差異可以忽略不計(jì)。

4.3 評 價(jià)

Optns的性能主要與幫助節(jié)點(diǎn)個(gè)數(shù)k相關(guān)，隨著k的增大，Optns的性能優(yōu)勢逐漸減小。但是，在實(shí)際的系統(tǒng)中，為了減少修復(fù)代價(jià)，會(huì)避免選用k值過大的糾刪碼方案。因此，可以使用Optns作為糾刪碼修復(fù)流水線新的網(wǎng)絡(luò)傳輸結(jié)構(gòu)。

5 結(jié)束語

為了解決糾刪碼修復(fù)流水線中節(jié)點(diǎn)負(fù)載不夠均衡的問題，本文提出了改進(jìn)的網(wǎng)絡(luò)結(jié)構(gòu)Optns。相比原始網(wǎng)絡(luò)結(jié)構(gòu)Cyclic，Optns構(gòu)造了更多的流水線路徑，平衡了節(jié)點(diǎn)的負(fù)載，同時(shí)，Optns以O(shè)(1)的時(shí)間完成了修復(fù)，保持了修復(fù)流水線優(yōu)秀的修復(fù)效率。由于所有的幫助節(jié)點(diǎn)均衡的攤分了所有的修復(fù)任務(wù)，Optns具有最優(yōu)的負(fù)載均衡性。

本文基于糾刪碼修復(fù)流水線的理論框架，只改變了流水線路徑，編碼方案沒有改變，不影響存儲(chǔ)效率、容錯(cuò)率、網(wǎng)絡(luò)帶寬、計(jì)算復(fù)雜度等性能，故沒有引入新的修復(fù)代價(jià)。