云計(jì)算環(huán)境下基于時(shí)間期限和預(yù)算的調(diào)度算法

劉亞秋，邢樂樂，景維鵬

(東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院，哈爾濱 150040)

1 概述

隨著網(wǎng)格計(jì)算和并行計(jì)算的發(fā)展，云計(jì)算應(yīng)運(yùn)而生，這宣告低成本、高性能計(jì)算時(shí)代的到來。它將計(jì)算作為一種服務(wù)提供給用戶，實(shí)際上是計(jì)算能力的商品化，用戶根據(jù)自己的需求使用云計(jì)算服務(wù)。在現(xiàn)有的云計(jì)算研究中，作業(yè)調(diào)度作為其運(yùn)行樞紐，一直是研究的熱點(diǎn)技術(shù)之一，除了影響作業(yè)響應(yīng)能力和執(zhí)行效率外，還直接關(guān)系到整個(gè)平臺(tái)的系統(tǒng)性能、吞吐量和資源利用率。

目前，在已有的云計(jì)算調(diào)度研究中鮮有考慮云計(jì)算動(dòng)態(tài)環(huán)境下用戶實(shí)際需求對(duì)調(diào)度影響的算法，其中，對(duì)時(shí)間期限和最高預(yù)算的研究，較早是在網(wǎng)格計(jì)算環(huán)境中。如文獻(xiàn)[1-2]分別提出一種網(wǎng)格環(huán)境下的考慮時(shí)間期限或者預(yù)算的作業(yè)調(diào)度，但滿足的是單一用戶需求，達(dá)到資源的時(shí)間最優(yōu)或者預(yù)算最優(yōu)，這樣很容易將任務(wù)集中分配到某一個(gè)資源上，造成負(fù)載不平衡。文獻(xiàn)[3]在上述算法基礎(chǔ)上同時(shí)考慮時(shí)間期限和預(yù)算問題，計(jì)算網(wǎng)格環(huán)境下所有資源在時(shí)間和預(yù)算上的均衡度，依此為任務(wù)分配合適的資源，以達(dá)到優(yōu)化的目的，但該算法在調(diào)度時(shí)忽略了數(shù)據(jù)傳輸時(shí)間和網(wǎng)格環(huán)境的變化，且算法復(fù)雜度較高。而文獻(xiàn)[4]算法側(cè)重于判斷網(wǎng)格中資源的在時(shí)間和預(yù)算上不同的效益值，僅以此動(dòng)態(tài)選擇時(shí)間最優(yōu)或者代價(jià)最優(yōu)，沒有明確考慮時(shí)間和預(yù)算效益值相同時(shí)調(diào)度的情況，且忽略了作業(yè)優(yōu)先級(jí)與用戶需求的關(guān)系。

已有的云計(jì)算調(diào)度問題研究除自帶算法外，如文獻(xiàn)[5]將該路由領(lǐng)域的加權(quán)輪詢思想應(yīng)用于作業(yè)調(diào)度中，提出了基于優(yōu)先級(jí)的加權(quán)輪轉(zhuǎn)調(diào)度算法，算法中優(yōu)先級(jí)和權(quán)值的計(jì)算僅以作業(yè)大小來判斷，既沒有考慮用戶要求，也不能適應(yīng)動(dòng)態(tài)的云環(huán)境。文獻(xiàn)[6-7]僅考慮了動(dòng)態(tài)云的特點(diǎn)，前者提出滑動(dòng)窗口的設(shè)計(jì)，通過調(diào)節(jié)窗口的大小來平衡云計(jì)算集群的負(fù)載，后者在原有 DLS算法的基礎(chǔ)上，加入Bayesian認(rèn)知模型和社會(huì)學(xué)信任模型，提出Cloud-DLS算法。但上述 2種算法均沒有考慮用戶對(duì)作業(yè)的實(shí)際需求。文獻(xiàn)[8]也提出一種動(dòng)態(tài)均衡調(diào)度，通過調(diào)整優(yōu)先級(jí)為作業(yè)提供不同的服務(wù)，但是也無(wú)法保證在特定時(shí)間期限下作業(yè)是否能被執(zhí)行。文獻(xiàn)[9]對(duì)作業(yè)的評(píng)價(jià)和最優(yōu)化進(jìn)行研究，側(cè)重于最優(yōu)化一組作業(yè)的總執(zhí)行時(shí)間，對(duì)其中的某一作業(yè)無(wú)法保證響應(yīng)時(shí)間。為更合理地分配計(jì)算資源，提高集群的作業(yè)容量，文獻(xiàn)[10]提出一種最后期限評(píng)價(jià)模型，由模型獲得作業(yè)所需的最小資源數(shù)，即最小map槽數(shù)和最小reduce槽數(shù)，以此保證作業(yè)完成時(shí)間，并盡可能地提高集群作業(yè)數(shù)。但是此模型是靜態(tài)的，最小資源數(shù)一旦確定便不再改變，而無(wú)法適應(yīng)動(dòng)態(tài)變化的集群網(wǎng)絡(luò)環(huán)境，且沒有考慮預(yù)算問題。

本文提出一種基于時(shí)間期限和預(yù)算雙重約束的云計(jì)算調(diào)度改進(jìn)算法(DBS)。根據(jù)用戶在時(shí)間期限和預(yù)算上的實(shí)際需求，設(shè)置不同優(yōu)先級(jí)的隊(duì)列，通過權(quán)值計(jì)算模型得到作業(yè)權(quán)值，并作為優(yōu)先級(jí)進(jìn)行作業(yè)排序，結(jié)合時(shí)間和預(yù)算評(píng)價(jià)模型，依次調(diào)度作業(yè)分配集群計(jì)算資源，并且更新作業(yè)和集群信息，以適應(yīng)云環(huán)境的動(dòng)態(tài)變化，形成完整的調(diào)度策略。

2 基本模型

針對(duì)云計(jì)算環(huán)境下網(wǎng)絡(luò)負(fù)載及任務(wù)數(shù)動(dòng)態(tài)變化的特點(diǎn)，同時(shí)考慮到用戶對(duì)時(shí)間期限和預(yù)算的實(shí)際需求，以及可能在時(shí)間期限和預(yù)算要求程度上的不同傾向，本文設(shè)計(jì)權(quán)值計(jì)算模型、最高預(yù)算評(píng)價(jià)模型和權(quán)值更新模型。

模型1 權(quán)值計(jì)算模型

根據(jù)作業(yè)的時(shí)間影響因子、最后截止時(shí)間和最高預(yù)算來計(jì)算權(quán)值，表達(dá)式如下：

其中，tasksNum表示作業(yè)的大??；D表示用戶設(shè)定的作業(yè)的最遲截止時(shí)間；B表示作業(yè)的最高預(yù)算；V表示資源在某一時(shí)刻的處理能力(考慮資源的當(dāng)前負(fù)載)；c表示資源處理任務(wù)時(shí)每秒的收費(fèi)；?表示用戶對(duì)作業(yè)完成時(shí)間要求的影響因子。

模型2 最高預(yù)算評(píng)價(jià)模型

二是拓寬思維視野。思維可以是工作發(fā)展的最大動(dòng)力，也可以是最大的阻力。歷史上任何一次變革，都是首先從拓展思維視野、變革思想觀念開始的。軍民融合參與主體多元、涉及領(lǐng)域?qū)拸V、利益交織重疊，必須倡導(dǎo)對(duì)思想的解放與更新，強(qiáng)化融合共贏理念，堅(jiān)持優(yōu)長(zhǎng)互促、兼容互補(bǔ)、資源互投、效益互享，破除自成體系、自我封閉的陳舊觀念，在更廣范圍、更高層次、更深程度上，凝聚軍民融合發(fā)展合力，提升軍民融合發(fā)展效能。

以時(shí)間期限評(píng)價(jià)模型[10]為模板，推導(dǎo)出預(yù)算評(píng)價(jià)模型，為使推導(dǎo)簡(jiǎn)化，本文做出以下假設(shè)：(1)集群中節(jié)點(diǎn)對(duì) map任務(wù)和reduce任務(wù)的處理時(shí)間是相等的；(2)輸入數(shù)據(jù)的塊大小在HDFS中已經(jīng)配置好；(3)每個(gè)reduce節(jié)點(diǎn)得到同等比例的reduce數(shù)據(jù)。

為評(píng)價(jià)作業(yè) J的執(zhí)行時(shí)間T，考慮 map完成時(shí)間，reduce完成時(shí)間和數(shù)據(jù)傳輸時(shí)間如下：

其中，Tm表示處理一個(gè) map任務(wù)所需的時(shí)間；Tr表示處理一個(gè)reduce任務(wù)所需的時(shí)間；Td表示map和reduce任務(wù)傳輸一單位數(shù)據(jù)所需的時(shí)間；δ表示job輸入數(shù)據(jù)；fδ表示reduce任務(wù)的輸入數(shù)據(jù)；nm表示map任務(wù)的槽數(shù)；nr表示reduce任務(wù)的槽數(shù)。

當(dāng)給出時(shí)間期限D(zhuǎn)和最高預(yù)算B時(shí)，表達(dá)式為：

其中，t表示job提交的時(shí)間；Sm表示第一個(gè)map任務(wù)開始的時(shí)間。從預(yù)算角度考慮，reduce任務(wù)最晚開始時(shí)間為：

時(shí)間期限D(zhuǎn)和最高預(yù)算B滿足：

因此，從預(yù)算角度考慮，作業(yè)Job需求的最小map槽數(shù)和最小reduce槽數(shù)分別為：

模型3 權(quán)值更新模型

系統(tǒng)設(shè)置為每隔500 ms更新一次作業(yè)最小槽數(shù)和作業(yè)權(quán)值。根據(jù)當(dāng)前集群的作業(yè)運(yùn)行情況，重新計(jì)算得出作業(yè)的最小槽數(shù)，然后和已得到的槽數(shù)進(jìn)行比較，如果已得到的槽數(shù)比應(yīng)得的槽數(shù)少，則適量地增加作業(yè)權(quán)值，如果已得到的槽數(shù)比應(yīng)得的槽數(shù)多，則適量地減少作業(yè)權(quán)值。

然后比較當(dāng)前作業(yè)的權(quán)值和平均值，如果作業(yè)權(quán)值小于平均值，則：

如果作業(yè)權(quán)值大于平均值，說明作業(yè)在其所在的隊(duì)列中已經(jīng)處于優(yōu)勢(shì)，等待500 ms，在下次更新時(shí)，若作業(yè)依然無(wú)法滿足最小槽數(shù)，則提交到上一級(jí)隊(duì)列，以增加獲得資源和調(diào)度的機(jī)會(huì)。

同理，當(dāng)作業(yè)得到的槽數(shù)多于最小槽數(shù)，且作業(yè)權(quán)值大于其所在隊(duì)列的平均值時(shí)，更新作業(yè)權(quán)值：

若500 ms后依然獲得過多的資源，則調(diào)到下一級(jí)隊(duì)列。

3 算法設(shè)計(jì)

本文在云計(jì)算環(huán)境下加入時(shí)間期限和預(yù)算的雙重約束，結(jié)合評(píng)價(jià)模型提出了DBS算法，為Hadoop集群設(shè)置3 個(gè)隊(duì)列：HightimeQueue，MidtimeQueue，LowtimeQueue，在配置文件中設(shè)置不同的計(jì)算資源比例和收費(fèi)標(biāo)準(zhǔn)：(1)HightimeQueue擁有最多的調(diào)度機(jī)會(huì)和計(jì)算資源，盡可能地保證對(duì)時(shí)間要求高的用戶作業(yè)的需求，但是相應(yīng)的費(fèi)用比其他2個(gè)隊(duì)列要高。(2)LowtimeQueue里的作業(yè)雖然對(duì)時(shí)間要求比較低，但是也為它配置一定的計(jì)算資源，盡可能避免高時(shí)間要求的作業(yè)獨(dú)占資源，低時(shí)間作業(yè)遲遲得不到響應(yīng)的情況，進(jìn)而可以使集群負(fù)載維持在一個(gè)較合理的水平。(3)MidtimeQueue的優(yōu)先級(jí)在上述兩者之間，針對(duì)的是用戶對(duì)時(shí)間期限和預(yù)算要求相同的作業(yè)，保證了該類作業(yè)也可以得到一定的調(diào)度機(jī)會(huì)。

當(dāng)JobClient提交作業(yè)后，會(huì)進(jìn)入一個(gè)等待隊(duì)列，經(jīng)過預(yù)處理，根據(jù)式(1)，計(jì)算出作業(yè)的權(quán)值，更新作業(yè)信息。然后根據(jù)用戶提交的時(shí)間影響因子，放入合適的隊(duì)列，為降低算法的復(fù)雜度，時(shí)間影響因子取值 0.0、0.5、1.0，分別對(duì)應(yīng) LowtimeQueue、MidtimeQueue和 HightimeQueue。分類結(jié)束之后，分別對(duì)隊(duì)列中的作業(yè)根據(jù)權(quán)值和提交時(shí)間進(jìn)行排序，完成之后，等待Tasktracker發(fā)送心跳請(qǐng)求分配任務(wù)。

TaskTracker自主檢測(cè)當(dāng)前節(jié)點(diǎn)的狀態(tài)，若發(fā)現(xiàn)存在空閑資源，則主動(dòng)向 JobTracker發(fā)送信息，請(qǐng)求任務(wù)，JobTracker接收到信息后，啟動(dòng)作業(yè)調(diào)度器，選擇作業(yè)進(jìn)行分配。算法的偽代碼如下：

其中，m為集群總的資源數(shù)；n為集群中的作業(yè)數(shù)。算法的時(shí)間復(fù)雜度為 O (3n)，空間復(fù)雜度為 O( m n)。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

為了檢測(cè)DBS算法的性能，在實(shí)驗(yàn)條件有限的情況下，搭建由6個(gè)節(jié)點(diǎn)構(gòu)成的虛擬hadoop集群，其中每個(gè)節(jié)點(diǎn)內(nèi)存為4 GB，CPU配置為雙核2.4 GHz，操作系統(tǒng)為L(zhǎng)inux Ubuntu 10.0，Hadoop版本為Hadoop0.20.2。使用HDFS進(jìn)行數(shù)據(jù)存儲(chǔ)，每一個(gè)文件塊大小為64 MB，并有3個(gè)副本。其中，一個(gè)節(jié)點(diǎn)設(shè)置為JobTracker和NameNode，其他節(jié)點(diǎn)為TaskTracker和DataNode。

4.2 結(jié)果分析

為比較調(diào)度算法對(duì)不同用戶需求作業(yè)的影響，實(shí)驗(yàn)將作業(yè)分為2組，用Hadoop自帶的FIFO算法進(jìn)行比較。

實(shí)驗(yàn)1 相同大小作業(yè)不同時(shí)間影響因子

在相同大小作業(yè)不同時(shí)間影響因子的情況下，相關(guān)作業(yè)的參數(shù)設(shè)定以及集群不同調(diào)度算法對(duì)作業(yè)的響應(yīng)時(shí)間如表1所示。

表1 DBS與FIFO調(diào)度算法結(jié)果比較1

可以看出，面對(duì)相同大小的作業(yè)，F(xiàn)IFO算法對(duì)作業(yè)無(wú)差別處理，平均響應(yīng)時(shí)間為1 175.5 s，平均費(fèi)用為152.6元，DBS算法平均響應(yīng)時(shí)間為1 154.75 s，平均費(fèi)用為145.29元，不僅提高了集群的處理能力，而且根據(jù)作業(yè)不同的需求調(diào)整執(zhí)行次序，盡可能保證時(shí)間和預(yù)算的約束，更好地體現(xiàn)了作業(yè)的公平性。

集群內(nèi)各個(gè)作業(yè)的map任務(wù)執(zhí)行情況如圖1所示。可以看出，Job1執(zhí)行速率最快，Job2執(zhí)行最慢，雖然Job3和Job4的map任務(wù)結(jié)束時(shí)間差不多，但是時(shí)間期限為1 300 s的Job3比時(shí)間期限為1 200 s的Job4完成時(shí)間要早一些，因?yàn)?個(gè)作業(yè)時(shí)間影響因子為0.5，綜合考慮時(shí)間和預(yù)算，Job3權(quán)值要比Job4高，增加了一些執(zhí)行的機(jī)會(huì)。此外，在Job1和Job3已完成，Job4即將完成的情況下，Job2試圖分配更多的map任務(wù)，體現(xiàn)了算法對(duì)集群的動(dòng)態(tài)變化的反應(yīng)，加快了map任務(wù)的執(zhí)行時(shí)間。

圖1 DBS算法下作業(yè)的map任務(wù)數(shù)分配執(zhí)行情況

實(shí)驗(yàn)2 不同作業(yè)不同時(shí)間影響因子

在不同作業(yè)不同時(shí)間影響因子的情況下，相關(guān)作業(yè)參數(shù)設(shè)定以及DBS算法和FIFO算法作業(yè)處理結(jié)果對(duì)比如表2所示。

表2 DBS與FIFO調(diào)度算法結(jié)果比較2

可以看出，面對(duì)不同大小的作業(yè)，DBS算法的平均響應(yīng)時(shí)間為1 230 s，平均花費(fèi)為148.07元，優(yōu)于FIFO算法76.5 s，節(jié)省21.9元。另外從圖中可以看到，雖然Job4的執(zhí)行時(shí)間比Deadline多了37 s，這是因?yàn)樵趓educe階段可能會(huì)出現(xiàn)數(shù)據(jù)不均衡的情況，但是由于Job4的時(shí)間影響因子為0.5，Budget沒有超出最高預(yù)算，所以認(rèn)為Job4執(zhí)行成功，響應(yīng)時(shí)間在可接受范圍內(nèi)。

各個(gè)作業(yè)的map和reduce任務(wù)執(zhí)行情況如圖2所示，Job3之所以比Job1結(jié)束的快，一方面是為了滿足截止時(shí)間，另一方面當(dāng)作業(yè)規(guī)模比較小時(shí)，數(shù)據(jù)本地性比較好，減少了數(shù)據(jù)在節(jié)點(diǎn)間的復(fù)制和傳輸，任務(wù)執(zhí)行速率加快。同理Job4作業(yè)數(shù)據(jù)比較大，增加了傳輸時(shí)間和處理時(shí)間，在reduce階段執(zhí)行時(shí)間較長(zhǎng)，但即使如此，也優(yōu)于FIFO的作業(yè)響應(yīng)時(shí)間。

圖2 DBS算法下作業(yè)的map和reduce任務(wù)分配執(zhí)行情況

5 結(jié)束語(yǔ)

本文提出一種在云計(jì)算環(huán)境下，根據(jù)作業(yè)在時(shí)間期限和預(yù)算上不同需求動(dòng)態(tài)調(diào)整分配的調(diào)度算法。實(shí)驗(yàn)結(jié)果表明，該算法能有效地減少作業(yè)響應(yīng)時(shí)間，均衡作業(yè)的不同需求，且算法復(fù)雜度較低，具有較好的穩(wěn)定性。由于云計(jì)算環(huán)境面臨作業(yè)類型的復(fù)雜多樣，因此下一步將致力于面向數(shù)據(jù)類型更復(fù)雜，且具有多元約束的作業(yè)的調(diào)度問題，可以從建立一般約束模型，簡(jiǎn)化約束等方面進(jìn)行研究。

[1]Abramson D, Buyya R, Giddy J.A Computational Economy for Grid Computing and Its Implementation in the Nimrod-G Resource Broker[J].Future Generation Computer Systems,2002, 18(8): 1061-1074.

[2]Yu Jia, Buyya R, Tham C K.Cost-based Scheduling of A Scientific Workflow Application on Utility Grids[C]//Proc.of the 1st International Conference on e-Science and Grid Computing.Washington D.C., USA: IEEE Press, 2005.

[3]Garg S K, Buyya R, Siegel H J.Time and Cost Trade-off Management for Scheduling Parallel Applications on Utility Grids[J].Future Generation Computer Systems, 2009, 26(1):1344-1355.

[4]李慧敏, 蔣秀鳳.基于時(shí)間期限和預(yù)算效益函數(shù)的網(wǎng)格資源調(diào)度算法[J].福州大學(xué)學(xué)報(bào), 2009, 37(6): 803-807.

[5]鄧自立.云計(jì)算中的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)和Hadoop平臺(tái)研究[D].合肥: 中國(guó)科學(xué)技術(shù)大學(xué), 2009.

[6]張密密.MapReduce模型在Hadoop實(shí)現(xiàn)中的性能分析及改進(jìn)優(yōu)化[D].成都: 電子科技大學(xué), 2010.

[7]Wang Wei, Zeng Guosun, Tang Daizhong.Cloud-DLS:Dynamic Trusted Scheduling for Cloud Computing[J].Expert Systems with Applications, 2011, 39(3): 2321- 2329.

[8]Sandholm T, Lai T.Dynamic Proportional Share Scheduling in Hadoop[C]//Proc.of the 15th International Workshop on Job Scheduling Strategies for Parallel Processing.Atlanta, USA:[s.n.], 2010.

[9]Zaharia M, Borthakur D, Sarma J S.Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling[C]//Proc.of the 5th European Conference on Computer Systems.New York, USA: ACM Press, 2010.

[10]Kc K, Anyamwu K.Scheduling Hadoop Jobs to Meet Deadlines[C]//Proc.of Conference on Cloud Computing Technology and Science.Indianapolis, USA: IEEE Press, 2010.