面向糾刪碼存儲集群的節點并發重構

黃建忠　曹　強　黃思倜　謝長生

(武漢光電國家實驗室(華中科技大學)　武漢　430074)

?

面向糾刪碼存儲集群的節點并發重構

黃建忠曹強黃思倜謝長生

(武漢光電國家實驗室(華中科技大學)武漢430074)

(hjzh@hust.edu.cn)

糾刪碼存儲集群的一個關鍵設計目標是降低重構IO所引起的網絡流量，因為降低網絡流量有助于縮短重構時間，進而提高可靠性. 針對2個或多個失效節點并發重構這一研究話題，提出一種交叉式重構方案(interleaved reconstruction scheme, IRS).所有替換節點能協同、并行地重構所有失效分塊.通過對現有集中式重構方案(centralized reconstruction scheme, CRec)和分散式重構方案(decentralized reconstruction scheme, DRec)的IO流進行分析，分析發現CRec中存儲管理器和DRec中替換節點是重構性能的瓶頸. 針對此，IRS從2個方面進行改進：1)替換節點充當重構節點進行并行式重構，消除CRec中管理器這一重構瓶頸；2)利用糾刪碼的編碼結構特性，所有替換節點協同地重構所有失效分塊，確保重構時只傳輸一次所需存活分塊.在Reed-Solomon碼存儲集群上實現了上述3個重構方案，并用真實IO trace進行對比測試. 實驗結果表明：當糾刪碼存儲集群的編碼參數為k=9和r=3時，IRS方案的雙節點重構性能是其他2種重構方案的1.63倍；而3節點重構性能是其他2種重構方案的2.14倍.

糾刪編碼；集群存儲；存儲可靠性；節點重構；交叉式重構

分布式存儲具有很高的性價比和擴展性，已成為大規模數據中心的主流存儲結構.然而，分布式存儲系統包含大量存儲節點，節點失效是經常性事件.為了避免數據丟失，通常采用副本進行容錯.對于PB級以內的數據集而言，3副本方案所增加的2倍存儲容量不是太大的問題，但對于PB級、EB級、ZB級存儲系統來說，多副本方案的存儲開銷對硬件成本和運營開支產生巨大壓力.而糾刪編碼具有高容錯能力和低存儲空間開銷的優點[1]，已經成為大規模存儲的基本容錯方案.

近年來糾刪碼存儲研究得到學術界和工業界的廣泛關注.國際學術會議(如USENIX FAST，USENIX ATC，IFIP DSN，ACM SOSP等)將糾刪碼相關研究列為征文主題；同時，出于存儲成本和運營開支考慮，一些知名數據中心或云存儲系統已大量采用糾刪碼集群存儲方案來存放低訪問頻度數據(即冷數據)，典型案例包括Google第2代文件系統GFS II[2]、微軟Azure云存儲系統[3]、Facebook部署的HDFS-RAID[4]存儲集群.

存儲可靠性與修復速度密切相關，對于糾刪碼存儲集群來說，當節點失效時，加速節點恢復是非常重要的[5].研究表明，容r錯的糾刪碼集群存儲中，系統MTTDL與節點恢復時間的r次方成反比[6].與此同時，為2個或2個以上節點的并發恢復進行重構優化也是非常必要的：一方面，最近研究表明小型集群系統同一時間發生雙節點失效的累計分布函數值CDF大于30%[7]；另一方面，為了降低恢復成本，多容錯系統會采取“延期修復(delayed repair)”策略[8]，即，單節點失效時系統并不即刻啟動重構，直至2個或2個以上節點失效時才啟動重構過程，避免節點短時失效時導致不必要的頻繁重構.

本文對糾刪碼存儲集群下2個及以上并發節點失效重構過程進行優化.通過分析現有重構方案可知，集中式重構方案中管理器節點是重構性能瓶頸；而分散式重構方案中每個替換節點獨立請求存活分塊，造成同一存活分塊的多次傳輸.本文提出一種交叉式重構方案(interleaved reconstruction scheme， IRS)，多個替換節點進行協同重構，并通過互傳已重構分塊來降低重構流量.

1　背景與相關工作

1.1背景

數據中心通常按容錯組方式來組織節點，9～20個節點構成一個容錯組，容錯組內節點按特定糾刪碼方案來組織數據放置，構成一個糾刪碼存儲集群[9].以里德所羅門碼(Reed Solomon， RS)集群存儲為例，文件先分成k個數據分塊{D1,1,D1,2,…,D1,k}，并按照式(1)所示的冗余矩陣計算得到r個校驗分塊{P1,1,P1,2,…,P1,r}，每個校驗分塊是k個數據分塊的線性組合；k個數據分塊及其相應r個校驗分塊獨立地存放到k+r個存儲節點{SN1,SN2,…,SNk+r}上，從而得到一種RS(k+r,k)碼存儲集群.根據RS碼的編碼特性，該存儲集群可容許r個任意節點的同時失效.

(1)

為了避免校驗分塊的更新訪問瓶頸，不同條帶上的數據分塊和校驗分塊是分散存儲.圖1以RS(6,4)碼集群存儲為例，與RAID5中分散式校驗塊布局相似，條帶1中第1個校驗分塊P1,1放置在節點SN5上，而條帶2中第1個校驗分塊P2,1放置在節點SN4上.

Fig. 1　Data placement of RS(6,4)-coded storage clusters.圖1　RS(6,4)碼存儲集群的數據放置

為便于描述，本文假設條帶總數為N，所有條帶都分布在k+r個節點上，并假設重構方案中所有條帶采用相同數據布局，即，條帶row的k個數據分塊{Drow,1,Drow,2,…,Drow,k}和r個校驗分塊{Prow,1,Prow,2,…,Prow,r}分別存放在節點{SN1,SN2,…,SNk,SNk+1,SNk+2,…,SNk+r}上.

在RS(k+r,k)碼集群存儲中，當失效節點數f

(2)

(3)

對式(2)兩邊同時乘以α2,2，得到式(4)：

(4)

結合式(3)和式(4)，可以推導出式(5) ：

(5)

同理可以推導出式(6)：

(6)

根據式(5)和式(6)可知，利用同一row上的k個存活分塊{Prow,1,Prow,2,Drow,3,…,Drow,k}可以計算出失效數據分塊Drow,1和Drow,2.

1.2相關工作

陣列碼是一種特殊的糾刪碼，其采用簡單高效的異或編碼運算.對于磁盤陣列中的磁盤失效重構，主要有以下4類優化方法：1) 提高重構并行性，如，DOR讓每個存活磁盤都參與重構[10]；2) 減少用戶IO的干擾，如，WorkOut為了讓一個降級RAID將其所有存儲資源用于重構，將所有寫請求和熱度高的讀請求外包給一個代理RAID集[11]；3) 優化解碼操作，如，Hafner等人[12]提出了一種具體的混合重構算法來減少異或操作，降低計算開銷以改善解碼效率；4) 減少對存活磁盤的讀取次數，如，當容雙錯的RDP磁盤陣列出現單盤失效時，RDOR通過選擇最低重構路徑，最小化對存活磁盤的讀請求數量[13].

磁盤陣列的故障盤重構只涉及磁盤開銷和異或運算開銷[14].相對于陣列重構，糾刪碼存儲集群的失效節點恢復顯得更加復雜，因為存儲集群是通過網絡互連，節點重構方案需要考慮磁盤訪問、CPU計算和網絡傳輸3方面因素.其中，網絡傳輸往往是節點重構性能的決定性因素.對于糾刪碼集群存儲下的重構優化，目前存在下列4類重構優化方案：

1) 降低校驗組規模.為了計算出失效分塊，重構節點需要獲取k個存活分塊，k值越小意味著需要傳輸的數據量越低.為此，微軟Azure云存儲系統、Facebook的存儲集群同時采用全局校驗組和局部校驗組(具體方案分別稱為局部重構碼LRC[3]和局部修復碼LRCs[15])，分別為所有數據分塊和部分數據分塊生成全局校驗分塊和局部校驗分塊.重構時可以從局部校驗組讀取存活數據，相對全局校驗組，該方法減少重構所需存活分塊的讀取數量.這種優化方法的代價是需要占用額外存儲空間.

3) 利用修復局部性.Facebook下Hitchhiker系統采用了PiggybackedRS編碼[20]，PiggybackedRS主要為單一節點失效恢復而優化，該編碼利用了修復局部性，減少了恢復時所關聯的存活節點數目，以加速重構過程.

糾刪碼存儲重構優化主要圍繞編碼和存儲2個方面展開：1)從編碼角度，設計新的糾編碼；2)從存儲角度，對重構IO進行調度和控制. 表1列出上述所提的幾種典型重構優化方案. 本文從IO調度角度對糾刪碼集群存儲進行重構優化.

Table 1　Reconstruction Schemes for Erasured-Coded Storage

本文IRS和上述“增加局部校驗組”、“基于再生碼的重構帶寬優化”和“利用修復局部性”3種重構方案都是以“降低網絡中數據傳輸量”為目標導向.但是，這3種重構方案以構建新編碼為切入點來研究重構優化，而本文IRS方案從重構IO流層面對存活分塊和已重構分塊進行調度，以最小化重構流量.特別地，IRS方案可應用于LRC和LRCs中全局校驗組或局部校驗組上的雙節點重構，即，IRS方案與LRC和LRCs是正交的.

2　針對多節點失效的交叉重構方案

集群存儲通常部署一個專門的存儲管理器來管理所有存儲節點.當節點失效時，存儲管理器將觸發重構操作.如圖2所示，按照重構IO流是否經過存儲管理器，IO傳輸可分為帶內和帶外模式.這里將帶內模式和帶外模式下重構分別稱作集中式重構(centralized reconstruction， CRec)和分散式重構(decentralized reconstruction， DRec).

Fig. 2　Transmission mode of reconstruction IOs.圖2　重構IO的傳輸模式

需要說明的是，CRec和DRec這2種重構模式存在于現有重構方案中.例如，重構方案CORE中[19]，所有重構操作(包括下載存活分塊、解碼計算和上傳已恢復分塊)由Relayer節點集中完成，其屬于CRec重構模式；重構方案PiggybackedRS中[20]，重構IO流程繞過了存儲管理器，一個替換節點(或新節點)專門負責一個失效節點的所有重構操作，該重構屬于DRec重構模式.下面以“節點SN1和SN2發生失效”為例來闡述CRec和DRec.

2.1.1CRec方案

在一個RS(k+r,k)碼存儲集群中，同一條帶中k+r個分塊中的任意k個分塊能夠恢復出失效的原始數據分塊.CRec中，存儲管理器能集中式地計算出失效分塊.如圖3所示，存儲管理器從k個存活節點{SN3,SN4,…,SNk+2}讀取2個條帶上2×k個存活分塊來進行重構，然后再將重構出來的數據分塊發送給替換節點RN1和RN2.其中解碼函數DEC1(·)和DEC2(·)分別采用式(5)和式(6).CRec方案有著明顯的缺點.僅當存儲管理器接收到同一條帶中k個存活分塊后方可進行重構解碼計算.當k值增大時，該存儲管理器將成為重構過程的性能瓶頸.

Fig. 3　Reconstruction flows of CRec.圖3　CRec的重構數據流

2.1.2DRec方案

與CRec方案不同，DRec方案將重構操作下放到替換節點來執行，從而解放了管理器節點.圖4所示為DRec的重構數據流，為了重構出2個條帶中失效分塊，2個替換節點RN1和RN2獨立地讀取多個2×k個存活分塊.DRec方案的不足之處是，其需要傳輸的存活分塊數量是CRec的2倍.對于f個節點失效情況，DRec將帶來f倍的存活分塊網絡流量.

Fig. 4　Reconstruction flows of DRec.圖4　DRec的重構數據流

鑒于CRec單一重構節點瓶頸以及DRec重復傳輸存活分塊這一不足，本文提出一種新的交叉重構方案IRS.IRS能夠在提供多個節點并行重構的同時最小化存活分塊的傳輸數量.

2.2IRS重構方案設計

在IRS中，1個條帶上的k個存活分塊只被一個替換節點讀取.圖5給出雙節點失效時的IRS重構數據流，替換節點RN1讀取第1條帶的k個存活分塊{P1,1,P1,2,D1,3,D1,4,…,D1,k}；替換節點RN2讀取第2條帶的k個存活分塊{P2,1,P2,2,D2,3,D2,4,…,D2,k}；RN1和RN2繼續分別重構第3和第4條帶，依此類推.替換節點RN1重構出數據分塊D1,1和D1,2；替換節點RN2重構出數據分塊D2,1和D2,2.根據RS碼存儲集群的數據布局，RN1應該保存D1,1和D2,1，而RN2應該保存D1,2和D2,2.于是，RN1將已重構分塊D1,2發送給RN2，作為交換，RN1從RN2接收已重構分塊D2,1.

算法1描述了f個節點{SN1,SN2,…,SNf}失效時IRS的重構流程.其中，{RN1,RN2,…,RNf}為失效節點{SN1,SN2,…,SNf}所對應的替換節點，1≤f≤r.當f=1時，IRS方案就等同于DRec.

Fig. 5　Reconstruction flows of IRS.圖5　IRS的重構數據流

算法1. IRS重構流程.

② introw=0;

③ while (row

④ {

⑤ for (inti=1;i≤f;i++){

⑥RNi讀取k個存活分塊{Drow+i,f+1,…,Drow+i,k,Prow+i,1,…,Prow+i,f}，計算出失效分塊{Drow+i,1,Drow+i,2,…,Drow+i,f};}

⑦ for (inti=1;i≤f;i++){

⑧RNi保留Drow+i,i;并將第row+i條帶上f-1個已重構分塊{Drow+i,1,Drow+i,2,…,Drow+i,i-1,Drow+i,i+1,…,Drow+i,f}分別發送到其余f-1個替換節點{RN1,RN2,…,RNi-1,RNi+1,…,RNf};}

⑨row=row+f;

⑩ }

Fig. 6　Disk request queue in a surviving node.圖6　存活節點的磁盤請求隊列

當條帶總數N不是f的倍數，上述IRS重構算法仍然可用，此時，最后N%f個條帶分別由替換節點{RN1,RN2,…,RNN%f}完成重構.

2.3優化用戶請求等待時間

用戶訪問存儲集群時，根據用戶訪問數據的位置可以將用戶訪問請求分為2類：用戶正常請求(請求落在存活節點上)和用戶失效請求(請求落在失效節點上).用戶失效請求通常轉換成對存活節點的修復請求.以用戶失效讀請求為例，當讀請求落在失效節點上，此時需要從k個存活節點讀取相應存活分塊，再重構出失效請求所需的數據.

在線重構場景下，存活節點要同時響應3種請求：重構讀請求、用戶正常請求和用戶修復請求.圖6所示為一個存活節點的在線重構過程中的磁盤請求隊列.對比圖6(a)和圖6(b)可知，相對于CRec和DRec，IRS下存活節點的磁盤將面臨2個替換節點RN1和RN2的交叉訪問，從而打破了重構讀請求的訪問順序性，并延長用戶請求等待時間.

為了減輕IRS交叉訪問模式對用戶訪問性能的影響，本文將預取機制引入到重構讀操作中，即，在讀取某一存活分塊時，存活節點讀取多個相鄰分塊并將它們緩存起來，后續的存活分塊讀請求可直接從緩沖區讀取.借助該預取機制，可以增強某一存活節點上對存活分塊的讀順序性.

2.4優化同步開銷

在IRS重構過程中，一個替換節點需要向其他f-1個替換節點發出讀取請求，以獲得屬于自己的已重構分塊，這會帶來一個同步的問題.如果這f-1個替換節點中的任意一個暫時沒有計算出相應分塊，則這次讀取請求將停滯，并推遲了重構過程.

針對這種同步延遲，IRS采用持久套接字連接，即，任意2個重構節點之間一旦啟動TCP連接，將一直保持該連接，直到所有重構操作結束.從而，每個替換節點能夠即時響應其他f-1替換節點的讀取請求，任意2個替換節點之間都形成雙向數據連接.持久連接有助于優化同步開銷的原因如下：1)同步請求的優先級和重構請求的一樣高，這樣使得同步與重構能夠平等地分享網絡帶寬；2)持久連接使用推傳輸模式，避免了拉傳輸模式的讀取停滯問題.

3　重構時間模型

3.1符號定義

本節對3種重構方案的重構進行建模.重構的過程主要分為3個階段：

階段1. 重構節點從存活節點讀取k個存活分塊.CRec的重構節點是管理器本身；DRec和IRS的重構節點是替換節點.這個階段的耗時用Tr_k_blks表示.本階段中，k個存活分塊需要從網線傳到網卡的傳輸緩沖區中，從而包含串行延遲.

階段2. 重構節點利用存活分塊解碼出失效分塊，用時記為Tcalc.

階段3. 將已重構分塊寫入到替換節點.CRec中，該過程包含管理器節點將已重構分塊發送給替換節點，由替換節點寫入磁盤的過程.DRec中，即為替換節點將已重構分塊寫入到本地磁盤的過程. IRS中，該寫入過程包含多個替換節點相互傳輸已重構分塊并寫入各自磁盤的過程.重構節點發送m個已重構分塊的用時記為Ts_m_blks，替換節點寫入m個已重構分塊的用時記為Tw_m_blks.

3.2CRec重構時間

Fig. 7　Analysis of reconstruction time in CRec.圖7　CRec重構時間分析

圖7繪出CRec方案中各階段的耗時示意圖.

管理器節點耗時Tr_k_blks接收完當前條帶的k個存活分塊，耗時Tcalc計算出失效分塊，再耗時Ts_f_blks將f個已重構分塊發送給替換節點.這里假設Ts_f_blks包含替換節點接收數據并寫入本地磁盤的時間.從而，CRec重構一個條帶的時間為

(7)

(8)

其中,S為節點重構時的條帶數.

3.3DRec重構時間

與CRec不同，DRec使用替換節點而非管理器節點來完成重構過程.圖8所示為DRec方案中各階段的耗時示意圖.

Fig. 8　Analysis of reconstruction time in DRec.圖8　DRec重構時間分析

DRec中，每個替換節點只重構對應的失效分塊，不需要為其他f-1替換節點完成重構操作，因此重構一個條帶的用時為

(9)

式(9)等號右邊前2項和式(7) 前2項相同，而式(9)中第3項Tw_1_blk表示將一個已重構分塊寫入本地磁盤的時間.在DRec中，每個替換節點只寫入當前條帶的1個已重構分塊.

與CRec相似，DRec也是在接收了當前條帶的k個存活分塊之后立刻啟動下一個條帶的重構，所以總重構時間TDRec約等于總條帶數與接收1個條帶中k個存活分塊用時的乘積. 如式(10)所示，TDRec與TCRec在形式上相等.

(10)

3.4IRS重構時間

IRS方案中，每個替換節點需要從存活節點讀取k個存活分塊；此外，IRS中1個替換節點從其余f-1替換節點接收f-1個已重構分塊，并向它們各發送一個已重構分塊.由于替換節點需要互傳已重構分塊，因此存在一定的同步開銷，圖9繪出IRS方案中一個替換節點所經歷的各階段操作.

Fig. 9　Analysis of reconstruction time in IRS.圖9　IRS重構時間分析

在接收k個存活分塊后，某替換節點一邊接收來自其他f-1個替換節點的已重構分塊(時間為Tr_f-1_blks)，一邊計算失效分塊(時間為Tcalc)，并將其中f-1個已重構分塊分別給其他f-1替換節點(時間為Ts_f-1_blocks).在計算出失效分塊或接收到已重構分塊時，該替換節點可以向本地磁盤寫入已重構分塊，總共要寫入f個已重構分塊(時間為Tw_f_blks).所以一個條帶的重構時間可表示為

(11)

如式(11)，TIRS_stripe考慮了同步延遲Tsync，因為每一個替換節點在發送f-1已重構分塊的同時也在接收其他f-1個替換節點的已重構分塊.既然f個替換節點同時重構f個條帶，某一替換節點在重構完第row條帶之后，就可以開始重構第row+f條帶，所以IRS總重構時間為

TIRS=(Tr_k_blks+Tsync+Ts_f-1_blks)×Sf.

(12)

由式(12)可知，每個替換節點平均完成Sf個條帶的重構，這是IRS能夠加速重構的原因.

3.5定量化驗證

用R表示DRec和IRS重構時間的比值.從式(10)和式(12)可以得出：

(13)

理想情況下，IRS的替換節點之間沒有同步延遲，即Tsync=0.另外，重構過程中重構流量非常大，k個分塊的傳輸時間可視為1個分塊傳輸時間的k倍.從而，式(13)可以進一步簡化為

(14)

表2列出了DRec和IRS在不同k值和f值下的理論重構時間比.其中，R隨著失效節點數f的增大而明顯增加.

Table 2Theoretical Ratio of Reconstruction Time Between

DRec and IRS

表2　DRec與IRS的理論重構時間比值

圖10給出了不同參數下理論重構時間比和實測重構時間比，其中重構時間實測值來自表3.

從圖10可以觀察到：1)重構時間比的理論值與實測值在f不變而k變化情況下相差不大(見圖10(a))，原因在于當f=2時，替換節點RN1只需和另一替換節點RN2交換已重構分塊，引起很低的同步開銷Tsync；2)在k不變而f變大時理論值和實測值之間差距在增大(見圖10(b))，原因在于同步開銷隨著f增大而增加，而理論重構時間比值將同步開銷忽略不計.通過對比圖10中重構時間理論對比值與實測對比值，很大程度上能反映出上述CRec，DRec，IRS方案的重構時間模型的正確性.

此外，從圖7～9可以看出，僅當重構節點(即CRec中的管理器節點、DRec和IRS中的替換節點)接收到存活分塊或已重構分塊后，該重構節點方可進行下一條帶的重構，這意味著重構節點的網絡接收帶寬將是整個重構過程的性能瓶頸.

4　實驗評估

4.1實驗環境

本實驗集群存儲采用RS碼，集群擁有15個存儲節點和1個客戶端服務器.所有機器通過思科千兆以太網交換機互連.每個存儲節點包含1個英特爾E5800@3.2GHz處理器和1個型號為WD1002FBYS的SATA2磁盤.客戶端服務器是一個浪潮服務器，包含2個X5650@2.80 GHz的4核處理器，12 GB容量的DDR3主存.所有機器采用2.6.32內核版本的Linux操作系統.客戶端服務器通過播放IO Trace來模擬多并發用戶訪問；另外，在CRec重構方案中，該服務器也充當管理器節點的角色.

4.2原型系統與測試方法

RS碼的編解碼操作使用Zfec庫[22]實現.在重構過程中，重構節點向k個存活節點發送分塊讀請求，以讀取k個存活分塊，并重構出失效分塊.

在線重構中，需要同時模擬重構過程和用戶訪問行為.為了測量用戶響應時間，在存儲集群上實現了應用層的trace播放器.如果請求數據位于失效節點上，trace播放器將直接發送k個讀請求給k個存活節點，以獲取k個存活數據.將IO trace限定于讀訪問的原因在于糾刪碼集群存儲主要應用于數據歸檔，而歸檔是一種一次寫多次讀的IO應用.本文使用Web-2 trace[23]這一讀密集型IO trace，該trace被廣泛地用來評估在線重構技術的性能[11,24-25].

重構測試時將失效節點存儲容量限制為10 GB，這個數據量足夠覆蓋trace負載的訪問范圍.離線重構測試關注重構時間這一性能指標；在線重構性能則包括重構時間和平均用戶響應時間.進行每個測試項之前，清空緩存；所有測試項重復測試5次，計算各測試值的平均值.

4.3實驗結果與分析

4.3.1離線重構

Table 3Comparison of Off-line Reconstruction Performance of three Schemes

表3　3種重構方案的離線重構性能比較

通過分析表3實驗數據，可得到如下結論：

1) 相比CRec和DRec，IRS擁有最短重構時間.以參數k=9，f=2為例，IRS對CRec和DRec的加速比分別為1.74和1.72.原因在于：當f個節點需要重構時，CRec和DRec下每個重構節點需要接收k×10 GB的存活分塊；而在IRS中，每個替換節點只需要接收(kf)×10 GB的存活分塊和(1-1f)×10 GB的已重構分塊.

2) 參數k和f在不同數值組合下，CRec和DRec的重構時間相差不大，這個實驗結果與重構時間模型中式(10)“TDRec=TCRec”是一致的.一方面，在一定程度上驗證了上述重構時間模型的正確性；另一方面，相對于CRec的集中式重構策略，DRec的分散式重構策略也無法提升重構性能，這也凸顯了IRS中交叉式重構策略的優越性.

4.3.2在線重構

圖11給出了RS(12,9)碼存儲集群在2個節點失效時在線重構的測試結果.其中，IRS+PRE表示采用預取機制的IRS方案.對于f節點失效重構，預取存活分塊的數量為f-1，即，在進行雙節點重構時，存活節點需要預取1個存活分塊.

Fig. 11　Performance of double-node on-line reconstruction.圖11　雙節點在線重構性能

CRec，DRec，IRS在參數k=9，f=2下的離線重構時間分別808.1 s，799.7 s，465.0 s，如表3所示；而3種方案在在線重構下的重構時間分別為816.8 s，810.2 s，497.4 s，如圖11(a)所示.一方面，說明在線重構時間大于離線重構時間，原因如下：這3種重構方案都需要經歷“從k個存活節點讀取k個存活分塊”這一節點，僅當接收到k個存活分塊，重構節點才進行解碼計算，在線重構時存活節點的IO帶寬被用戶IO和重構請求共同占用，用戶IO將對重構請求造成干擾，這會影響到“重構節點讀取k個存活分塊”請求的響應，最后導致時間Tr_k_blks的增加；另一方面，相對于離線重構時間，在線重構時間有少量增加，原因在于3種重構方案的重構性能瓶頸是重構節點的網絡接收帶寬，而磁盤IO帶寬競爭無法對重構時間造成很大影響.

Fig. 12　Performance of triple-node on-line reconstruction.圖12　3節點在線重構性能

從圖11(b)可知，在IRS在線重構時，預取機制能同時改進重構性能和用戶訪問性能，因為預取機制能將存活節點磁盤的順序讀合并在一起，減少了磁盤在重構請求和用戶請求之間的切換次數，因而獲得比原先更好的用戶響應和重構響應.綜合來講，IRS+PRE能獲得最優的重構時間，同時能達到與DRec相近的平均用戶響應時間.

圖12所示為RS(12,9)碼存儲集群在3個節點失效時在線重構的測試結果.其中，IRS+PRE表示采用預取機制的IRS方案；在進行3節點重構時，存活節點需要預取2個存活分塊.

對比圖11和圖12可知，隨著失效節點數f從2變為3時，IRS的重構時間有很大降低，原因是多了一個替換節點參與重構，單個替換節點承擔的重構流量減少了.當糾刪碼存儲集群的編碼參數為k=9時，IRS方案的雙節點在線重構性能至少是其他2種重構方案的1.63倍；而3節點在線重構性能是其他2種重構方案的2.14倍.

4.3.3預取機制

4.3.2節驗證了預取機制能夠改進IRS方案的重構性能和用戶訪問性能.CRec方案中存活節點能以連續讀方式響應管理器節點的重構讀請求，即CRec能獲得讀連續性.DRec方案中f個替換節點會發出重構讀請求，請求一個存活節點上的同一存活分塊， 因此需要評估預取機制對DRec性能的影響.圖13為DRec在線重構性能，其中，DRec+PRE表示采用預取機制的DRec方案，參數k=9.

Fig. 13　On-line reconstruction performance of DRec.圖13　DRec在線重構性能

從圖13可知，一方面，不管是否采用預取機制，DRec方案的重構時間變化不大.原因在于，當每個替換節點向某一存活節點發出讀請求以讀取某一存活分塊時，該存活分塊會自動緩存到該存活節點的緩沖區中，所緩存的存活分塊可以響應其他f-1個替換節點的讀請求，從邏輯上講，它同樣達到了數據預取效果；另一方面，預取機制對DRec 方案的平均用戶響應時間有少許優化作用.

5　方案適用性分析

對于RS(k+r，k)碼存儲集群來說，為了保障能夠恢復出失效節點上的失效分塊，必須保證失效節點數f不大于容錯數r，即f≤r.隨著失效節點數f的增加，有更多替換節點參與重構，這樣的話，每個重構節點需要重構的條帶數量將減少.

圖1中，所有條帶的k+r分塊分別放置到k+r存儲節點上，該k+r個節點構成一個容錯組.在實際集群中，不同條帶可放置在不同的容錯組上，這種情況下CRec，DRec，IRS方案的重構性能將保持不變，因為重構節點仍舊要讀取k個存活分塊，同時，重構節點接收帶寬是重構性能瓶頸.

當不同條帶放置在不同的容錯組時，失效節點上的失效分塊可能是數據分塊，也可能是校驗分塊，此時需要調整相應的重構解碼函數.

從IRS重構時間模型可知，重構節點的接收帶寬通常決定了整體重構過程的性能，這意味著存活節點仍然擁有可用帶寬，從而，預取機制通常能達到預期效果；但在特殊情況下，如用戶IO和重構IO競爭帶寬，造成存活節點的可用帶寬不足，此時將影響到預取操作，針對此，可以將重構IO的請求設為高優先級.

6　結論和展望

針對糾刪碼存儲集群中2個及2個以上節點失效，本文提出一種能有效降低重構流量的交叉式重構方案——IRS.IRS方案中，不同替換節點分別重構不同條帶上的失效分塊，然后通過交換已重構分塊來完成所有失效分塊的重構.本文為3種重構方案建立了重構時間模型，并用實測數據定量化驗證了模型正確性，模型揭示了“重構節點的網絡接收帶寬是重構性能瓶頸”這一結論.在真實存儲集群下測試了重構方案，對比測試結果表明：一方面，IRS能夠大幅度地減少重構流量，進而提升并發節點重構性能；另一方面，存活分塊預取機制能有效增強重構讀請求的訪問順序性，并提升用戶訪問性能.

在建立重構時間模型時，本文僅僅分析了重構過程中的3個基本操作：計算、IO和傳輸；而在實際系統中，重構過程涉及多任務排隊處理和隨機過程，我們擬在未來工作中考慮這些因素，以完善3種重構方案的重構時間模型；另外，為了能全面評估和分析重構性能影響因素，需要實測TCP連接、解碼運算、多任務切換等性能開銷.

[1]Fan B, Tantisiriroj W, Xiao L, et al. Diskreduce: Replication as a prelude to erasure coding in data-intensive scalable computing[C]Proc of 2011 Int Conf for High Performance Computing Networking, Storage and Analysis. New York: ACM, 2011: 6-10[2]Ford D, Labelle F, Popovici F, et al. Availability in globally distributed storage systems[C]Proc of the 9th Symp on Operating Systems Design and Implementation(OSDI 2010). Berkeley, CA: USENIX Association, 2010: 61-74[3]Huang C, Simitci H, Xu Y, et al. Erasure coding in windows azure storage[C]Proc of the 2012 USENIX Annual Technical Conf (ATC 2012). Berkeley, CA: USENIX Association, 2012: 15-26[4]Thusoo A, Shao Z, Anthony S, et al. Data warehousing and analytics infrastructure at Facebook[C]Proc of the 2010 ACM SIGMOD Int Conf on Management of Data(SIGMOD 2010). New York: ACM, 2010: 1013-1020[5]Luo Xianghong, Shu Jiwu. Summary of research for erasure code in storage system[J]. Journal of Computer Research and Development, 2012, 49(1): 1-11 (in Chinese)(羅象宏, 舒繼武. 存儲系統中的糾刪碼研究綜述[J]. 計算機研究與發展, 2012, 49(1): 1-11)[6]Rao K, Hafner J, Golding R. Reliability for networked storage nodes[J]. IEEE Trans on Dependable and Secure Computing, 2011, 8(3): 404-418[7]Schroeder B, Gibson G. A large-scale study of failures in high-performance computing systems[J]. IEEE Trans on Dependable and Secure Computing, 2011, 7(4): 337-350[8]Bhagwan R, Tati K, Cheng Y, et al. Total recall: System support for automated availability management[C]Proc of the 1st Symp on Networked Systems Design and Implementation (NSDI 2004). Berkeley, CA: USENIX Association, 2004: 337-350[9]Calder B, Wang J, Ogus A, et al. Windows azure storage: A highly available cloud storage service with strong consistency[C]Proc of the 23rd ACM Symp on Operating Systems Principles (SOSP 2011). New York: ACM, 2011: 143-157[10]Holland M, Gibson G, Siewiorek D. Architectures and algorithms for on-line failure recovery in redundant disk arrays[J]. Distributed and Parallel Databases, 1994, 2(3): 295-335[11]Wu S, Jiang H, Feng D, et al. Workout: IO workload outsourcing for boosting RAID reconstruction performance[C]Proc of the 7th USENIX Conf on File and Storage Technologies(FAST 2009). Berkeley, CA: USENIX Association, 2009: 239-252[12]Hafner J, Deenadhayalan V, Rao K. Matrix methods for lost data reconstruction in erasure codes[C]Proc of the 4th USENIX Conf on File and Storage Technologies(FAST 2005). Berkeley, CA: USENIX Association, 2005: 183-196[13]Xiang L, Xu Y, Lui J, et al. Optimal recovery of single disk failure in RDP code storage systems[J]. ACM SIGMETRICS Performance Evaluation Review, 2010, 38(1): 119-130[14]Kenchammana-Hosekote D, He D, Hafner J. REO: A generic RAID engine and optimizer[C]Proc of the 5th USENIX Conf on File and Storage Technologies(FAST 2007). Berkeley, CA: USENIX Association, 2007: 261-276[15]Sathiamoorthy M, Asteris M, Papailiopoulos D, et al. XORing elephants: Novel erasure codes for big data[C]Proc of the 39th Int Conf on Very Large Data Bases. New York: ACM, 2013: 325-336[16]Wei Dongsheng, Li Jun, Wang Xin. Performance study of exact minimum bandwidth regenerating codes in distributed storage[J]. Journal of Computer Research and Development, 2014, 51(8): 1671-1680 (in Chinese)(衛東升, 李鈞, 王新. 分布式存儲中精確修復最小帶寬再生碼的性能研究[J]. 計算機研究與發展, 2014, 51(8): 1671-1680)[17]Dimakis A, Godfrey P, Wu Y, et al. Network coding for distributed storage systems[J]. IEEE Trans on Information Theory, 2010, 56(9): 4539-4551[18]Wu Y, Dimakis A. Reducing repair traffic for erasure coding-based storage via interference alignment[C]Proc of the 2009 IEEE Int Symp on Information Theory. Piscataway, NJ: IEEE, 2009: 2276-2280[19]Li R, Lin J, Lee P. CORE: Augmenting regenerating-coding-based recovery for single and concurrent failures in distributed storage systems[C]Proc of the 29th IEEE Conf on Massive Data Storage. Piscataway, NJ: IEEE, 2013: 1-6[20]Rashmi K, Shah N, Gu D, et al. A hitchhiker's guide to fast and efficient data reconstruction in erasure-coded data centers[C]Proc of the 2014 ACM Conf on SIGCOMM. New York: ACM, 2014: 331-342[21]Huang J, Liang X, Qin X, et.al. PUSH: A pipelined reconstruction IO for erasure-coded storage clusters[J]. IEEE Trans on Parallel and Distributed Systems, 2015, 26(2): 516-526[22]Wilcox-O’Hearn Z. Zfec 1.4.2[CPOL]. 2011[2014-09-01]. http:pypi.python.orgpypizfec

[23]Liberatore M. Search engine IO[OL]. 2007 [2014-10-01]. http:traces.cs.umass.edu[24]Wan S, Cao Q, Huang J, et al. Victim disk first: An asymmetric cache to boost the performance of disk arrays under faulty conditions[C]Proc of the 2011 USENIX Annual Technical Conf(ATC 2011). Berkeley, CA: USENIX Association, 2011: 173-186[25]Tian L, Feng D, Jiang H, et al. PRO: A popularity-based multi-threaded reconstruction optimization for RAID-structured storage systems[C]Proc of the 5th USENIX Conf on File and Storage Technologies(FAST 2007). Berkeley, CA: USENIX Association, 2007: 301-314

Huang Jianzhong, born in 1975. Received his PhD degree from the Huazhong University of Science and Technology in 2005. Associate professor. His main research interests include computer architecture,networked storage and dependable storage.

Cao Qiang, born in 1975. Received his PhD degree from the Huazhong University of Science and Technology in 2003. Professor and PhD supervisor. His main research interests include computer architecture, large-scale storage, and power-efficient storage.

Huang Siti, born in 1989. Received his master degree from the Huazhong University of Science and Technology in 2015. His main research interests include dependable storage and distributed file system.

Xie Changsheng, born in 1957. Received his master degree from the Huazhong University of Science and Technology in 1982. Professor and PhD supervisor. His main research interests include computer architecture, IO system, networked storage, ultra-density optical storage technology, and so on.

Concurrent Node Reconstruction for Erasure-Coded Storage Clusters

Huang Jianzhong, Cao Qiang, Huang Siti, and Xie Changsheng

(WuhanNationalLaboratoryforOptoelectronics(HuazhongUniversityofScienceandTechnology),Wuhan430074)

A key design goal of erasure-coded storage clusters is to minimize network traffic incurred by reconstruction IOs, because reducing network traffic helps to shorten reconstruction time, which in turn leads to high system reliability. An interleaved reconstruction scheme (IRS) is proposed to address the issue of concurrently recovering two and more failed nodes. With analyzing the IO flows of centralized reconstruction scheme (CRec) and decentralized reconstruction scheme (DRec), it is revealed that reconstruction performance bottleneck lies in the manager node for CRec and replacement nodes for DRec. IRS improves CRec and DRec from two aspects: 1) acting as rebuilding nodes, replacement nodes deal with reconstruction IOs in a parallel manner, thereby bypassing the storage manager in CRec; 2) all replacement nodes collaboratively rebuild all failed blocks, exploiting structural properties of erasure codes to transfer each surviving block only once during the reconstruction process, and achieving high reconstruction IO parallelism. The three reconstruction schemes (i.e., CRec, DRec, and IRS) are implemented under (k+r,k) Reed-Solomon-coded storage clusters where real-world IO traces are replayed. Experimental results show that, under an erasure-coded storage cluster with parametersk=9 andr=3, IRS outperforms both CRec and DRec schemes in terms of reconstruction time by a factor of at least 1.63 and 2.14 for double-node and triple-node on-line reconstructions, respectively.

erasure codes; clustered storage; storage reliability; node reconstruction; interleaved reconstruction

2015-01-23；

2015-08-11

國家自然科學基金項目(61572209)；國家“八六三”高技術研究發展計劃基金項目(2013AA013203)；國家“九七三”重點基礎研究發展計劃基金項目(2011CB302303)

曹強(caoqiang@hust.edu.cn)

TP333

This work was supported by the National Natural Science Foundation of China (61572209), the National High Technology Research and Development Program of China (863 Program) (2013AA013203), and the National Basic Research Program of China (973 Program) (2011CB302303).