一種改進(jìn)的延時(shí)調(diào)度算法

王鐘斐，王鐘磊

（1.寶雞文理學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西寶雞721013；2.成都銀行四川成都610000）

近年來(lái)，隨著互聯(lián)網(wǎng)應(yīng)用的飛速增長(zhǎng)，海量數(shù)據(jù)的存儲(chǔ)以及處理問(wèn)題得到廣泛的關(guān)注。基于這一背景，云計(jì)算[1-3]應(yīng)運(yùn)而生，該新興的商業(yè)計(jì)算模型以網(wǎng)絡(luò)技術(shù)、虛擬化技術(shù)、分布式計(jì)算技術(shù)為基礎(chǔ)，以按需分配為業(yè)務(wù)模式，具備動(dòng)態(tài)擴(kuò)展、資源共享、寬帶接入等特點(diǎn)[1]。

當(dāng)前大多數(shù)云計(jì)算系統(tǒng)都采用Hadoop平臺(tái)[4-6]來(lái)開發(fā)和調(diào)試程序，Hadoop項(xiàng)目是由Doug Cutting領(lǐng)隊(duì)開發(fā)的開源框架。Hadoop平臺(tái)中的作業(yè)調(diào)度器是以可插拔的方式加載的，目前Hadoop發(fā)布版本中的主流調(diào)度器有3種：先進(jìn)先出調(diào)度器（First In First Out Scheduler）[7-9]、公平調(diào)度器（Fair Scheduler）[10-11]以及計(jì)算能力調(diào)度器（Capacity Scheduler）[12-14]。其中，F(xiàn)IFO為Hadoop的默認(rèn)作業(yè)調(diào)度器，這種調(diào)度算法簡(jiǎn)單明了，但在某些特殊情況下，本地化任務(wù)[15-16]不能充分實(shí)現(xiàn)。

文中從Hadoop主旨出發(fā)，設(shè)計(jì)了旨在增加本地化任務(wù)比率并減少作業(yè)響應(yīng)時(shí)間的改進(jìn)算法。通過(guò)分析各個(gè)作業(yè)的作業(yè)時(shí)間敏感度指標(biāo)并進(jìn)行排序，本文算法優(yōu)先選擇時(shí)間敏感度高的作業(yè)及任務(wù)進(jìn)行資源分配，同時(shí)，引入延時(shí)的調(diào)度思想，以能夠獲得更大比率的本地化任務(wù)，并且顯著縮短作業(yè)的響應(yīng)時(shí)間。實(shí)驗(yàn)結(jié)果表明，使用本文改進(jìn)算法可以顯著降低作業(yè)的響應(yīng)時(shí)間。

1 問(wèn)題的提出

先進(jìn)先出調(diào)度算法（FIFO）為Hadoop的默認(rèn)作業(yè)調(diào)度器，適用于在集群中運(yùn)行單一作業(yè)。該算法簡(jiǎn)單明了，而且JobTracker的工作負(fù)擔(dān)比較輕，但是它也存在以下不足之處。

首先，它遵循嚴(yán)格的FIFO作業(yè)順序來(lái)分配任務(wù)，這意味著，假如隊(duì)列中第一個(gè)作業(yè)還有未被分配的map任務(wù)，那么隊(duì)列中的其他任何作業(yè)任何任務(wù)都得不到分配。這種缺陷在數(shù)據(jù)本地性方面也會(huì)有很大影響，即便隊(duì)列中其他作業(yè)的任務(wù)在某個(gè)節(jié)點(diǎn)上有多個(gè)輸入數(shù)據(jù)塊，這些任務(wù)在第一個(gè)作業(yè)所有map任務(wù)被調(diào)度前，都得不到調(diào)度。其次，由于數(shù)據(jù)本地化是由工作節(jié)點(diǎn)的心跳信息序列隨機(jī)決定的。即工作節(jié)點(diǎn)根據(jù)自己完成任務(wù)的進(jìn)度以及自身的空閑任務(wù)槽情況，發(fā)送相關(guān)信息給主機(jī)節(jié)點(diǎn)并請(qǐng)求任務(wù)分配，由于集群中節(jié)點(diǎn)眾多，而且運(yùn)行情況各異，因此數(shù)據(jù)本地化的具體信息不能事先估計(jì)。

文中考慮到小規(guī)模集群系統(tǒng)中短作業(yè)比較多、數(shù)據(jù)規(guī)模處理不大的特點(diǎn)，提出了一種改進(jìn)的延時(shí)調(diào)度算法。該算法有兩個(gè)特點(diǎn)，一是優(yōu)先選擇時(shí)間敏感度高的作業(yè)及任務(wù)進(jìn)行資源分配，這可以優(yōu)先分配資源給交互型的短作業(yè)；二是根據(jù)優(yōu)先級(jí)的不同決定每個(gè)作業(yè)的等待時(shí)間，這樣可以獲得更大比率的本地化任務(wù)，并且顯著縮短作業(yè)的響應(yīng)時(shí)間。

2 改進(jìn)的延時(shí)調(diào)度算法

針對(duì)原有調(diào)度算法在特殊情況下，本地化任務(wù)不能充分實(shí)現(xiàn)的問(wèn)題，本文從Hadoop主旨出發(fā)，設(shè)計(jì)了旨在增加本地化任務(wù)比率從而減少作業(yè)響應(yīng)時(shí)間的改進(jìn)算法。算法的主要思想是：在執(zhí)行某個(gè)作業(yè)的非本地化任務(wù)之前，都有公平的機(jī)會(huì)獲得該作業(yè)本地化任務(wù)。即該算法的中心思想是為每個(gè)作業(yè)在合理的等待時(shí)間內(nèi)找到一個(gè)本地化map任務(wù)。

對(duì)于短作業(yè)的優(yōu)先調(diào)度目標(biāo)，引入作業(yè)進(jìn)度時(shí)間敏感度，即單位時(shí)間內(nèi)作業(yè)的進(jìn)度增加情況。顯然，作業(yè)進(jìn)度時(shí)間敏感度越高，說(shuō)明進(jìn)度對(duì)時(shí)間的敏感程度越高，這時(shí)若該作業(yè)等待調(diào)度時(shí)間越久，則會(huì)嚴(yán)重影響到該作業(yè)的執(zhí)行性能，這種延時(shí)在交互型作業(yè)中更加不可忍受。舉個(gè)例子：假設(shè)我們有兩個(gè)作業(yè)A和B，A是科學(xué)計(jì)算的作業(yè)，在10 s時(shí)間中，進(jìn)度增加了1%，那么說(shuō)明此刻，該作業(yè)的作業(yè)進(jìn)度時(shí)間敏感度為0.001，該作業(yè)的預(yù)期完成時(shí)間為1 000 s；而作業(yè)B是一個(gè)交互型作業(yè)，在2 s的時(shí)間內(nèi)，已經(jīng)運(yùn)行了50%，那么該作業(yè)的PTU值為0.25，預(yù)期完成時(shí)間為4 s，在這樣的情況下，如果A作業(yè)延時(shí)10 s調(diào)度，則不會(huì)給作業(yè)所屬的用戶帶來(lái)非常明顯的作業(yè)響應(yīng)滯后的感覺(jué)，而如果B作業(yè)延時(shí)10 s調(diào)度，這時(shí)云計(jì)算的用戶體會(huì)非常糟糕。我們更關(guān)注在短時(shí)間內(nèi)，進(jìn)展速度快的作業(yè)應(yīng)該優(yōu)先得到執(zhí)行，需要盡快分配集群資源響應(yīng)該作業(yè)。因此，我們?cè)O(shè)計(jì)該指標(biāo)計(jì)算公式如下：

公式中的f即調(diào)節(jié)因子，根據(jù)實(shí)際情況，調(diào)節(jié)作業(yè)優(yōu)先級(jí)在該作業(yè)進(jìn)度時(shí)間敏感度指標(biāo)中的比重。

首先，該算法在進(jìn)行任務(wù)分配時(shí)不必遵循嚴(yán)格的作業(yè)順序。假如作業(yè)隊(duì)列中第一個(gè)作業(yè)中沒(méi)有本地化map任務(wù)，那么調(diào)度器會(huì)繼續(xù)在后續(xù)作業(yè)中查找。其次，為了給每個(gè)作業(yè)公平的機(jī)會(huì)去獲得自己的本地化任務(wù)，當(dāng)某個(gè)作業(yè)等待一段時(shí)間T1后，還不能從具有空閑任務(wù)槽的節(jié)點(diǎn)中找到本地化任務(wù)，那么為了避免浪費(fèi)集群的計(jì)算資源，本文提出的算法會(huì)分配該作業(yè)的一個(gè)非本地化任務(wù)。這樣，該算法不僅能達(dá)到高本地化任務(wù)的比率，也能增加集群的高利用率。第三，按照作業(yè)時(shí)間進(jìn)度的指標(biāo)對(duì)作業(yè)進(jìn)行排序，這樣對(duì)于某些交互型的需要很快響應(yīng)的作業(yè)，調(diào)度器能夠優(yōu)先調(diào)度并分配集群資源。第四，當(dāng)某個(gè)新作業(yè)加入隊(duì)列時(shí)，把該作業(yè)放在隊(duì)首，優(yōu)先給該作業(yè)分配定額的計(jì)算資源，隨后該作業(yè)在隊(duì)列中的位置則由該作業(yè)的作業(yè)時(shí)間敏感度值所決定。

優(yōu)化調(diào)度算法的執(zhí)行示意圖如下所示：

1）在0:00時(shí)，集群現(xiàn)狀如圖1所示。

圖1 某時(shí)刻集群現(xiàn)狀

2）0:04 s時(shí)，由于此時(shí)任務(wù)1的等待時(shí)間為3 s，故分配該任務(wù)給節(jié)點(diǎn)A，該任務(wù)為非本地化任務(wù)，如圖2所示。

3）0:08 s時(shí)，如圖3所示任務(wù)3進(jìn)入隊(duì)列，則放入隊(duì)首，同時(shí)，由于節(jié)點(diǎn)B具有任務(wù)2的本地化數(shù)據(jù)，將任務(wù)2分配至節(jié)點(diǎn)B，任務(wù)2為本地化任務(wù)。

圖2 某時(shí)刻集群現(xiàn)狀

圖3 某時(shí)刻集群現(xiàn)狀

因此在優(yōu)先響應(yīng)短作業(yè)的前提下，通過(guò)對(duì)非本地化任務(wù)的延時(shí)調(diào)度，寄希望于具有本地化數(shù)據(jù)的節(jié)點(diǎn)在一定時(shí)間內(nèi)向主控節(jié)點(diǎn)報(bào)告狀態(tài)，從而使該非本地化任務(wù)編程本地化任務(wù)。

優(yōu)化后算法的偽代碼如下所示：

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

測(cè)試數(shù)據(jù)：設(shè)定兩組相同的任務(wù)，但輸入數(shù)據(jù)規(guī)模不同，其中作業(yè)A處理數(shù)據(jù)為1 GB，作業(yè)B處理數(shù)據(jù)為64 MB，這樣相對(duì)B而言，作業(yè)A為長(zhǎng)作業(yè)，而B為短作業(yè)，因此作業(yè)B需要及時(shí)分配集群計(jì)算資源，盡快得到響應(yīng)。

如圖4所示，采用作業(yè)時(shí)間敏感度排序：當(dāng)1 GB作業(yè)正在運(yùn)行時(shí)，64 MB作業(yè)加入到作業(yè)隊(duì)列，剛開始64 MB作業(yè)進(jìn)展緩慢，這是前期集群在準(zhǔn)備作業(yè)B的執(zhí)行資源，隨后由于B作業(yè)處理數(shù)據(jù)規(guī)模非常小，這時(shí)其作業(yè)時(shí)間敏感度相對(duì)較高，優(yōu)先得到調(diào)度及計(jì)算資源分配，而1 GB作業(yè)則由于分配少量計(jì)算資源而相對(duì)執(zhí)行速度較慢。

圖4 作業(yè)時(shí)間敏感度因子對(duì)作業(yè)執(zhí)行影響

未采用作業(yè)時(shí)間敏感度排序：1 GB作業(yè)和64 MB作業(yè)呈現(xiàn)競(jìng)爭(zhēng)計(jì)算資源的情況，作業(yè)進(jìn)度增加速率差別不大。

縱向比較同一個(gè)作業(yè)在不同情況下的執(zhí)行結(jié)果：

采用作業(yè)時(shí)間敏感度排序：

64 MB作業(yè)：67 s

1 GB作業(yè)：252 s

未采用作業(yè)時(shí)間敏感度排序：

64 MB作業(yè)：102 s

1 GB作業(yè)：237 s

由上面數(shù)據(jù)可以看出：對(duì)于64 MB的短作業(yè)來(lái)講，采用作業(yè)時(shí)間敏感度的作業(yè)運(yùn)行時(shí)間比未采用作業(yè)時(shí)間敏感度的作業(yè)運(yùn)行時(shí)間減少了35 s，減少百分比為34.31%，雖然這時(shí)的1 GB長(zhǎng)作業(yè)運(yùn)行時(shí)間增加了15 s，其增加百分比為6.33%。

因此，加入作業(yè)時(shí)間敏感度排序指標(biāo)可以有效減少短作業(yè)執(zhí)行時(shí)間，提高用戶體驗(yàn)，而長(zhǎng)作業(yè)雖然響應(yīng)時(shí)間增加，但是增加不大，基本不會(huì)影響該作業(yè)的預(yù)期執(zhí)行效果。

4 結(jié) 論

首先簡(jiǎn)要介紹了現(xiàn)有Hadoop平臺(tái)的3種調(diào)度算法；然后提出現(xiàn)有算法的本地化任務(wù)不能充分實(shí)現(xiàn)的問(wèn)題；為解決此問(wèn)題，本文考慮到小規(guī)模集群系統(tǒng)中短作業(yè)比較多、數(shù)據(jù)規(guī)模處理不大的特點(diǎn)，提出了一種改進(jìn)的延時(shí)調(diào)度算法；實(shí)驗(yàn)結(jié)果表明，本文的改進(jìn)算法不但可以獲得更大比率的本地化任務(wù)，并且能夠顯著縮短作業(yè)的響應(yīng)時(shí)間。