周長俊，宗 平

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.南京郵電大學 海外教育學院，江蘇 南京 210023)

0 引 言

隨著信息技術(shù)的迅速發(fā)展，互聯(lián)網(wǎng)以及電子商務的用戶數(shù)量急劇增加，在互聯(lián)網(wǎng)中有著各種各樣的應用，這些應用無時無刻不在產(chǎn)生數(shù)據(jù)，最終帶來了海量數(shù)據(jù)[1]。當前主流的分布式文件系統(tǒng)包含GFS、TFS、HDFS等。GFS在保留傳統(tǒng)分布式文件系統(tǒng)特點(伸縮性、可用性等)的基礎上添加新的特性，將系統(tǒng)中組件的失效現(xiàn)象視為常態(tài)，處理文件大小為GB，TB甚至PB等[2]。TFS主要用于對海量的非結(jié)構(gòu)化數(shù)據(jù)的存儲與管理，文件大小通常不會超過1 MB[3]。王魯俊等針對TFS存在的讀寫延遲，提出一種新的低延遲、高可用的分布式存儲方案，而且也實現(xiàn)了分布式文件系統(tǒng)[4]。HDFS(Hadoop distributed filesystem)，是可以在通用硬件(commodity hardware)上運行的分布式文件系統(tǒng)之一[5]，也是具有高度容錯性能的分布式文件系統(tǒng)。HDFS針對數(shù)據(jù)訪問具有高吞吐量，因此十分適合那些需要操作大規(guī)模數(shù)據(jù)集的應用。HDFS通過流式來實現(xiàn)文件系統(tǒng)數(shù)據(jù)的讀取。

HDFS擁有兩類節(jié)點，分別為namenode(名稱節(jié)點)和datanode(數(shù)據(jù)節(jié)點)，以master-worker方式運行[6]。名稱節(jié)點的主要職責是存儲每個文件的各個塊到其所在的數(shù)據(jù)節(jié)點信息的映射[7]。數(shù)據(jù)節(jié)點的主要職責是存儲和檢索數(shù)據(jù)塊，而且需要通過心跳機制(heart beat)來實現(xiàn)定期向名稱節(jié)點發(fā)送它們當前所存放的數(shù)據(jù)塊的列表[8]?？蛻舳?client)表示用戶，它通過名稱節(jié)點獲取讀取文件的數(shù)據(jù)塊所在數(shù)據(jù)節(jié)點的信息或者是通過名稱節(jié)點獲取寫入的數(shù)據(jù)節(jié)點的信息[9]。

HDFS整體架構(gòu)可參見圖1。

圖1 HDFS整體架構(gòu)

1 數(shù)據(jù)流

1.1 文件讀取

客戶端通過對名稱節(jié)點發(fā)起文件訪問請求，名稱節(jié)點接收到來自客戶端的請求之后查詢該文件的起始塊的地址。需要注意的是，由于默認復制因子為3，故每個數(shù)據(jù)塊在文件系統(tǒng)中共有3塊，其中namenode會考慮客戶端和所要讀取的數(shù)據(jù)塊所在的數(shù)據(jù)節(jié)點的距離，返回最優(yōu)的數(shù)據(jù)節(jié)點的位置供客戶端讀取。當然，若客戶端自身為文件系統(tǒng)中的某個數(shù)據(jù)節(jié)點，同時自身還擁有所請求的數(shù)據(jù)塊的一個副本，那么則直接通過本地讀取數(shù)據(jù)。

文件讀取的具體流程可參見圖2。

圖2 HDFS中的文件讀取

1.2 文件寫入

客戶端創(chuàng)建文件時，首先需要訪問名稱節(jié)點來驗證用戶是否具有新建文件的權(quán)限以及新建的文件是否已經(jīng)在文件系統(tǒng)中存在，若通過上述驗證，則開始寫操作?？蛻舳嗽趯懭氩僮髦?，還需要考慮的是文件系統(tǒng)的復制因子，需要根據(jù)復制因子來選取對應數(shù)目的數(shù)據(jù)節(jié)點數(shù)，默認復制因子數(shù)為3。數(shù)據(jù)寫入的過程可以類比為流水線形式，客戶端寫入數(shù)據(jù)至第一個數(shù)據(jù)節(jié)點，第一個節(jié)點寫數(shù)據(jù)至第二個數(shù)據(jù)節(jié)點，以此類推。這種流式寫入提高了寫的效率，提升了文件系統(tǒng)的吞吐量。直至每個節(jié)點數(shù)據(jù)寫入完畢才能確認客戶端的數(shù)據(jù)寫入完畢。

HDFS中的文件寫入具體參見圖3。

圖3 HDFS中的文件寫入

2 Hadoop備份數(shù)據(jù)存放策略

2.1 HDFS默認備份數(shù)據(jù)存放策略

HDFS的副本存放策略是機架敏感(rack awareness)，默認復制因子的數(shù)目(文件的副本數(shù))為3[10]。假如客戶端自身是集群中的某個數(shù)據(jù)節(jié)點，那么就把第一個副本存放在運行客戶端的節(jié)點中，否則(即客戶端運行在集群之外)隨機選擇集群中的一個節(jié)點作為第一個副本存放的節(jié)點。第二個副本的存放需要通過名稱節(jié)點隨機選擇與第一個副本不是同一個機架的其他機架上的節(jié)點當中。對于第三個副本，則需要存放在和第二個副本同一個機架但不同的節(jié)點當中。上述方法[11]一方面降低了機架間的寫的流量，實現(xiàn)了寫的性能的提升；另一方面，顯然機架發(fā)生故障的概率要遠遠低于節(jié)點發(fā)生故障的概率，在沒有改變數(shù)據(jù)的可靠性和可用性的同時，也降低了讀操作消耗的網(wǎng)絡帶寬。

HDFS默認備份數(shù)據(jù)存放策略參見圖4。

因為HDFS的默認副本存放策略為一個任意選擇遠端機架策略，所以副本最終存放的節(jié)點是無法被控制的。其具體表現(xiàn)如下：

圖4 HDFS默認備份數(shù)據(jù)存放策略

(1)使用不同機架來存放同一數(shù)據(jù)塊的不同副本，如果集群包含多個機架，那么可以實現(xiàn)數(shù)據(jù)塊的高可用性以及數(shù)據(jù)的均衡分布，但是要是集群只擁有一個機架，那么隨之而來的問題是無法實現(xiàn)數(shù)據(jù)塊的均勻分布以及無法保證數(shù)據(jù)塊的高可用性。

(2)節(jié)點當前的負載數(shù)目沒有納入節(jié)點選擇的考慮范圍之內(nèi)，可能發(fā)生的情況是負載較高的節(jié)點會被持續(xù)寫入，使得集群中不同節(jié)點負載出現(xiàn)兩種極端現(xiàn)象(某些節(jié)點負載很高，其他節(jié)點負載很低)。如果產(chǎn)生上述問題，那么帶來的問題是當數(shù)據(jù)塊恢復時會造成集群內(nèi)部網(wǎng)絡帶寬的巨大消耗。

(3)如果存在對數(shù)據(jù)塊有較大的讀請求，那么通過增加副本數(shù)目來提升讀性能，但是對于超過三個的備份數(shù)據(jù)塊，后續(xù)的每一個備份數(shù)據(jù)存放節(jié)點的選擇都是隨機的，這就會造成上述(2)的問題。

當然，HDFS內(nèi)部的均衡器(balancer)守護進程對上述問題做出了回應。它通過移動數(shù)據(jù)塊，實現(xiàn)降低負載較高的節(jié)點的當前數(shù)據(jù)塊數(shù)目，從而提升負載較低的節(jié)點的當前數(shù)據(jù)塊數(shù)目，最終目的是實現(xiàn)集群中數(shù)據(jù)塊數(shù)目的均勻分布。誠然均衡器守護進程在一定程度上解決了上述問題，但缺陷如下：對數(shù)據(jù)塊的移動調(diào)整是滯后的；存在集群內(nèi)部帶寬資源的不合理消耗，與其事后糾正前期存在的問題，不如在進行遠端機架節(jié)點選擇時就進行優(yōu)化，從而避免后期的糾正，減少損耗。

2.2 HDFS備份數(shù)據(jù)存放策略研究現(xiàn)狀

段效琛等[12]提出了基于初始信息素篩選的蟻群優(yōu)化算法的副本選擇機制，結(jié)合遺傳算法與蟻群優(yōu)化算法，使用蟻群優(yōu)化算法篩選初始信息，利用遺傳算法進行全局搜索，最終決定副本的存放位置。

王來等[13]提出由數(shù)據(jù)驅(qū)動任務分配，使得每一個數(shù)據(jù)節(jié)點都在做合適的任務，從而實現(xiàn)效率的提升。

李曉愷等[14]提出基于糾刪碼和動態(tài)副本策略的HDFS改進系統(tǒng)，對副本使用糾刪碼來計算冗余程度，對數(shù)據(jù)塊進行分解編碼，產(chǎn)生很多的數(shù)據(jù)分片，將分片存儲于系統(tǒng)之中來替代多副本策略。

3 改進的備份數(shù)據(jù)存放策略

3.1 改進的備份數(shù)據(jù)存放策略思想

依據(jù)上述分析發(fā)現(xiàn)的問題，解決的關鍵應該放在備份副本存放的遠端機架的選擇上，而不是存放完畢之后再去想著補救之法，因此文中對HDFS默認備份數(shù)據(jù)存放策略進行合理的優(yōu)化。

之所以將備份數(shù)據(jù)存放在遠端機架節(jié)點之上，是為了確保當?shù)谝粋€副本所在節(jié)點發(fā)生故障時，能夠通過遠端機架上的備份數(shù)據(jù)進行數(shù)據(jù)塊的恢復工作。與此同時為了降低數(shù)據(jù)恢復時消耗的內(nèi)部帶寬，需要盡可能地選擇相鄰機架上的節(jié)點，實現(xiàn)數(shù)據(jù)恢復時降低內(nèi)部帶寬的消耗；由于節(jié)點選擇時的隨機性，可能出現(xiàn)某個機架的某個節(jié)點備份數(shù)據(jù)過于冗余，為了避免出現(xiàn)節(jié)點的非負載均衡，故選擇節(jié)點時需要考慮節(jié)點目前已存放的數(shù)據(jù)備份的數(shù)目；最后針對需要經(jīng)?；謴偷臒狳c備份數(shù)據(jù)，通過調(diào)整比例系數(shù)來實現(xiàn)失效熱點數(shù)據(jù)的快速恢復，通過階段性的分析，獲取不同階段的備份數(shù)據(jù)失效情況，從而實現(xiàn)對不同階段備份數(shù)據(jù)的存放進行動態(tài)選擇。

改進的備份數(shù)據(jù)存放策略思想如下：當用戶請求上傳文件到HDFS集群時，名字節(jié)點首先任意選擇特定數(shù)值的不同機架上的節(jié)點作為目標節(jié)點；其次獲取所有目標節(jié)點到當前節(jié)點的距離值，目標節(jié)點當前存放的備份數(shù)據(jù)的數(shù)目，依據(jù)這兩個數(shù)值得出每個節(jié)點的匹配度，選取匹配度最高的節(jié)點作為備份數(shù)據(jù)的存放目標節(jié)點。最后通過定時任務獲取階段性的備份數(shù)據(jù)的失效次數(shù)，一旦發(fā)現(xiàn)失效次數(shù)超過指定閾值，通過上述方法重新選擇備份數(shù)據(jù)存放節(jié)點(此時需要調(diào)整比例系數(shù))，用于解決熱點失效數(shù)據(jù)恢復時帶來的內(nèi)部帶寬的損耗。

3.2 節(jié)點匹配度評價方法

如上所述，對于每一個目標節(jié)點，改進策略會依據(jù)節(jié)點的當前負載信息、節(jié)點間的距離來給出該目標節(jié)點的匹配度，將該值作為目標節(jié)點選擇的依據(jù)，具體計算方式如下：

其中，C(i)表示編號為i的目標節(jié)點當前的負載數(shù)目，該值與節(jié)點的匹配度成反比；L(i)表示編號為i的目標節(jié)點到當前的網(wǎng)絡距離，該值與節(jié)點的匹配度成反比；α1、α2為比例系數(shù)，需要根據(jù)不同的匹配度評估時刻進行合適的指定，分別針對用戶上傳文件至集群時和針對備份數(shù)據(jù)失效次數(shù)超過閾值時即熱點備份數(shù)據(jù)進行恢復時進行的節(jié)點選擇。

3.3 算法描述

基于上面的思想，對改進備份數(shù)據(jù)存放策略給出具體的算法描述：

(1)當有新的數(shù)據(jù)塊提交或者備份數(shù)據(jù)失效次數(shù)超過閾值，名字節(jié)點獲取已匹配節(jié)點列表中節(jié)點的數(shù)目，若該數(shù)目小于指定值K，則轉(zhuǎn)向步驟2，否則轉(zhuǎn)向步驟3；

(2)隨機選取節(jié)點，若選取節(jié)點不在已匹配節(jié)點列表中并且該節(jié)點與已匹配節(jié)點列表中任一節(jié)點不在同一機架，則將該節(jié)點添加到待匹配節(jié)點列表；

(3)計算待匹配節(jié)點列表中每一個待匹配節(jié)點的匹配度，將計算結(jié)果記錄至已匹配節(jié)點列表，清空待匹配節(jié)點列表；

(4)對已匹配節(jié)點列表按照匹配度進行排序；

(5)返回已匹配節(jié)點列表中匹配度最高的節(jié)點，作為備份數(shù)據(jù)存放的目標節(jié)點。

3.4 實 現(xiàn)

利用Hadoop默認備份策略進行節(jié)點選擇的步驟如下：

(1)通過默認數(shù)據(jù)塊存放策略類BlockPlacementPolicyDefault的chooseTarget()方法進行節(jié)點選擇；

(2)通過調(diào)用NetworkTopolcgy類的contains()方法來判斷客戶端是否是集群中的一個數(shù)據(jù)節(jié)點，若客戶端是集群中的一個數(shù)據(jù)節(jié)點，則通過chooseLocalStorge()方法選擇客戶端作為第一個節(jié)點；否則通過調(diào)用chooseRandom()方法隨機選擇集群中的任一機架中的一個節(jié)點，通過chooseLocalRack()方法在本地機架上隨機選擇一個節(jié)點作為第一個節(jié)點；

(3)通過調(diào)用chooseRemoteRack()方法在遠程機架上隨機選擇一個節(jié)點作為第二個節(jié)點，使用NetworkTopolcgy類的isOnSameRack()方法來判斷該節(jié)點是否與前一個節(jié)點在同一個機架上，若不在同一機架上，則將該節(jié)點作為第二個節(jié)點;

(4)通過調(diào)用chooseLocalRack()方法在第二個節(jié)點的本地機架上隨機選擇一個節(jié)點作為第三個節(jié)點。

上述為Hadoop默認備份數(shù)據(jù)存放策略的具體實現(xiàn)，在此基礎上，按照文中提出的算法做出如下修改，具體實現(xiàn)如下：

public class ImprovedBlockPlacementPolicy extends BlockPlacementPolicy {

/*NetworkTopology用來表示Hadoop集群的網(wǎng)絡拓撲結(jié)構(gòu)*/

private NetworkTopology clusMap;

/*其余私有成員變量未標注*/

DataNodeDesriptorchooseTarget(

//文件系統(tǒng)相關信息

FSInodeInfo fsInodeInfo,

//備份文件的份數(shù)

int countReplicas

DataNodeDescriptor descriptor,

List targetNodes,

long blockNum) {

//省略部分重復代碼

double[] calc=new double[randomNum];

for(int k=0;k

//進行節(jié)點選擇

DataNodeDescriptor dataNodeDes=choseRandom(...);

//計算節(jié)點匹配度

calc[k]=match(dataNodeDes);

}

//獲取匹配度最高的節(jié)點

double max_calc=sort(calc);

return choose_max(max_calc);

}

}

4 實驗與結(jié)果分析

為了驗證改進的Hadoop備份數(shù)據(jù)存放策略相對于默認備份數(shù)據(jù)存放策略所能帶來的性能上的提升，進行了以下實驗。其中Hadoop版本為2.7.0，總共包含5個機架(機架分別命名為A,B,C,D,E)，每個機架包含6個數(shù)據(jù)節(jié)點(每個數(shù)據(jù)節(jié)點對應一臺機器)，默認每個數(shù)據(jù)節(jié)點擁有相同的性能。集群中任意兩個節(jié)點之間的距離為這兩個節(jié)點到最近公共祖先的距離的和。通過上述定義，可得如下分類：

(1)同一節(jié)點上的進程；

(2)同一機架上的不同節(jié)點；

(3)同一數(shù)據(jù)中心不同機架上的節(jié)點。

給出如下三種描述(數(shù)據(jù)中心：d1,機架：r1，節(jié)點：n1)：

(1)distance(/d1/r1/n1,/d1/r1/n1)=0：同一節(jié)點上的進程；

(2)distance(/d1/r1/n1,/d1/r1/n2)=2：同一機架上的不同節(jié)點上的進程；

(3)distance(/d1/r1/n1,/d1/r2/n1)=4：同一數(shù)據(jù)中心不同機架上的節(jié)點。

為了規(guī)避特殊性，保證選取提交數(shù)據(jù)節(jié)點的隨機性，實驗中，通過隨機算法選中機架C中的某個節(jié)點作為提交數(shù)據(jù)的客戶端。本次實驗累計選取3 000個大小相同的數(shù)據(jù)塊，由Hadoop默認的備份數(shù)據(jù)存放策略可知，對于每一個數(shù)據(jù)塊，只有一個數(shù)據(jù)塊備份存放在本地一機架的節(jié)點之上，故另外4個機架(A,B,D,E)總共需要存放6 000個數(shù)據(jù)塊，本地機架(機架C)則需要存放3 000個數(shù)據(jù)塊。默認實驗初始時每個機架的每個數(shù)據(jù)節(jié)點上存放的數(shù)據(jù)塊數(shù)目為0。

對于默認的Hadoop備份數(shù)據(jù)存放策略，備份數(shù)據(jù)的分布情況如圖5(a)和(b)所示。對于改進的備份數(shù)據(jù)存放策略,指定系數(shù)分別為α1=0.5,α2=0.5，目標節(jié)點的數(shù)目固定為12，通過改進算法計算這12個節(jié)點的匹配度，選取其中匹配度最高的作為備份數(shù)據(jù)存放的節(jié)點，備份數(shù)據(jù)的分布情況如圖5(c)和(d)所示。

改進算法中考慮到節(jié)點間的距離，節(jié)點當前的負載情況，熱點失效備份數(shù)據(jù)三個因素，初始時節(jié)點當前的負載皆為0，熱點數(shù)據(jù)也還未有相關統(tǒng)計，故初始時距離機架C近的節(jié)點能夠獲得較大的評價值，因此更多的副本將會被存放在距離較近的節(jié)點上。通過采用改進備份策略算法可知，每一個存放在非機架C上的備份數(shù)據(jù)到節(jié)點C之間的距離大致為2.571 4，相對于默認的備份策略距離大致縮短了接近21.4%，同時由于后續(xù)對節(jié)點的評價是考慮到節(jié)點目前的負載情況，故節(jié)點獲得了更好的負載情況，節(jié)點間的備份數(shù)據(jù)數(shù)目之差不超過4，而采用默認備份策略時最高可達32。

(a)默認情況下各機架存放備份數(shù)據(jù)數(shù)目

(b)默認情況下各機架中各節(jié)點存放備份數(shù)據(jù)數(shù)目

(c)改進算法下各機架存放備份數(shù)據(jù)數(shù)目

(d)改進算法下各機架中各節(jié)點存放備份數(shù)據(jù)數(shù)目

當然，隨著改進算法的引入，隨之而來的負面影響則是選取目標節(jié)點時增加了時間損耗。通過分析改進算法可知，時間復雜度為O(n),其中n為實驗時設定的匹配節(jié)點數(shù)目。本次實驗中指定n=12。默認備份數(shù)據(jù)存放策略與改進備份數(shù)據(jù)存放策略對從接收到文件存儲請求直至文件存儲完畢所耗的時間可參見圖6。

圖6 默認算法與改進算法所耗時間對比

通過圖6可知，改進算法相比于默認算法平均需要多耗費357 ms，但相對于改進算法在數(shù)據(jù)恢復時所帶來的內(nèi)部帶寬的消耗減少，各節(jié)點分布備份數(shù)據(jù)更加均勻，基本可以忽略不計，故而改進算法確實提升了默認備份數(shù)據(jù)存放策略的性能，解決了默認備份數(shù)據(jù)存放策略所存在的問題。

5 結(jié)束語

基于節(jié)點目前的負載情況，節(jié)點間的距離以及失效的熱點備份數(shù)據(jù)，提出一種通過適當?shù)南禂?shù)來選擇最優(yōu)的備份數(shù)據(jù)存放節(jié)點的算法。該算法首先查詢目標節(jié)點集合是否達到預期數(shù)目，若未達到預期目標節(jié)點數(shù)則選取若干節(jié)點填充目標節(jié)點集，之后依次計算出每一個節(jié)點的匹配度，選取匹配度最大的節(jié)點作為備份數(shù)據(jù)的存放節(jié)點。實驗結(jié)果驗證了該算法的有效性。

默認備份數(shù)據(jù)存放策略的備份數(shù)據(jù)為3份，對于經(jīng)常需要訪問的數(shù)據(jù)塊(熱點數(shù)據(jù))降低了讀的性能，對于不需要經(jīng)常訪問的數(shù)據(jù)(冷卻數(shù)據(jù))則存在存儲空間的浪費，故而后續(xù)的研究將著重關注通過實現(xiàn)備份數(shù)據(jù)塊的數(shù)目的動態(tài)變化來提升HDFS的讀性能，降低默認備份數(shù)據(jù)存放策略存在的存儲空間的浪費。