Hadoop環(huán)境下節(jié)點(diǎn)負(fù)載均衡調(diào)度策略的設(shè)計(jì)與實(shí)現(xiàn)

王溪波 王珊珊 王越峰

（沈陽工業(yè)大學(xué) 遼寧省沈陽市 110000）

1 引言

云計(jì)算是用戶通過遠(yuǎn)程連接來獲取計(jì)算資源的一種計(jì)算方式，許多IT公司都推出相應(yīng)的云計(jì)算平臺，將云計(jì)算技術(shù)看成是一項(xiàng)重要的且有利于公司發(fā)展的技術(shù)，由此看出對云計(jì)算的研究是緊追IT技術(shù)的發(fā)展路線，有較高的應(yīng)用價(jià)值。但伴隨云計(jì)算技術(shù)的發(fā)展會涌現(xiàn)大量的數(shù)據(jù)，用戶和企業(yè)都會面臨海量數(shù)據(jù)的存儲與處理問題，分布式存儲模塊可以存儲海量數(shù)據(jù)，系統(tǒng)將大的數(shù)據(jù)塊拆分成若干小的數(shù)據(jù)塊，將這些小的數(shù)據(jù)塊存放在集群的各個節(jié)點(diǎn)上。云計(jì)算技術(shù)的重要典型框架是MapReduce框架，為海量數(shù)據(jù)的處理提供平臺。Hadoop是MapReduce框架的開源實(shí)現(xiàn)，既為海量數(shù)據(jù)的存儲提供了可靠的平臺-HDFS(Hadoop分布式文件系統(tǒng))[1]。又能夠很好地實(shí)現(xiàn)MapReduce框架，MapReduce框架為提高云計(jì)算平臺上的大批量作業(yè)的性能而設(shè)計(jì)的[2]。

2 Hadoop體系結(jié)構(gòu)

Hadoop是可靠的，可擴(kuò)展的和開放式的源代碼框架，由Apache基金會所開發(fā)。Hadoop系統(tǒng)本身具有高擴(kuò)展性，高效性以及高可靠性等特質(zhì)。分布式文件系統(tǒng)HDFS（Hadoop Distributed Files System）和分布式計(jì)算框架 MapReduce計(jì)算架構(gòu)屬于Apache Hadoop的兩個核心子模塊。

2.1 HDFS分布式文件系統(tǒng)

作為Hadoop集群的核心子項(xiàng)目之一的分布式并行文件系統(tǒng)是基于流數(shù)據(jù)訪問模式開發(fā)的，可用于分布式計(jì)算的數(shù)據(jù)存儲管理，也可以滿足超大規(guī)模文件處理的需求。HDFS將分好的數(shù)據(jù)塊存儲在各個節(jié)點(diǎn)上，對數(shù)據(jù)塊進(jìn)行備份，以防節(jié)點(diǎn)失效。HDFS只需一次寫入數(shù)據(jù)便可以多次使用該數(shù)據(jù)，這種訪問方式具有高效性[5]。在HDFS中，數(shù)據(jù)可用性可通過數(shù)據(jù)備份來實(shí)現(xiàn)。數(shù)據(jù)丟失將會立即采取修復(fù)措施[6]。

用戶需要在系統(tǒng)中運(yùn)行的應(yīng)用程序被稱為作業(yè)，任務(wù)作為作業(yè)的基本工作單元，各個計(jì)算節(jié)點(diǎn)可以處理任務(wù)，可以把一個作業(yè)分成一個或者多個任務(wù)[7]。這些任務(wù)處理完后被存儲在分布式文件系統(tǒng)中。

2.2 MapReduce計(jì)算框架

規(guī)模性，多樣性和高速性的特性促進(jìn)大數(shù)據(jù)更加快速的發(fā)展[8]。MapReduce是一種編程框架，支持高效的大規(guī)模計(jì)算，由Google提出。MapReduce架構(gòu)如圖1所示。

系統(tǒng)通常設(shè)計(jì)為在無共享架構(gòu)中運(yùn)行。數(shù)據(jù)可以分布式存儲，并通過并行使用多個磁盤來提高輸入/輸出速率。MapReduce計(jì)

圖1：MapReduce架構(gòu)示意圖

算框架依賴于Shuffle機(jī)制。Shuffle機(jī)制[9]的工作原理是把在Map任務(wù)中處理完的作業(yè)拉取到Reduce任務(wù)執(zhí)行之前。分塊，拷貝和排序代表Shuffle機(jī)制的每個不同的階段。MapReduce的主要目標(biāo)是分配處理以利用并行處理能力。這通常是通過將輸入數(shù)據(jù)集分割成若干塊在不同的機(jī)器上運(yùn)行來完成的。大型集群可以通過MapReduce框架進(jìn)行高效排序，在幾個小時內(nèi)達(dá)到對數(shù)兆字節(jié)的速度。

3 國內(nèi)外研究現(xiàn)狀

減少作業(yè)的完成時間和提高數(shù)據(jù)本地性是目前許多調(diào)度算法的研究重點(diǎn)。在基于節(jié)點(diǎn)本地任務(wù)完成時間預(yù)測的基礎(chǔ)上，通過控制不同的資源分配策略來提高數(shù)據(jù)本地性。現(xiàn)有算法對于作業(yè)缺乏整體性規(guī)劃。

估算一個作業(yè)的剩余完成時間方面，楊浩等人[10]設(shè)計(jì)并實(shí)現(xiàn)了一種基于空閑時間的硬實(shí)時調(diào)度器 LSS，根據(jù)作業(yè)的剩余完成時間來調(diào)整作業(yè)的優(yōu)先級，作業(yè)越快處理完優(yōu)先級越高。Teng等人[11]提出的基于截止時間的硬實(shí)時任務(wù)調(diào)度算法 SPS，該算法通過流工作的周期長短來規(guī)定作業(yè)的優(yōu)先級，同時盡量使作業(yè)在本地執(zhí)行，從而大大提高了作業(yè)在本地完成的幾率。Ullah等人[12]提出了一種新的搶占方法，該方法在進(jìn)行搶占決策時考慮了被執(zhí)行作業(yè)的剩余執(zhí)行時間。為了讓作業(yè)能在時間約束范圍內(nèi)執(zhí)行完，盧慧[13]提出一種基于資源預(yù)估的作業(yè)調(diào)度算法。不同作業(yè)對資源的需求也有所不同，根據(jù)資源預(yù)估模型以及數(shù)據(jù)本地性因素來改進(jìn)延遲調(diào)度策略。

表1：Map任務(wù)的平均運(yùn)行時間實(shí)現(xiàn)偽代碼

圖2：數(shù)據(jù)塊分布情況

圖3：非本地任務(wù)數(shù)量實(shí)驗(yàn)對比

現(xiàn)實(shí)中存在40%的重復(fù)性工作[14]，根據(jù)重復(fù)性工作規(guī)律探索出可預(yù)測的特征，可以對節(jié)點(diǎn)的預(yù)計(jì)完成時間進(jìn)行預(yù)測從而規(guī)劃資源分配，提高系統(tǒng)資源利用率。

4 數(shù)據(jù)本地化調(diào)度策略設(shè)計(jì)

數(shù)據(jù)本地性是Hadoop集群平臺下衡量作業(yè)調(diào)度器的重要的指標(biāo)。數(shù)據(jù)可以在同一機(jī)架內(nèi)傳輸，也可在不同的機(jī)架內(nèi)傳輸，這種跨機(jī)架的傳輸方式，產(chǎn)生網(wǎng)絡(luò) I/O，降低作業(yè)的平均完成時間，增加非本地任務(wù)的數(shù)量。節(jié)點(diǎn)優(yōu)先處理本地任務(wù)可以實(shí)現(xiàn)數(shù)據(jù)本地化，數(shù)據(jù)的讀取和處理便于任務(wù)的執(zhí)行。本地任務(wù)越多，數(shù)據(jù)讀取時間越短，非本地任務(wù)會加重?cái)?shù)據(jù)讀取時間，它需要從其它節(jié)點(diǎn)上讀取數(shù)據(jù)，加重網(wǎng)絡(luò)負(fù)擔(dān)，使節(jié)點(diǎn)間信息傳輸產(chǎn)生延遲。降低系統(tǒng)運(yùn)行效率。

數(shù)據(jù)分配不均會導(dǎo)致任務(wù)負(fù)載失衡，某些節(jié)點(diǎn)需要處理的任務(wù)增多，而其余節(jié)點(diǎn)會因沒有需要處理的任務(wù)處于空閑狀態(tài)。通過計(jì)算節(jié)點(diǎn)負(fù)載情況的任務(wù)調(diào)度方法來解決MapReduce集群存在大量非本地任務(wù)的問題，該方法先計(jì)算節(jié)點(diǎn)的負(fù)載情況，根據(jù)節(jié)點(diǎn)負(fù)載情況進(jìn)行調(diào)度，有利于數(shù)據(jù)塊的合理分配，讓節(jié)點(diǎn)間的負(fù)載處于中間狀態(tài)，這種根據(jù)節(jié)點(diǎn)的使用情況進(jìn)行任務(wù)分配的策略在很大程度上滿足了數(shù)據(jù)本地化思想。

如圖2表明數(shù)據(jù)塊在集群中的分布狀況。MapReduce在選擇任務(wù)進(jìn)行調(diào)度時，只是簡單的根據(jù)網(wǎng)絡(luò)拓?fù)湓谕壢蝿?wù)中隨機(jī)選取。這樣的選擇方式會造成更多非本地任務(wù)的產(chǎn)生,從而降低處理和存儲速度。通過計(jì)算節(jié)點(diǎn)負(fù)載進(jìn)行任務(wù)分配的方法可以盡可能的解決這一問題。

5 算法實(shí)現(xiàn)

在觀察節(jié)點(diǎn)負(fù)載情況時，并不能直接根據(jù)節(jié)點(diǎn)剩余任務(wù)數(shù)量來分配任務(wù)，節(jié)點(diǎn)性能不同，能處理的任務(wù)數(shù)量就不同，性能好的節(jié)點(diǎn)本身就能處理更多的本地任務(wù)。節(jié)點(diǎn)在作業(yè)執(zhí)行之初先不需要分配非本地任務(wù)，在執(zhí)行本地任務(wù)的過程中根據(jù)負(fù)載情況完成非本地任務(wù)的分配，這一過程是非靜態(tài)的。所以本文通過節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時間與全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時間的平均值做比較，小于平均值極為負(fù)載較輕的節(jié)點(diǎn)，反之較重。

節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時間是通過Map任務(wù)的平均運(yùn)行時間與所有的本地任務(wù)的數(shù)量的乘積計(jì)算得出的。代表已完成的Map任務(wù)的平均運(yùn)行時間，節(jié)點(diǎn)中本地任務(wù)的數(shù)量用表示，給節(jié)點(diǎn)分配的任務(wù)可能是本地任務(wù)和非本地任務(wù)，先通過本地任務(wù)數(shù)量的計(jì)算再進(jìn)行任務(wù)合理分配。如公式（2）所示。節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時間：

全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時間的平均值根據(jù)節(jié)點(diǎn)的本地任務(wù)預(yù)計(jì)完成時間的總值與節(jié)點(diǎn)的個數(shù)的比值計(jì)算得出。通過平均值與單個節(jié)點(diǎn)的預(yù)計(jì)完成時間我們可以觀察到節(jié)點(diǎn)的狀態(tài)。如公式（3）所示。全部節(jié)點(diǎn)執(zhí)行本地任務(wù)的預(yù)計(jì)完成時間的平均值：

6 實(shí)驗(yàn)設(shè)計(jì)

本文研究的作業(yè)調(diào)度算法是基于Hadoop平臺之下，因此需要搭建Hadoop集群。Hadoop集群的核心是HDFS和MapReduce計(jì)算框架。通過虛擬機(jī)的方式搭建Hadoop集群及其測試環(huán)境，假設(shè)存在兩個機(jī)架，給每個機(jī)架分配5臺虛擬機(jī)，每一個虛擬機(jī)占據(jù)512MB的內(nèi)存。測試工作為WordCount，通過測試傳統(tǒng)的任務(wù)調(diào)度策略非本地任務(wù)的數(shù)量以及平均完成時間和本文提出的負(fù)載均衡的任務(wù)調(diào)度策略中非本地任務(wù)的數(shù)量和平均完成時間進(jìn)行對比。

首先對兩種算法的非本地任務(wù)數(shù)量進(jìn)行對比實(shí)驗(yàn)，運(yùn)行job1，job2，job3和job4四個作業(yè)，非本地任務(wù)數(shù)量實(shí)驗(yàn)數(shù)據(jù)如圖3所示。默認(rèn)調(diào)度算法的作業(yè)中非本地任務(wù)數(shù)量分別是59，49，99和120。負(fù)載均衡的調(diào)度策略中非本地任務(wù)數(shù)量是43，33，85，109。由實(shí)驗(yàn)對比圖可以看出作業(yè)1非本地任務(wù)數(shù)量降低了27%，作業(yè)2的非本地任務(wù)數(shù)量降低了32%，作業(yè)3的非本地任務(wù)數(shù)量降低了14%，以及作業(yè)4的非本地任務(wù)數(shù)量降低了9%。綜上四個任務(wù)的非本地任務(wù)數(shù)量降低值可以預(yù)估每個任務(wù)的降低值。通過負(fù)載均衡調(diào)度算法可以看出非本地任務(wù)數(shù)量降低了20.5%。節(jié)點(diǎn)負(fù)載均衡調(diào)度策略可以減少系統(tǒng)中非本地任務(wù)的數(shù)量，同時減少數(shù)據(jù)遷移量，減少任務(wù)處理時間，提高系統(tǒng)效率。

其次，對兩種算法的平均完成時間進(jìn)行對比實(shí)驗(yàn)，默認(rèn)調(diào)度算法下job1 平均完成時間為700s，job2的平均完成時間為350s，job3的平均完成時間為460s以及job4的平均完成時間為653s。負(fù)載均衡調(diào)度策略中作業(yè)的平均完成時間分別為399，268，430，590。節(jié)點(diǎn)負(fù)載均衡的任務(wù)調(diào)度策略相比與系統(tǒng)默認(rèn)的調(diào)度策略有一定的縮短，平均完成時間實(shí)驗(yàn)數(shù)據(jù)如圖4所示。作業(yè)1的平均完成時間縮短了43%，作業(yè)2的平均完成時間縮短了23%，作業(yè)3的平均完成時間縮短了6%，作業(yè)4的平均完成時間縮短了9%。由多個個體可以估算出整體平均完成時間縮短了20.25%，通過實(shí)驗(yàn)證明節(jié)點(diǎn)負(fù)載調(diào)度策略降低了系統(tǒng)的平均完成時間，有效的優(yōu)化了系統(tǒng)性能。

通過對非本地任務(wù)數(shù)量以及平均完成時間的對比實(shí)驗(yàn)可以看出，負(fù)載均衡的任務(wù)調(diào)度策略比系統(tǒng)默認(rèn)的調(diào)度策略的非本地任務(wù)數(shù)量減少了，平均完成時間降低了，網(wǎng)絡(luò)I/O減少了，系統(tǒng)性能提高了。

圖4：作業(yè)的平均完成時間對比

7 結(jié)束語

本文主要提出對數(shù)據(jù)本地性調(diào)度方面進(jìn)行優(yōu)化，通過計(jì)算節(jié)點(diǎn)負(fù)載情況的方法來減少非本地任務(wù)的產(chǎn)生，從而減少數(shù)據(jù)遷移量。借助集群環(huán)境中MapReduce計(jì)算框架來實(shí)現(xiàn)根據(jù)節(jié)點(diǎn)情況分配任務(wù)的調(diào)度策略，提升系統(tǒng)性能。這種計(jì)算節(jié)點(diǎn)的調(diào)度算法仍存在一些不足，所以接下來，從這幾方面完善該任務(wù)調(diào)度策略。