劉盼紅

(河北工程大學信息與電氣工程學院，河北邯鄲056038)

近年來，隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、移動網(wǎng)絡(luò)、傳感網(wǎng)絡(luò)等各種新技術(shù)在各行各業(yè)的滲透式應(yīng)用，數(shù)據(jù)呈現(xiàn)爆炸式的增長，對海量數(shù)據(jù)的處理與分析被稱為“大數(shù)據(jù)”［1］。Hadoop，以一種可靠、高效、可伸縮的方式進行數(shù)據(jù)處理，為處理海量數(shù)據(jù)提供了一個很好的解決方案［2］。任務(wù)調(diào)度器是Hadoop中最核心的組件，負責整個集群資源的管理和分配。因此調(diào)度算法的好壞直接影響到Hadoop平臺的整體性能和集群的資源利用率［3］。Hadoop自帶的調(diào)度算法在處理混合作業(yè)時沒有考慮資源負載均衡的問題，在調(diào)度各節(jié)點任務(wù)時，沒有達到一種最優(yōu)的狀態(tài)?；谝陨蠁栴}，文中考慮到混合作業(yè)的特點提出了一種基于粒子群優(yōu)化算法的調(diào)度算法，以便可以更高效全面的進行任務(wù)調(diào)度，平衡資源負載，減少數(shù)據(jù)處理時間，提高平臺性能。

1 Hadoop任務(wù)調(diào)度

1.1 Hadoop原有的任務(wù)調(diào)度算法

默認調(diào)度器FIFO。FIFO將所有用戶提交的作業(yè)都放到一個隊列中，并將作業(yè)按照優(yōu)先級高低和提交的先后順序進行排序，然后按此隊列的順序執(zhí)行作業(yè)。優(yōu)點是實現(xiàn)非常簡單、調(diào)度過程快;缺點是資源的利用率不高。

計算能力調(diào)度算法Capacity Schedule。Capacity Schedule［4］采用多個隊列，每個隊列分配一定的系統(tǒng)容量，空閑資源可以動態(tài)分配給負荷重的隊列，支持作業(yè)優(yōu)先級;優(yōu)點是支持多作業(yè)并行執(zhí)行，提高資源利用率，動態(tài)調(diào)整資源分配，提高作業(yè)執(zhí)行效率;缺點是用戶需要了解大量系統(tǒng)信息，才能設(shè)置和選擇隊列。

公平調(diào)度算法 Fair Schedule。Fair Schedule［5］將作業(yè)分組形成作業(yè)池，每個作業(yè)池分配最小共享資源，然后將多余的資源平均分配給每個作業(yè);優(yōu)點是支持作業(yè)分類調(diào)度，提高服務(wù)質(zhì)量，動態(tài)調(diào)整并行作業(yè)數(shù)量，充分利用資源;缺點是不考慮節(jié)點的實際負載狀態(tài)，導致節(jié)點負載實際不均衡。

2 基于PSO的調(diào)度算法

粒子群優(yōu)化算法(Particle Swarm Optimization，簡稱PSO)最早是由J.Kennedy和電氣工程師R.Eberhart模擬自然界的生物群體覓食而提出的一種優(yōu)化方法［6］，通過粒子之間的集體協(xié)作來交換信息并作出決策。算法采用迭代的方式，使每個粒子向找到的最佳位置和群體中最佳粒子靠近，從而搜索到最優(yōu)解。

本文將粒子群算法引入到大數(shù)據(jù)處理框架Hadoop中，用于解決任務(wù)調(diào)度的問題。采用粒子群算法進行作業(yè)調(diào)度時，任務(wù)被作為粒子，資源池即為搜索空間，粒子尋找最優(yōu)解的過程即為任務(wù)調(diào)度的過程［7－8］，通過為任務(wù)賦予其在資源池中的初始位置和速度信息，并對其速度和位置進行迭代更新，最終形成任務(wù)和資源的映射關(guān)系。

2.1 相關(guān)定義

定義 1:集合T={t1，t2，…，tn}表示待分配的n個任務(wù)。

定義2:集合R={r1，r2，…，rm}表示 YARN 資源管理系統(tǒng)中m個Container資源。

執(zhí)行時間。其中元素eij(i=1，2，…，m;j=1，2，…，n)表示任務(wù)ti在rj個 Container資源上的執(zhí)行時間。

2.2位置和速度的更新

其中，c1、c2為學習因子，w為權(quán)重參數(shù)，rand()、R(0，1)是出于0和1之間的隨機數(shù)，pb和gb分別表示個體極值和全局極值所對應(yīng)的位置，表示粒子當前位置。

2.3 確定目標函數(shù)

Container資源節(jié)點rj上執(zhí)行的任務(wù)時間為H，任務(wù)的完成時間計算公式為T=max(H(rj))。

2.4 算法的實現(xiàn)

采用PSO進行調(diào)度的具體步驟如下:

1)接收用戶提交的任務(wù)，并把每個任務(wù)劃分為若干個子任務(wù)。

2)初始化算法參數(shù)(c1、c2、w等)，隨機產(chǎn)生初始種群，設(shè)定每個粒子的位置和速度初始值，設(shè)定最大迭代數(shù)。

3)通過目標函數(shù)計算每個粒子的適應(yīng)度函數(shù)值，比較粒子當前適應(yīng)值與自身歷史最優(yōu)值，若當前粒子優(yōu)于歷史最優(yōu)值，則當前粒子替代歷史最優(yōu)值作為個體最優(yōu)pb;否則pb取歷史最優(yōu)。

4)比較粒子種群的適應(yīng)度函數(shù)值，從所有粒子中選取最小的作為最優(yōu)粒子，最優(yōu)粒子值作為群體最優(yōu)值gb。

5)利用速度更新公式，更新每個粒子的速度及位置信息。

6)判斷是否達到最大迭代次數(shù)，若沒有，則重復步驟(3)(4)(5)。達到迭代次數(shù)則輸出最優(yōu)結(jié)果，算法結(jié)束。采用PSO進行調(diào)度的流程圖如圖1所示。

3 實驗結(jié)果

3.1 實驗環(huán)境

集群環(huán)境配置如表1所示。

表1 實驗環(huán)境配置Tab.1 The experimental environment configuration

3.2 實驗結(jié)果及性能分析

1)處理相同作業(yè)的性能。本實驗在Hadoop系統(tǒng)中將本算法與Hadoop現(xiàn)有的FIFO算法、Capacity Schedule計算能力調(diào)度算法和Fair Schedule公平調(diào)度算法進行對比驗證，將此四種算法分別作為調(diào)度方法，提交1～10個相同的WordCount作業(yè)，每個WordCount作業(yè)處理相同的128MB文本文件，記錄其作業(yè)。其中，運算時間通過代碼獲取運算開始及結(jié)束的計算機系統(tǒng)時間相減得到。為減少誤差，同樣的實驗進行5次運算取平均值，效果對比圖如圖2所示。

2)處理不同類型作業(yè)的性能。實驗將一個WordCount作業(yè)、一個Teragen作業(yè)與一個Terasort作業(yè)作為一個作業(yè)組。WordCount作業(yè)屬于統(tǒng)計詞頻的CPU資源密集型作業(yè);TeraGen作業(yè)屬于隨機生成數(shù)據(jù)的磁盤I/O密集型作業(yè);TeraSort作業(yè)是對輸入數(shù)據(jù)進行排序的作業(yè)，它既是CPU密集型的也是磁盤密集型的。其中WordCount作業(yè)處理128 MB的文本文件，Teragen作業(yè)生成一個500 M的數(shù)據(jù)集，Terasort則對一個事先已經(jīng)生成好的500 MB的數(shù)據(jù)進行排序。同時運行1～5組這樣的作業(yè)組，記錄其平均運行時間。效果對比圖如圖3所示。

從圖2、圖3中可以看出使用本文提出的調(diào)度算法平均運行時間是最少的。實驗證明本算法針對不論是相同類型的作業(yè)還是面對負載不均衡的不同類型的作業(yè)都能較好的完成調(diào)度任務(wù)，使得整體運算效率較高。

4 結(jié)語

采用粒子尋優(yōu)策略，找到調(diào)度層面最優(yōu)的粒子進行尋優(yōu)，以減少調(diào)度計算所用的時間。通過在實際Hadoop平臺的測試和分析表明，本文提出的調(diào)度算法能夠很好的平衡不同類型作業(yè)之間的負載，減少作業(yè)運行時間，提高了平臺性能。

［1］MANYIKA J，CHUI M，BROWN B，et al.Big data:The next frontier for innovation，competition，and productivity［J］.Communications of the ACM，2011，56(2):100－105.

［2］SHVACHKO K，KUANG H，RADIA S，et al.The hadoop distributed file system［C］//Mass Storage Systems and Technologies(MSST)，2010 IEEE 26th Symposium on.IEEE，2010:1－10.

［3］曹 英.大數(shù)據(jù)環(huán)境下 Hadoop性能優(yōu)化的研究［D］.大連:大連海事大學，2013.

［4］Capacity Scheduler for Hadoop［EB/OL］.http://hadoop.apache.org/docs/current/hadoop－yarn/hadoopyarn －site/CapacityScheduler.html，2014 －09 －05.

［5］Fair Scheduler for Hadoop［EB/OL］.http://hadoop.apache.org/docs/current/hadoop－yarn/hadoop－yarnsite/FairScheduler.html，2014 －09 －05.

［6］李愛國，覃征.粒子群優(yōu)化算法［J］.計算機工程與應(yīng)用，2002，38(21):1－3.

［7］劉素芹，王 婧，李興盛，等.基于粒子群優(yōu)化算法的集群調(diào)度策略［J］.鄭州大學學報:理學版，2010，42(2):43－46.

［8］張京軍，劉文娟，劉光遠.基于改進免疫遺傳算法的網(wǎng)格任務(wù)調(diào)度［J］.河北工程大學:自然科學版，2013，30(2):80－83.