吳 岳

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

0 引言(Introduction)

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

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

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

1.1 HDFS的架構(gòu)

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

1.2 HDFS的復(fù)制

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法設(shè)計

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

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

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

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

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

3 實驗與結(jié)果(Experiments and results)

3.1 實驗設(shè)置

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

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

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

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

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

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

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

3.2 試驗結(jié)果

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

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

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

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

應(yīng)用優(yōu)化的數(shù)據(jù)放置算法后,得到的數(shù)據(jù)塊放置建議見表4。算法建議將其中8個數(shù)據(jù)塊放置到新的位置,剩下的4個數(shù)據(jù)塊沒有建議新位置,因為將它們放置到當(dāng)前集群中的任何可用節(jié)點都不會縮短任務(wù)執(zhí)行時間。

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

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

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

4 結(jié)論(Conclusion)

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