唐英杰 王 芳 謝燕文

(武漢光電國家研究中心(華中科技大學(xué)) 武漢 430074) (信息存儲系統(tǒng)教育部重點實驗室(華中科技大學(xué)) 武漢 430074) (深圳華中科技大學(xué)研究院 廣東深圳 518000)

隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)的爆炸式增長使得存儲系統(tǒng)的規(guī)模不斷增加[1-3]，但是存儲設(shè)備的可靠性卻一直沒有得到顯著提高.Google的研究發(fā)現(xiàn)[4]，傳統(tǒng)機械磁盤的年更換率為2%～9%，而固態(tài)盤 (solid-state drive, SSD)在4年內(nèi)的整盤更換率為4%～10%，比磁盤具有更低的更換率，但壞消息是SSD在數(shù)據(jù)局部損壞方面遠遠高于磁盤.這些問題給數(shù)據(jù)的持久化存儲帶來了巨大的挑戰(zhàn).

傳統(tǒng)的分布式存儲系統(tǒng)，比如GFS(Google file system)[5]和HDFS(Hadoop distributed file system)[1]采用多副本策略來保證系統(tǒng)可靠性.其中三副本策略可以容忍任意2個副本數(shù)據(jù)的丟失，在數(shù)據(jù)恢復(fù)過程中只需要從剩余可用副本拷貝數(shù)據(jù)即可，并且在并發(fā)訪問中，3個副本可以同時提供服務(wù)、分擔(dān)負載.但是隨著存儲規(guī)模越來越大，對每份數(shù)據(jù)維護3個副本不僅在存儲開銷上代價高昂，而且大大增加系統(tǒng)管理員的負擔(dān).因此大量的數(shù)據(jù)中心開始部署糾刪碼[2,6-10]，以較小的存儲開銷來保證足夠高的系統(tǒng)可靠性.

目前制約糾刪碼系統(tǒng)的主要因素是恢復(fù)開銷問題.糾刪碼的冗余策略是將文件分成若干數(shù)據(jù)塊，然后通過計算產(chǎn)生指定數(shù)量的校驗塊，數(shù)據(jù)塊和校驗塊共同形成了一個稱為條帶的結(jié)構(gòu).糾刪碼系統(tǒng)的存儲開銷和容錯能力均取決于校驗塊的數(shù)量，不過校驗塊與副本不同，在正常情況下，校驗塊沒有任何作用，無法分擔(dān)負載.但是當出現(xiàn)設(shè)備故障、節(jié)點失效等異常情況時，就可以通過條帶上剩余可用的數(shù)據(jù)塊以及校驗塊進行數(shù)據(jù)恢復(fù)，不過在這個過程中，恢復(fù)1個數(shù)據(jù)塊往往需要讀取數(shù)倍的數(shù)據(jù)，產(chǎn)生大量的I/O請求以及網(wǎng)絡(luò)流量，最終導(dǎo)致高的降級讀延遲和顯著的數(shù)據(jù)重建時間.

糾刪碼系統(tǒng)的恢復(fù)開銷一般認為來自于3個方面：編解碼運算、存儲I/O以及網(wǎng)絡(luò)傳輸.但是隨著軟硬件技術(shù)的發(fā)展，通過利用CPU的新指令[11]，可以大大提高編解碼效率，因此性能瓶頸主要集中在網(wǎng)絡(luò)和存儲上[12-20].

在本文中，我們將優(yōu)化方向著眼于數(shù)據(jù)重建路徑，針對數(shù)據(jù)恢復(fù)過程中網(wǎng)絡(luò)流量過大的問題，利用軟件定義網(wǎng)絡(luò)(software defined networking, SDN)[21]的技術(shù)，在交換機上進行部分計算[22]，使得數(shù)據(jù)恢復(fù)的解碼計算盡量靠近數(shù)據(jù)存儲節(jié)點，從而避免數(shù)據(jù)在網(wǎng)絡(luò)中大范圍傳輸，克服了恢復(fù)節(jié)點端的網(wǎng)絡(luò)瓶頸問題[18-20].因為整個解碼過程中，數(shù)據(jù)流在網(wǎng)絡(luò)中聚合、計算，然后向下一個交換機傳輸，所以我們將這種基于網(wǎng)絡(luò)計算的故障重建方案稱為網(wǎng)絡(luò)流水線(in-network pipeline, INP).

本文的主要貢獻有4個方面：

1) 提出了INP這種基于網(wǎng)絡(luò)計算的高效故障重建方案，通過利用SDN的技術(shù)，在交換機上執(zhí)行部分解碼運算，從而減少網(wǎng)絡(luò)流量，提高降級讀以及數(shù)據(jù)重建的性能.

2) 通過對解碼過程進行分析，說明INP方案可以適用于多種常見的糾刪碼，比如RS碼(Reed-Solomon code)[23-24]、PC碼(product code)[25]以及LRC碼(local reconstruction code)[13]等，并且INP可以和現(xiàn)有的優(yōu)化技術(shù)[12,16,18-20]相結(jié)合，進一步提升恢復(fù)性能.

3) 擴展了SDN控制器的功能模塊，使其能夠根據(jù)交換機的實時負載情況，靈活地選擇出合適的交換機參與到解碼計算中.

4) 以RS碼為例，評估了INP與傳統(tǒng)糾刪碼系統(tǒng)在降級讀操作中的網(wǎng)絡(luò)流量大小.另外在不同的網(wǎng)絡(luò)帶寬下，測試了正常讀、傳統(tǒng)降級讀以及基于INP方案的降級讀這3種讀取方式的性能，結(jié)果顯示基于INP方案的降級讀方式可以在一定帶寬限制下得到和正常讀接近的性能.

1 相關(guān)工作

目前，分布式存儲系統(tǒng)的規(guī)模越來越大，故障更加頻繁，存儲系統(tǒng)往往通過存儲冗余數(shù)據(jù)以保障在故障發(fā)生時，數(shù)據(jù)不丟失，持續(xù)可用.而今，越來越多的分布式文件系統(tǒng)采用糾刪碼的冗余數(shù)據(jù)方案，而不是多副本.糾刪碼在提供足夠的可靠性同時，大大降低了存儲開銷，但代價是高昂的恢復(fù)開銷.這使得降級讀和數(shù)據(jù)重建的完成時間大大增加，前者會導(dǎo)致用戶感受到明顯的訪問時延，而重建窗口的擴大則會降低系統(tǒng)的可靠性，一旦在數(shù)據(jù)重建階段再次發(fā)生節(jié)點故障，可能會導(dǎo)致數(shù)據(jù)無法恢復(fù).在不犧牲系統(tǒng)可靠性以及存儲開銷的前提下，為降低恢復(fù)開銷，我們提出了一種基于網(wǎng)絡(luò)計算的故障重建方案，利用交換機的計算能力，在網(wǎng)絡(luò)中實現(xiàn)數(shù)據(jù)合并，從而大大減少網(wǎng)絡(luò)中的數(shù)據(jù)流量，提高恢復(fù)性能.

現(xiàn)在實際生產(chǎn)系統(tǒng)中，比如Google的ColossusFS[8]、Facebook的HDFS[7]等，分別使用2種不同的RS編碼：RS(6,3)和RS(10,4).RS編碼的優(yōu)勢在于可以編碼任意k個數(shù)據(jù)塊，產(chǎn)生任意m個校驗塊，k和m都可以完全由管理員自定義，一旦發(fā)生數(shù)據(jù)丟失，只需要任意k個塊(不管是數(shù)據(jù)塊還是校驗塊)都能完全恢復(fù)出所有數(shù)據(jù)，即可以容忍任意m個塊的丟失.但RS編碼會導(dǎo)致比較高的恢復(fù)開銷，以RS(10,4)為例，10個數(shù)據(jù)塊編碼產(chǎn)生4個校驗塊，存儲開銷是1.4倍，如果發(fā)生數(shù)據(jù)丟失，則需要從10個節(jié)點上讀取數(shù)據(jù)，恢復(fù)開銷是10倍，可以看到RS編碼是在存儲開銷和恢復(fù)開銷之間做一個權(quán)衡.但是有研究發(fā)現(xiàn)，超過98%的數(shù)據(jù)丟失都是單數(shù)據(jù)塊丟失，因此有很多針對單塊恢復(fù)的優(yōu)化工作，其中Microsoft Azure Storage[2,13]使用一種稱為LRC的編碼，它編碼12個數(shù)據(jù)塊，產(chǎn)生2個全局校驗塊，另外每6個數(shù)據(jù)塊1組編碼產(chǎn)生2個局部校驗塊，如果出現(xiàn)單塊丟失，只需要讀取6個塊即可進行恢復(fù)，這種LRC(12,2,2)編碼具有1.33倍的存儲開銷和6倍的單塊恢復(fù)開銷，但缺點是犧牲了部分可靠性，不能容忍任意4個塊的丟失.

關(guān)于糾刪碼的優(yōu)化研究大致可以分為2類：1)一種新的編碼方案，比如再生碼[22]、階梯碼[14]等;2)系統(tǒng)級的優(yōu)化，比如雙糾刪碼系統(tǒng)[16]，利用負載中存在的數(shù)據(jù)訪問傾斜，對頻繁訪問的少量熱數(shù)據(jù)使用恢復(fù)開銷較小的編碼，對大量冷數(shù)據(jù)使用存儲開銷較小的編碼，從而獲得低的存儲開銷和恢復(fù)開銷.這些新型編碼或多或少都是在存儲性能和恢復(fù)性能上做一些權(quán)衡.另外還有針對數(shù)據(jù)重建方案的優(yōu)化[17]，傳統(tǒng)的數(shù)據(jù)重建方案如圖1所示.當系統(tǒng)檢測到塊丟失或者節(jié)點故障，則會在某些可用節(jié)點上啟動重建任務(wù)，以一種并行的方式恢復(fù)丟失數(shù)據(jù).圖中數(shù)據(jù)塊D1丟失，需要從其他節(jié)點上讀取相應(yīng)塊進行恢復(fù)，當數(shù)據(jù)通過網(wǎng)絡(luò)傳輸?shù)交謴?fù)節(jié)點時，恢復(fù)節(jié)點端的網(wǎng)絡(luò)帶寬將成為瓶頸，從而限制了恢復(fù)性能.

Fig. 1 The traditional erasure code data reconstruction scheme圖1 傳統(tǒng)的糾刪碼數(shù)據(jù)重建方案

Fig. 2 The erasure code data reconstruction scheme based on pipeline圖2 基于流水線的糾刪碼數(shù)據(jù)重建方案

文獻[17]中提出一種新的恢復(fù)方案，如圖2所示，它充分利用各個節(jié)點的帶寬和計算能力，采用流水線的方式，將前一個節(jié)點的數(shù)據(jù)傳輸?shù)较乱粋€節(jié)點上進行計算，然后將計算結(jié)果繼續(xù)向后續(xù)節(jié)點傳輸，直到到達恢復(fù)節(jié)點，這種方式能比較好地解決恢復(fù)節(jié)點的瓶頸問題，但它并沒有減少傳輸過程中的網(wǎng)絡(luò)流量.

我們的想法得益于SDN技術(shù)的快速發(fā)展.SDN是一種新型的可編程網(wǎng)絡(luò)架構(gòu)，其最核心的概念是將網(wǎng)絡(luò)設(shè)備的控制面和數(shù)據(jù)面分離，并強調(diào)控制面和數(shù)據(jù)面的可編程性.其中可編程控制面技術(shù)已經(jīng)日趨成熟，現(xiàn)在已經(jīng)有大量的開源控制器實現(xiàn)方案，控制器由一系列基本網(wǎng)絡(luò)服務(wù)模塊構(gòu)成，并通過特定的接口(比如OpenFlow協(xié)議標準)與交換機進行通信，以此實現(xiàn)拓撲獲取、流量統(tǒng)計、路由控制等功能.在此基礎(chǔ)上，用戶可以很容易地根據(jù)需求開發(fā)擴展功能，并對外提供訪問接口.而關(guān)于可編程數(shù)據(jù)面的研究，目前正在逐步完善，其中P4[26]語言已經(jīng)被設(shè)計出來，旨在實現(xiàn)交換機功能的動態(tài)配置.

在這樣的背景下，我們運用SDN的技術(shù)，提出了基于網(wǎng)絡(luò)計算的高效故障重建方案INP，由可編程控制器面實現(xiàn)網(wǎng)絡(luò)的拓撲管理和調(diào)度功能，由可編程數(shù)據(jù)面實現(xiàn)數(shù)據(jù)處理功能.如圖3所示，通過在交換機上對數(shù)據(jù)進行合并計算，不僅能夠解決網(wǎng)絡(luò)瓶頸問題，還能大大減少網(wǎng)絡(luò)中的流量，從而提升恢復(fù)性能.

設(shè)計INP方案主要是為了實現(xiàn)3個目標：

1) 更快的降級讀.當客戶端訪問到不可用的數(shù)據(jù)塊時，能夠在很短的時間內(nèi)完成解碼操作，使客戶端感受不到太大的延時.

2) 更短的重建時間.數(shù)據(jù)重建完成得越快，系統(tǒng)可靠性越高，在新的重建方案下，針對可能發(fā)生的多數(shù)據(jù)塊重建，如何保證高并發(fā)非常值得思考.

3) 盡可能小地影響交換機正常工作.因為交換機計算能力有限，在不影響其正常工作的前提下，如何調(diào)度交換機也是一個非常重要的工作.

2 設(shè) 計

本節(jié)首先介紹INP方案的整體結(jié)構(gòu)、包括SDN控制器、OpenFlow交換機網(wǎng)絡(luò)等；之后討論INP在降級讀過程中的I/O詳細原理；最后分析解碼計算對交換機性能的影響.

2.1 INP方案結(jié)構(gòu)

INP方案的整體結(jié)構(gòu)如圖4所示，主要由2部分組成：SDN網(wǎng)絡(luò)和Hadoop集群.其中SDN網(wǎng)絡(luò)又分為SDN控制器和OpenFlow交換機群.SDN控制器維護著整個交換機網(wǎng)絡(luò)的拓撲關(guān)系，并負責(zé)交換機的調(diào)度.交換機通過OpenFlow協(xié)議與SDN控制器通信，并在數(shù)據(jù)重建過程中執(zhí)行部分計算任務(wù).

HDFS-RAID(redundant array of independent disks)：INP方案中的Hadoop集群是基于HDFS-RAID的一個擴展.HDFS-RAID是Facebook基于第1代Hadoop開發(fā)的支持糾刪碼的系統(tǒng)，它在HDFS的基礎(chǔ)上實現(xiàn)了一個RAID方案，HDFS-RAID將存儲在HDFS中的數(shù)據(jù)塊編碼產(chǎn)生若干校驗塊，并刪除原來的副本數(shù)據(jù)塊.一旦發(fā)現(xiàn)數(shù)據(jù)丟失，就會在集群中啟動重建任務(wù)執(zhí)行數(shù)據(jù)重建操作，如果在數(shù)據(jù)重建期間，客戶端需要訪問丟失的數(shù)據(jù)，而此時系統(tǒng)中不存在副本數(shù)據(jù)，這將導(dǎo)致正常的讀取操作拋出異常，從而開始執(zhí)行降級讀操作.降級讀本質(zhì)上也是一種數(shù)據(jù)重建操作，與一般意義上的數(shù)據(jù)重建相比，降級讀操作的主要區(qū)別在于它不會將重建的數(shù)據(jù)塊寫回相應(yīng)的節(jié)點，而只是將其返回給訪問的客戶端.在2.2節(jié)中，我們將主要討論降級讀操作，因為從原理和性能上來說，降級讀操作和數(shù)據(jù)重建操作是大體一致的.

1) SDN控制器.在INP方案中，我們對SDN控制器的功能進行了擴展，當HDFS-RAID集群進行降級讀或者數(shù)據(jù)重建操作時，集群中的某個節(jié)點會首先向SDN控制器發(fā)出請求，控制器利用自身對交換機網(wǎng)絡(luò)的全局視角，選擇出合適的交換機參與解碼計算，并將選擇結(jié)果以一種樹型的結(jié)構(gòu)返回給集群，集群憑借該結(jié)構(gòu)與相應(yīng)交換機建立連接.關(guān)于SDN控制器對交換機的選擇策略，基于交換機的性能考慮，在SDN控制器中維護了交換機的狀態(tài)信息，以此作為評估標準，避免出現(xiàn)熱點問題.交換機選擇策略的設(shè)計將在2.3節(jié)中詳細介紹.

2) OpenFlow交換機.在INP方案中，交換機被用來作為聚合節(jié)點，通過在交換機上執(zhí)行一些簡單計算，將來自不同節(jié)點的數(shù)據(jù)流合并，然后將計算結(jié)果繼續(xù)向后轉(zhuǎn)發(fā)，從而達到減少網(wǎng)絡(luò)流量的目的.為了盡可能小地影響交換機正常工作，在整個數(shù)據(jù)重建過程中，交換機只需要進行異或操作.具體的原理將會在2.3節(jié)中介紹.

2.2 INP中的降級讀

本節(jié)討論INP方案中完整的數(shù)據(jù)讀取流程.如圖5所示.1)首先用戶通過HDFS客戶端向HDFS中的數(shù)據(jù)塊D1發(fā)出讀取請求.2)但此時數(shù)據(jù)塊D1因為某些故障模式導(dǎo)致數(shù)據(jù)丟失，而系統(tǒng)可能尚未發(fā)現(xiàn)該故障或者正處于數(shù)據(jù)重建過程中，所以訪問的最終結(jié)果是拋出異常.3)HDFS客戶端捕獲到讀取異常，了解到數(shù)據(jù)塊丟失，從而啟動降級讀操作.在后文的后續(xù)說明中，均采用的是RS(3,2)編碼，即3個數(shù)據(jù)塊通過編碼產(chǎn)生2個校驗塊，在這種編碼模式下，如果1個塊丟失，則需要從剩余4個可用塊中任意選出3個塊進行數(shù)據(jù)重建，在圖5中，當數(shù)據(jù)塊D1丟失時，選擇從數(shù)據(jù)塊D3以及校驗塊P1和P2中讀取數(shù)據(jù)用于數(shù)據(jù)重建.而在INP架構(gòu)中，從指定塊讀取數(shù)據(jù)之前，HDFS客戶端會向SDN 控制器發(fā)出請求，在請求消息中，HDFS 客戶端告知SDN控制器需要參與到降級讀操作當中的數(shù)據(jù)塊和校驗塊所在節(jié)點位置，SDN控制器不僅維護著整個OpenFlow交換機網(wǎng)絡(luò)的拓撲信息，還掌握著邊緣設(shè)備(Hadoop集群節(jié)點)與交換機的連接關(guān)系，當SDN控制器收到HDFS客戶端的請求后，它根據(jù)交換機拓撲信息和節(jié)點位置選擇出合適的交換機用于計算.4)SDN控制器將交換機和節(jié)點的連接關(guān)系通過一種樹型結(jié)構(gòu)返回給HDFS客戶端，我們將這種樹型結(jié)構(gòu)命名為重建樹，如圖6(a)所示.5)HDFS客戶端收到重建樹后，嘗試進行初始化，與各交換機和節(jié)點建立連接，在圖5中HDFS客戶端向交換機SW1發(fā)出建立連接請求并等待響應(yīng)，SW1收到請求后按照重建樹結(jié)構(gòu)向交換機SW2和節(jié)點D3發(fā)出連接請求并等待響應(yīng)，以此類推.當各節(jié)點確認自身狀態(tài)，同意建立連接，就會向上一級交換機發(fā)出確認信號，當HDFS客戶端收到所有的確認信號，就表示連接建立成功，從而可以開始讀取數(shù)據(jù)，進行解碼運算.

Fig. 6 Structure of reconstruction tree圖6 重建樹結(jié)構(gòu)

2.3 交換機性能分析

在INP方案中，交換機在整個數(shù)據(jù)重建操作中具有至關(guān)重要的作用，它是使得網(wǎng)絡(luò)流量減少的關(guān)鍵設(shè)備，在本節(jié)中將重點討論針對交換機性能設(shè)計的調(diào)度策略以及交換機在解碼運算中的工作原理.

1) 交換機調(diào)度策略.在實際應(yīng)用場景中，多用戶并發(fā)訪問或者多數(shù)據(jù)塊重建是非常常見的.以用戶訪問為例，當不同用戶同時引發(fā)降級讀時，SDN控制器會根據(jù)網(wǎng)絡(luò)拓撲選擇出合適的交換機進行解碼運算，這時可能會出現(xiàn)某臺交換機被多個降級讀所共享的情況.為了避免出現(xiàn)交換機熱點問題，對SDN控制器功能進行擴展，實現(xiàn)了3步調(diào)度策略：①如圖7所示，首先選擇出各節(jié)點到HDFS客戶端的最短路徑，各路徑交點為解碼交換機，從而得到如圖6(a)所示的重建樹結(jié)構(gòu)；②如果選擇出的交換機的連接數(shù)(參與降級讀的數(shù)量)超過某個閾值，則進行向上調(diào)度，即從當前交換機沿數(shù)據(jù)流方向(圖7中箭頭所指方向)選擇出空閑交換機用于解碼，所得重建樹如圖6(b)所示；③如果最短路徑上所有交換機均不符合，則放棄最短路徑，直接從高層交換機中選擇出空閑交換機.

Fig. 7 Shortest-path strategy圖7 最短路徑策略

2) RS解碼運算的分解.在2.2節(jié)的討論中，已經(jīng)提到了基于網(wǎng)絡(luò)計算的重建方案的核心思想，即在交換機上進行部分計算，使得網(wǎng)絡(luò)中傳輸?shù)牧髁繙p少.考慮到交換機本身的計算能力，為了盡量小地影響其基本的路由轉(zhuǎn)發(fā)功能，在重建方案的設(shè)計中，在交換機上只需要進行非常簡單的異或運算.具體的工作原理可通過式(1)來解釋.

(1)

RS碼的解碼過程可以表示為2個矩陣相乘，其中a1，a2，a3組成了系數(shù)矩陣，D3，P1，P2是用于解碼的數(shù)據(jù)塊和校驗塊.將式(1)左邊的矩陣運算展開，得到式(1)右邊的表達式，可以看到解碼操作的實質(zhì)就是若干系數(shù)各自乘上對應(yīng)的塊，然后將結(jié)果累加.需要注意的是，式(1)中的乘法和加法運算都是伽羅華域中的運算，伽羅華域中的乘法運算非常復(fù)雜，涉及到查表等操作，而加法運算非常簡單，就是異或操作，因此在INP的設(shè)計中，當從各節(jié)點讀取數(shù)據(jù)時，首先在各節(jié)點上對原始數(shù)據(jù)D3，P1，P2執(zhí)行乘法運算，即式(1)中的乘法項a1×D3，a2×P1，a3×P2，然后將計算結(jié)果發(fā)送給對應(yīng)的交換機，在交換機上只需要將來自不同節(jié)點的數(shù)據(jù)進行異或合并即可.另外通過式(1)也可以分析出降級讀過程中的流量變化，假設(shè)需要降級讀取1 GB的數(shù)據(jù)，按照傳統(tǒng)的數(shù)據(jù)重建方案，HDFS客戶端所在的網(wǎng)絡(luò)將接收到3 GB的數(shù)據(jù)，而INP方案中，交換機將來自不同節(jié)點的數(shù)據(jù)進行異或合并，大大減少了向后傳輸?shù)木W(wǎng)絡(luò)流量，理論上HDFS客戶端收到的數(shù)據(jù)量應(yīng)該為1 GB，從而解決數(shù)據(jù)恢復(fù)中的瓶頸問題.

2.4 編碼擴展性分析

2.3節(jié)中已經(jīng)詳細說明了RS碼在INP方案下的解碼過程，可以發(fā)現(xiàn)INP方案的有效性依賴于交換機上的數(shù)據(jù)合并過程.在本節(jié)中我們將分析一些常見糾刪碼的解碼過程，從而證明INP方案可以運用在多種糾刪碼系統(tǒng)中.

1) LRC碼.LRC(12,2,2)的編碼結(jié)構(gòu)如圖8所示，12個數(shù)據(jù)塊使用RS編碼的算法產(chǎn)生2個全局校驗塊，另外每6個數(shù)據(jù)塊通過異或產(chǎn)生1個局部校驗塊.在解碼過程中，如果出現(xiàn)單塊故障，則只需要通過式(2)進行異或計算即可，顯然可以在交換機上進行數(shù)據(jù)合并減少網(wǎng)絡(luò)流量；如果出現(xiàn)多塊故障，則需要用到全局校驗塊，該解碼過程和RS完全一致.

d4=d1+d2+d3+d5+d6+L1.

(2)

Fig. 8 LRC code圖8 LRC編碼結(jié)構(gòu)

2) PC碼.PC(2,5)的編碼結(jié)構(gòu)如圖9所示，每行5個數(shù)據(jù)塊通過異或產(chǎn)生1個局部校驗塊，每列2個數(shù)據(jù)塊通過異或產(chǎn)生1個局部校驗塊，所有的數(shù)據(jù)塊異或產(chǎn)生1個全局校驗塊.其解碼過程類似于LRC的單塊恢復(fù)，每塊數(shù)據(jù)的恢復(fù)都涉及單次異或運算，因此PC碼也可以部署在INP方案中.

Fig. 9 PC code圖9 PC編碼結(jié)構(gòu)

3) SD(sector-disk)碼[15].SD碼是一種可以修復(fù)扇區(qū)錯誤的糾刪碼，其結(jié)構(gòu)如圖10所示.與傳統(tǒng)糾刪碼相比，SD碼將扇區(qū)作為最小編碼單元，每行采用RS編碼算法產(chǎn)生2個局部校驗塊，所有扇區(qū)經(jīng)過編碼產(chǎn)生2個全局校驗塊，其解碼過程與RS碼相同，區(qū)別只在于SD碼重建粒度更小，所以INP方案也可以兼容用于扇區(qū)修復(fù)的糾刪碼.

Fig. 10 SD code圖10 SD編碼結(jié)構(gòu)

3 實 現(xiàn)

3.1 傳統(tǒng)糾刪碼系統(tǒng)

HDFS-RAID中實現(xiàn)糾刪碼功能的核心模塊主要是DRFS(distributed raid file system)和RaidNode，其中DRFS是在HDFS基礎(chǔ)上實現(xiàn)的RAID方案，而RaidNode進程主要負責(zé)數(shù)據(jù)編碼以及數(shù)據(jù)重建工作.RaidNode進程會周期性地查詢NameNode，來獲取需要編碼和需要進行重建的文件條目.

DRFS客戶端是在HDFS客戶端的基礎(chǔ)上進行封裝，它的大部分功能其實都是由下層的HDFS客戶端實現(xiàn)的，在讀取數(shù)據(jù)時，如果出現(xiàn)塊丟失等異常情況，DRFS客戶端將會捕獲到這些異常，并且定位到異常發(fā)生的位置，進而檢索同一條帶上的可用塊用于解碼操作，得到請求的數(shù)據(jù)，這就是傳統(tǒng)的降級讀操作.

3.2 基于網(wǎng)絡(luò)計算的糾刪碼系統(tǒng)

在INP方案中， 當客戶端讀取到某個丟失塊時，客戶端同樣會捕獲異常，與傳統(tǒng)降級讀不同的是客戶端之后會采取的措施，即開始執(zhí)行2.2節(jié)所描述的降級讀操作.在整個INP方案的實現(xiàn)中，SDN控制器選擇的是基于Java語言的Floodlight，OpenFlow交換機則采用Open vSwitch虛擬交換機.在客戶端捕獲到讀取異常之后，首先向條帶上的其余數(shù)據(jù)塊和校驗塊發(fā)起訪問，確定有足夠多的可用塊，并獲取這些塊所在節(jié)點的IP地址.因為Floodlight采用REST(representational state transfer)風(fēng)格的編程接口對外提供服務(wù)，所以客戶端將節(jié)點的IP地址通過HTTP請求的方式發(fā)送給Floodlight，F(xiàn)loodlight收到請求后，根據(jù)維護的交換機負載信息，對交換機進行調(diào)度.當成功選擇出合適的交換機后，更新交換機負載信息，并將交換機和節(jié)點的連接方式以重建樹的結(jié)構(gòu)發(fā)送回客戶端.然后客戶端開始計算式(1)中的系數(shù)矩陣，也稱為解碼矩陣，在與交換機以及各節(jié)點建立連接的過程中，將系數(shù)矩陣以及文件偏移等信息發(fā)送到對應(yīng)節(jié)點.當節(jié)點接收到客戶端的連接請求之后，它會去打開指定文件，根據(jù)文件偏移定位數(shù)據(jù)，如果在這個過程中發(fā)生異常，會向客戶端發(fā)送一個值為false的確認，只要有1個節(jié)點不能正常連接，客戶端收到的確認就是false，只有當所有的節(jié)點以及交換機都做好數(shù)據(jù)傳輸準備，客戶端才會收到值為true的確認.

連接成功建立之后，客戶端會采用流水線的方式向節(jié)點發(fā)出讀取請求.為了提升讀取效率，客戶端上建立了雙緩沖區(qū)，在連接建立后客戶端啟動1個子線程向緩沖區(qū)中寫數(shù)據(jù)，寫線程會一直循環(huán)檢查2個緩沖區(qū)，一旦發(fā)現(xiàn)某個緩沖區(qū)為空，就會向服務(wù)器發(fā)出讀取數(shù)據(jù)請求.采用雙緩沖區(qū)這樣的方式，是為了讀線程在讀某個緩沖區(qū)時，寫線程可以去填滿另一個緩沖區(qū)，當讀線程讀完前一個緩沖區(qū)時，可以無等待地切換到另一個緩沖區(qū)，而同時寫線程會去填滿之前被讀完的緩沖區(qū).

當寫線程讀取到1個塊的塊尾時，表示已經(jīng)成功讀取1個丟失的塊，這時客戶端就應(yīng)該與交換機以及各節(jié)點斷開連接，在這個過程中客戶端會向Floodlight發(fā)送一個斷開連接的信號，收到此信號的控制器就會更新交換機的負載信息.如果客戶端還需要讀取文件的下一個塊，且該數(shù)據(jù)塊也發(fā)生丟失，則需要重新建立連接，重復(fù)整個流程.因為即使是文件中連續(xù)的2個塊，也可能編碼在不同的條帶上.

4 測 試

4.1 測試環(huán)境

如圖11所示，在1臺配置有2TB磁盤、12 GB內(nèi)存以及2個4核2.4 GHz Intel Xeon E5620 CPU的物理機上構(gòu)建了1個由11個Docker容器和1臺虛擬交換機組成的小集群，其中8個容器作為DataNode服務(wù)器節(jié)點，另外3個容器分別作為NameNode、HDFS客戶端以及交換機的計算節(jié)點.容器內(nèi)運行Ubuntu 14.04.2操作系統(tǒng)，Docker版本為1.7.1，SDN控制器是Floodlight-0.90，交換機使用Open vSwitch 2.0.2來模擬.

Fig. 11 Experimental cluster圖11 測試集群

因為虛擬交換機本身并不具備數(shù)據(jù)解碼中的計算功能，而修改其源代碼代價太大.因此我們?yōu)槊總€虛擬交換機綁定1個計算節(jié)點，如圖11所示，當交換機接收到服務(wù)器節(jié)點傳來的數(shù)據(jù)時，首先將數(shù)據(jù)轉(zhuǎn)發(fā)給對應(yīng)的計算節(jié)點，在計算節(jié)點上完成異或合并運算，然后再發(fā)送回交換機，并繼續(xù)向后傳輸.但是采用這種方式，會給測試引入不必要的開銷，在4.3節(jié)我們將分析這種方式對測試結(jié)果造成的影響，并合理估計這部分額外開銷.

另外關(guān)于糾刪碼的設(shè)置，我們采用的編碼是RS(3,2)，即每3個數(shù)據(jù)塊編碼產(chǎn)生2個校驗塊，5個塊一起構(gòu)成1個條帶，基于這種編碼，每次降級讀取1個塊需要連接另外3個可用塊.另外設(shè)置HDFS塊大小為128 MB，使用HDFS-RAID默認的塊分布方案將編碼后的數(shù)據(jù)塊和校驗塊平均分布在集群中，確保同一糾刪碼條帶上的任意2個塊不在同一節(jié)點上.

在4.2～4.4節(jié)中，我們將分別從網(wǎng)絡(luò)流量、降級讀延遲以及帶寬競爭力這3個方面說明INP方案的有效性.

4.2 流量測試

通過第2節(jié)分析可知，影響降級讀性能的一個重要因素是網(wǎng)絡(luò)流量，在我們的測試集群中，網(wǎng)絡(luò)瓶頸主要出現(xiàn)在交換機與客戶端相連的鏈路上.因為測試過程中客戶端降級讀取1 GB的數(shù)據(jù)，而編碼方案采用的是RS(3,2)編碼，即每次需要讀取3倍的數(shù)據(jù)用于解碼操作，所以理論上客戶端的降級讀會從服務(wù)器上獲取3 GB的數(shù)據(jù)，傳統(tǒng)降級讀方式中3 GB的數(shù)據(jù)將全部流經(jīng)交換機到達客戶端，在客戶端上進行解碼得到丟失的數(shù)據(jù).而基于網(wǎng)絡(luò)計算的降級讀方式因為在交換機上已經(jīng)完成了計算，因此理論上只需要向客戶端傳輸1 GB數(shù)據(jù).我們通過調(diào)用Floodlight控制器的接口可以獲取到交換機各端口的輸入輸出流量，經(jīng)過簡單處理后的結(jié)果如圖12所示，其中HDFS-RAID表示傳統(tǒng)降級讀，INP表示基于網(wǎng)絡(luò)計算的降級讀.

Fig. 12 Comparison of network traffic圖12 網(wǎng)絡(luò)流量對比

第1組數(shù)據(jù)測的是交換機從各服務(wù)器節(jié)點讀取的數(shù)據(jù)量，可以看到在傳統(tǒng)降級讀過程中，需要從集群中讀取2.98 GB的數(shù)據(jù)，與理論分析值3 GB基本相符，另外INP方案中的降級讀從服務(wù)器獲取了2.91 GB的數(shù)據(jù)，略少于傳統(tǒng)降級讀，但認為是在測試誤差范圍內(nèi).

我們比較關(guān)注的是第2組數(shù)據(jù)：交換機轉(zhuǎn)發(fā)給客戶端的數(shù)據(jù)量.圖12中數(shù)據(jù)顯示INP方案中交換機轉(zhuǎn)發(fā)給客戶端的數(shù)據(jù)量與傳統(tǒng)降級讀的比例為1:3，基本與理論值相符.

后面2組數(shù)據(jù)測試的是交換機的總的接收數(shù)據(jù)量和發(fā)送數(shù)據(jù)量，統(tǒng)計這2組數(shù)據(jù)主要是為了說明在降級讀中，交換機接收的流量幾乎都來自服務(wù)器，而轉(zhuǎn)發(fā)的流量都是送往客戶端.

測試中我們采用的是一種恢復(fù)開銷相對較小的編碼，每次恢復(fù)1個數(shù)據(jù)塊只需要讀取3倍的數(shù)據(jù)量.而在Google ColossusFS中使用的是RS(6,3)，F(xiàn)acebook HDFS-RAID使用的是RS(10,4)，如果在INP方案中部署這2種編碼，能夠減少的網(wǎng)絡(luò)流量會更多.

4.3 降級讀延時

在本節(jié)中，我們將分別在不同網(wǎng)絡(luò)帶寬下對正常讀、傳統(tǒng)降級讀和INP方案中的降級讀的時間進行比較.測試結(jié)果如表1和圖13所示，其中HDFS表示正常讀.

關(guān)于網(wǎng)絡(luò)帶寬的設(shè)置，采用的辦法是在交換機到客戶端的出口端口上創(chuàng)建1個QoS(quality of service)隊列，并設(shè)置最大最小速度，以此來限制網(wǎng)絡(luò)帶寬.需要注意的是所有的網(wǎng)絡(luò)限制都是針對交換機到客戶端的出口帶寬，其余鏈路不做限制，以此來分析網(wǎng)絡(luò)流量所引起的瓶頸問題，同時說明INP方案的有效性.

Table 1 Time Required to Read 1 GB Data at DifferentNetwork Bandwidths

Note: The value in parentheses is the correction data, because the simulation method used in our experiments has a large impact on the result at 10 000 Mbps.

Fig. 13 Time required to read 1 GB data at different network bandwidths圖13 不同帶寬下讀取1 GB數(shù)據(jù)所需時間對比

在整個測試部分，我們以正常讀取1 GB數(shù)據(jù)的時間作為基準來分析傳統(tǒng)降級讀和基于INP方案的降級讀的性能.在10 000 Mbps下，測得客戶端正常讀取1 GB的數(shù)據(jù)需要1.65 s，基于流水線原理，讀取時間取決于瓶頸帶寬和瓶頸鏈路上的網(wǎng)絡(luò)流量，在傳統(tǒng)降級讀中，客戶端所在鏈路需要傳輸3倍于正常讀的流量，因此理論上傳統(tǒng)降級讀讀取1 GB的數(shù)據(jù)需要3倍的正常讀時間，而實際測試結(jié)果是8.79 s.這主要是因為降級讀除了網(wǎng)絡(luò)傳輸開銷，還存在存儲I/O以及解碼計算開銷.

再觀察10 000 Mbps下INP方案的測試結(jié)果.因為4.2節(jié)實際測得交換機最后轉(zhuǎn)發(fā)到客戶端的流量和正常讀是一致的，即INP方案中瓶頸鏈路帶寬以及瓶頸鏈路傳輸?shù)木W(wǎng)絡(luò)流量均與正常讀相同，所以INP方案中的網(wǎng)絡(luò)傳輸時間理論上也應(yīng)該與正常讀一致，不過根據(jù)4.1節(jié)所述，因為硬件設(shè)備受限，所以在仿真測試中為交換機綁定1個計算節(jié)點，按照這種方式，在10 000 Mbps下，雖然消除了客戶端的網(wǎng)絡(luò)瓶頸，但是計算節(jié)點處的鏈路反而成為了瓶頸，而且交換機轉(zhuǎn)發(fā)給計算節(jié)點的數(shù)據(jù)和計算節(jié)點回送給交換機的計算結(jié)果均在同一鏈路上傳輸，所以該段鏈路上的網(wǎng)絡(luò)流量是正常讀的4倍，為了消除這部分開銷，我們測試了3 GB數(shù)據(jù)在萬兆鏈路下的網(wǎng)絡(luò)傳輸時間，以此來近似估計交換機與計算節(jié)點之間的額外開銷，如表1所示，我們列出了INP方案的原始測試結(jié)果和修正之后的結(jié)果，消除開銷之后INP方案讀取時間為9.82 s.但即使是修正之后的數(shù)據(jù)，也遠遠大于正常讀，甚至要比傳統(tǒng)降級讀時間略長，不僅沒有減少恢復(fù)開銷，反而增大.分析INP方案的額外時間開銷，不僅包括存儲I/O和解碼計算，另外在INP方案中，客戶端在讀取數(shù)據(jù)之前還需要訪問SDN控制器，并等待控制器返回重建樹信息，之后還要與交換機、服務(wù)器建立連接，這些操作都存在一定的時間開銷.而且由于客戶端鏈路的網(wǎng)絡(luò)帶寬達到10 000 Mbps，數(shù)據(jù)傳輸速度較快，導(dǎo)致網(wǎng)絡(luò)開銷并不是影響恢復(fù)性能的主導(dǎo)因素.這就使得INP方案性能反而沒有傳統(tǒng)降級讀性能好.由于集群規(guī)模的限制，我們在測試中只能采用條帶較短的編碼方案，但是考慮到實際系統(tǒng)中往往會部署恢復(fù)開銷更大的編碼，這時網(wǎng)絡(luò)流量將會成倍增加，這些都將有利于INP方案的性能發(fā)揮.

當我們將帶寬設(shè)置為2 000 Mbps時，交換機與計算節(jié)點之間的鏈路不再是網(wǎng)絡(luò)瓶頸，因此不用對測試結(jié)果進行修正.測試結(jié)果顯示INP方案性能優(yōu)于傳統(tǒng)降級讀，且隨著帶寬資源越來越緊張，INP方案的優(yōu)勢也越來越明顯，甚至接近正常讀時間.如圖13所示，在1 000 Mbps下，INP方案可以減少50%的降級讀開銷；而在200 Mbps下，INP方案已經(jīng)達到正常讀的性能.這主要是因為隨著帶寬降低，降級讀的恢復(fù)開銷主要取決于網(wǎng)絡(luò)傳輸時間，而INP方案大大減少了網(wǎng)絡(luò)流量，因此可以獲得非常大的性能提升.而且目前用于測試的INP方案只是一個簡單原型，在性能優(yōu)化上還有一些工作有待完成.

4.4 網(wǎng)絡(luò)競爭力

在4.3節(jié)的測試中，評估的都是某種讀取方式獨享整個網(wǎng)絡(luò)帶寬時的性能.而在真實應(yīng)用場景里，往往是既有正常讀，也有降級讀，2種讀取方式并行執(zhí)行.在這部分，將考量正常讀+正常讀、正常讀+傳統(tǒng)降級讀、正常讀+INP降級讀這3種共享讀取模式下各讀取方式的性能表現(xiàn).設(shè)置這組測試的目的主要是為了評估降級讀與正常讀產(chǎn)生的數(shù)據(jù)流在網(wǎng)絡(luò)中的競爭力表現(xiàn).

如圖14所示，在1 000 Mbps下，第1組數(shù)據(jù)顯示的是獨占模式下各讀取方式的性能，即4.3節(jié)中測得的數(shù)據(jù).第2組數(shù)據(jù)表示的是當網(wǎng)絡(luò)中存在2個客戶端同時讀取數(shù)據(jù)時正常讀的性能表現(xiàn).結(jié)果符合預(yù)期，當網(wǎng)絡(luò)中流量成倍增加時，正常讀性能成倍降低，圖14中顯示2個正常讀操作的時間都是原來獨占網(wǎng)絡(luò)帶寬時的2倍.再觀察第3組數(shù)據(jù)，當網(wǎng)絡(luò)中同時存在正常讀和傳統(tǒng)降級讀時，正常讀的完成時間接近于獨占網(wǎng)絡(luò)帶寬時的3倍，這是因為當網(wǎng)絡(luò)中存在降級讀時，網(wǎng)絡(luò)流量大大增加，嚴重占用了網(wǎng)絡(luò)帶寬，實驗結(jié)果顯示在這種共享模式下，正常讀分配有1/3的帶寬，傳統(tǒng)降級讀占用了剩下的2/3，但是考慮到傳統(tǒng)降級讀的流量是正常讀的3倍，所以說明正常讀的網(wǎng)絡(luò)競爭力會略強于傳統(tǒng)降級讀.第4組數(shù)據(jù)測的是正常讀和INP降級讀的共享模式，其中正常讀的時間相比于獨占帶寬增加了1倍，即正常讀在混合模式下占用了一半的帶寬，這與第2組數(shù)據(jù)情況相同，因此可以認為INP方案在網(wǎng)絡(luò)競爭力方面與正常讀表現(xiàn)一致.

Fig. 14 Shared read mode in 1 000 Mbps圖14 1 000 Mbps下的共享讀取模式

另外我們還分別在500 Mbps下和100 Mbps下對3種混合讀取模式進行了測試，如圖15和圖16所示.在這2種帶寬下，正常讀和INP降級讀的混合模式中，正常讀均占有一半的帶寬，與1 000 Mbps下表現(xiàn)一致.特別是100 Mbps下的測試結(jié)果，非常直觀地顯示了INP降級讀具有和正常讀一樣的網(wǎng)絡(luò)競爭力.如圖16所示，因為在該帶寬下，INP降級讀已經(jīng)具有接近正常讀的時間開銷，所以圖16中第4組數(shù)據(jù)和第2組數(shù)據(jù)表現(xiàn)完全吻合，這也說明了可以將INP降級讀等價于正常讀來看待.

Fig. 15 Shared read mode in 500 Mbps圖15 500 Mbps下的共享讀取模式

Fig. 16 Shared read mode in 100 Mbps圖16 100 Mbps下的共享讀取模式

4.5 未來工作

在本次測試過程中，我們從網(wǎng)絡(luò)流量、降級讀延遲以及網(wǎng)絡(luò)競爭力說明了INP方案的有效性，它能夠大大減少降級讀過程中的網(wǎng)絡(luò)流量，從而提升恢復(fù)性能，甚至可以在一定帶寬下接近正常讀水平，而且我們可以預(yù)見到，在恢復(fù)開銷更大的編碼系統(tǒng)上，我們的方案會獲得進一步的性能提升.

但是我們在測試環(huán)境上還存在一些不足，比如單機性能有限，在單機上模擬集群，對于集群的很多特性無法表現(xiàn)出來，比如存儲I/O操作，這也是一個影響恢復(fù)性能的重要因素；另外一個不足是目前沒有在實際的OpenFlow交換機上去實現(xiàn)我們的功能，這也導(dǎo)致實驗過程中引入了一些額外開銷，雖然我們在測試中修正了這部分開銷，但還是不能完全代表真實場景.關(guān)于測試部分，在代碼實現(xiàn)上還存在不少優(yōu)化空間，可以進一步提升INP方案的性能，另外目前INP方案尚未與更多編碼方案進行對比測試.這些問題都將作為我們未來的研究方向.

5 總 結(jié)

本文提出一種新型的基于網(wǎng)絡(luò)計算的高效故障重建方案INP來解決糾刪碼系統(tǒng)中恢復(fù)開銷太大的問題，考慮到影響恢復(fù)開銷的3個因素：較高的網(wǎng)絡(luò)傳輸開銷、解碼計算復(fù)雜以及大量的磁盤讀寫.INP方案選擇從網(wǎng)絡(luò)傳輸量這個主要因素上進行優(yōu)化.

通過分析傳統(tǒng)糾刪碼系統(tǒng)恢復(fù)數(shù)據(jù)時的網(wǎng)絡(luò)情況，可以發(fā)現(xiàn)客戶端所在鏈路經(jīng)常需要傳輸大量的數(shù)據(jù)，這是由RS碼的解碼算法決定的，傳統(tǒng)糾刪碼系統(tǒng)在解碼時總是把所有需要的數(shù)據(jù)都傳輸?shù)?個節(jié)點上進行計算，這就使得該節(jié)點所在鏈路成了整個網(wǎng)絡(luò)的瓶頸，從而導(dǎo)致恢復(fù)開銷增大.

因此我們利用SDN，設(shè)計出一種可以在交換機上進行聚合計算的數(shù)據(jù)重建方案，以此來減少向后傳輸?shù)木W(wǎng)絡(luò)流量，最終解決客戶端處的網(wǎng)絡(luò)瓶頸問題.

實驗結(jié)果顯示INP方案能夠大大減少降級讀過程中的網(wǎng)絡(luò)流量，從而提升恢復(fù)性能，在1 000 Mbps下能夠降低50%的降級讀開銷，而且隨著帶寬資源緊缺，INP方案中的降級讀可以接近正常讀水平.