李霞++柯琦

摘要：對Hadoop平臺(tái)下現(xiàn)有的調(diào)度算法進(jìn)行分析研究。在MapReduce計(jì)算模型下，針對Reduce階段的任務(wù)調(diào)度問題提出在異構(gòu)Hadoop環(huán)境下新的調(diào)度算法，算法在最大程度上提升 數(shù)據(jù)本地性的同時(shí)考慮各處理機(jī)節(jié)點(diǎn)的不同處理能力。對該算法進(jìn)行實(shí)驗(yàn)和性能分析，表明該算法在減少調(diào)度時(shí)間方面有較好的表現(xiàn)，同時(shí)可以適用于更加符合實(shí)際的異構(gòu)Hadoop機(jī)群系統(tǒng)中。

關(guān)鍵詞：Hadoop；MapReduce模型；任務(wù)調(diào)度

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）02-0144-02

1 引言

隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的發(fā)展，通過網(wǎng)絡(luò)進(jìn)行傳輸、處理的數(shù)據(jù)流急劇增加，這也給傳統(tǒng)的計(jì)算模式帶來極大的挑戰(zhàn)，在此情形下，云計(jì)算平臺(tái)以強(qiáng)大的計(jì)算機(jī)能力和低廉的實(shí)現(xiàn)代價(jià)得到了廣泛的應(yīng)用。MapReduce是Google在2004年提出的用于處理海量數(shù)據(jù)的一個(gè)高效的并行計(jì)算模型，這種模型向程序員屏蔽了復(fù)雜的內(nèi)部細(xì)節(jié)，并提供了簡單的編程接口，這樣大大縮短了分布式程序員的開發(fā)周期，因此得到廣泛應(yīng)用。而Hadoop作為MapReduce的開源實(shí)現(xiàn)，它提供了一個(gè)高可靠性、高容錯(cuò)性、良好的擴(kuò)展性的分布式文件系統(tǒng)，因此被諸多企業(yè)應(yīng)用于數(shù)據(jù)的存儲(chǔ)與處理中。MapReduce的任務(wù)調(diào)度算法對Hadoop平臺(tái)的性能有著非常重要的影響，但是，在實(shí)際環(huán)境中，MapReduce的任務(wù)調(diào)度依舊存在著不少的缺陷，因此許多學(xué)者與組織在此課題上做了不少的研究。

2 研究進(jìn)展分析

在Hadoop平臺(tái)中，機(jī)群節(jié)點(diǎn)數(shù)通常很多，因此，數(shù)據(jù)本地性是調(diào)度算法所要考慮的一個(gè)非常重要的指標(biāo)，因?yàn)閿?shù)據(jù)在網(wǎng)絡(luò)中傳輸需要時(shí)間，且在不同機(jī)架之間傳輸需要的時(shí)間更多，從而會(huì)導(dǎo)致作業(yè)的執(zhí)行周期變長，同時(shí)也會(huì)增加網(wǎng)絡(luò)傳輸?shù)拈_銷。

MateiZaharia等人提出的延遲調(diào)度算法（Delay Scheduler）是目前研究的熱點(diǎn)，該算法以犧牲公平性和響應(yīng)時(shí)間來最大限度的保證作業(yè)在本機(jī)節(jié)點(diǎn)上被執(zhí)行，并且設(shè)定一個(gè)時(shí)間閾值，在時(shí)間閾值內(nèi)，讓非本地任務(wù)進(jìn)行等待。因此，當(dāng)集群中大部分作業(yè)為小作業(yè)時(shí)，該算法可以大大提高數(shù)據(jù)本地性。針對該算法中時(shí)間閾值的設(shè)定，文獻(xiàn)[1]和文獻(xiàn)[2]通過節(jié)點(diǎn)負(fù)載量和節(jié)點(diǎn)釋放速度進(jìn)行分析，提出在運(yùn)行中自適應(yīng)調(diào)整時(shí)間閾值。以上研究都是提高M(jìn)ap階段數(shù)據(jù)的本地性。

綜上所述，許多研究學(xué)者為了提高Hadoop系統(tǒng)的各方面的性能，圍繞MapReduce作業(yè)調(diào)度算法進(jìn)行了大量的研究與改進(jìn)，然而，其中大部分對Reduce任務(wù)的調(diào)度算法的研究較少。同時(shí)，他們更多考慮的是機(jī)群中節(jié)點(diǎn)具有相同處理能力的同構(gòu)環(huán)境，從而限制了調(diào)度算法的應(yīng)用范圍。本文從提高數(shù)據(jù)本地性的角度出發(fā)，考慮更加符合實(shí)際應(yīng)用的異構(gòu)環(huán)境下的Reduce任務(wù)的調(diào)度算法。

3 MapReduce計(jì)算模型

在MapReduce計(jì)算模型下，把運(yùn)行于大規(guī)模集群上的復(fù)雜的并行計(jì)算過程高度的抽象為兩個(gè)函數(shù)：Map和Reduce。一個(gè)Map/Reduce作業(yè)（job）通常會(huì)把輸入的數(shù)據(jù)集劃分為若干獨(dú)立的數(shù)據(jù)塊，由Map任務(wù)以完全并行的方式處理它們?？蚣軙?huì)對Map輸出進(jìn)行排序，然后把結(jié)果輸入給Reduce任務(wù)。過程如圖1所示。

通常，Map/Reduce框架由一個(gè)單獨(dú)的Master JobTraker 和集群中節(jié)點(diǎn)上的Slave TaskTracker共同組成。Master節(jié)點(diǎn)負(fù)責(zé)調(diào)度構(gòu)成一個(gè)作業(yè)的所有任務(wù)，這些任務(wù)分布在不同的Slave節(jié)點(diǎn)上。Master監(jiān)控它們的執(zhí)行，并重新執(zhí)行已經(jīng)失敗的任務(wù)，而Slave節(jié)點(diǎn)負(fù)責(zé)執(zhí)行由Master指派的任務(wù)。

4 新的調(diào)度算法

然而，在執(zhí)行Reduce階段任務(wù)時(shí)，由于數(shù)據(jù)和Reduce（ ）可能處在不同的節(jié)點(diǎn)上，因此在通常情況下需要通過數(shù)據(jù)或者Reduce任務(wù)的轉(zhuǎn)移來實(shí)現(xiàn)數(shù)據(jù)的正常處理，為了避免在轉(zhuǎn)移時(shí)花費(fèi)巨大的網(wǎng)絡(luò)開銷和時(shí)間延遲，就要從根本上減少后期數(shù)據(jù)或Reduce任務(wù)的轉(zhuǎn)移，提高數(shù)據(jù)的本地性。

4.1 Map階段

由于本文考慮的是異構(gòu)機(jī)群系統(tǒng)，因此每個(gè)處理機(jī)節(jié)點(diǎn)的處理能力可能都不一樣，為了能夠減少任務(wù)調(diào)度時(shí)間，根據(jù)處理能力的高低來分配數(shù)據(jù)，處理能力強(qiáng)的節(jié)點(diǎn)分配更多的數(shù)據(jù)塊。這樣，處理能力強(qiáng)的計(jì)算機(jī)節(jié)點(diǎn)上在該階段結(jié)束后也會(huì)擁有更多的Map結(jié)果集，會(huì)減少Reduce階段數(shù)據(jù)的轉(zhuǎn)移。

4.2 Reduce階段

在該階段，由于Reduce任務(wù)所需要的數(shù)據(jù)塊分布在不同的處理機(jī)節(jié)點(diǎn)上，為了減少數(shù)據(jù)的轉(zhuǎn)移帶來的時(shí)間及網(wǎng)絡(luò)消耗，本文也盡量的將Reduce任務(wù)調(diào)度到擁有最多所需數(shù)據(jù)集的節(jié)點(diǎn)上運(yùn)行。

就Reduce任務(wù)何時(shí)開始執(zhí)行的問題，Hadoop中提供了一種開關(guān)機(jī)制，也就是當(dāng)Map任務(wù)執(zhí)行到一定程度（默認(rèn)是5%）的時(shí)候，同步執(zhí)行Reduce任務(wù)，這樣可以提高任務(wù)執(zhí)行的并行性，但是會(huì)降低數(shù)據(jù)的本地性。同時(shí)，由于Reduce任務(wù)一旦被啟動(dòng)就會(huì)占用資源，如果該任務(wù)的數(shù)據(jù)集斷斷續(xù)續(xù)被提供直到所有Map任務(wù)結(jié)束，這樣就會(huì)降低系統(tǒng)資源的利用率。如果這種開關(guān)機(jī)制關(guān)閉的話，則是當(dāng)所有的Map任務(wù)執(zhí)行結(jié)束后才開始執(zhí)行Reduce任務(wù)，這樣就可以清楚的知道每個(gè)Reduce任務(wù)所需的數(shù)據(jù)集所在的位置，通過向擁有最多所需數(shù)據(jù)集的節(jié)點(diǎn)轉(zhuǎn)移Reduce任務(wù)，可以提高數(shù)據(jù)的本地性。本文考慮開關(guān)機(jī)制關(guān)閉的情形。

在Map階段之后為每個(gè)Reduce任務(wù)建立列表，其中包含其所需的數(shù)據(jù)集所在的節(jié)點(diǎn)及數(shù)據(jù)量。然后依次對列表中的Reduce任務(wù)進(jìn)行調(diào)度，如果當(dāng)前Reduce任務(wù)所需最多的數(shù)據(jù)集所在的處理機(jī)節(jié)點(diǎn)的處理能力很低，還應(yīng)該要考慮更換節(jié)點(diǎn)。

為了便于描述，假設(shè)機(jī)群系統(tǒng)中共有N個(gè)處理機(jī)節(jié)點(diǎn)，它們的計(jì)算速度分別為P1，P2，P3...PN。當(dāng)前Reduce任務(wù)所需的數(shù)據(jù)集分布在P1，P2，...PM節(jié)點(diǎn)上（M<=N），這些節(jié)點(diǎn)上擁有該Reduce任務(wù)所需的數(shù)據(jù)量分別為L1，L2，...LM，數(shù)據(jù)在節(jié)點(diǎn)之間進(jìn)行傳輸?shù)乃俾蕿镾。

令：L=L1+L2+...+LM，則選擇P1節(jié)點(diǎn)進(jìn)行Reduce任務(wù)處理所需的時(shí)間為： ，選擇P2節(jié)點(diǎn)進(jìn)行Reduce任務(wù)處理所需的時(shí)間為：；即，選擇Pi（i=1，2...M）節(jié)點(diǎn)進(jìn)行Reduce任務(wù)處理所需要的時(shí)間為：（i=1，2...M）。

因此，將當(dāng)前的Reduce任務(wù)轉(zhuǎn)移到具有MIN（）值的處理機(jī)節(jié)點(diǎn)j上，同時(shí)將所需的其他數(shù)據(jù)集傳輸?shù)絡(luò)節(jié)點(diǎn)上。如果j節(jié)點(diǎn)上已經(jīng)有任務(wù)在處理，則要分兩種情形：如果j節(jié)點(diǎn)上任務(wù)處理還需要的時(shí)間比j節(jié)點(diǎn)和下一個(gè)MIN（）值的處理機(jī)節(jié)點(diǎn)k（k<>j）之間時(shí)間差值大，則選擇下一個(gè)節(jié)點(diǎn)，而對下一個(gè)節(jié)點(diǎn)的判斷和剛剛判斷的過程一致；否則選擇j節(jié)點(diǎn)，等現(xiàn)有的Reduce任務(wù)處理完，再繼續(xù)處理。

5 實(shí)驗(yàn)結(jié)果論證

本文通過在實(shí)際的異構(gòu)Hadoop機(jī)群系統(tǒng)上分別以Hadoop自帶的WordCount（單詞統(tǒng)計(jì)程序）、Terasort（字符串排序算法）為測試程序?qū)嵗?，所有的?shí)驗(yàn)在一臺(tái)Intel四核機(jī)器、兩臺(tái)聯(lián)想雙核機(jī)器、一臺(tái)聯(lián)想單核機(jī)器通過100Mbps以太網(wǎng)互連組成的異構(gòu)Hadoop機(jī)群系統(tǒng)上實(shí)現(xiàn)。各處理機(jī)節(jié)點(diǎn)運(yùn)行的操作系統(tǒng)均為CentOS6.4；編程語言為Java，版本jdk1.7；Hadoop版本為2.2.0。

（1）實(shí)驗(yàn)一：實(shí)驗(yàn)向系統(tǒng)提交Hadoop自帶的WordCount（單詞統(tǒng)計(jì)程序）作業(yè)，作業(yè)輸入的大小分別為2GB，4GB，8 GB。實(shí)驗(yàn)分別使用Hadoop自帶的Fair Scheduler（公平調(diào)度算法）和本文提出的調(diào)度算法分別執(zhí)行6次，統(tǒng)計(jì)了WordCount不同規(guī)模下整個(gè)任務(wù)執(zhí)行的時(shí)間，然后取得平均值，實(shí)驗(yàn)結(jié)果對比如圖2所示。

（2）實(shí)驗(yàn)二：實(shí)驗(yàn)向系統(tǒng)提交Hadoop自帶的Terasort（字符串排序算法）作業(yè)，作業(yè)輸入的大小分別為2GB，4GB，8 GB。實(shí)驗(yàn)分別使用Hadoop自帶的Fair Scheduler（公平調(diào)度算法）和本文提出的調(diào)度算法分別執(zhí)行6次，統(tǒng)計(jì)了Terasort不同規(guī)模下整個(gè)任務(wù)執(zhí)行的時(shí)間，然后取得平均值，結(jié)果對比如圖3所示。

通過兩個(gè)不同的程序?qū)嵗?，從?shí)際的實(shí)驗(yàn)結(jié)果可以看出，本文提出的調(diào)度算法在不同數(shù)據(jù)規(guī)模下均有較好的表現(xiàn)，因?yàn)樵谡{(diào)度的過程中充分考慮了處理機(jī)節(jié)點(diǎn)處理能力的不同，同時(shí)在Reduce任務(wù)轉(zhuǎn)移時(shí)考慮各處理機(jī)節(jié)點(diǎn)的數(shù)據(jù)集問題，從而最大程度減少數(shù)據(jù)的轉(zhuǎn)移所花費(fèi)的代價(jià)，進(jìn)而減少了任務(wù)調(diào)度時(shí)間。

6 結(jié)語

本文就MapReduce計(jì)算模型下Reduce任務(wù)的調(diào)度問題，針對異構(gòu)機(jī)群構(gòu)成的Hadoop平臺(tái)提出了新的調(diào)度算法，算法在考慮數(shù)據(jù)本地性的同時(shí)還考慮各個(gè)處理機(jī)節(jié)點(diǎn)的處理能力，最大程度減少調(diào)度長度，通過實(shí)驗(yàn)對調(diào)度算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明新的調(diào)度算法有著良好的調(diào)度效果。

參考文獻(xiàn)

[1]金嘉暉，羅軍舟，宋愛波，等.基于數(shù)據(jù)中心負(fù)載分析的自適應(yīng)延遲調(diào)度算法[J].通信學(xué)報(bào)，2011（7）：47-56.

[2]寧文瑜，吳慶波，譚郁松.面向MapReduce 的自適應(yīng)延遲調(diào)度算法[J].計(jì)算機(jī)工程與科學(xué)，2013（13）：53-57.