王鐘斐，王鐘磊

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

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

當前大多數(shù)云計算系統(tǒng)都采用Hadoop平臺[4-6]來開發(fā)和調(diào)試程序，Hadoop項目是由Doug Cutting領隊開發(fā)的開源框架。Hadoop平臺中的作業(yè)調(diào)度器是以可插拔的方式加載的，目前Hadoop發(fā)布版本中的主流調(diào)度器有3種：先進先出調(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的默認作業(yè)調(diào)度器，這種調(diào)度算法簡單明了，但在某些特殊情況下，本地化任務[15-16]不能充分實現(xiàn)。

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

1 問題的提出

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

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

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

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

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

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

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

首先，該算法在進行任務分配時不必遵循嚴格的作業(yè)順序。假如作業(yè)隊列中第一個作業(yè)中沒有本地化map任務，那么調(diào)度器會繼續(xù)在后續(xù)作業(yè)中查找。其次，為了給每個作業(yè)公平的機會去獲得自己的本地化任務，當某個作業(yè)等待一段時間T1后，還不能從具有空閑任務槽的節(jié)點中找到本地化任務，那么為了避免浪費集群的計算資源，本文提出的算法會分配該作業(yè)的一個非本地化任務。這樣，該算法不僅能達到高本地化任務的比率，也能增加集群的高利用率。第三，按照作業(yè)時間進度的指標對作業(yè)進行排序，這樣對于某些交互型的需要很快響應的作業(yè)，調(diào)度器能夠優(yōu)先調(diào)度并分配集群資源。第四，當某個新作業(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時，由于此時任務1的等待時間為3 s，故分配該任務給節(jié)點A，該任務為非本地化任務，如圖2所示。

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

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

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

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

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

3 實驗結果分析

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

如圖4所示，采用作業(yè)時間敏感度排序：當1 GB作業(yè)正在運行時，64 MB作業(yè)加入到作業(yè)隊列，剛開始64 MB作業(yè)進展緩慢，這是前期集群在準備作業(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è)進度增加速率差別不大。

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

采用作業(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è)時間敏感度排序指標可以有效減少短作業(yè)執(zhí)行時間，提高用戶體驗，而長作業(yè)雖然響應時間增加，但是增加不大，基本不會影響該作業(yè)的預期執(zhí)行效果。

4 結 論

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