吳 岳

(國(guó)家林業(yè)和草原局產(chǎn)業(yè)發(fā)展規(guī)劃院,北京 100010)

0 引言(Introduction)

大數(shù)據(jù)系統(tǒng)的作用是存儲(chǔ)和分析大量的數(shù)據(jù),同時(shí)確保數(shù)據(jù)的安全性和可訪問(wèn)性。大數(shù)據(jù)系統(tǒng)將數(shù)據(jù)存儲(chǔ)管理委托給分布式文件系統(tǒng)(DFS)執(zhí)行,例如Apache Hadoop的數(shù)據(jù)存儲(chǔ)基于Hadoop分布式文件系統(tǒng)(HDFS)[1]。Hadoop可以實(shí)現(xiàn)擴(kuò)展集群上的復(fù)雜計(jì)算,它的工作原理是將復(fù)雜的計(jì)算分布在多臺(tái)機(jī)器上,并且使計(jì)算靠近數(shù)據(jù),而不是將數(shù)據(jù)送至計(jì)算,最大限度地減少對(duì)網(wǎng)絡(luò)帶寬的占用,從而提高全局性能[2]。

HDFS的數(shù)據(jù)放置策略會(huì)將數(shù)據(jù)塊分條和復(fù)制,可在發(fā)生故障時(shí)盡可能地保護(hù)數(shù)據(jù)。該策略的數(shù)據(jù)保護(hù)原則是為相同數(shù)據(jù)創(chuàng)建多個(gè)副本,并將副本分布放置在多個(gè)機(jī)架的多臺(tái)計(jì)算機(jī)上。然而,該策略放置副本時(shí)沒(méi)有考慮到隨著時(shí)間變化,每個(gè)數(shù)據(jù)的被需求程度也會(huì)變化,有可能導(dǎo)致沒(méi)有發(fā)揮集群的最優(yōu)性能。本文通過(guò)深入研究Hadoop和HDFS的整體工作機(jī)制,提出一種綜合考慮需求和處理性能實(shí)現(xiàn)重新放置副本的算法,并通過(guò)實(shí)驗(yàn)證明,該算法可以將集群的處理性能提高20%以上。

1 Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System)

1.1 HDFS的架構(gòu)

HDFS的架構(gòu)由單個(gè)活動(dòng)的Master(Name Node)和多個(gè)Slave(Data Node)組成[3]。Name Node負(fù)責(zé)管理集群中Data Node的狀態(tài),并處理整個(gè)集群中的存儲(chǔ)分布。用戶的每次讀寫(xiě)操作都從向NameNode發(fā)起請(qǐng)求開(kāi)始[4]。文件系統(tǒng)元信息(包含數(shù)據(jù)塊定位)與數(shù)據(jù)塊分別存儲(chǔ)在NameNode和Data Node上,Name Node只是將用戶查詢的Data Node列表作為元數(shù)據(jù)塊傳輸給用戶,之后用戶在不重復(fù)讀取NameNode的情況下與Data Node通信。Name Node不參與用戶和Data Node之間的數(shù)據(jù)傳輸,這種方法簡(jiǎn)化了HDFS 的架構(gòu),避免了NameNode成為瓶頸[5]。

1.2 HDFS的復(fù)制

HDFS在復(fù)制過(guò)程中,將文件分成幾個(gè)大小相等的數(shù)據(jù)塊,這個(gè)操作稱為數(shù)據(jù)條帶化[6]。HDFS通過(guò)將這些數(shù)據(jù)塊存儲(chǔ)在不同DataNode上實(shí)現(xiàn)并行化數(shù)據(jù)訪問(wèn),從而縮短響應(yīng)時(shí)間。將每個(gè)數(shù)據(jù)塊復(fù)制成多個(gè)副本(默認(rèn)是3個(gè),可修改配置),并將每個(gè)副本存放在根據(jù)預(yù)定義策略確定的Data Node上[7]。這樣可以降低由于硬件發(fā)生故障導(dǎo)致數(shù)據(jù)丟失的風(fēng)險(xiǎn)。Data Node能通過(guò)心跳機(jī)制向NameNode匯報(bào)狀態(tài)信息,當(dāng)某個(gè)DataNode發(fā)生故障時(shí),NameNode可在其他DataNode上重構(gòu)該DataNode上的數(shù)據(jù)塊,保持每個(gè)數(shù)據(jù)塊的副本數(shù)量正常[8]。

副本的數(shù)量也稱為復(fù)制因子,由NameNode管理,可以隨時(shí)針對(duì)每個(gè)文件進(jìn)行單獨(dú)更改[9]。創(chuàng)建文件時(shí),NameNode會(huì)向用戶提供可以存儲(chǔ)該數(shù)據(jù)的Data Node列表,該列表包含N個(gè)DataNode,其中N是復(fù)制因子。用戶先將數(shù)據(jù)塊傳輸?shù)降谝粋€(gè)本地的Data Node,之后該Data Node將數(shù)據(jù)塊副本傳輸?shù)搅斜碇械牡诙€(gè)Data Node,第二個(gè)Data Node繼續(xù)傳輸副本,直到第N個(gè)Data Node,數(shù)據(jù)就像在一個(gè)管道中傳遞。

1.3 HDFS默認(rèn)的副本放置策略

HDFS通常被配置為由多個(gè)機(jī)架組成的集群,每個(gè)機(jī)架裝配有多個(gè)DataNode。不同機(jī)架之間的節(jié)點(diǎn)通信需要依靠交換機(jī)等網(wǎng)絡(luò)設(shè)備,所以同一機(jī)架節(jié)點(diǎn)之間的數(shù)據(jù)交換速度會(huì)快于不同機(jī)架中的節(jié)點(diǎn)。如果只考慮網(wǎng)絡(luò)帶寬的占用和數(shù)據(jù)訪問(wèn)時(shí)間,可以從同一個(gè)機(jī)架上選擇幾個(gè)Data Node存儲(chǔ)所有數(shù)據(jù)塊的副本,但是這樣的系統(tǒng)是脆弱的,如果該機(jī)架出現(xiàn)故障,則數(shù)據(jù)將會(huì)全部丟失。

HDFS在執(zhí)行數(shù)據(jù)塊寫(xiě)入操作時(shí),應(yīng)用了一種平衡故障風(fēng)險(xiǎn)和訪問(wèn)速度的策略。如果復(fù)制因子為3,第一個(gè)副本放置在與客戶端相同節(jié)點(diǎn)的Data Node上,第二個(gè)副本放置在同一個(gè)機(jī)架的另一個(gè)Data Node上,第三個(gè)副本放置在不同機(jī)架的DataNode上。如果復(fù)制因子大于3,第四個(gè)及后續(xù)的副本都隨機(jī)放置在集群中。這種策略可以在網(wǎng)絡(luò)、機(jī)架或交換機(jī)出現(xiàn)故障時(shí)提供更好的數(shù)據(jù)健壯性,并且優(yōu)化了寫(xiě)入時(shí)間,因?yàn)?/3的數(shù)據(jù)量是在同一機(jī)架間交換的(復(fù)制因子為3時(shí))。

這種策略存在一個(gè)問(wèn)題,它在確定放置副本的Data Node時(shí),沒(méi)有考慮對(duì)副本的訪問(wèn)需求,事實(shí)上在創(chuàng)建數(shù)據(jù)塊時(shí),第一個(gè)副本總是放置在靠近“寫(xiě)入者”的Data Node上。這種副本放置策略可能會(huì)因集群上數(shù)據(jù)分布不均而影響處理性能。本文提出一種分析副本需求的方法,并開(kāi)發(fā)一種綜合考慮需求和處理性能實(shí)現(xiàn)重新放置副本的算法。通過(guò)模擬實(shí)驗(yàn)表明,通過(guò)對(duì)集群操作中對(duì)副本的需求進(jìn)行分析后,將請(qǐng)求量最多的數(shù)據(jù)轉(zhuǎn)移到能夠最快處理它們的節(jié)點(diǎn)上,可以將處理性能顯著提高[10]。

2 算法設(shè)計(jì)(Algorithm design)

2.1 評(píng)估數(shù)據(jù)塊需求

在HDFS管理的數(shù)據(jù)塊元數(shù)據(jù)中增加2個(gè)元數(shù)據(jù)C和T C。在一段可配置時(shí)間(比如一個(gè)月)內(nèi),C是數(shù)據(jù)塊被查詢率,即某數(shù)據(jù)塊被下載的次數(shù);T C是該數(shù)據(jù)塊在這段時(shí)間內(nèi)的平均讀取時(shí)間。T C的計(jì)算公式參見(jiàn)公式(1)。其中,C是數(shù)據(jù)塊被查詢次數(shù),t i是數(shù)據(jù)塊第i次被查詢時(shí)的讀取時(shí)間。

Data Node在每次讀取操作后計(jì)算這些元數(shù)據(jù),并隨數(shù)據(jù)塊報(bào)告?zhèn)鬏斀oMaster。每當(dāng)一個(gè)數(shù)據(jù)塊被查詢時(shí),它相應(yīng)的C和T C都會(huì)更新。NameNode使用一個(gè)包含所有數(shù)據(jù)塊合并排序的數(shù)據(jù)表維護(hù)這兩個(gè)元數(shù)據(jù)值,示例詳見(jiàn)表1。

表1 數(shù)據(jù)塊需求統(tǒng)計(jì)示例表Tab.1 Sample table of data chunk requirement statistics

理想狀態(tài)下,統(tǒng)計(jì)表的每行應(yīng)該是按照最大的請(qǐng)求數(shù)C對(duì)應(yīng)最小的響應(yīng)時(shí)間T C有序排列的。然而,通過(guò)對(duì)從模擬集群中回調(diào)的數(shù)據(jù)進(jìn)行分析發(fā)現(xiàn),高請(qǐng)求率的數(shù)據(jù)塊響應(yīng)時(shí)間相對(duì)較長(zhǎng)。本文的目標(biāo)是將請(qǐng)求最多的數(shù)據(jù)塊移動(dòng)到能提供最優(yōu)讀取時(shí)間的節(jié)點(diǎn)中。利用元數(shù)據(jù)計(jì)算每個(gè)節(jié)點(diǎn)平均性能的方法詳見(jiàn)公式(2)。其中,P n是節(jié)點(diǎn)n的平均性能;k是節(jié)點(diǎn)n中數(shù)據(jù)塊的數(shù)量;Ci是節(jié)點(diǎn)n中第i個(gè)數(shù)據(jù)塊的被查詢次數(shù);是節(jié)點(diǎn)n中查詢第i個(gè)數(shù)據(jù)塊的平均讀取時(shí)間。

將數(shù)據(jù)塊移動(dòng)到具有更快讀取時(shí)間的位置,并不代表該數(shù)據(jù)塊的響應(yīng)時(shí)間會(huì)提高,因?yàn)槠骄憫?yīng)時(shí)間還取決于客戶端請(qǐng)求的性質(zhì)(如發(fā)起讀取請(qǐng)求的位置、數(shù)據(jù)處理性能等),但評(píng)估算法將繼續(xù)收集被移動(dòng)的數(shù)據(jù)塊在其新位置上的響應(yīng)時(shí)間,并重新評(píng)估是否需要將其移動(dòng)到更好的位置。在數(shù)據(jù)塊迭代進(jìn)行幾次移動(dòng)后,平均查詢時(shí)間會(huì)明顯提高或者停滯在其最小值,這表示數(shù)據(jù)塊在響應(yīng)時(shí)間方面已處于最佳位置。數(shù)據(jù)塊的移動(dòng)操作應(yīng)該在數(shù)據(jù)訪問(wèn)較少或沒(méi)有的時(shí)候進(jìn)行,這樣網(wǎng)絡(luò)帶寬就不會(huì)被該操作過(guò)度占用。

2.2 算法設(shè)計(jì)

優(yōu)化放置算法的流程:函數(shù)從最大查詢次數(shù)開(kāi)始掃描數(shù)據(jù)塊,查詢次數(shù)統(tǒng)計(jì)表,檢索出請(qǐng)求數(shù)量最多的數(shù)據(jù)塊。算法同時(shí)嘗試檢索具有最佳性能P n的可用節(jié)點(diǎn),在理想情況下,具有最高被查詢數(shù)C的數(shù)據(jù)塊將被移動(dòng)到具有最優(yōu)平均性能P n的節(jié)點(diǎn)上。

優(yōu)化放置算法步驟如下。第1步:讀取數(shù)據(jù)塊需求統(tǒng)計(jì)表chunks_Table(ChunkId,T C,C);第2步:按照C值對(duì)統(tǒng)計(jì)表進(jìn)行降序排序,得到表chunks_Ordred Table;第3步:按順序讀取chunks_Ordred Table中ChunkId;第4步:當(dāng)ChunkId不為空時(shí),循環(huán)執(zhí)行第5步,否則,執(zhí)行第6步;第5步:移動(dòng)數(shù)據(jù)塊至節(jié)點(diǎn)(ChunkId,Get Best Node(ChunkId));第6 步:返回null。

上述算法中調(diào)用了獲取最佳節(jié)點(diǎn)(Get Best Node)算法。這個(gè)算法可以為選定數(shù)據(jù)塊建議一個(gè)能夠提供最佳平均性能P n的節(jié)點(diǎn)。遍歷表中數(shù)據(jù)塊的平均查詢時(shí)間,為統(tǒng)計(jì)表中的每個(gè)節(jié)點(diǎn)計(jì)算P n值,并根據(jù)P n值升序排序,檢查每個(gè)節(jié)點(diǎn)是否與待放置數(shù)據(jù)塊的參數(shù)匹配。

基于以下四個(gè)標(biāo)準(zhǔn)判斷節(jié)點(diǎn)是否匹配,這些標(biāo)準(zhǔn)均符合Hadoop的基本策略,即同一機(jī)架中的副本不超過(guò)兩個(gè)。①該節(jié)點(diǎn)與待放置數(shù)據(jù)塊所在節(jié)點(diǎn)不是同一個(gè);②該節(jié)點(diǎn)有充足的可用空間;③該節(jié)點(diǎn)尚未存儲(chǔ)待放置數(shù)據(jù)塊的副本;④該節(jié)點(diǎn)與待放置數(shù)據(jù)塊的其他兩個(gè)副本都不在同一個(gè)機(jī)架中。

Get Best Node算法步驟如下。第1步:讀取待放置數(shù)據(jù)塊C m;第2步:讀取數(shù)據(jù)塊需求統(tǒng)計(jì)表chunks_Table(ChunkId,T C,C);第3步:計(jì)算chunks_Table中每個(gè)數(shù)據(jù)塊的P n值;第4步:按照P n值對(duì)統(tǒng)計(jì)表進(jìn)行升序排序得到表chunks_Ordred Table;第5 步:按順序讀取chunks_Ordred Table中ChunkId;第6步:循環(huán)選擇chunks_Ordred Table中下一個(gè)數(shù)據(jù)塊所在節(jié)點(diǎn)N;第7步:當(dāng)節(jié)點(diǎn)N的P n值小于C m的T C值且符合4個(gè)判斷標(biāo)準(zhǔn),返回節(jié)點(diǎn)N;第8步:循環(huán)結(jié)束。

3 實(shí)驗(yàn)與結(jié)果(Experiments and results)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中模擬了一個(gè)由12個(gè)節(jié)點(diǎn)組成的集群,結(jié)構(gòu)詳見(jiàn)圖1。使用Hadoop版本為2.5.0,Hadoop的數(shù)據(jù)塊配置為64 MB,復(fù)制因子為3。實(shí)驗(yàn)中使用12個(gè)大小為64 MB的文件模擬待處理數(shù)據(jù)。該集群由3個(gè)機(jī)架組成,每個(gè)機(jī)架由4個(gè)節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)的存儲(chǔ)容量等于數(shù)據(jù)塊的3倍,即192 MB。每個(gè)節(jié)點(diǎn)的性能是不同的,每個(gè)機(jī)架上4個(gè)節(jié)點(diǎn)的配置見(jiàn)表2。同一機(jī)架內(nèi)的帶寬設(shè)為1 GB/s,機(jī)架之間的帶寬配置見(jiàn)圖1。

圖1 實(shí)驗(yàn)?zāi)M集群結(jié)構(gòu)圖Fig.1 Cluster structure in experiment

表2 節(jié)點(diǎn)配置表Tab.2 Nodes configuration table

由于每個(gè)節(jié)點(diǎn)最多只能存儲(chǔ)三個(gè)數(shù)據(jù)塊,所以在實(shí)驗(yàn)中可以迅速使節(jié)點(diǎn)存儲(chǔ)達(dá)到飽和,便于更加準(zhǔn)確地測(cè)試算法的性能。

測(cè)試作業(yè)為集群中的12個(gè)節(jié)點(diǎn)對(duì)每一個(gè)均勻分布存儲(chǔ)在集群上的文件執(zhí)行不同數(shù)量的Map任務(wù)。每個(gè)作業(yè)只調(diào)用一個(gè)文件,因此被請(qǐng)求數(shù)C等于執(zhí)行的作業(yè)數(shù)。

實(shí)驗(yàn)步驟如下。第1步:在集群中按照Hadoop默認(rèn)放置策略存儲(chǔ)12個(gè)文件;第2步:運(yùn)行測(cè)試作業(yè);第3步:收集執(zhí)行時(shí)間,并創(chuàng)建/更新統(tǒng)計(jì)表;第4步:計(jì)算平均性能值P;第5步:如果P值不理想,使用算法找出數(shù)據(jù)塊的建議放置點(diǎn),否則,實(shí)驗(yàn)結(jié)束;第6步:移動(dòng)數(shù)據(jù)塊至建議放置點(diǎn),并由第2步開(kāi)始重新執(zhí)行。

上述步驟會(huì)迭代幾次,在每次迭代后都會(huì)計(jì)算集群的整體性能P n值。通過(guò)比較默認(rèn)副本放置策略和優(yōu)化后的放置算法的P值評(píng)估優(yōu)化算法的有效性。

3.2 試驗(yàn)結(jié)果

測(cè)試作業(yè)第一次運(yùn)行后收集的結(jié)果見(jiàn)表3。

表3 數(shù)據(jù)塊初始統(tǒng)計(jì)表Tab.3 Initial statistics table of data chunk

由于實(shí)驗(yàn)選用文件的大小與Hadoop數(shù)據(jù)塊配置相同,一個(gè)文件對(duì)應(yīng)一個(gè)數(shù)據(jù)塊,所以每個(gè)作業(yè)只調(diào)用一個(gè)文件,C是執(zhí)行作業(yè)的次數(shù),也就等于數(shù)據(jù)塊被請(qǐng)求數(shù)。將表4的數(shù)值代入公式(2)可以計(jì)算出集群的整體性能P1為25 594.86 ms,其中的T C值反映了Hadoop默認(rèn)放置策略下的平均讀取時(shí)間。

表4 數(shù)據(jù)塊建議放置位置表Tab.4 Recommended placement table of data chunks

應(yīng)用優(yōu)化的數(shù)據(jù)放置算法后,得到的數(shù)據(jù)塊放置建議見(jiàn)表4。算法建議將其中8個(gè)數(shù)據(jù)塊放置到新的位置,剩下的4個(gè)數(shù)據(jù)塊沒(méi)有建議新位置,因?yàn)閷⑺鼈兎胖玫疆?dāng)前集群中的任何可用節(jié)點(diǎn)都不會(huì)縮短任務(wù)執(zhí)行時(shí)間。

按照算法建議位置移動(dòng)數(shù)據(jù)塊后,再次運(yùn)行相同的測(cè)試任務(wù),重新計(jì)算的響應(yīng)時(shí)間T C,結(jié)果見(jiàn)表5。

表5 第一次重新放置后數(shù)據(jù)塊統(tǒng)計(jì)表Tab.5 Data chunks statistics table after the first replacement

將表5的數(shù)值代入公式(2)可以計(jì)算出集群的整體性能P2為20 125.21 ms,與集群初始整體性能P1相比,提高了21.37%。在執(zhí)行5次測(cè)試任務(wù)后,后4次的集群整體性能P值依次為20 125.21 ms、20 098.96 ms、20 964.57 ms、20 732.94 ms。由此可看出,在第一次執(zhí)行測(cè)試任務(wù)后,P值處于穩(wěn)定狀態(tài),之后的數(shù)據(jù)塊位置改變幾乎不會(huì)再影響集群的整體性能,那么,可以認(rèn)為數(shù)據(jù)塊在第一次執(zhí)行優(yōu)化算法后就被放置在了最佳位置。

4 結(jié)論(Conclusion)

實(shí)驗(yàn)數(shù)據(jù)證明,在符合HDFS默認(rèn)數(shù)據(jù)放置算法基本規(guī)則的前提下,提出的優(yōu)化的數(shù)據(jù)放置策略算法,可以使集群的整體性能提高20%以上。并且,該算法執(zhí)行一次即可使集群整體性能接近最優(yōu)值,不會(huì)因?yàn)閿?shù)據(jù)塊頻繁移動(dòng)而過(guò)多占用集群的網(wǎng)絡(luò)帶寬。實(shí)驗(yàn)結(jié)果符合預(yù)期,優(yōu)化后的數(shù)據(jù)塊放置算法能夠有效優(yōu)化集群整體性能。