Hadoop平臺下基于資源預測的Delay調(diào)度算法

魏曉輝, 付慶午, 李洪亮

(吉林大學 計算機科學與技術(shù)學院, 長春 130012)

計算機網(wǎng)絡技術(shù)的高速發(fā)展和應用, 帶來了數(shù)據(jù)規(guī)模的爆炸式增長, 使大規(guī)模數(shù)據(jù)的處理和存儲成為目前高性能計算領(lǐng)域的研究熱點. 傳統(tǒng)的高性能計算系統(tǒng)多用于處理計算密集型作業(yè), 并不適合解決數(shù)據(jù)密集型應用問題. Google提出的Mapreduce[1]計算模型和GFS[2]分布式存儲系統(tǒng), 為海量數(shù)據(jù)處理和存儲需求提供了全新的方法. 近年來, Hadoop作為Mapreduce和GFS模型的開源實現(xiàn), 得到了廣泛的應用和認可. Hadoop平臺是新一代的高性能計算和存儲平臺, 其系統(tǒng)結(jié)構(gòu)有別于傳統(tǒng)的高性能計算系統(tǒng)[3-8]. Hadoop的系統(tǒng)結(jié)構(gòu)具有將數(shù)據(jù)資源(HDFS)和計算資源(Mapreduce)整合的特點. 該特點使Hadoop集群資源調(diào)度過程遵循一個基本思想： 移動計算不移動數(shù)據(jù)----將計算任務派到包含要處理的數(shù)據(jù)計算節(jié)點, 即任務本地化計算(task locality). 任務調(diào)度作為Hadoop系統(tǒng)的重要組成部分, 直接影響作業(yè)的執(zhí)行效率和機群資源利用率. 目前的Hadoop調(diào)度方法優(yōu)化多基于提高Locality比例優(yōu)化作業(yè)的執(zhí)行效率, 從而提高系統(tǒng)作業(yè)吞吐量.

本文基于對機群整體計算資源合理分配的調(diào)度思想, 針對Hadoop集群數(shù)據(jù)資源和計算資源整合的特點, 提出一種資源可用性預測方法----基于資源預測的Delay調(diào)度算法(resource forecast delay scheduling, RFD). 基于該方法, RFD控制任務進行合理的等待, 提高了系統(tǒng)的整體作業(yè)執(zhí)行效率和系統(tǒng)作業(yè)吞吐量. 實驗結(jié)果表明, 在Hadoop一般應用場景下, 本文提出的方法在保證任務Locality比例相近的前提下, 相比Fairshare算法[9], 平均作業(yè)執(zhí)行效率提高了28.8%.

1 基于資源預測的Delay調(diào)度算法

1.1 算法思想及框架

Hadoop系統(tǒng)中作業(yè)的本地化計算比例(Locality)是影響作業(yè)執(zhí)行效率和系統(tǒng)資源利用率的關(guān)鍵因素. 因此, 如何合理控制任務進行等待, 在保證系統(tǒng)Locality的同時, 合理分配資源是Hadoop調(diào)度程序要解決的關(guān)鍵問題. 本文提出一種基于資源預測的Delay調(diào)度算法(RFD). RFD算法以計算資源可用性為依據(jù)控制任務進行合理地等待, 提高作業(yè)的運行效率和系統(tǒng)的整體資源利用率.

數(shù)據(jù)的非本地化計算和作業(yè)等待過長都會導致機群整體計算資源浪費, FIFO和Fairshare算法都沒能很好地解決這個問題. Delay算法雖然能提高本地化運算比例, 但難以適應資源可用性動態(tài)變化. 因此, RFD調(diào)度器基于Delay思想, 針對資源實時可用性的預測進行合理地等待, 在數(shù)據(jù)非本地化計算和作業(yè)等待時間之間取得更好的平衡, 以提高機群整體利用效率.

RFD算法包含一個資源可用性預測模塊, 對各作業(yè)所需的資源可用性進行預測. 每個作業(yè)的資源需求不同和依賴的數(shù)據(jù)文件不同導致同一個資源對不同的作業(yè)可用性不同. 因此, RFD中使用作業(yè)的“可用資源期望”表達集群資源對作業(yè)的可用性. 圖1為RFD調(diào)度示意圖, job1的可用資源期望為2, 表示在未來一個調(diào)度周期中, 將到來的含有job1所需數(shù)據(jù)的節(jié)點請求數(shù)量為2. 在RFD算法進行資源分配前, 先根據(jù)歷史數(shù)據(jù)估計出作業(yè)隊列中各作業(yè)的資源期望值, 即可根據(jù)可用資源期望進行作業(yè)調(diào)度. 由圖1可見, job1的可用資源期望為2, job2的可用資源期望為3. 因此, 這兩個作業(yè)均可在本輪調(diào)度周期進行等待. 如果此時Tasktracker2有任務請求且該節(jié)點無job1要處理的數(shù)據(jù)塊, 則可以讓job1等待, 調(diào)度job2在該節(jié)點的本地化運算Map任務. 若job2也無本地化運行Map任務, 則繼續(xù)等待, 匹配下一個作業(yè)(如圖1中Tasktracker3的任務調(diào)度). 因此, RFD算法中任務等待是依據(jù)作業(yè)的資源可用性進行的, 這樣的等待不會影響作業(yè)的運行.

圖1 RFD調(diào)度示意圖Fig.1 Scheme of RFD scheduler

另一方面, 為了在通用環(huán)境下能夠高效運行, RFD調(diào)度器引入了FIFO簡單而高效的設計思路, 強調(diào)作業(yè)的先后優(yōu)先級別. 在為計算資源匹配本地化計算任務時, 按作業(yè)提交順序進行匹配, 如圖2所示. 在Delay時機選擇方面, 本文遵循使總體效益損失最小的原則進行調(diào)度. 圖2為RFD調(diào)度器基本流程, 對于Tasktracker的任務請求, 為提高整體作業(yè)Locality計算比例, 先匹配該Tasktracker數(shù)據(jù)本地化計算的Map任務； 若匹配不成功, 為了整體作業(yè)合理等待, 則根據(jù)作業(yè)等待判斷模塊計算的可用資源期望決定是否等待.

圖2 本文調(diào)度算法基本框架Fig.2 Scheduling algorithm basic framework

1.2 RFD調(diào)度算法

針對RFD調(diào)度算法的需要, 本文對Hadoop系統(tǒng)進行如下定義：j為jobj;N為機群中的總機器數(shù);Mj為作業(yè)j未運行的Map task;Kj為Mj未處理數(shù)據(jù)分布的機器數(shù);TT為數(shù)據(jù)塊在兩個計算節(jié)點間傳輸所需的時間;Pj為下一個“心跳”的源機器上有jobj未處理數(shù)據(jù)塊的概率:

Pj=Kj/N;

(1)

H為Jobtracker每秒鐘接收的“心跳”數(shù)：

H=N/3;

(2)

S為每個Tasktracker上可運行的Map任務數(shù);t為作業(yè)平均完成時間;Ph為某個“心跳”有作業(yè)請求的概率：

Ph=3×S/t;

(3)

Ej為在未來TT時間內(nèi), Jobtracker接收的“心跳”中, 有作業(yè)請求, 且該“心跳”的源機器上有jobj未處理的數(shù)據(jù)塊的期望：

Ej=H×TT×Pj×Ph;Ej=(TT×N/3)×(kj/N)×(3×S/t)=TT×S×Kj/t.

(4)

期望Ej評判是否值得對作業(yè)j等待. 該期望值體現(xiàn)了一個數(shù)據(jù)塊傳輸?shù)臅r間內(nèi)能收到本地化作業(yè)請求的期望, 如果Ej≥1, 表明對于該作業(yè), 等待是值得的.

在作業(yè)進行等待的同時, RFD算法需要考慮資源競爭問題. 對于當前調(diào)度的作業(yè), 如果在未處理的數(shù)據(jù)塊機器上同樣含有在它之前作業(yè)未處理的數(shù)據(jù)塊, 則計算Ej時, 應考慮資源競爭的問題. 否則, 當計算該作業(yè)的Ej≥1時, 會出現(xiàn)與前面作業(yè)沖突, 前面的作業(yè)會占用與該作業(yè)有共同數(shù)據(jù)塊的機器作業(yè)請求, 導致Ej值虛高, 容易使該作業(yè)出現(xiàn)饑餓. 因此, 本文引入如下兩個變量：Rj為作業(yè)j與它前面作業(yè)的未處理數(shù)據(jù)塊在同一臺機器上的機器數(shù); Prj為作業(yè)j與它前面作業(yè)會發(fā)生資源競爭的概率:

Prj=Rj/Kj;Ej=TT×S×Kj/t×Prj=TT×S×Rj/t.

(5)

RFD調(diào)度算法流程如下.

Begin

將作業(yè)調(diào)度隊列JobQueue按提交順序排列

assignedTasks=0； //標記已經(jīng)派給Tasktracker的Map任務數(shù)

while(true)

If (assignedTasks==Tasktracker.請求作業(yè)數(shù)) then //滿足Tasktracker作業(yè)請求

break;

endif

For jobiin jobQueue do

If jobi有數(shù)據(jù)塊在發(fā)送“心跳”的機器上 then //Data-Local, 直接派作業(yè)

將jobi的數(shù)據(jù)本地化Map派到該機器上；

assignedTasks + +；

break；

endif

endfor

If (前面沒有找到合適的Map任務) then //下面引入等待機制

For jobiin jobQueue do

根據(jù)式(7)計算作業(yè) jobi的期望值Ei；

If (Ei<1) then //如果Ei<1, 不值得等待, 分非本地化計算的Map任務

將jobi的數(shù)據(jù)非本地化Map派到該機器上；

assignedTasks + +；

break；

Else then

continue; //等待, 調(diào)度隊列中下一個作業(yè)

endif

endfor

If (前面沒有找到分配Map任務) then //前面沒有找到合適Map的任務

分配隊首作業(yè)非本地化Map任務；

assignedTasks + +；

endif

endwhile

End.

RFD調(diào)度算法吸收了FIFO和Delay-Scheduling算法的簡單高效特點, 避免了兩種算法的各自缺點, 提高了作業(yè)本地化計算Map任務的比例, 同時不會產(chǎn)生過度的等待, 有效地提高了機群整體的資源利用率. 通過分析可知, 第一個循環(huán)以FIFO的順序?qū)㈥犃兄凶鳂I(yè)于請求作業(yè)的Tasktracker進行數(shù)據(jù)本地化匹配. 循環(huán)結(jié)束, 若未匹配, 則該Tasktracker在當前的情況下不能分配到數(shù)據(jù)本地化計算的Map任務. 進入算法的Delay機制, 考慮作業(yè)是否應該等待； 基于對作業(yè)的可用計算資源預測, 對作業(yè)是否值得等待進行合理的評估. 上述兩次循環(huán)匹配都是基于整體計算資源的合理利用考慮. 如果還沒有分配到Map任務, 則將作業(yè)隊列隊首的Map任務分配給Tasktracker, 這種情況較少.

2 實驗結(jié)果和數(shù)據(jù)分析

2.1 實驗環(huán)境及結(jié)果

實驗機群由10臺Dell optiple x380 PC服務器構(gòu)成(英特爾酷睿4核處理器, 2 Gb內(nèi)存, 200 Gb硬盤), 采用100 M以太網(wǎng)絡相連, 實驗軟件采用Hadoop-0.21.0版本, 實驗所用數(shù)據(jù)為某網(wǎng)站訪問日志文件, 經(jīng)過處理分成128 Mb～4 Gb不等10份樣本, 實驗用例是基于基本數(shù)據(jù)采樣處理的Mapreduce 作業(yè), 用于統(tǒng)計訪問該網(wǎng)站的客戶端IP登陸次數(shù).

本文對FIFO算法、 Fairshare算法和本文提出的RFD調(diào)度算法進行對比實驗. 為了反映真實的對比結(jié)果, 所用的實驗環(huán)境、 數(shù)據(jù)分布及作業(yè)完全一致. Fairshare調(diào)度器采用默認Delay時間設置. 針對10份不同的數(shù)據(jù)樣本, 每組測試6個作業(yè). 在實驗過程中, 重點關(guān)注各實驗用例中作業(yè)的本地化計算任務數(shù)(比例)和作業(yè)的平均完成時間, 實驗結(jié)果列于表1和表2.

由RFD算法分析可知, 調(diào)度器是否對作業(yè)進行等待取決于對資源的預測期望值Ej； 若Ej≥1, 則作業(yè)等待; 否則, 將該作業(yè)非本地化計算的Map任務派出去. 可見, 系統(tǒng)計算期望值Ej的準確性將對作業(yè)是否等待產(chǎn)生決定性影響, 若該期望值不符合機群的實際運行情況, 將導致機群計算資源的浪費, 降低作業(yè)執(zhí)行效率.

由于該期望值是對未來一段時間內(nèi)(TT)Jobtracker能夠收到的包含某個作業(yè)未執(zhí)行的Map任務要處理的數(shù)據(jù)塊的Tasktracker任務請求次數(shù). 因此, 要將在某個時刻計算的所有作業(yè)的期望值都記錄下來, 對于某個作業(yè), 記錄在未來時間TT內(nèi), Jobtracker收到任務請求的Tasktracker中, 包含有該作業(yè)未處理的數(shù)據(jù)塊的任務請求次數(shù). 過了TT時刻開始輸出記錄每個作業(yè)真正收到的本地化計算Map任務請求； 實驗測試中, 在調(diào)度器中啟動一個統(tǒng)計線程, 該線程負責記錄每個收到的命中每個作業(yè)的本地化計算Map任務請求數(shù), 定時輸出, 實驗結(jié)果列于表3.

表1 作業(yè)平均完成時間(s)

表2 數(shù)據(jù)本地化計算Map任務比例(%)

表3 資源預測準確性測試

由表3可見, 系統(tǒng)計算的資源預測期望值Ej與真實運行情況基本相同, 若將預測結(jié)果按四舍五入對應真實值, 預測準確度達90%以上, 表明本文基于資源預測的算法可行、 有效.

2.2 實驗結(jié)果分析

實驗結(jié)果可分為以下3種情況： 1) Map數(shù)為2, RFD調(diào)度器的本地化計算低于FIFO和Fairshare調(diào)度器, 作業(yè)運行時間高于后兩種調(diào)度器; 2) Map任務數(shù)為4和8, RFD調(diào)度器的數(shù)據(jù)本地化計算Map任務比例和執(zhí)行時間都優(yōu)于FIFO, 但不如Fairshare調(diào)度器; 3) Map任務數(shù)為16～64時, RFD調(diào)度器的本地化計算Map任務比例和作業(yè)運算時間優(yōu)于FIFO, 本地化計算比例與Fairshare調(diào)度器相當, 但作業(yè)執(zhí)行時間優(yōu)于Fairshare調(diào)度器, 如圖3和圖4所示. 情況1)和2)屬于運行小作業(yè)的情況, Hadoop機群一般運行的作業(yè)都較大, 所以前兩種情況不常見； 情況3)運行的是中型和大型作業(yè), 是Hadoop機群實際應用中經(jīng)常出現(xiàn)的情況, 更具代表性.

圖3 作業(yè)運行時間Fig.3 Jobs’ running time

圖4 Map任務本地化計算(Locality)比例Fig.4 Percentages of locality computing Map tasks

當Hadoop運行作業(yè), 分配非本地化計算的Map任務時, 傳輸數(shù)據(jù)塊和作業(yè)等待會導致作業(yè)運行時間增加； Delay算法是通過作業(yè)等待增加本地化計算Map任務數(shù), 所以, 如何合理地等待是在這兩者取得平衡、 降低作業(yè)運行時間的關(guān)鍵.

由上述分析可知, RFD算法是否等待與作業(yè)未處理的數(shù)據(jù)塊分布機器數(shù)有關(guān)； Map任務數(shù)太少不會觸動等待機制. 分配一個非本地化計算Map任務給某個Tasktracker會影響其他作業(yè)的本地化計算任務分配到該Tasktracker(Tasktracker上分布著多個作業(yè)數(shù)據(jù)塊), 因此, Map任務較少時, RFD調(diào)度器會導致整體作業(yè)本地化計算Map任務比例低； Fairshare的等待時間是固定的4.5 s, 初始調(diào)度時, 調(diào)度器一定會收到一個Map本地化計算的作業(yè)請求(3 s就會收到Tasktracker一次“心跳”), 當Map任務數(shù)太少時, 本地化計算比例較高. FIFO調(diào)度器調(diào)度時只針對隊首作業(yè), 不會受多個作業(yè)的數(shù)據(jù)塊分布在同一個計算節(jié)點的情況影響. 由圖3和圖4可見, 情況1)和2)中RFD調(diào)度器與Fairshare調(diào)度器相比, 在本地化計算任務比例低, 作業(yè)運行時間長； 但這兩項指標優(yōu)于FIFO調(diào)度器.

隨著Map任務數(shù)增多, RFD調(diào)度器的等待機制被觸動, 本地化計算Map任務數(shù)開始增加. FIFO調(diào)度作業(yè)時只對隊首作業(yè)調(diào)度, 本地化計算Map任務數(shù)比例增長緩慢. 由圖4可見, Fairshare的等待時間固定, 所以本地化計算Map任務數(shù)比例變化不大.

情況3)中, RFD調(diào)度器的本地化Map任務數(shù)比例明顯上升(圖3), 作業(yè)運行時間低于Fairshare調(diào)度器, 這是由于Fairshare調(diào)度器等待時機不合理所致. 若某Tasktracker沒有一個作業(yè)的本地化計算數(shù)據(jù)會導致整個作業(yè)隊列都在等待, 因此作業(yè)運行時間較長； RFD調(diào)度器在以動態(tài)可用資源預測為等待基礎(chǔ)且以數(shù)據(jù)本地化調(diào)度優(yōu)先, 等待時間較合理. 所以, 該情況下RFD調(diào)度器不僅本地化計算Map任務數(shù)比例較高, 且等待時間較合理, 作業(yè)運行時間也較少.

Hadoop的應用場景是處理大數(shù)據(jù), 運行作業(yè)的Map任務數(shù)較多, 情況3)的出現(xiàn)概率遠大于情況1)和2). 實驗表明, RFD調(diào)度器在一般情況下比Fairshare和FIFO調(diào)度器的作業(yè)運行效率高, 且整體機群資源利用更合理. 根據(jù)Hadoop機群應用場景和本文的實驗結(jié)果可知, RFD在一般情況下, 本地化計算Map任務數(shù)比例與Fairshare調(diào)度器相近； 但作業(yè)平均運行時間低于Fairshare調(diào)度器的28.8%.

對比實驗表明, 本文提出的RFD算法與Fairshare算法相比, 一般情況下, 在保持系統(tǒng)高本地化作業(yè)執(zhí)行比例(Locality)相近的同時, 優(yōu)化了作業(yè)的整體執(zhí)行效率(平均提高28%).

[1] Dean J, Ghemawat S. Mapreduce: Simplified Data Processing on Large Clusters [J]. ACM, 2008, 51: 107-113.

[2] Ghemawat S, Gobioff H, LEUNG Shun-tak. The Google File System [J]. ACM, 2003, 37: 29-43.

[3] Apache. The Oomepage of Hadop [EB/OL]. 2012-03-19. http://Hadoop.apache.org/.

[4] Shvachko K, KUANG Hai-rong, Radia S, et al. The Hadoop Distributed File System [J]. MSST, 2010, 1: 1-10.

[5] Amazon. The Homepage of s3 Distributed File System [EB/OL]. [2011-10-28]. http://aws.amazon.com/s3.

[6] Cloudstore. Cloudstore Distributed File System Website [EB/OL]. [2011-11-29]. http://kosmosfs.sourceforge.net/.

[7] GUO Dong, DU Yong, HU Liang. HDFS Based Cloud Data Backup System [J]. Journal of Jilin University: Science Edition, 2012, 50(1): 101-105. (郭東, 杜勇, 胡亮. 基于HDFS的云數(shù)據(jù)備份系統(tǒng) [J]. 吉林大學學報: 理學版, 2012, 50(1): 101-105.)

[8] WEI Xiao-hui, Li Wilfred, XU Gao-chao, et al. Implementing Data Aware Scheduling on Gfarm by Using LSFTMScheduler Plugin [J]. Journal of Jilin University: Science Edition, 2005, 43(6): 763-767. (魏曉輝, Li Wilfred, 徐高潮, 等. 利用LSF調(diào)度程序的插件機制在Gfarm上實現(xiàn)Data aware調(diào)度 [J]. 吉林大學學報: 理學版, 2005, 43(6): 763-767.)

[9] Zaharia M, Borthakur D, Sarma J S, et al. Job Scheduling for Multi-user Mapreduce Clusters [J]. EECS Department, 2009, 55: 1-16.