李鑫 張鵬

摘要：Hadoop作為MapReduce的開源實現(xiàn)被越來越多的企業(yè)使用。但是當Hadoop集群中出現(xiàn)較多的小作業(yè)時，使用其內(nèi)置的調(diào)度算法就會降低整個系統(tǒng)的吞吐率[1]。該文針對這個不足，提出了基于公平調(diào)度的延時調(diào)度算法。通過設定一定的延時來保證數(shù)據(jù)的本地性，實驗結(jié)果表明改進的調(diào)度算法可以提高整個系統(tǒng)的吞吐率。

關鍵詞：公平調(diào)度；延時分配；MapReduce；Hadoop

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2012)01-0166-03

Hadoop Cluster of Fair Scheduling Lgorithms to Improve and Achieve

LI Xin, ZHANG Peng

( Xian University of Architecture and Technology, Xian 710055, China)

Abstract: Hadoop is increasingly using for enterprises as an open source implantation of MapReduce. But when Hadoop clusters occur more small job, using its built-in scheduling will reduce the overall system throughput. In this paper, put forward a delay scheduling algorithm base on fair scheduling aiming at its defect. By setting a delay to ensure the local nature of the data. Experimental results show that the new scheduling algorithm can improve overall system throughput.

Key words: fair scheduling; delay scheduling; MapReduce; Hadoop

作業(yè)調(diào)度算法是一個集群的核心[2]，一個好的調(diào)度算法可以提高整個集群的利用率和吞吐率。Hadoop其自身就帶有一種簡單的作業(yè)調(diào)度算法，為了滿足各種不同類型的復雜作業(yè)的調(diào)度，又有一些新的調(diào)度算法被以插件的形式集成到Hadoop中去[3,4]，使用比較多的有公平調(diào)度算法(Fair Scheduling)和計算能力調(diào)度算法(Capacity Schedule)。但是針對系統(tǒng)從在較多小左的情況，目前上面提出的這兩種新的調(diào)度算法并不能保證系統(tǒng)較高的吞吐率。針對由小作業(yè)引起的吞吐率下降，采用一種作業(yè)延時分配的策略可以有效的解決這個問題[1,5]。

1 Hadoop現(xiàn)有的作業(yè)調(diào)度算法分析

1.1 MapReduce簡介

MapReduce是由Google發(fā)明的一種處理大規(guī)模數(shù)據(jù)的分布式編程框架，最初是由Google的工程師設計并實現(xiàn)。Hadoop是Ma? pReduee計算模型的一種開源實現(xiàn)，用于大規(guī)模數(shù)據(jù)集的并行化分析處理。Hadoop由Hadoop MapReduce和HDFS(Hadoop Distribut? ed File System)組成。HDFS提供了一個集群范圍內(nèi)的全局文件訪問機制。Hadoop中的作業(yè)調(diào)度是Job Tracker指派任務(Tasks)到相應Task Tracker上執(zhí)行的過程。下面對Hadoop中的調(diào)度算法進行介紹和分析。

1.2 Hadoop默認調(diào)度策略

最早的Hadoop Map/Reduce計算架構(gòu)中，Job Tracker在進行作業(yè)調(diào)度時使用的是FIFO(First In First Out)算法。所有用戶的作業(yè)都被提交到一個隊列中，然后由Job Tracker先按照作業(yè)的優(yōu)先級高低，再按照作業(yè)提交時間的先后順序選擇將被執(zhí)行的作業(yè)。FIFO算法的優(yōu)點是簡單明了，Job Tracker工作負擔輕。但是缺點也很突出，該算法主要是忽略了不同作業(yè)的需求差異。基于FIFO的缺點，新的調(diào)度算法被提出，分別是計算能力調(diào)度算法(Fail Scheduling)和公平調(diào)度算法(Capacity Schedule)。當前，新的調(diào)度器已經(jīng)作為插件的形式集成在Hadoop框架當中。

1.3計算能力調(diào)度算法

計算能力調(diào)度算法是由Yahoo提出的一種調(diào)度算法。其核心思想就是為每一個作業(yè)隊列定義一個指標，該指標是隊列中正在運行的作業(yè)數(shù)與其應該分得的計算資源(配置文件中為此隊列分配了相應數(shù)量的資源，而實際中該隊列可能沒有分配到)之間的比值。當系統(tǒng)中出現(xiàn)空閑的Task Tracker，算法會首先選擇一個該比值最低的隊列。

隊列被選中后，將按照作業(yè)優(yōu)先級(如果支持的話)和提交時間順序選擇執(zhí)行的作業(yè)。在選擇作業(yè)的時候，還需要考慮作業(yè)所屬的用戶是否已經(jīng)超出了他所能使用的資源限制。此外，還會考慮Task Tracker內(nèi)存資源是否滿足作業(yè)的要求。

1.4公平調(diào)度算法

公平調(diào)度算法是由Facebook提出的一種調(diào)度算法。公平調(diào)度是一種賦予作業(yè)(Job)資源的方法，它的目的是讓所有的作業(yè)隨著時間的推移，都能平均的獲取等同的共享資源。當單獨一個作業(yè)在運行時，它將使用整個集群。當有其它作業(yè)被提交上來時，系統(tǒng)會將任務(Task)空閑時間片(Slot)賦給這些新的作業(yè)，以使得每一個作業(yè)都大概獲取到等量的CPU時間。

公平調(diào)度器按資源池(Pool)來組織作業(yè)，并把資源公平的分到這些資源池里。默認情況下，每一個用戶擁有一個獨立的資源池，以使每個用戶都能獲得一份等同的集群資源而不管他們提交了多少作業(yè)。

公平調(diào)度器還可以限制每用戶和每資源池的并發(fā)運行作業(yè)數(shù)量。當一個用戶必須一次性提交數(shù)百個作業(yè)時，或當大量作業(yè)并發(fā)執(zhí)行時，用來確保中間數(shù)據(jù)不會塞滿集群上的磁盤空間，這是很有用的。設置作業(yè)限制會使超出限制的作業(yè)被列入調(diào)度器的隊列中進行等待，直到一些用戶/資源池的早期作業(yè)運行完畢。系統(tǒng)會根據(jù)作業(yè)優(yōu)先權和提交時間的排列來運行每個用戶/資源池中的作業(yè)。

2延時調(diào)度(Delay Scheduling)

2.1公平調(diào)度算法吞吐率分析

公平調(diào)度算法可以讓有多用戶提交的作業(yè)在一定的時間內(nèi)都能平均的獲取等同的共享資源。本文通過實驗發(fā)現(xiàn)，當出現(xiàn)較多小作業(yè)時，整個集群的吞吐率就會出現(xiàn)明顯的下降，分析原因發(fā)現(xiàn)，是由于作業(yè)數(shù)據(jù)的本地性所造成的。集群對于數(shù)據(jù)的計算采用移動計算比移動數(shù)據(jù)更劃算，換句話說就是要把計算放在離數(shù)據(jù)比較近的節(jié)點。由于集合中網(wǎng)絡的傳輸速度是不同的，數(shù)據(jù)傳輸速度最快的是在本節(jié)點之內(nèi)，緊接是在本機架內(nèi)，最慢是在不同的機架之間。所以為了提高整個集群的吞吐率，就要提高數(shù)據(jù)的本地性，盡量讓數(shù)據(jù)在本節(jié)點或本機架內(nèi)運算。下面分析一下為什么較多的小作業(yè)會導致數(shù)據(jù)的本地性變差。

由于小作業(yè)占用資源池的資源比較小，集群當中很容易出現(xiàn)空閑的資源池滿足小作業(yè)的需求，所以當一個小作業(yè)按照最小共享額度的公平調(diào)度算法被調(diào)度到隊列的頭部時，就會很快出現(xiàn)滿足條件的資源，而這個滿座條件的資源不是本節(jié)點的概率會很高，而且跟集群的大小有直接關系，當集群較小時，這個概率會較小，當集群很大時，這個概率也會很大。由于這個原因從而導致當小作業(yè)較多時，整個集群的吞吐率就會出現(xiàn)明顯的下降。為了解決小作業(yè)的調(diào)度問題，本文提出了基于公平調(diào)度算法的延時調(diào)度算法(DSFS, Delay Scheduling Base on Fail Scheduling)。

2.2基于公平調(diào)度的延時調(diào)度

當一個小作業(yè)按照公平調(diào)度算法被調(diào)度到隊列的頭部時，此時會等待滿足條件的資源，在有節(jié)點釋放空閑資源池時，調(diào)度隊列頭部用戶池的作業(yè)就會判斷此空閑資源是否滿足節(jié)點本地性，如果滿足本地性，就立即分配資源，否則就繼續(xù)等待滿足條件的本節(jié)點所釋放的資源，等待時間為T1，如果超過時間T1，就會繼續(xù)等待滿足條件的本機架所釋放的空閑資源，等待時間為T2。如果超過時間T2還沒有分配到資源，就會在第一時間獲取到其他節(jié)點所釋放的空閑資源(這里的其他節(jié)點可能是本節(jié)點的，也可能是本機架的，也有可能是其他節(jié)點的)。其中等待時間，T2>T1，這兩個時間可以自由的由用戶自己在配置文件當中定義。具體的算法如下：

初始化作業(yè)隊列JobList

if節(jié)點n發(fā)送心跳信號到master then

if節(jié)點n釋放了空閑池then

for作業(yè)J=JobList.get(i), 0 =< i < JobList.size(), i++

if作業(yè)J有一個在節(jié)點n上的節(jié)點本地性任務then

立即執(zhí)行此任務

else if作業(yè)J.wait < T1then

繼續(xù)等待

else if作業(yè)T1< J.wait < T2then

if作業(yè)J有一個在節(jié)點n所在機架的任務then立即執(zhí)行此任務

else繼續(xù)等待

end if

else if作業(yè)J.wait > T2

立即執(zhí)行此任務

end if

end for

end if

end if

2.3延時調(diào)度算法吞吐率分析

在有很多作業(yè)運行且各節(jié)點之間負載均衡時，當一個作業(yè)無法提交本地作業(yè)時，調(diào)度隊列后面也可能會有符合數(shù)據(jù)本地性的作業(yè)，故延時調(diào)度對系統(tǒng)的吞吐率的提高是有利的。

Hadoop分布式文件系統(tǒng)(HDFS)在進行數(shù)據(jù)的存儲時是考慮了數(shù)據(jù)在整個集群分布的均衡性的。但不排除在一些情況下會出現(xiàn)多個調(diào)度隊列中的作業(yè)都等待在同一個節(jié)點上執(zhí)行作業(yè)。如果這多個待執(zhí)行作業(yè)在性能特性上相似(如都為計算型作業(yè))，那么延時調(diào)度對吞吐率幾乎沒有影響。

為了進一步提高系統(tǒng)的吞吐率，可以根據(jù)作業(yè)的性能特性采用不同的調(diào)度策略，針對計算型作業(yè)可以調(diào)度它到本機架內(nèi)的節(jié)點上執(zhí)行，I/O型作業(yè)可以調(diào)度到具有節(jié)點本地性的節(jié)點上執(zhí)行。同樣數(shù)據(jù)大小的輸入數(shù)據(jù)，I/O型作業(yè)需要花費更多的時間去讀取數(shù)據(jù)，需要較高的數(shù)據(jù)帶寬，而計算型作業(yè)的主要時間花費在計算上從而可以邊計算邊進行數(shù)據(jù)的讀取，對數(shù)據(jù)帶寬要求相對較低。

3實驗

3.1實驗環(huán)境

整個集群共由9臺普通PC機組成，其中1臺作為主控制節(jié)點，另外8臺是工作節(jié)點。我們將工作節(jié)點分為2組，每組4臺PC機構(gòu)成一個機柜，在同一個機柜內(nèi)的工作節(jié)點通過全雙工1Gbps以太網(wǎng)卡與CiscoSD208 1Gbps交換機相連接，連接兩個機柜的是一個千兆路由器。在集群中的每臺計算機都是Dell OptiPlex 780的PC機，配置2G內(nèi)存，CPU配置為Intel酷睿2雙核E7500，硬盤為7200轉(zhuǎn)的SCSI硬盤。每臺機器上都裝有相同的RHEL5作為操作系統(tǒng)。

3.2 I/O型數(shù)據(jù)節(jié)點本地性實驗

本實驗采用文本搜索進行I/O型實驗，因為文本搜索主要是掃描整個文本，搜索到匹配值輸出，輸出結(jié)果是非常小的，且集群絕大部分時間是在進行數(shù)據(jù)讀取和掃描操作，主要受限于硬盤的I/O速度。對不同的作業(yè)規(guī)模試驗結(jié)果如圖1所示。

圖1不同規(guī)模作業(yè)的本地性分布

圖1為3中調(diào)度算法在9中不同規(guī)模的I/O類型作業(yè)的節(jié)點數(shù)據(jù)本地性分布圖。延時調(diào)度在所有的規(guī)模作業(yè)幾乎都可達到100%的節(jié)點本地性。FIFO和公平調(diào)度在小作業(yè)上節(jié)點本地性都很差。

3.3系統(tǒng)吞吐率實驗及分析

為了證明DSFS算法能夠有效的提高系統(tǒng)的吞吐率，本實驗設計了兩組對比試驗，每組實驗都有100個Job，這100個Job平均的分布在集群的所有節(jié)點上。這里的小作業(yè)指的是其計算時間遠遠小于網(wǎng)絡傳輸時間。

實驗一，其中小作業(yè)占據(jù)整個作業(yè)數(shù)的30%，小作業(yè)較多。實驗二，其中小作業(yè)占據(jù)整個作業(yè)數(shù)的5%，小作業(yè)較少。表1和表2分別展示了FIFO算法和DSFS算法在較多和較少小作業(yè)時的集群吞吐率數(shù)據(jù)。

通過上面的數(shù)據(jù)分析可以看出，當系統(tǒng)有較多小作業(yè)時，DSFS算法可以有效地減少作業(yè)的完成時間，從而提高系統(tǒng)的吞吐率。

4結(jié)束語

MapReduce計算模型已經(jīng)被越來越多的企業(yè)的支持和應用。由于MapReduce集群的昂貴硬件成本和其上的許多應用都使得多用戶共享集群變得更加必要。集群的共享，就要求集群調(diào)度器能夠?qū)崿F(xiàn)公平性和效率的均衡。公平調(diào)度算法可以很好的保證公平性，但小作業(yè)調(diào)度數(shù)據(jù)本地性差的問題，明顯的降低了整個集群的吞吐率。本文通過延時調(diào)度可以極大改善數(shù)據(jù)本地性的問題，甚至可以達到幾乎100%的節(jié)點本地性，實驗證明延時調(diào)度對整個集群的平均吞吐率有明顯的提高。

參考文獻:

[1]張密密.MapReduce模型在Hadoop實現(xiàn)中的性能分析及改進優(yōu)化[D].電子科技大學,2010.

[2]張青.網(wǎng)格環(huán)境下任務調(diào)度算法的應用研究[D].大連海事大學,2009.

[3]陳全,鄧倩妮.異構(gòu)環(huán)境下自適應的Map-Reduce調(diào)度[J].計算機工程與科學,2009,31(z1):5.

[4]王凱,吳泉源,楊樹強.一種多用戶MapReduce集群的作業(yè)調(diào)度算法的設計與實現(xiàn)[J].計算機與現(xiàn)代化,2010(10).

[5]開華東,田琪.基于MapReduce集群的加權公平隊列調(diào)度算法研究[J].電腦知識與技術,2011,7(9).

[6]王峰.Hadoop集群作業(yè)的調(diào)度算法[J].程序員,2009(12).

[7]周鋒,李旭偉.一種改進的MapReduce并行編程模型[J].科協(xié)論壇(下半月),2009(02).

[8]孫廣中,肖鋒,熊曦.MapReduce模型的調(diào)度及容錯機制研究[J].微電子學與計算機,2007(09).

[9] Dean Jeffrey. MapReduce:simplified data processing on large clusters[C].Communications of the ACM, 2008 :107-113 .

[10] Ranger C,Raghuraman R,Penmetsa A,et al. Evaluating Map Reduce for Multi-core and Multiprocessor Systems[C].Pro-ceedings of the 13th Symposium on High-Performance Computer Architecture (HPCA). 2007:13-24 .

[11] Apache. Apache hadoop .http://hadoop.apache.org/core/.