葛茂松 富春巖 支援 李微娜 周虹

摘要：很多需要對(duì)數(shù)據(jù)流進(jìn)行實(shí)時(shí)處理、快速響應(yīng)。本文對(duì)已有的MapReduce調(diào)度器進(jìn)行了分析，結(jié)合它們的優(yōu)缺點(diǎn)，對(duì)MapReduce調(diào)度算法進(jìn)行了優(yōu)化。實(shí)驗(yàn)表明，該優(yōu)化算法可進(jìn)行精準(zhǔn)的估算，運(yùn)行效率較高。

關(guān)鍵詞：數(shù)據(jù)流;調(diào)度算法;優(yōu)化查詢

中圖分類號(hào)：TP391? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）22-0003-02

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 引言

目前，在電力、電信、金融、網(wǎng)絡(luò)安全等很多領(lǐng)域，都需要對(duì)數(shù)據(jù)流進(jìn)行在線實(shí)時(shí)處理。數(shù)據(jù)流無(wú)須存儲(chǔ)，而需要通過(guò)數(shù)據(jù)流查詢被及時(shí)、快速地處理。為了應(yīng)對(duì)不斷增大的數(shù)據(jù)流規(guī)模，出現(xiàn)了分布式數(shù)據(jù)流處理技術(shù)，根據(jù)數(shù)據(jù)流速率的變化可動(dòng)態(tài)調(diào)整數(shù)據(jù)流查詢所需的計(jì)算資源。

MapReduce是一個(gè)用于大規(guī)模數(shù)據(jù)集的并行運(yùn)算模型，廣泛地應(yīng)用在分布式查詢、分布式排序、web訪問(wèn)日志分析、機(jī)器學(xué)習(xí)等方面。它有FIFO、Capacity Scheduler和Fair Scheduler三種調(diào)度器，這三種調(diào)度器它們有各自的優(yōu)點(diǎn)。但是，共同的缺點(diǎn)是：在作業(yè)提交前，要求對(duì)系統(tǒng)的參數(shù)進(jìn)行預(yù)設(shè)。也就是說(shuō)，一旦作業(yè)提交預(yù)先設(shè)定完成，MapReduce系統(tǒng)給每一個(gè)任務(wù)的資源分配策略就已經(jīng)確定，再無(wú)法根據(jù)實(shí)際情況進(jìn)行動(dòng)態(tài)的調(diào)整，更不要說(shuō)自適應(yīng)的調(diào)整。因此，本文對(duì)MapReduce調(diào)度算法進(jìn)行了優(yōu)化，改進(jìn)后的算法能夠基于正在進(jìn)行的任務(wù)的進(jìn)度對(duì)任務(wù)完成的時(shí)間進(jìn)行預(yù)估，這樣就可以根據(jù)每個(gè)任務(wù)進(jìn)行的情況，自適應(yīng)地動(dòng)態(tài)的分配資源，從而提高系統(tǒng)資源的利用率。

2 相關(guān)定義

為了準(zhǔn)確描述優(yōu)化的MapReduce調(diào)度算法，本文有如下定義，見(jiàn)表1。

其中，作業(yè)m中第i項(xiàng)任務(wù)的任務(wù)完成時(shí)間由任務(wù)已運(yùn)行時(shí)間和任務(wù)剩余時(shí)間兩部分組成，因此有，[αmi=βmi+δmi]，作業(yè)集合[tmi]由[Cm]、[Um]和[Rm]三部分組成。

3 任務(wù)調(diào)度策略

任務(wù)調(diào)度策略就是要根據(jù)作業(yè)性能估算后得到的任務(wù)平均完成時(shí)間，通過(guò)相應(yīng)的公式推導(dǎo)出當(dāng)前作業(yè)所需的任務(wù)執(zhí)行單元的數(shù)量，通過(guò)這個(gè)數(shù)量來(lái)確定當(dāng)前作業(yè)的優(yōu)先級(jí)。調(diào)度器將根據(jù)所確定的優(yōu)先級(jí)分配相適應(yīng)的合理資源。該任務(wù)調(diào)度策略由給作業(yè)分配合適的優(yōu)先級(jí)和分配算法兩部分組成。

3.1 作業(yè)的優(yōu)先級(jí)

在MapReudce中，正在運(yùn)行的某作業(yè)，需要進(jìn)行調(diào)度時(shí)，調(diào)度器會(huì)根據(jù)任務(wù)調(diào)度策略給其分配合適數(shù)量的任務(wù)執(zhí)行單元。

因?yàn)橐鶕?jù)在規(guī)定時(shí)間內(nèi)完成作業(yè)所需要分配的執(zhí)行單元數(shù)而算出來(lái)的作業(yè)的優(yōu)先級(jí)，因此，需要估算出某項(xiàng)作業(yè)m中，正在執(zhí)行的任務(wù)數(shù)和尚未執(zhí)行的任務(wù)數(shù)。如果，每個(gè)任務(wù)執(zhí)行單元需要花費(fèi)[μm]時(shí)間，我們可對(duì)作業(yè)m當(dāng)前所需任務(wù)執(zhí)行單元數(shù)[smreq]進(jìn)行估算，見(jiàn)如下公式：

其中，[Tmgoal]為目標(biāo)完成時(shí)間，[Tcurr]為當(dāng)前時(shí)間。

計(jì)算后，調(diào)度器將依據(jù)得到的[smreq]值作為作業(yè)m的權(quán)重，將當(dāng)前作業(yè)集合放于優(yōu)先隊(duì)列中。

但是，由于任務(wù)調(diào)度策略是依據(jù)以往的任務(wù)運(yùn)行情況對(duì)任務(wù)完成時(shí)間進(jìn)行估算的，因此，在一些特殊情況下，任務(wù)調(diào)度策略無(wú)法準(zhǔn)確地進(jìn)行估算。例如，一些已超過(guò)目標(biāo)完成時(shí)間的作業(yè)，優(yōu)先級(jí)會(huì)被賦予的較高，使其盡快得到資源完成任務(wù)。另外，作業(yè)剛提交的時(shí)，調(diào)度器還未收集到信息，無(wú)法估算作業(yè)最終完成時(shí)間，也就無(wú)法計(jì)算出所需任務(wù)執(zhí)行單元數(shù)[smreq]。這種情況下的作業(yè)將獲得較高的優(yōu)先級(jí)，以方便調(diào)度器盡快調(diào)度該任務(wù)。

因此，調(diào)度器要通過(guò)以下幾個(gè)因素對(duì)任務(wù)的優(yōu)先級(jí)進(jìn)行整體的評(píng)估計(jì)算：第一，判斷作業(yè)是否已超過(guò)目標(biāo)完成時(shí)間;第二，看調(diào)度器是否收集了作業(yè)的狀態(tài)信息;第三，估算出的任務(wù)執(zhí)行單元數(shù)目。

任務(wù)調(diào)度策略中規(guī)定調(diào)度器分配資源的順序?yàn)椋阂呀?jīng)超過(guò)目標(biāo)完成時(shí)間的作業(yè)、未被調(diào)度器收集到信息的作業(yè)、所需任務(wù)執(zhí)行單元數(shù)較大的作業(yè)。

3.2 優(yōu)化的調(diào)度算法

確定了優(yōu)先級(jí)之后就要確定基于作業(yè)的優(yōu)先級(jí)的分配算法。調(diào)度算法主要完成在作業(yè)服務(wù)器中維護(hù)優(yōu)先隊(duì)列的功能。優(yōu)化后的調(diào)度算法定義了三個(gè)函數(shù)，分別是初始化函數(shù)、添加作業(yè)到優(yōu)先隊(duì)列函數(shù)和調(diào)度優(yōu)先隊(duì)列已有作業(yè)函數(shù)。

初始化作業(yè)優(yōu)先隊(duì)列函數(shù)的主要功能是創(chuàng)建一個(gè)優(yōu)先隊(duì)列。其中隊(duì)列的元素為Job類型，包含作業(yè)的Id、作業(yè)的狀態(tài)和當(dāng)前任務(wù)執(zhí)行單元數(shù)等。作業(yè)又包括UDEAD、NODATA、ADJUST這3種狀態(tài)。

用戶在提交新的作業(yè)時(shí)，開(kāi)始調(diào)用添加作業(yè)到優(yōu)先隊(duì)列函數(shù)，這個(gè)函數(shù)的功能是將新作業(yè)加入到優(yōu)先隊(duì)列中去。輸入?yún)?shù)為Job類型，Job類型參數(shù)的初始狀態(tài)為NODATA，偽代碼如下：

當(dāng)工作服務(wù)器收到來(lái)自作業(yè)服務(wù)器的信息時(shí)，將執(zhí)行調(diào)度優(yōu)先隊(duì)列中已有作業(yè)函數(shù)。在函數(shù)中，先遍歷作業(yè)服務(wù)器中返回的任務(wù)列表，如果該任務(wù)已在優(yōu)先隊(duì)列中，就更新作業(yè)優(yōu)先隊(duì)列中相關(guān)信息。若該任務(wù)不在優(yōu)先隊(duì)列中，就將該任務(wù)所屬作業(yè)加入優(yōu)先隊(duì)列中。然后，再按照作業(yè)的優(yōu)先級(jí)依次地取出作業(yè)，進(jìn)行相應(yīng)操作。若該作業(yè)狀態(tài)是UNDEAD狀態(tài)或NODATA狀態(tài)，那么，說(shuō)明該作業(yè)已超出了作業(yè)的目標(biāo)完成時(shí)間;或者此作業(yè)處于剛剛提交狀態(tài)，無(wú)信息可循，那么，將給該作業(yè)分配最大任務(wù)執(zhí)行器數(shù)目maxSlot;若作業(yè)當(dāng)前處于ADJUST狀態(tài)，就依據(jù)公式1進(jìn)行計(jì)算，得出作業(yè)所需任務(wù)執(zhí)行單元數(shù)，并進(jìn)行分配。

4 結(jié)論

本文對(duì)MapReduce調(diào)度算法中的任務(wù)調(diào)度策略進(jìn)行了優(yōu)化。調(diào)度器可根據(jù)記錄的作業(yè)及任務(wù)信息數(shù)據(jù)，估算出任務(wù)完成時(shí)間。優(yōu)化后的算法可計(jì)算出當(dāng)前作業(yè)所需資源，并給出當(dāng)前作業(yè)對(duì)應(yīng)的優(yōu)先級(jí)，形成優(yōu)先隊(duì)列。

通過(guò)模擬真實(shí)場(chǎng)景下多個(gè)作業(yè)提交的情況，對(duì)算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，作業(yè)運(yùn)行的前30%時(shí)間里，因?yàn)槭占降年P(guān)于該作業(yè)的信息數(shù)據(jù)少，所以估算的完成時(shí)間與實(shí)際作業(yè)的完成時(shí)間差距較大。但在作業(yè)運(yùn)行了30%的時(shí)間以后，由于調(diào)度器收集到了足夠的關(guān)于該作業(yè)的信息數(shù)據(jù)，估算的完成時(shí)間與實(shí)際完成時(shí)間基本相符。

在實(shí)驗(yàn)過(guò)程中，初始的幾次實(shí)驗(yàn)運(yùn)行時(shí)間較長(zhǎng)，但實(shí)驗(yàn)次數(shù)增加后，調(diào)度器收集到的信息數(shù)據(jù)量足夠大之后，就可以對(duì)作業(yè)的完成時(shí)間做出比較精準(zhǔn)的估算，分配給作業(yè)的任務(wù)執(zhí)行單元數(shù)也更為合適，運(yùn)行效率較高。

參考文獻(xiàn)：

[1] Bonnet P， Gehrke JE， Seshadri P. Towards sensor database systems[C]//Tan K-L， Franklin MJ， Lui JCS， eds. Proceedings of the 2nd International Conference on Mobile Data Management. Hong Kong： Springer-Verlag， 2010. 3-14.

[2] 富春巖，葛茂松，張立銘，李微娜，趙佳彬，等. 一種準(zhǔn)實(shí)時(shí)MapReduce調(diào)度算法的改進(jìn)與實(shí)現(xiàn)[J]. 電腦知識(shí)與技術(shù)，2016（12）：3-4.

【通聯(lián)編輯：梁書(shū)】