一種基于交互式的Hadoop作業(yè)調(diào)度算法

吳 佳，蘇 丹，李環(huán)媛，袁衛(wèi)國

(國網(wǎng)冀北電力有限公司信息通信分公司 信息通信工程中心,北京 100053)

一種基于交互式的Hadoop作業(yè)調(diào)度算法

吳 佳，蘇 丹，李環(huán)媛，袁衛(wèi)國

(國網(wǎng)冀北電力有限公司信息通信分公司 信息通信工程中心,北京 100053)

Hadoop平臺中作業(yè)調(diào)度是一個重要環(huán)節(jié)。FIFO是Hadoop默認的調(diào)度算法，簡單易實現(xiàn)且應(yīng)用廣泛，但其在數(shù)據(jù)的本地化(data locality)這一特性上考慮不足，會引起網(wǎng)絡(luò)的負載量增大，任務(wù)的等待執(zhí)行時間長，計算資源得不到充分利用等一系列弊端；同時Map階段和Reduce階段資源槽的靜態(tài)職能形式也更一步加深了這種缺陷。針對這些缺陷，從數(shù)據(jù)的本地性、任務(wù)分配的角度出發(fā)，提出了一種基于主從節(jié)點間交互的作業(yè)調(diào)度算法(Interactive Scheduler，IS)。該算法是對FIFO的一種改進，同時也使不同資源槽之間可以動態(tài)轉(zhuǎn)換，提高了資源的使用率。通過實驗對比，結(jié)果表明IS調(diào)度算法對Hadoop平臺的作業(yè)調(diào)度效率有顯著的提升。

Hadoop；MapReduce；交互式；slots資源槽；IS調(diào)度

0 引 言

隨著互聯(lián)網(wǎng)的高速發(fā)展及用戶量的迅速增長，數(shù)據(jù)量的產(chǎn)生速度也呈現(xiàn)出爆炸性增長，使得大數(shù)據(jù)成為時下的熱門搜索詞。面對越來越龐大的數(shù)據(jù)量，傳統(tǒng)的大機器的處理方式顯得越來越力不從心。隨著軟件技術(shù)的飛速發(fā)展，分布式計算的概念再一次被提上日程。它是一種低成本、高效率的處理方式，通過將大量廉價的PC彼此連接起來組成集群的方式進行海量數(shù)據(jù)的存儲與分析。簡單地說它是一種在數(shù)據(jù)處理領(lǐng)域從“猛虎到群狼”的策略的轉(zhuǎn)變。在眾多的分布式處理平臺中，Apache Hadoop[1]無疑是目前最活躍、應(yīng)用最廣泛的一個，同時也是Apache Software Foundation下的開源項目之一。Hadoop平臺對開發(fā)者隱藏了底層的實現(xiàn)細節(jié)。在此平臺上，只需考慮算法的本身而不用關(guān)注平臺的底層實現(xiàn)。用戶只需要根據(jù)自己的需求編寫Map和Reduce函數(shù)就可實現(xiàn)分布式的應(yīng)用。因此，眾多的云計算運營商及Hadoop愛好者積極投入到Hadoop的陣營中，也使得Hadoop的用戶數(shù)和活躍度在不停攀升。

Hadoop中有三種調(diào)度方法：FIFO Scheduler[2]、Fair Scheduler[3]、Capacity Scheduler[4]。其中默認的調(diào)度算法是FIFO。Fair Scheduler和Capacity Scheduler都是基于多用戶、公平性的調(diào)度器，區(qū)別只是在調(diào)度策略上有所不同。Capacity Scheduler是Yahoo公司開發(fā)的一種基于計算能力的調(diào)度算法,它以隊列的形式分配資源,通過對內(nèi)存的約束來限制每個用戶占用的資源數(shù)；Fair Scheduler由Facebook公司開發(fā),為了保證公平性，該算法采用資源池的形式組織作業(yè)，具有小作業(yè)快速響應(yīng)、大作業(yè)確保性能的特點。FIFO是一種批處理調(diào)度器，所有的作業(yè)被提交到一個作業(yè)隊列，依照先來后到的順序?qū)⒚總€作業(yè)切分成不同的任務(wù)，再依次對任務(wù)進行調(diào)度。

FIFO調(diào)度算法的優(yōu)點很明顯：簡單易實現(xiàn)，對JobTracker的負擔(dān)?。坏泊嬖诤芏嗖蛔悖喝蝿?wù)分配時只是盡量保持本地性，任務(wù)槽是面向職能而非作業(yè)。因此，眾多學(xué)者試圖從各個方面對此進行改進。文獻[5]提出的一種調(diào)度算法考慮了當(dāng)任務(wù)調(diào)度器不能選擇Data-local任務(wù)時是否允許分配Non-Local任務(wù)；文獻[6-7]提出了一種基于Map任務(wù)節(jié)點數(shù)量和數(shù)據(jù)片復(fù)制模式的Map任務(wù)選擇的調(diào)度算法；Delay Scheduler[8-10]解決了由非本地數(shù)據(jù)作業(yè)調(diào)度引起的局部性問題；Dynamic Proportional Scheduler[11-13]支持用戶優(yōu)先級的改變,通過計算動態(tài)為用戶按比例分配任務(wù)；文獻[14]提出了一種基于截止時間的實時調(diào)度算法；文獻[15]提出了一種在異構(gòu)環(huán)境下基于MapReduce任務(wù)調(diào)度改進機制；文獻[16]提出了基于改進遺傳算法的Hadoop作業(yè)調(diào)度；文獻[17]解決了短作業(yè)執(zhí)行性能優(yōu)化。但是這些算法都沒能兼顧任務(wù)分配時數(shù)據(jù)的本地化特性及TaskTracker節(jié)點在任務(wù)分配中的能動性?；诖?，文中提出了一種基于交互式的調(diào)度算法(Interactive Scheduler)——IS調(diào)度算法。

1 IS調(diào)度算法的相關(guān)定義

傳輸時間：DataNode節(jié)點將數(shù)據(jù)片(split)從當(dāng)前節(jié)點傳輸?shù)降却龍?zhí)行任務(wù)的節(jié)點所需的時間，用t1表示，則：

(1)

其中，s表示數(shù)據(jù)塊的大?。籿表示交換機的傳輸速率。

等待時間：TaskTracker節(jié)點處于執(zhí)行狀態(tài)的任務(wù)的剩余執(zhí)行時間，用t2表示，則：

t2=MAX{T1,T2,…,TN}(1-w)

(2)

其中，考慮到不同任務(wù)之間的差異性，MAX{T1,T2,…,TN}表示該TaskTracker節(jié)點執(zhí)行隊列中執(zhí)行時間的最大值；w表示當(dāng)前任務(wù)完成百分比。

Slot資源槽是MapReduce中執(zhí)行任務(wù)的基本單位。默認的配置中每個節(jié)點分配2個mapslot和1個reduceslot，且mapslot只負責(zé)執(zhí)行map任務(wù)，reduceslot只負責(zé)執(zhí)行reduce任務(wù)。slot的數(shù)量可在一定程度上代表集群的計算規(guī)模。

有效slot：map或者reduce任務(wù)中處于執(zhí)行狀態(tài)下的slot數(shù)量。假設(shè)集群A中節(jié)點數(shù)量為n，那么默認有效mapslot的數(shù)量Qm∈[0,2n]，有效reduceslot的數(shù)量Qr∈[0,n]。

有效slot率：map或者reduce任務(wù)中處于執(zhí)行狀態(tài)下的slot數(shù)量與集群中對應(yīng)總slots的比值，其中：

(3)

(4)

其中，lm表示map任務(wù)的有效執(zhí)行率；lr表示reduce任務(wù)的有效執(zhí)行率；Qm和Qr分別表示集群中mapslot或者reduceslot的總數(shù)。

2 IS調(diào)度算法

2.1 IS調(diào)度算法的設(shè)計目標(biāo)

FIFO調(diào)度策略是作業(yè)按到達的順序依次排序等候調(diào)度。被調(diào)度的作業(yè)被切分成任務(wù)片依次被分配到TaskTracker節(jié)點執(zhí)行。等到這個作業(yè)全部執(zhí)行完才進行下一作業(yè)的調(diào)度。整個過程是一個串行的過程。因此存在以下弊端：

(1)任務(wù)片被分配到TaskTracker節(jié)點執(zhí)行時，不一定能夠保證數(shù)據(jù)的本地性,而執(zhí)行非本地性任務(wù)需要通過網(wǎng)絡(luò)拷貝數(shù)據(jù)，這樣會加重網(wǎng)絡(luò)的負載。

(2)由于機器處理速度的差異性、任務(wù)的不確定性、資源的靜態(tài)分配等，一部分機器在處理完map任務(wù)后處于等待狀態(tài)，這對計算資源是一種浪費。

據(jù)此，提出的交互式調(diào)度算法的主要目標(biāo)是對JobTracker和TaskTracker間主從結(jié)構(gòu)的一種改進，充分發(fā)揮TaskTracker節(jié)點在任務(wù)分配中的能動性，旨在對于TaskTracker節(jié)點中不具有數(shù)據(jù)本地性的任務(wù)，通過與JobTracker節(jié)點的交互協(xié)商的方式，選擇最佳的任務(wù)分配給該TaskTracker節(jié)點；其次在集群初始化時，資源槽全部設(shè)置為map slot，而對reduce slot的初始值設(shè)置為0，在任務(wù)的執(zhí)行過程中由map slot動態(tài)轉(zhuǎn)換為reduce slot。這樣一方面可以有效減少map階段產(chǎn)生的中間數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸量，另一方面也提升了資源的利用率。

2.2 HDFS與IS的結(jié)合

由于HDFS在存放副本時對數(shù)據(jù)的容錯性與可靠性進行了充分的考慮，因此，在IS算法中要充分利用這一特性來達到調(diào)度目標(biāo)。同時為了避免跨數(shù)據(jù)塊(block)的任務(wù)，Map任務(wù)片(split)的大小要與HDFS數(shù)據(jù)塊的大小保持一致。假定在圖1所示的網(wǎng)絡(luò)環(huán)境中，有Rack1、Rack2兩個機架通過交換機1和交換機2互聯(lián)，采用HDFS默認的存儲策略，數(shù)據(jù)塊布局會隨著節(jié)點的意外失效和負載均衡動態(tài)改變。在IS算法中，當(dāng)數(shù)據(jù)不具有本地化特性時，會對存儲該數(shù)據(jù)的最“鄰近”節(jié)點在數(shù)據(jù)塊傳輸時間和等待時間兩方面的大小進行權(quán)衡。在此對這種“鄰近”節(jié)點有一個距離上的定義。

圖1 集群拓撲圖

在保證不失一般性的前提下，依默認存儲規(guī)則任選三個節(jié)點。在此取n1,n5,n10三個節(jié)點，數(shù)據(jù)塊D在這三個節(jié)點均有備份。d表示連點間的距離。則有：

其中，0表示同一節(jié)點中不同進程間的距離；1表示同一機架間節(jié)點的距離；2表示不同機架間節(jié)點的距離。

JobTracker在對鄰近節(jié)點權(quán)衡時以距離為依據(jù)從大到小依次選取。

2.3 IS調(diào)度算法的數(shù)據(jù)流程

數(shù)據(jù)從Input到Output要經(jīng)過4個過程：

(1)從Input到Map階段存在數(shù)據(jù)本地性的問題。若數(shù)據(jù)分片在當(dāng)前TaskTracker節(jié)點有備份且被分配到該節(jié)點執(zhí)行，這是一種最優(yōu)的情況；否則轉(zhuǎn)下步。

(2)若該task被分配到其他不存在備份數(shù)據(jù)的節(jié)點，則計算“鄰近”節(jié)點等待時間和傳輸時間。當(dāng)“鄰近”節(jié)點的等待時間小于傳輸時間，則為“鄰近”節(jié)點保留此數(shù)據(jù)塊，等待當(dāng)前任務(wù)完成后進行下次調(diào)用。否則數(shù)據(jù)塊傳輸?shù)疆?dāng)前等待分配任務(wù)的節(jié)點。

(3)如果上述條件都不滿足，則認為作業(yè)進程已進入到Reduce階段。期間map slot轉(zhuǎn)化為reduce slot會處理flush到本地磁盤的中間數(shù)據(jù)及RPC到本地的數(shù)據(jù)。

(4)最終所有節(jié)點完全進入Reduce階段，處理Reduce任務(wù)及輸出操作。

數(shù)據(jù)的整體流程圖如圖2所示。

圖2 MapReduce數(shù)據(jù)流程圖

2.4 IS的執(zhí)行流程

JobTracker與TaskTracker之間依據(jù)數(shù)據(jù)的本地性采取一種協(xié)調(diào)的方式分配任務(wù)。首先先試探性地按FIFO的順序分配，在TaskTracker節(jié)點不滿足本地性的情況下反饋回JobTracker節(jié)點調(diào)整再分配，而不是一次性地根據(jù)請求的次序依次分配任務(wù)。流程圖如圖3所示。

圖3 調(diào)度流程圖

執(zhí)行步驟：

(1)TaskTracker節(jié)點接到任務(wù)后，首先判斷任務(wù)對應(yīng)的數(shù)據(jù)塊是否存在，若存在則直接執(zhí)行；否則轉(zhuǎn)下步。

(2)TaskTracker通過心跳把信息反饋回JobTracker節(jié)點。JobTracker節(jié)點會依據(jù)數(shù)據(jù)本地性在JobQueue中重新選擇任務(wù)。若存在則直接分配執(zhí)行；否則轉(zhuǎn)下步。

(3)JobTracker節(jié)點會依據(jù)距離選擇最“鄰近”節(jié)點計算等待時間與傳輸時間。若傳輸時間小于等待時間，則傳輸數(shù)據(jù)執(zhí)行任務(wù)，否則轉(zhuǎn)下步。

(4)上述條件都不滿足時說明當(dāng)前Job的任務(wù)片正在執(zhí)行態(tài)或即將被執(zhí)行?？傮w上Job處于即將完成map階段的時期，此時閑置的map slot轉(zhuǎn)換為reduce slot來執(zhí)行reduce任務(wù)。

(5)所有任務(wù)執(zhí)行完成，等待下一作業(yè)的到來進行重新的調(diào)度分配。

3 實 驗

首先用有效slot和有效slot率預(yù)估FIFO算法與IS算法之間的優(yōu)劣。從經(jīng)驗中表明FIFO的有效map slot率與集群的規(guī)模有關(guān)且是一種反比關(guān)系；IS調(diào)度算法是在FIFO的基礎(chǔ)上著重考慮數(shù)據(jù)的本地性及資源槽的動態(tài)性，因此slot率基本會在一個較高的范圍內(nèi)波動，且在Map階段和Reduce階段有一定的并發(fā)，一定程度上會縮短任務(wù)的執(zhí)行時間。

實驗環(huán)境是由9個節(jié)點組成的Hadoop集群。采用Hadoop1.1.2版本。測試數(shù)據(jù)由RandomWriter隨機生成。其中主節(jié)點和四個從節(jié)點在一臺宿主機中，其余四個節(jié)點在另一臺宿主機中。兩臺宿主機通過千兆交換機互聯(lián)。

通過slave節(jié)點的有效slot數(shù)量、總體執(zhí)行時間及CPU的利用率對兩種算法進行對比。在一個確定的集群中，有效slot率是由有效slot數(shù)量確定的。因此只需要取有效slot數(shù)量一個參數(shù)進行對比。

集群中每個slave節(jié)點上運行的TaskTracker通過相關(guān)的“/proc/stat”命令在預(yù)設(shè)時間段監(jiān)控CPU的狀態(tài)?！?proc/stat”中顯示了所有CPU及每個CPU的所有活動信息。在此取其中的I/O等待時間信息iowait并采集樣點對CPU的使用率進行計算。對于不同的數(shù)據(jù)分片設(shè)置不同的閾值。當(dāng)I/O等待時間超過指定的閾值，認為此時的數(shù)據(jù)處于傳輸中；否則就認為是有效的slot。

圖4為在處理同一任務(wù)中兩種算法的有效slot的數(shù)量概圖?？傮w上IS的有效slot數(shù)量是多于FIFO的，但兩者間的差距不大。這是因為節(jié)點的數(shù)量比較少，即使按順序依次分配也會有很大的概率選中具有數(shù)據(jù)本地性的節(jié)點；但是在節(jié)點較多的集群上，隨著這種概率的降低，IS算法的優(yōu)勢才能體現(xiàn)得更好，兩者間的差距才能拉大；同時，還可以看出IS的結(jié)束時間比FIFO提前，這也在一定程度上體現(xiàn)了算法的優(yōu)勢。

圖5是對同樣數(shù)據(jù)量完成時間的測試的歸一化表示。首先，在執(zhí)行時間上顯然是IS快于FIFO；另一方面可以看出，隨著數(shù)據(jù)量的增大執(zhí)行時間差呈增大的趨勢，這同時也說明了算法在大數(shù)據(jù)量上的優(yōu)勢。

圖5 不同數(shù)據(jù)量執(zhí)行時間對比圖

4 結(jié)束語

文中提出了一種交互式作業(yè)調(diào)度算法(IS)，該算法在主從節(jié)點之間以一種交互機制來最大化數(shù)據(jù)的本地性，減少網(wǎng)絡(luò)中數(shù)據(jù)的傳輸量，加快任務(wù)的完成速度，是對FIFO算法的一種優(yōu)化改進，對作業(yè)調(diào)度中任務(wù)執(zhí)行時間有很大提升。但該算法還有一些瑕疵，幾個參數(shù)計算式在精確度上難以把握，會在一定程度上影響任務(wù)的分配；同時過多的權(quán)衡計算也加大了主節(jié)點的工作量。這是下一步研究的重點。

[1] ApacheHadoop.Hadoop[EB/OL].2015-12-28.http://hadoop.apache.org.

[2] He C, Lu Y, Swanson D. Matchmaking:a new MapReduce scheduling technique[C]//Proceedings of IEEE third international conference on cloud computing technology and science.[s.l.]:IEEE,2011:40-47.

[3] Zaharia M,Borthakur D,Sarma J S,et al.Job scheduling for multi-user mapreduce clusters[R].Berkeley:University of California,2009.

[4] Raj A,Kaur K,Dutta U,et al.Enhancement of Hadoop clusters with virtualization using the capacity scheduler[C]//Third international conference on services in emerging markets.[s.l.]:IEEE,2012:50-57.

[5] Zhang Xiaohong,Feng Yuhong,Feng Shengzhong,et al.An effective data locality aware task scheduling method for MapRe-duceframeworkinheterogeneousenvironments[C]//Proceedingsofinternationalconferenceoncloudandservicecomputing.HongKong:IEEE,2011:235-242.

[6]IbrahimS,JinH,LuL,etal.Maestro:replica-awaremapschedulingformapreduce[C]//Proceedingsof12thIEEE/ACMinternationalsymposiumoncluster,cloudandgridcomputing.Ottawa,Canada:IEEE,2012:435-442.

[7] 鄭曉薇,項 明,張大為,等.基于節(jié)點能力的Hadoop集群任務(wù)自適應(yīng)調(diào)度方法[J].計算機研究與發(fā)展,2014,51(3):618-626.

[8]ZahariaM,BorthakurD,SenSarmaJ,etal.Delayscheduling:asimpletechniqueforachievinglocalityandfairnessinclusterscheduling[C]//Proceedingsofthe5thEuropeanconferenceoncomputersystems.NewYork,NY,USA:ACM,2010:265-278.

[9] 李麗英,唐 卓,李仁發(fā).基于LATE的Hadoop數(shù)據(jù)局部性改進調(diào)度算法[J].計算機科學(xué),2011,38(11):67-70.

[10] 寧文瑜,吳慶波,譚郁松.面向MapReduce的自適應(yīng)延遲調(diào)度算法[J].計算機工程與科學(xué),2013,35(3):52-57.

[11]SandholmT,LaiK.DynamicproportionalshareschedulinginHadoop[C]//Jobschedulingstrategiesforparallelprocessing.Berlin:Springer,2010:110-131.

[12] 鄒偉明,于 炯,英昌甜,等.基于動態(tài)等待時間閾值的延遲調(diào)度算法[J].計算機應(yīng)用研究,2012,29(11):4073-4078.

[13]KurazumiS,TsumuraT,SaitoS,etal.DynamicprocessingslotsschedulingforI/OintensivejobsofHadoopMapReduce[C]//Proceedingsofthethirdinternationalconferenceonnetworkingandcomputing.[s.l.]:[s.n.],2012:288-292.

[14]KcK,AnyanwuK.SchedulingHadoopjobstomeetdeadlines[C]//Proceedingsofthe2ndIEEEinternationalconferenceoncloudcomputingtechnologyandscience.[s.l.]:IEEE,2012:388-392.

[15] 何 翔,李仁發(fā),唐 卓.一種異構(gòu)環(huán)境下的基于MapReduce任務(wù)調(diào)度改進機制[J].計算機應(yīng)用研究,2013,30(11):3370-3373.

[16] 徐 肖,胡吉明.一種Hadoop中基于改進遺傳算法的作業(yè)調(diào)度算法[J].計算機技術(shù)與發(fā)展,2013,23(3):10-13.

[17] 顧 榮,嚴(yán)金雙,楊曉亮,等.HadoopMapReduce短作業(yè)執(zhí)行性能優(yōu)化[J].計算機研究與發(fā)展,2014,51(6):1270-1280.

An Job Scheduling Algorithm for Hadoop Based on Interaction

WU Jia,SU Dan,LI Huan-yuan,YUAN Wei-guo

(Center of Information and Communication Engineering,State Grid Jibei Information &Telecommunication Company,Beijing 100053,China)

Job scheduling is an important part of Hadoop.FIFO,as a scheduling algorithm by Hadoop,is simple and easy to achieve and widely used,but it is lack of consideration in the characteristic of data locality,that will cause network transmission increased and task waiting long execution time and computing resources cannot be fully utilized and a series of drawbacks.Meanwhile the static function of resource slots in Map and Reduce stages further increases the defects.So a job scheduling algorithm (Interactive Scheduler,IS) based on interacting the master node and slave nodes from the data locality and tasks allocation is proposed,which is improvement for FIFO,and realizes the dynamic conversion of map slots and reduce slots,and increases the usage of resources.Through the comparison of experiment,it proves that the IS has a great improvement in job scheduling for Hadoop.

Hadoop;MapReduce;interaction;slots;IS scheduling

2016-01-29

2016-05-13

時間：2016-10-24

國家發(fā)改委高科技產(chǎn)業(yè)化項目(發(fā)改高技[2009]1365號)

吳 佳(1986-),女,工程師，碩士,研究方向為分布式系統(tǒng)、中間件。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1117.070.html

TP393

A

1673-629X(2016)11-0045-04

10.3969/j.issn.1673-629X.2016.11.010