富春巖+葛茂松+張立銘+李微娜+趙佳彬

摘要：該文通對MapReduce調(diào)度器中準實時調(diào)度算法的研究， 實現(xiàn)了在MapReduce調(diào)度器上能夠依據(jù)正在進行的任務(wù)的進度，對任務(wù)的完成時間進行估計，在運行時給每個任務(wù)動態(tài)的分配資源。實驗表明，本算法提高了MapReduce系統(tǒng)的資源利用率，達到了準實時MapReduce調(diào)度的預期目標。

關(guān)鍵詞：MapReduce；調(diào)度策略；調(diào)度算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）15-0003-02

1 引言

MapReduce是一個用于大規(guī)模數(shù)據(jù)集的并行運算模型. 廣泛應用于分布式查詢、分布式排序、Web訪問日志分析、機器學習以及基于統(tǒng)計的機器翻譯等領(lǐng)域[1]。MapReduce系統(tǒng)中現(xiàn)有的三種調(diào)度器：FIFO調(diào)度器、Capacity Scheduler調(diào)度器以及Fair Scheduler調(diào)度器[2]。目前這三種調(diào)度算法，在作業(yè)提交前，必須對系統(tǒng)的參數(shù)進行預先設(shè)定。而且，一旦作業(yè)提交，MapReduce系統(tǒng)給每一個任務(wù)的資源分配策略就已經(jīng)確定下來，不能根據(jù)任務(wù)執(zhí)行的實際情況進行動態(tài)的調(diào)整[3]。本文提出的算法使MapReduce調(diào)度器能夠?qū)φ谶M行的任務(wù)的進度及任務(wù)的完成時間進行估計，并在運行時給每個任務(wù)動態(tài)的分配資源，從而提高了MapReduce系統(tǒng)的資源利用率。

2 算法思想

準實時MapReduce調(diào)度算法主要由作業(yè)性能估計及任務(wù)調(diào)度策略兩部分組成。

1）作業(yè)性能估計的主要思想是：通過作業(yè)m中，已完成任務(wù)集合的完成時間和任務(wù)數(shù)量的統(tǒng)計，推測作業(yè)m中的任務(wù)平均完成時間，并且以此推測正在執(zhí)行任務(wù)的剩余完成時間。然后，準實時調(diào)度算法就可以以此作為判斷任務(wù)性能的依據(jù)，確定任務(wù)的優(yōu)先級并對任務(wù)進行調(diào)度。

2）任務(wù)調(diào)度策略的主要思想是：根據(jù)作業(yè)性能估計中得到的任務(wù)平均完成時間，通過公式推導，得出作業(yè)還需要的任務(wù)執(zhí)行單元的數(shù)量，以此確定作業(yè)的優(yōu)先級，調(diào)度器再根據(jù)作業(yè)的優(yōu)先級，給不同的作業(yè)分配相應的資源。任務(wù)調(diào)度策略包括兩部分：一是將合適的優(yōu)先級賦給作業(yè)；二是基于作業(yè)優(yōu)先級的分配算法。

3 準實時MapReduce調(diào)度器的核心類及主要功能

準實時MapReduce調(diào)度器的核心類由SoftRealTimeConfiguration類、Soft Real Time Operation In Progress Listener類、Soft Real Time Task Scheduler類、Soft Real Time Operation類、Operation Tracker類和Operation In Progress類等組成。準實時MapReduce調(diào)度器的核心類圖如圖1所示，核心類及主要功能如下：

1）SoftRealTimeConfiguration類繼承自org.apache.hadoop.conf.Configuration類，功能是進行配置文件管理。在Hadoop MapReduce啟動加載時，SoftRealTimeConfiguration會讀取配置文件中的參數(shù)，并保存至相應的數(shù)據(jù)結(jié)構(gòu)中。

2）Soft Real Time Operation In Progress Listener類該類繼承自org. apache. hadoop. Map red. Operation In Progress Listener類，功能是當作業(yè)添加或者刪除時，通知調(diào)度器。該類包含三個主要函數(shù)：operation Added、operation Removed以及operation Updated，功能是當有作業(yè)添加到作業(yè)隊列，從作業(yè)隊列刪除；作業(yè)的狀態(tài)有更新時，該類偵聽到這些事件并且執(zhí)行對應的函數(shù)。

3）Soft Real Time Task Scheduler類繼承自org. apache. hadoop.mapreduce. server. operationtracker. Task Tracker類，實現(xiàn)核心調(diào)度算法。Soft Real Time Task Scheduler類除了包含init Schedule Queue，priority Op及add Operation To Queue三個主要函數(shù)以外，還包括assign Tasks和getOperations函數(shù)。assign Tasks函數(shù)的功能是用于返回正在某個Task Tracker上執(zhí)行的任務(wù)集合；getOperations函數(shù)的功能是通過作業(yè)隊列的名稱返回該隊列中的作業(yè)。

4）Soft Real Time Operation類記錄作業(yè)的狀態(tài)和估計作業(yè)完成時間，并以此為依據(jù)比較正在運行的兩個作業(yè)之間的優(yōu)先級大小。

5）Operation Tracker類用于調(diào)度作業(yè)，其主要功能有：

1獲取集群的狀態(tài)，比如task tracker列表，map過程中空閑的slot任務(wù)執(zhí)行器總數(shù)，reduce過程中空閑的slot任務(wù)執(zhí)行器總數(shù)，當前正在運行的map/reduce 任務(wù)的總數(shù)等；

2獲取QueueManager對象，通過該對象，可以獲取MapReduce系統(tǒng)中所有作業(yè)隊列的名稱，以及每個隊列的權(quán)限訪問列表；

3停止某個作業(yè)；

4停止某個任務(wù)，用于資源搶占。

6）Operation In Progress類，當用戶向Hadoop MapReduce提交一個作業(yè)后，Hadoop MapReduce會為該作業(yè)創(chuàng)建一個Operation In Progress的對象，該對象中包含了作業(yè)相關(guān)的基本信息，并會伴隨某個作業(yè)的生命周期。該對象中包含該作業(yè)的所有任務(wù)的信息，作業(yè)的優(yōu)先級，作業(yè)的提交時間，開始運行時間，運行結(jié)束時間等作業(yè)信息。

4 結(jié)論

本文提出了一種準實時MapReduce調(diào)度算法，及對作業(yè)性能的估計和任務(wù)調(diào)度的策略。在算法實驗中，分別進行了估計完成時間準確率實驗和性能比較實驗。還對調(diào)度器估計作業(yè)完成時間的準備率與實際作業(yè)完成時間進行了對比，并將該調(diào)度器和其他三種已有的調(diào)度器進行了對比實驗。實驗結(jié)果表明，本算法基本達到了準實時MapReduce調(diào)度的預期目標，具有推廣價值。

參考文獻：

[1] 陳艷金. MapReduce模型在Hadoop平臺下實現(xiàn)作業(yè)調(diào)度算法的研究和改進.[D].華南理工大學，2011.

[2] 張霄宏，雒芬，賈宗璞，等. 一種適用于Hadoop MapReduce環(huán)境的數(shù)據(jù)預取方法[J]. 西安電子科技大學學報，2014（2）.

[3] Z. Guo，G. Fox，M. Zhou.Investigation of data locality inMapReduce[C]. Proceedings of the12th IEEE/ACM International Symposiumon Cluster， Cloud and Grid Computing，2012.