一種優(yōu)化的并行數(shù)據(jù)流調(diào)度算法

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

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

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

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

文章編號：1009-3044（2019）22-0003-02

開放科學（資源服務(wù)）標識碼（OSID）：

1 引言

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

其中，[Tmgoal]為目標完成時間，[Tcurr]為當前時間。

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

參考文獻：

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

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