基于粒子群優化算法的Hadoop調度算法研究

劉盼紅

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

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

1 Hadoop任務調度

1.1 Hadoop原有的任務調度算法

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

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

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

2 基于PSO的調度算法

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

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

2.1 相關定義

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

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

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

2.2位置和速度的更新

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

2.3 確定目標函數

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

2.4 算法的實現

采用PSO進行調度的具體步驟如下:

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

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

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

4)比較粒子種群的適應度函數值，從所有粒子中選取最小的作為最優粒子，最優粒子值作為群體最優值gb。

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

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

3 實驗結果

3.1 實驗環境

集群環境配置如表1所示。

表1 實驗環境配置Tab.1 The experimental environment configuration

3.2 實驗結果及性能分析

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

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

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

4 結語

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

［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］曹 英.大數據環境下 Hadoop性能優化的研究［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］李愛國，覃征.粒子群優化算法［J］.計算機工程與應用，2002，38(21):1－3.

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

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