基于MapReduce的并行數據流調度策略

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

摘要：本文提出一種基于MapReduce的并行數據流調度策略，包括作業性能估計策略和任務調度策略。通過對過去作業和任務信息的統計，對任務完成時間、所需資源和優先級進行估算，并以此對作業進行調度。經實驗測試，利用該策略設計的算法可達到預期調度目標。

關鍵詞：并行數據流;調度策略;作業性能

中圖分類號： TP31? ? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

MapReduce是用于大規模數據集的一種并行運算模型，可用于分布式查詢、分布式排序、機器學習、文檔聚類等等[1]。MapReduce調度算法分兩部分：作業性能估計算法和任務調度算法。當用戶提交一項作業時，作業會被分成多個任務，一個作業的任務將由作業調度功能將其分配到某個節點上完成，作業調度算法的主要任務就是選擇一個合適的作業并將其分配到合適的節點上[2]。

2 作業性能估計策略

作業性能估計策略就是，統計出當前作業中的已完成任務所用的完成時間和任務數，再根據這些數據推測當前作業中的任務平均完成時間，然后推測出當前執行任務的剩余完成時間。當我們就完成對任務剩余時間的估算后，就可以利用該數據作為判斷任務性能的依據，來確定任務的優先級，再進行后期的任務調度功能了。

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

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

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

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

在調度算法執行過程中，對于任意一個屬于作業m的正在執行的任務[tmi]，我們用公式2表示：

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

當我們完成了對任務[tmi]的剩余時間[δmi]的估算后，就可以以此作為判斷任務性能的依據，來確定任務的優先級并對任務進行調度了。

3 任務調度策略

任務調度策略的主要思想是計算出作業的優先級，再根據作業的優先級進行調度。調度算法的思想是在作業服務器的工作節點中進行優先隊列的維護，用戶存儲作業的ID、狀態以及優先級。

3.1 維護優先隊列思路

1） 當有作業提交時，將作業進隊，作業狀態為NODATA。

2）當任務服務器將作業狀態發送給作業服務器JobTracker時，如果作業已經超過目標完成時間，將優先隊列中該作業的狀態改為UNDEAD;否則更新其估計的任務執行單元數目[smreq]，作業狀態設置為ADJUST。

3）當有作業完成時，將該作業從優先隊列中去除。

4） 調度器從優先隊列隊首取出作業，根據作業的狀態分為UNDEAD、NODATA、ADJUST三種狀態。

5） 如果作業狀態為UNDEAD，取出隊首中同樣為UNDEAD的作業，分別給每個作業最大數目的任務執行單元。

6） 如果作業狀態為NODATA，取出隊首中同樣為NODATA的作業，分別給每個作業最大數目的任務執行單元。

7） 如果作業狀態為ADJUST，計算估計的任務執行單元數目，并分配給作業數目的任務執行單元。

3.2初始化優先隊列的算法

4 估計完成時間準確率實驗

在某RFID資產管理系統中，我們利用MapReduce模型對列存儲中的RFID數據建立作業。實驗記錄了每次工作節點進行調度時估算的作業完成時間和實際的工作結束時間。我們將這兩種數據進行對比，來驗證此策略下估算的工作完成時間的準確率。實驗結果如圖1所示：

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

5 結論

在該策略中，調度器可通過記錄的作業和任務的相關數據信息，對任務完成時間進行估算，再計算出當前作業所需資源數和相應的優先級，然后根據作業優先級對作業進行調度。實驗結果表明，當本調度器獲得了一定數量的信息后，估算出的作業完成時間基本接近實際完成時間。該策略基本達到了MapReduce調度的預期目標。

參考文獻：

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

[2] 富春巖，葛茂松，張立銘，等.一種準實時MapReduce調度算法的改進與實現[J].電腦知識與技術，2016（12）：3-4.

【通聯編輯：梁書】