一種準(zhǔn)實(shí)時(shí)MapReduce調(diào)度算法的改進(jìn)與實(shí)現(xiàn)

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

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

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

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）15-0003-02

1 引言

MapReduce是一個(gè)用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算模型. 廣泛應(yīng)用于分布式查詢(xún)、分布式排序、Web訪(fǎng)問(wèn)日志分析、機(jī)器學(xué)習(xí)以及基于統(tǒng)計(jì)的機(jī)器翻譯等領(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è)提交前，必須對(duì)系統(tǒng)的參數(shù)進(jìn)行預(yù)先設(shè)定。而且，一旦作業(yè)提交，MapReduce系統(tǒng)給每一個(gè)任務(wù)的資源分配策略就已經(jīng)確定下來(lái)，不能根據(jù)任務(wù)執(zhí)行的實(shí)際情況進(jìn)行動(dòng)態(tài)的調(diào)整[3]。本文提出的算法使MapReduce調(diào)度器能夠?qū)φ谶M(jìn)行的任務(wù)的進(jìn)度及任務(wù)的完成時(shí)間進(jìn)行估計(jì)，并在運(yùn)行時(shí)給每個(gè)任務(wù)動(dòng)態(tài)的分配資源，從而提高了MapReduce系統(tǒng)的資源利用率。

2 算法思想

準(zhǔn)實(shí)時(shí)MapReduce調(diào)度算法主要由作業(yè)性能估計(jì)及任務(wù)調(diào)度策略?xún)刹糠纸M成。

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

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

3 準(zhǔn)實(shí)時(shí)MapReduce調(diào)度器的核心類(lèi)及主要功能

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

[2] 張霄宏，雒芬，賈宗璞，等. 一種適用于Hadoop MapReduce環(huán)境的數(shù)據(jù)預(yù)取方法[J]. 西安電子科技大學(xué)學(xué)報(bào)，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.