基于Hadoop平臺的MapReduce模型任務調度算法的研究與改進

李霞++柯琦

摘要：對Hadoop平臺下現有的調度算法進行分析研究。在MapReduce計算模型下，針對Reduce階段的任務調度問題提出在異構Hadoop環境下新的調度算法，算法在最大程度上提升 數據本地性的同時考慮各處理機節點的不同處理能力。對該算法進行實驗和性能分析，表明該算法在減少調度時間方面有較好的表現，同時可以適用于更加符合實際的異構Hadoop機群系統中。

關鍵詞：Hadoop；MapReduce模型；任務調度

中圖分類號：TP311.13 文獻標識碼：A 文章編號：1007-9416（2017）02-0144-02

1 引言

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

2 研究進展分析

在Hadoop平臺中，機群節點數通常很多，因此，數據本地性是調度算法所要考慮的一個非常重要的指標，因為數據在網絡中傳輸需要時間，且在不同機架之間傳輸需要的時間更多，從而會導致作業的執行周期變長，同時也會增加網絡傳輸的開銷。

MateiZaharia等人提出的延遲調度算法（Delay Scheduler）是目前研究的熱點，該算法以犧牲公平性和響應時間來最大限度的保證作業在本機節點上被執行，并且設定一個時間閾值，在時間閾值內，讓非本地任務進行等待。因此，當集群中大部分作業為小作業時，該算法可以大大提高數據本地性。針對該算法中時間閾值的設定，文獻[1]和文獻[2]通過節點負載量和節點釋放速度進行分析，提出在運行中自適應調整時間閾值。以上研究都是提高Map階段數據的本地性。

綜上所述，許多研究學者為了提高Hadoop系統的各方面的性能，圍繞MapReduce作業調度算法進行了大量的研究與改進，然而，其中大部分對Reduce任務的調度算法的研究較少。同時，他們更多考慮的是機群中節點具有相同處理能力的同構環境，從而限制了調度算法的應用范圍。本文從提高數據本地性的角度出發，考慮更加符合實際應用的異構環境下的Reduce任務的調度算法。

3 MapReduce計算模型

在MapReduce計算模型下，把運行于大規模集群上的復雜的并行計算過程高度的抽象為兩個函數：Map和Reduce。一個Map/Reduce作業（job）通常會把輸入的數據集劃分為若干獨立的數據塊，由Map任務以完全并行的方式處理它們。框架會對Map輸出進行排序，然后把結果輸入給Reduce任務。過程如圖1所示。

通常，Map/Reduce框架由一個單獨的Master JobTraker 和集群中節點上的Slave TaskTracker共同組成。Master節點負責調度構成一個作業的所有任務，這些任務分布在不同的Slave節點上。Master監控它們的執行，并重新執行已經失敗的任務，而Slave節點負責執行由Master指派的任務。

4 新的調度算法

然而，在執行Reduce階段任務時，由于數據和Reduce（ ）可能處在不同的節點上，因此在通常情況下需要通過數據或者Reduce任務的轉移來實現數據的正常處理，為了避免在轉移時花費巨大的網絡開銷和時間延遲，就要從根本上減少后期數據或Reduce任務的轉移，提高數據的本地性。

4.1 Map階段

由于本文考慮的是異構機群系統，因此每個處理機節點的處理能力可能都不一樣，為了能夠減少任務調度時間，根據處理能力的高低來分配數據，處理能力強的節點分配更多的數據塊。這樣，處理能力強的計算機節點上在該階段結束后也會擁有更多的Map結果集，會減少Reduce階段數據的轉移。

4.2 Reduce階段

在該階段，由于Reduce任務所需要的數據塊分布在不同的處理機節點上，為了減少數據的轉移帶來的時間及網絡消耗，本文也盡量的將Reduce任務調度到擁有最多所需數據集的節點上運行。

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

在Map階段之后為每個Reduce任務建立列表，其中包含其所需的數據集所在的節點及數據量。然后依次對列表中的Reduce任務進行調度，如果當前Reduce任務所需最多的數據集所在的處理機節點的處理能力很低，還應該要考慮更換節點。

為了便于描述，假設機群系統中共有N個處理機節點，它們的計算速度分別為P1，P2，P3...PN。當前Reduce任務所需的數據集分布在P1，P2，...PM節點上（M<=N），這些節點上擁有該Reduce任務所需的數據量分別為L1，L2，...LM，數據在節點之間進行傳輸的速率為S。

令：L=L1+L2+...+LM，則選擇P1節點進行Reduce任務處理所需的時間為： ，選擇P2節點進行Reduce任務處理所需的時間為：；即，選擇Pi（i=1，2...M）節點進行Reduce任務處理所需要的時間為：（i=1，2...M）。

因此，將當前的Reduce任務轉移到具有MIN（）值的處理機節點j上，同時將所需的其他數據集傳輸到j節點上。如果j節點上已經有任務在處理，則要分兩種情形：如果j節點上任務處理還需要的時間比j節點和下一個MIN（）值的處理機節點k（k<>j）之間時間差值大，則選擇下一個節點，而對下一個節點的判斷和剛剛判斷的過程一致；否則選擇j節點，等現有的Reduce任務處理完，再繼續處理。

5 實驗結果論證

本文通過在實際的異構Hadoop機群系統上分別以Hadoop自帶的WordCount（單詞統計程序）、Terasort（字符串排序算法）為測試程序實例，所有的實驗在一臺Intel四核機器、兩臺聯想雙核機器、一臺聯想單核機器通過100Mbps以太網互連組成的異構Hadoop機群系統上實現。各處理機節點運行的操作系統均為CentOS6.4；編程語言為Java，版本jdk1.7；Hadoop版本為2.2.0。

（1）實驗一：實驗向系統提交Hadoop自帶的WordCount（單詞統計程序）作業，作業輸入的大小分別為2GB，4GB，8 GB。實驗分別使用Hadoop自帶的Fair Scheduler（公平調度算法）和本文提出的調度算法分別執行6次，統計了WordCount不同規模下整個任務執行的時間，然后取得平均值，實驗結果對比如圖2所示。

（2）實驗二：實驗向系統提交Hadoop自帶的Terasort（字符串排序算法）作業，作業輸入的大小分別為2GB，4GB，8 GB。實驗分別使用Hadoop自帶的Fair Scheduler（公平調度算法）和本文提出的調度算法分別執行6次，統計了Terasort不同規模下整個任務執行的時間，然后取得平均值，結果對比如圖3所示。

通過兩個不同的程序實例，從實際的實驗結果可以看出，本文提出的調度算法在不同數據規模下均有較好的表現，因為在調度的過程中充分考慮了處理機節點處理能力的不同，同時在Reduce任務轉移時考慮各處理機節點的數據集問題，從而最大程度減少數據的轉移所花費的代價，進而減少了任務調度時間。

6 結語

本文就MapReduce計算模型下Reduce任務的調度問題，針對異構機群構成的Hadoop平臺提出了新的調度算法，算法在考慮數據本地性的同時還考慮各個處理機節點的處理能力，最大程度減少調度長度，通過實驗對調度算法進行驗證，實驗結果表明新的調度算法有著良好的調度效果。

參考文獻

[1]金嘉暉，羅軍舟，宋愛波，等.基于數據中心負載分析的自適應延遲調度算法[J].通信學報，2011（7）：47-56.

[2]寧文瑜，吳慶波，譚郁松.面向MapReduce 的自適應延遲調度算法[J].計算機工程與科學，2013（13）：53-57.