葛茂松 王永利 張立銘 趙佳彬 于占龍 張國忠

摘要：本文提出一種基于MapReduce的并行數(shù)據(jù)流調(diào)度策略，包括作業(yè)性能估計策略和任務(wù)調(diào)度策略。通過對過去作業(yè)和任務(wù)信息的統(tǒng)計，對任務(wù)完成時間、所需資源和優(yōu)先級進(jìn)行估算，并以此對作業(yè)進(jìn)行調(diào)度。經(jīng)實(shí)驗(yàn)測試，利用該策略設(shè)計的算法可達(dá)到預(yù)期調(diào)度目標(biāo)。

關(guān)鍵詞：并行數(shù)據(jù)流;調(diào)度策略;作業(yè)性能

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

文章編號：1009-3044（2019）26-0011-02

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

MapReduce是用于大規(guī)模數(shù)據(jù)集的一種并行運(yùn)算模型，可用于分布式查詢、分布式排序、機(jī)器學(xué)習(xí)、文檔聚類等等[1]。MapReduce調(diào)度算法分兩部分：作業(yè)性能估計算法和任務(wù)調(diào)度算法。當(dāng)用戶提交一項(xiàng)作業(yè)時，作業(yè)會被分成多個任務(wù)，一個作業(yè)的任務(wù)將由作業(yè)調(diào)度功能將其分配到某個節(jié)點(diǎn)上完成，作業(yè)調(diào)度算法的主要任務(wù)就是選擇一個合適的作業(yè)并將其分配到合適的節(jié)點(diǎn)上[2]。

2 作業(yè)性能估計策略

作業(yè)性能估計策略就是，統(tǒng)計出當(dāng)前作業(yè)中的已完成任務(wù)所用的完成時間和任務(wù)數(shù)，再根據(jù)這些數(shù)據(jù)推測當(dāng)前作業(yè)中的任務(wù)平均完成時間，然后推測出當(dāng)前執(zhí)行任務(wù)的剩余完成時間。當(dāng)我們就完成對任務(wù)剩余時間的估算后，就可以利用該數(shù)據(jù)作為判斷任務(wù)性能的依據(jù)，來確定任務(wù)的優(yōu)先級，再進(jìn)行后期的任務(wù)調(diào)度功能了。

設(shè)某一項(xiàng)正在運(yùn)行的作業(yè)為m，已完成任務(wù)集合為[Cm]，作業(yè)m中的任務(wù)i的完成時間為[αmi]。我們可通過作業(yè)m中的已完成任務(wù)集合[Cm]來推測作業(yè)m中的任務(wù)平均完成時間，若設(shè)任務(wù)m的平均完成時間為[μm]，我們有公式1：

可看出，對于不同的任務(wù)執(zhí)行器[TTt]，將會有相應(yīng)的[μtm]。并且由于存在任務(wù)執(zhí)行器之間的異構(gòu)，一般情況下，[μtm≠μm]。但是，在本文的調(diào)度算法策略中，我們假設(shè)[μtm=μm]。因?yàn)?，位于工作?jié)點(diǎn)中的作業(yè)調(diào)度器，是通過從任務(wù)節(jié)點(diǎn)傳來的心跳函數(shù)被觸發(fā)執(zhí)行的，任務(wù)節(jié)點(diǎn)的心跳函數(shù)包括一些當(dāng)前狀態(tài)信息，例如，目前空閑的執(zhí)行單元數(shù)目等，工作節(jié)點(diǎn)中的作業(yè)調(diào)度器則需要根據(jù)心跳函數(shù)傳來的狀態(tài)信息，來完成它的調(diào)度工作。為了實(shí)現(xiàn)快速響應(yīng)，我們盡量保持調(diào)度算法簡單。所以，當(dāng)假設(shè)[μtm=μm]時，只需根據(jù)所有正在運(yùn)行的作業(yè)m的平均完成時間就可以估計資源分配情況，其復(fù)雜度為O（M）。但若把所有任務(wù)執(zhí)行器[TTt]以及其平均任務(wù)完成時間[μtm]都考慮在內(nèi)的話，算法的復(fù)雜度將會達(dá)到指數(shù)級別，無法保證作業(yè)調(diào)度器的快速響應(yīng)。

另外，任務(wù)調(diào)度動態(tài)而高速的，因此，任務(wù)調(diào)度和任務(wù)完成時間的估算也會相隔很短時間就執(zhí)行一次。即使將[μtm≠μm]的情況考慮在內(nèi)，并以此得到更為精確的估算調(diào)度算法，其實(shí)，對于作業(yè)資源分配的影響也是很小的。

而且，作業(yè)m的完成時間估算只與那些分配到該作業(yè)m任務(wù)的任務(wù)執(zhí)行器有關(guān)，在實(shí)際情況中，某作業(yè)執(zhí)行過程中，只與MapReduce集群中的部分任務(wù)執(zhí)行器相關(guān)，因此，沒有必要獲取所有任務(wù)執(zhí)行器的平均任務(wù)完成時間[μtm]。

在調(diào)度算法執(zhí)行過程中，對于任意一個屬于作業(yè)m的正在執(zhí)行的任務(wù)[tmi]，我們用公式2表示：

其中，只有任務(wù)的已運(yùn)行時間[βmi]已知，任務(wù)完成時間[αmi]和任務(wù)剩余時間[δmi]均未知。我們假設(shè)任務(wù)[tmi]的完成時間等于任務(wù)平均完成時間，即[αmi=μm]，將其帶入公式，我們可以得到公式3：

當(dāng)我們完成了對任務(wù)[tmi]的剩余時間[δmi]的估算后，就可以以此作為判斷任務(wù)性能的依據(jù)，來確定任務(wù)的優(yōu)先級并對任務(wù)進(jìn)行調(diào)度了。

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

任務(wù)調(diào)度策略的主要思想是計算出作業(yè)的優(yōu)先級，再根據(jù)作業(yè)的優(yōu)先級進(jìn)行調(diào)度。調(diào)度算法的思想是在作業(yè)服務(wù)器的工作節(jié)點(diǎn)中進(jìn)行優(yōu)先隊(duì)列的維護(hù)，用戶存儲作業(yè)的ID、狀態(tài)以及優(yōu)先級。

3.1 維護(hù)優(yōu)先隊(duì)列思路

1） 當(dāng)有作業(yè)提交時，將作業(yè)進(jìn)隊(duì)，作業(yè)狀態(tài)為NODATA。

2）當(dāng)任務(wù)服務(wù)器將作業(yè)狀態(tài)發(fā)送給作業(yè)服務(wù)器JobTracker時，如果作業(yè)已經(jīng)超過目標(biāo)完成時間，將優(yōu)先隊(duì)列中該作業(yè)的狀態(tài)改為UNDEAD;否則更新其估計的任務(wù)執(zhí)行單元數(shù)目[smreq]，作業(yè)狀態(tài)設(shè)置為ADJUST。

3）當(dāng)有作業(yè)完成時，將該作業(yè)從優(yōu)先隊(duì)列中去除。

4） 調(diào)度器從優(yōu)先隊(duì)列隊(duì)首取出作業(yè)，根據(jù)作業(yè)的狀態(tài)分為UNDEAD、NODATA、ADJUST三種狀態(tài)。

5） 如果作業(yè)狀態(tài)為UNDEAD，取出隊(duì)首中同樣為UNDEAD的作業(yè)，分別給每個作業(yè)最大數(shù)目的任務(wù)執(zhí)行單元。

6） 如果作業(yè)狀態(tài)為NODATA，取出隊(duì)首中同樣為NODATA的作業(yè)，分別給每個作業(yè)最大數(shù)目的任務(wù)執(zhí)行單元。

7） 如果作業(yè)狀態(tài)為ADJUST，計算估計的任務(wù)執(zhí)行單元數(shù)目，并分配給作業(yè)數(shù)目的任務(wù)執(zhí)行單元。

3.2初始化優(yōu)先隊(duì)列的算法

4 估計完成時間準(zhǔn)確率實(shí)驗(yàn)

在某RFID資產(chǎn)管理系統(tǒng)中，我們利用MapReduce模型對列存儲中的RFID數(shù)據(jù)建立作業(yè)。實(shí)驗(yàn)記錄了每次工作節(jié)點(diǎn)進(jìn)行調(diào)度時估算的作業(yè)完成時間和實(shí)際的工作結(jié)束時間。我們將這兩種數(shù)據(jù)進(jìn)行對比，來驗(yàn)證此策略下估算的工作完成時間的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果如圖1所示：

由圖1可看出，在作業(yè)運(yùn)行的前30%時間里，由于準(zhǔn)實(shí)時調(diào)度器只收集到關(guān)于該作業(yè)的少量信息，估算出的作業(yè)完成時間與實(shí)際完成時間差距比較大。但當(dāng)作業(yè)運(yùn)行時間超過30%后，由于調(diào)度器獲得了越來越多的信息數(shù)據(jù)，估算出的作業(yè)完成時間就在實(shí)際完成時間附近上下震蕩，振幅越來越小，逐漸接近實(shí)際完成時間。

5 結(jié)論

在該策略中，調(diào)度器可通過記錄的作業(yè)和任務(wù)的相關(guān)數(shù)據(jù)信息，對任務(wù)完成時間進(jìn)行估算，再計算出當(dāng)前作業(yè)所需資源數(shù)和相應(yīng)的優(yōu)先級，然后根據(jù)作業(yè)優(yōu)先級對作業(yè)進(jìn)行調(diào)度。實(shí)驗(yàn)結(jié)果表明，當(dāng)本調(diào)度器獲得了一定數(shù)量的信息后，估算出的作業(yè)完成時間基本接近實(shí)際完成時間。該策略基本達(dá)到了MapReduce調(diào)度的預(yù)期目標(biāo)。

參考文獻(xiàn)：

[1] 朱付保，白慶春，湯萌萌，等.基于MapReduce的數(shù)據(jù)流頻繁項(xiàng)集挖掘算法[J].華中師范大學(xué)學(xué)報 （自然科學(xué)版） ，2017，51（4）：429-434.

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

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