具有最優負載均衡性的糾刪碼修復流水線

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

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

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

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

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

1 相關理論基礎

1.1 問題定義

首先，將本文的相關參數統一羅列成表，具體見表1。

表1 參數

其次，給出本文相關的性質和術語定義。

性質1 (最大距離可分離碼)：最大距離可分離(maximum distance separable，MDS)碼通常用于通信和存儲系統中的各種應用。一個(k,r)-MDS碼取一個大小為B的文件，將其分成大小相等的k個塊后編碼，生成r個檢驗塊，形成一個糾刪碼組(共包含n個編碼塊)，分別存放在n個獨立的節點上。讀取其中任意k塊，通過譯碼運算可修復一個故障數據塊，編碼后的系統最多可容忍任意r個原始數據塊或校驗塊發生故障。可知

n=k+r

(1)

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

定義2 時間片段：將修復過程劃分時間片段，每個時間片段內只有一個數據切片可以通過網絡鏈路傳輸。

定義3 節點負載：系統修復一個故障時，節點所承擔的工作量。

1.2 糾刪碼修復流水線原理

修復流水線基于最典型的糾刪碼算法——里德-所羅門碼(Reed-Solomon，RS)。RS碼是一類MDS編碼，修復任何一個故障時的代價為k，即需要從其它磁盤上讀取，并在網絡上傳輸k份數據。互聯網中節點的網絡帶寬比較低時會造成修復擁塞，網絡資源成為了系統的性能瓶頸。

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

圖1 常規修復vs修復流水線拓撲

從圖1(b)的拓撲圖抽象出RP的網絡結構Cyclic[13]，如圖2(a)所示，Cyclic構造了多條不同的流水線路徑，將數據文件切分為更小的單位后分組進行修復。Cyclic修復流程如下：

t1時刻，第一組流水線啟動，N1、N2、N3同時開始發送數據。

t2、t3時刻，N1～N4作為中間節點，接收、計算并轉發數據給下一個節點。

t4時刻，第一組流水線負責的數據修復完成。

t5時刻，第二組流水線啟動，同時N4將第一組中修復完的第一個數據切片發送給R。

t6時刻，第二組的修復流水線繼續工作，N1也將在第一組中修復好的第二個數據切片發送給R。

圖2 網絡結構(k=4，m=2，s=6)

在相同的模式下持續修復，直到整個修復工作完成。分布式存儲系統中，R作為代替節點比一般的節點分布的更遠，常位于網絡邊緣，因此與R的交互受限更多。幫助節點循環參與修復中的各項工作，例如N1在t1時刻發送數據；t3時刻接收、計算、轉發數據；t6時刻將數據發送給R，參與了每一項修復任務。但是可以看出，Cyclic存在缺陷：N3節點沒有與R交互，即沒有承擔工作量最大的修復任務，這一部分工作由部分幫助節點承擔，導致負載不夠均衡。

2 Optns網絡結構

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

(1)當系統發生故障時，從剩余的可用節點中任意選取k個節點用于修復。

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

(3)構造不同的修復流水線路徑。k個幫助節點依次排列，每次將幫助節點循環左移一位，k個幫助節點可以構造k條不同的路徑。

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

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

Optns結構如圖2(b)所示，空白區塊表示空置的時間片段。Optns的修復過程與Cyclic類似：

t1時刻，第一組的流水線啟動。

t2、t3時刻，傳輸數據進行修復。

t4時刻，第一組負責的數據修復完成，但還沒有把修復完成的數據傳輸給R。

t5時刻，第二組啟動，N4開始工作，給N1傳輸數據。如果N4同時發送數據給R，節點將被重載，出口帶寬資源被競爭，可能導致擁塞。因此，空置一個時間片段，推遲給R發送數據的時間。

t6時刻，N4將數據發送給R。以N4為啟動節點的流水線的終端節點為N3，因此，所有的幫助節點都會參與每一項修復任務。

t6時刻及以后，幫助節點全部并行，系統中不再有空閑的幫助節點，修復效率達到最高。

對比圖2(a)和圖2(b)，Optns結構與Cyclic結構最大的區別在于，Cyclic只構造了(k-1)條不同的流水線路徑，剩余一個幫助節點沒有參與和請求節點交互的修復任務，節點的負載不夠均衡。而Optns構造了k條不同的流水線，所有幫助節點都會循環參與每一項子任務，十分均衡。

3 理論分析

為了評價Optns的性能，以節點負載L和修復時間T作為評判標準。

3.1 計算節點負載算法

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

算法1：計算節點負載

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

輸出：節點負載L。

過程：

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

(2)FORi=1 tokin N

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

把Ni加入集合P

ENDIF

ENDFOR

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

(5) 輸出節點負載L，算法停止。

3.2 計算修復時間

糾刪碼系統的故障修復時間實際上由幾部分組成，計算公式如下

Trepair=TI/O+Ttrans+Tcompute

(2)

其中，Trepair表示總的修復時間，TI/O表示磁盤I/O時間，Ttrans表示數據傳輸時間，Tcompute表示譯碼計算時間。數據在網絡中的傳輸時間占比高達94%，為了避免其它因素的干擾，本算法中忽略磁盤的I/O時間和計算時間，令

TI/O=0，Tcompute=0

(3)

根據式(2)、式(3)，修復時間Trepair=Ttrans。基于此，提出通用算法2，計算修復時間，具體步驟如下。

算法2：計算修復時間

輸入：s、k、t; //s表示數據切片的個數，k表示幫助節點的個數，t表示修復一個數據塊故障的時間。

輸出：修復時間T。

過程：

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

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

ENDFOR

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

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

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

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

3.3 理論分析

3.3.1 節點負載

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

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

(4)

因此，Optns減少了幫助節點對工作量最大的修復任務的分攤量，均衡了節點的負載。

3.3.2 修復時間

根據通用算法2，原始的網絡結構Cyclic的修復時間TCyclic= (k-1 +s)×(t/s)=[1+(k-1)/s]t。Optns結構中空置了一個時間片段，需要加以計算，修復時間TOptns=(ttotal+1)th=(1+k/s)t。Cyclic與Optns的時間差

ΔT=TOptns-TCyclic=t/s

(5)

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

4 實驗結果及分析

4.1 實驗步驟

(1)搭建實驗環境。在NS-3(network simulator version 3)運行環境中進行程序的仿真工作。根據網絡拓撲模型搭建實驗環境，如圖3所示，在NS-3中創建一個節點作為路由器，n個節點作為實際的存儲節點，并在網絡鏈路上配置帶寬為1 Gb/s、時延為1 ms，IP地址為10.0.0.x等。這(n+1)個節點可以模擬分布式存儲環境，進行實驗測試。

圖3 網絡拓撲模型

(2)以節點負載和修復時間作為實驗指標，發生故障的數據塊大小、(k,r)編碼參數為變化條件，測定Cyclic和Optns相應的數據并繪圖。

4.2 實驗結果

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

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

圖4 實驗結果

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

4.3 評 價

Optns的性能主要與幫助節點個數k相關，隨著k的增大，Optns的性能優勢逐漸減小。但是，在實際的系統中，為了減少修復代價，會避免選用k值過大的糾刪碼方案。因此，可以使用Optns作為糾刪碼修復流水線新的網絡傳輸結構。

5 結束語

為了解決糾刪碼修復流水線中節點負載不夠均衡的問題，本文提出了改進的網絡結構Optns。相比原始網絡結構Cyclic，Optns構造了更多的流水線路徑，平衡了節點的負載，同時，Optns以O(1)的時間完成了修復，保持了修復流水線優秀的修復效率。由于所有的幫助節點均衡的攤分了所有的修復任務，Optns具有最優的負載均衡性。

本文基于糾刪碼修復流水線的理論框架，只改變了流水線路徑，編碼方案沒有改變，不影響存儲效率、容錯率、網絡帶寬、計算復雜度等性能，故沒有引入新的修復代價。