王鐘斐，王鐘磊

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

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

當(dāng)前大多數(shù)云計算系統(tǒng)都采用Hadoop平臺[4-6]來開發(fā)和調(diào)試程序，Hadoop項目是由Doug Cutting領(lǐng)隊開發(fā)的開源框架。Hadoop平臺中的作業(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]以及計算能力調(diào)度器（Capacity Scheduler）[12-14]。其中，F(xiàn)IFO為Hadoop的默認(rèn)作業(yè)調(diào)度器，這種調(diào)度算法簡單明了，但在某些特殊情況下，本地化任務(wù)[15-16]不能充分實現(xiàn)。

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

1 問題的提出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

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

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

64 MB作業(yè)：67 s

1 GB作業(yè)：252 s

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

64 MB作業(yè)：102 s

1 GB作業(yè)：237 s

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

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

4 結(jié) 論

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