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

劉亞秋，邢樂樂，景維鵬

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

1 概述

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

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

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

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

2 基本模型

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

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

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

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

模型2 最高預(yù)算評價模型

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

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

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

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

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

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

時間期限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è)的最小槽數(shù)，然后和已得到的槽數(shù)進行比較，如果已得到的槽數(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è)在其所在的隊列中已經(jīng)處于優(yōu)勢，等待500 ms，在下次更新時，若作業(yè)依然無法滿足最小槽數(shù)，則提交到上一級隊列，以增加獲得資源和調(diào)度的機會。

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

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

3 算法設(shè)計

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

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

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

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

4 實驗與結(jié)果分析

4.1 實驗環(huán)境

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

4.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

[6]張密密.MapReduce模型在Hadoop實現(xià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.