【摘 要】本文分析了先入先出調(diào)度算法（FIFO）、公平調(diào)度算法（Fair-Scheduler）以及計算能力調(diào)度算法（Capacity Scheduler）的優(yōu)缺點，并針對 Hadoop 的調(diào)度算法問題，提出了一種基于預(yù)期效用的Hadoop作業(yè)調(diào)度算法，詳細(xì)敘述了該算法的原理和實現(xiàn)過程。最后對該算法編程驗證，實驗結(jié)果表明，其在調(diào)度時間方面的性能有了明顯的改進(jìn)。

【關(guān)鍵詞】云計算 Hadoop 任務(wù)調(diào)度

近年來云計算技術(shù)取得了長足發(fā)展，大量的云計算系統(tǒng)投入使用，實際中絕大多數(shù)的云計算系統(tǒng)采用Hadoop平臺來作為基礎(chǔ)平臺。作業(yè)調(diào)度技術(shù)在Hadoop系統(tǒng)中作為核心技術(shù)之一，其技術(shù)直接關(guān)系到Hadoop系統(tǒng)的運(yùn)行性能，改進(jìn)現(xiàn)有調(diào)度算法的不足之處，對提高Hadoop系統(tǒng)具有重要的意義。

一、三種作業(yè)調(diào)度算法

Hadoop現(xiàn)有的作業(yè)調(diào)度算法包括默認(rèn)的FIFO調(diào)度算法，F(xiàn)acebook公司開發(fā)的公平調(diào)度算法以及Yahoo公司開發(fā)的計算能力調(diào)度算法。在FIFO的實現(xiàn)中，使用了一個單獨的隊列，TaskTracker總是將新任務(wù)追加到就緒隊列的末端。該FIFO算法是容易實現(xiàn)，且調(diào)度開銷要小于整個群集。但該算法無視不同用戶以及不同任務(wù)間的需求差異，系統(tǒng)會阻止低優(yōu)先級的任務(wù)執(zhí)行，由于優(yōu)先級搶占的情況不被FIFO算法所支持，這就使得平臺系統(tǒng)的整體性能和資源利用率不高，影響了執(zhí)行這些任務(wù)。

公平調(diào)度算法（Fair Scheduler）的目標(biāo)是能夠并行執(zhí)行的多種作業(yè)在MapReduced的計算框架中能夠靈活應(yīng)對[1]。其想法是盡可能的以確保所有的作業(yè)都是能夠獲得相同量的資源。由于其支持分類的任務(wù)調(diào)度，資源分配可以充分的在不同任務(wù)間進(jìn)行分配，使得服務(wù)質(zhì)量得到提高，系統(tǒng)資源充分利用[2]。它克服了簡單的FIFO算法資源利用低和不支持任務(wù)搶占的缺點，但它不考慮每個節(jié)點當(dāng)前的實際負(fù)載狀態(tài)，導(dǎo)致負(fù)載不均衡的情況發(fā)生，從而影響到整個系統(tǒng)的響應(yīng)時間。在實際應(yīng)用中，系統(tǒng)的性能還極大的受到算法配置文件優(yōu)劣的影響。

計算能力調(diào)度算法與公平調(diào)度算法雖在功能上很類似，但還是有很多特別之處。計算能力調(diào)度支持多個作業(yè)隊列，用戶提交的作業(yè)直接添加到隊列中。為了提升其資源利用效率，每個隊列會共享已分配但處于閑置狀態(tài)的資源。在配置文件中配置相應(yīng)的參數(shù)，為隊列分配相應(yīng)的資源數(shù)量，可以使得為各個隊列完成Map/Reduce的各種操作。計算能力調(diào)度算法雖然克服了FIFO算法簡單以及資源利用率低的特點，而且它支持多任務(wù)并行執(zhí)行，但是計算能力調(diào)度算法中隊列設(shè)置無法自動進(jìn)行，需要了解系統(tǒng)信息才能對作業(yè)進(jìn)行隊列選組和隊列設(shè)置，在很多大型商業(yè)系統(tǒng)中，這可能成為提高系統(tǒng)性能的瓶頸。

二、基于預(yù)期效用的作業(yè)調(diào)度算法

針對前面調(diào)度算法的一些不足，我們提出了基于預(yù)期效用的作業(yè)調(diào)度算法。此算法要求在作業(yè)進(jìn)入系統(tǒng)執(zhí)行以前且作業(yè)已經(jīng)被提交到作業(yè)等待服務(wù)隊列中去時，進(jìn)行作業(yè)的預(yù)先判斷。在作業(yè)隊列中通過作業(yè)分類機(jī)制，對作業(yè)的當(dāng)前特征和所需要占用的系統(tǒng)的資源情況等進(jìn)行分析，以此判斷作業(yè)是否能夠被系統(tǒng)接受并處理。根據(jù)當(dāng)前作業(yè)被接受或者拒絕的概率作為判斷依據(jù)，在候選的作業(yè)中要選擇被成功接受的概率大于不被成功接受的概率的作業(yè)去執(zhí)行。通過作業(yè)的預(yù)期效用計算值來判斷被接收或者拒絕，被選擇成為將要執(zhí)行的作業(yè)就是那個計算得出的預(yù)期效用值最大的作業(yè)。

在基于預(yù)期效用的作業(yè)調(diào)度算法設(shè)計過程中，所有提交到系統(tǒng)的相關(guān)作業(yè)將使用任務(wù)槽來完成存儲或者計算任務(wù)，這些Map和Reduce任務(wù)槽是由云計算系統(tǒng)平臺來指定的。每個作業(yè)都可以在執(zhí)行過程中去預(yù)估計它的資源耗費的情況，例如內(nèi)存的占用，CPU時間占用的長短以及預(yù)算量的大小等；對節(jié)點上的評估也是這樣，也包括內(nèi)存大小、帶寬大小、磁盤數(shù)量、CPU速度及數(shù)量等節(jié)點特征，通過這些特征可以得知節(jié)點資源的占用情況；合理的調(diào)度與分配資源，可以平衡的讓作業(yè)分享系統(tǒng)服務(wù)，避免大作業(yè)長時間占用資源，而小作業(yè)長時間得不到系統(tǒng)的服務(wù)[3]。

在進(jìn)行作業(yè)選擇調(diào)度的時候，根據(jù)預(yù)期效用的假設(shè)理論，我們一般按照式（1）來選擇作業(yè)：

在上式（1）中是作業(yè)在系統(tǒng)指定的效用函數(shù)值，此值需要一定時間的積累和調(diào)整。是作業(yè)在分類器處理過后，作業(yè)被成功接受的概率，此值要受資源消耗狀況的影響，主要包括了CPU、內(nèi)存以及IO的占用情況等，F(xiàn)是綜合描述作業(yè)特征。其算法的流程如圖1所示。

預(yù)期效用函數(shù)計算出來的值將直接決定作業(yè)是否被系統(tǒng)所調(diào)度執(zhí)行，在此效用計算過程中先計算與作業(yè)相關(guān)的概率值，它的含義是在集群環(huán)境下作業(yè)被成功調(diào)度的概率，是綜合描述作業(yè)特的征。由此，有如下公式：

上式（2）是基于預(yù)期效用的Hadoop作業(yè)調(diào)度算法的理論基礎(chǔ)，總體思路是在進(jìn)行下一次作業(yè)的調(diào)度決策前，先要分析上次的作業(yè)調(diào)度運(yùn)行的相關(guān)數(shù)值。為使調(diào)度盡量達(dá)到最優(yōu)的狀態(tài)，就要不斷的追蹤上次所做的決定，修正下次的決策，通過先驗概率計算出可能產(chǎn)生的相關(guān)結(jié)果。其中也是可以計算的，因為是代表資源耗費情況的預(yù)計值，是在作業(yè)提交之前的設(shè)定值，也就可以當(dāng)作常數(shù)。概率在作業(yè)調(diào)度算法決策過程中，先要進(jìn)行分析比較這兩個概率值，然后選擇被成功接受概率值最大的值作為候選作業(yè)進(jìn)行判斷處理，而不符合要求的作業(yè)會被系統(tǒng)拒絕進(jìn)行調(diào)度；通過這種設(shè)計的作業(yè)分類器將作業(yè)進(jìn)行適當(dāng)?shù)姆诸悺赡懿槐怀晒φ{(diào)度的作業(yè)和可能被成功調(diào)度的作業(yè)兩類，在可能成功的作業(yè)隊列中計算相應(yīng)的作業(yè)預(yù)期效用值，從中選擇預(yù)期效用值最大的作業(yè)進(jìn)行調(diào)度執(zhí)行。通過如下的公式計算作業(yè)的預(yù)期效用值，

在公式（3）中，為作業(yè)的預(yù)期效用值，為其作業(yè)效用函數(shù)。在選定作業(yè)進(jìn)入調(diào)度序列執(zhí)行后，如何去判斷作業(yè)是否被成功調(diào)用呢，這就需要制定作業(yè)評判的標(biāo)準(zhǔn)。我們將作業(yè)任務(wù)節(jié)點執(zhí)行的情況定為調(diào)度是否合適的評判指標(biāo)。在節(jié)點反饋的信息中，通過一些集群信息參數(shù)來為節(jié)點上的資源消耗設(shè)定一個閥值。當(dāng)作業(yè)執(zhí)行過程中，如果反饋回來的節(jié)點信息這一閥值，就可以認(rèn)為作業(yè)調(diào)度不合理，節(jié)點負(fù)載過重。集群參數(shù)列表如表格1所示。

在計算得出被成功調(diào)用的分類作業(yè)效用值后，就選擇執(zhí)行預(yù)期效用值最大的作業(yè)進(jìn)行調(diào)度。如果來自作業(yè)的節(jié)點心跳信息的資源使用狀況沒有超過閥值，可認(rèn)為調(diào)度決策是成功的，否則就是失敗的；如果決策是失敗的話，需要對預(yù)期效用值進(jìn)行重新分析，對相關(guān)參數(shù)進(jìn)行修改。

三、算法驗證

該算法的具體實現(xiàn)是在已有的Hadoop提供的API接口基礎(chǔ)之上進(jìn)行的程序開發(fā)。實驗環(huán)境為Ubuntu9.04、JDK1.6、Hadoop0.20；節(jié)點數(shù)量設(shè)置為4個，1個為NameNode，其他為計算節(jié)點。在實驗中搭建好hadoop的計算環(huán)境集群，將用戶作業(yè)分別提交到系統(tǒng)中進(jìn)行處理。配置數(shù)據(jù)塊的副本數(shù)量為5個，HDFS數(shù)據(jù)塊的大小為64M，以及TaskTracker上心跳信息的反饋時間間隔為4秒等。實驗中提交了三種作業(yè)，分別是在50G的數(shù)據(jù)文件中統(tǒng)計某個單詞出現(xiàn)的頻率；對100M數(shù)據(jù)中的鍵/值對進(jìn)行一次平方運(yùn)算；在本地服務(wù)器上對200M數(shù)據(jù)進(jìn)行FTP上傳下載100次。每次作業(yè)運(yùn)行完成之后得到處理時間的數(shù)據(jù)，實驗的結(jié)果如圖2所示。

從圖2中可以得出，基于預(yù)期效用的作業(yè)調(diào)度算法在處理作業(yè)的時間響應(yīng)性方面大多數(shù)時候要優(yōu)于FIFO算法以及公平調(diào)度算法，和計算能力調(diào)度算法的處理時間相當(dāng)。剛開始時基于預(yù)期效用的調(diào)度算法所花費的時間較多，隨著運(yùn)算次數(shù)的增加，調(diào)度所花時間逐漸減少。

四、結(jié)論

在處理相同作業(yè)隊列時，F(xiàn)IFO算法所消耗的時間最多，由于其未充分考慮了資源的使用情況，故調(diào)度算法實現(xiàn)起來比較簡單。公平算法和計算能力調(diào)度算法在算法的設(shè)計上比FIFO復(fù)雜些，但是如果其參數(shù)設(shè)置不合理，也可能造成消耗時間比較多。隨著時間的推移，基于預(yù)期效用的調(diào)度算法處理作業(yè)的時間會越來越少，直至達(dá)到穩(wěn)定的狀態(tài)。FIFO算法，公平算法以及計算能力算法在預(yù)先參數(shù)配置不恰當(dāng)?shù)那闆r之下其作業(yè)處理的響應(yīng)時間將會受到影響，并且在以后的作業(yè)調(diào)度過程中不會被糾正，基于預(yù)期效用的調(diào)度算法則允許初始配置不合理，允許犯錯，在后續(xù)的作業(yè)調(diào)度過程中，不斷的去修改配置參數(shù)，使得系統(tǒng)的處理能力達(dá)到一個越來越優(yōu)的狀態(tài)。

參考文獻(xiàn)：

[1] Fair Scheduler for Hadoop[EB/OL].Hadoop.apache.org/common/docs/current/Fair_scheduler.html， 2010-04-15

[2] 姜淼，Hadoop云平臺下調(diào)度算法的研究[D]，吉林大學(xué)通信工程學(xué)院，2012-06

[3] Shvachko k，KUANG Hai-rong，Radia S，etal.The Hadoop Distributed File System[J].MSST，2010.1

作者簡介：

方剛（1976—），男，四川，碩士研究生，主要研究領(lǐng)域為應(yīng)用軟件和云計算技術(shù)。