基于Hadoop MapReduce的組合服務性能優化研究

秦 軍，翟 釗

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

基于Hadoop MapReduce的組合服務性能優化研究

秦 軍1，翟 釗2

(1.南京郵電大學 教育科學與技術學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210003)

對Hadoop中的任務調度進行了研究，在分析Hadoop作業調度算法的需求的基礎上，文中提出了調度算法在線性意義上的解空間。針對Hadoop的編程模型框架，提出了一種結合禁忌搜索思想的改進人工魚群算法。在該算法中，以任務總執行時間作為尋優函數，采用線性編碼方式，每一個N維向量代表一種具體調度方案；利用將解向量直接作為人工魚的方法，使人工魚群算法可以直接在解空間內運行。結合禁忌搜索思想，既保留了人工魚群算法計算基數大仍能快速收斂的優點，又充分利用禁忌搜索不會陷入局部最優解的優勢。通過仿真實驗將該算法和Fair算法進行比較，結果表明：改進的人工魚群作業調度算法可以提高系統性能，降低任務運行時間，是一種Hadoop環境下有效的任務調度程序。

Hadoop；人工魚群算法；作業調度算法；組合優化

1 概 述

在Hadoop系統中，作業調度的策略一直都是重點優化目標之一，其目標是實現高可用性服務、網絡吞吐量和集群負載的動態均衡[1-2]。其實質是尋求資源和能力之間進行匹配的最佳解決方案，即尋取一個作業執行時間最短的全局最優解[3]。對于云服務大多采用租賃形式向用戶提供服務的現行模式來說，快速的任務響應無疑是云服務的服務質量(Quality of Service，QoS)的一個重要因素。在Hadoop系統[4]中，Master節點作為Hadoop集群的控制中樞，作業調度是其功能的重要組成之一，這就要求調度算法不能過于復雜。如果調度算法采用復雜設計，全局最優解固然可以得到，但快速的任務響應卻很難做到，尤其是如果調度算法復雜度過高，隨著節點數目的增加，Master的管理負擔會呈現幾何級數的增長，進而使得Master計算壓力增加，不利于集群的實時調度需求，最終影響服務的QoS。Hadoop自帶了三種資源調度策略，分別是先進先出調度算法[5](First In First Out，FIFO)、公平調度算法—Fair算法[6]、計算能力調度算法—Capacity算法[7]。但是這幾種調度策略設計過于簡單，存在資源浪費、作業響應時間長等不足，并且算法具有容易陷入局部最優解、不能高效使用資源等問題。

目前，主流的集群調度算法主要是針對同構環境下的作業調度，在調度過程中研究的主要熱點包括作業執行順序、計算資源分配以及調度性能優化等多個方面。國內外學者針對MapReduce集群，先后提出了許多調度算法。Matei等提出一種競爭性調度算法[8]；Polo等提出基于時間閾值來決定作業調度和執行以及資源自適應策略[9]；Zaharia等提出了作業延時等待的策略[10]；國內有人提出異構環境下的自適應算法、公平隊列調度算法[11]……

上述算法絕大部分都是討論在同構的環境中進行的優化。然而，在實際的運行環境中，集群往往是由不同制造商生產的計算機、網絡設備和系統組成的高度差異化系統，一般實現方式為跨協議集成以實現表層接口統一。上述調度算法在這樣的集群中運行時，往往隨著集群PC數量的增長和作業量的增大而變得效率越來越低下；而蟻群算法、人工魚群算法等群智能算法，具有效率對基數不敏感、對海量作業適應性高等優點，將群智能算法作為調度算法可以獲得效率的極大提升。

人工魚群算法(Artificial Fish Swarm Algorithm,AFSA)[12-15]是一種新的啟發式生物智能算法，具有計算基數大仍能快速收斂和不需要問題的精確描述等優點。AFSA主要適用于連續變量型問題的優化[16]，另外AFSA擅長的是尋取一個最優解域，再則由于覓食行為中隨機行為，使得算法中有迂回搜索的缺點。

針對上述問題，文中在AFSA基礎上，結合禁忌搜索算法[17](Tabu Search，TS)，提出了一種改進的人工魚群算法(Improved Artificial Fish Swarm Algorithm，IAFSA)。仿真結果表明,IAFSA不僅保留了AFSA的優點，而且以較快的速度收斂，并且相比于Hadoop自帶的Fair調度算法在作業執行速度上有較大提升。

2 Hadoop作業調度策略的解空間

假設用戶向Hadoop提交了一個批次的任務，系統將這個批次的任務劃分為m個Mapper節點和r個Reducer節點，master節點決定m個Mapper節點產生的中間結果如何在r個Reducer節點上進行Reduce操作。m個Mapper節點產生的m個中間結果以1至m編號，r個Reducer節點以1至r編號。master分配方案的解空間的構成為：m個中間結果互相獨立，每一個中間結果都可以在r個Reducer節點中隨意選擇。這意味著一共有rm個選擇方案，這rm個解決方案形成了一個m維的、分量取值范圍為1至r的解空間，在這個解空間中的每一個點都是一個n維向量,如式(1)所示：

(1)

式中,ai表示第i個中間結果分配到第ai個Reducer節點。

每一個n維向量都是一個分配方案,也即是master節點可選擇的一個調度策略。任意一個n維向量作為調度策略的選擇時，最終耗費的Reduce作業時間見式(2)。

F(X)=max{cost(1),cost(2),…,cost(r)}

(2)

式中,cost(i)表示分配到第i個Reducer節點上的任務的執行時間花費。

3 人工魚群算法及禁忌搜索

AFSA主要的特點是對問題的優劣性進行比較，然后由個體人工魚在局部區域進行搜索，最終給出一個最佳解決方案。

TS是Glover在1986年提出的一種算法，它延伸了本地搜索的概念，是一種全局性的漸進的優化算法，是仿真人類智能的過程。

3.1 人工魚群算法

AFSA的主要思想是，一片水域中富含營養物質最多的地方生存的魚類數目也就最多。通過這一特點，李曉磊等提出利用單條魚的行為及魚和魚之間互相作用的行為進行全局尋優。以下對魚的這幾種行為進行簡要描述。

(1)覓食行為。

設人工魚當前狀態為Xi，在其感知范圍內隨機選擇一個狀態Xj，如果在求極大問題中，YiYj，因極大和極小問題可以互相轉換，所以以下均以求極大問題討論)，則向該方向前進一步；反之，再重新隨機選擇狀態Xj，判斷是否滿足前進條件；這樣反復嘗試try_number次后，如果仍不滿足前進條件，則隨機移動一步。

(2)聚群行為。

(3)追尾行為。

3.2 禁忌搜索算法

TS算法采用模擬人類智力的標記模式，采用禁忌表的形式來避免搜索過程陷入本地最優解導致的反復搜索，進而保證有效且多樣的搜索并最終實現全局優化。禁忌搜索核心思想是，對已得到的本地最優解進行記錄，并在之后的迭代搜索中對此類解進行無視操作，從而保證能實現對所有有效搜索路徑的覆蓋。禁忌搜索提出了鄰域、禁忌表、禁忌長度、候選解、特赦準則等概念。文中僅對在IAFSA中用到的幾個概念進行說明。

(1)鄰域點。

定義網格點A的鄰域點為在Rm維解空間中和網格點A相鄰的網格點，易得在m維空間中除邊界點外每個網格點都有2*m個鄰域點。圖1是二維解空間中的網格點A的鄰域點顯示。鄰域點概念在IAFSA中使用時，相當于AFSA中的覓食行為中的隨機狀態Xj。

圖1 二維解空間的鄰域點顯示

(2)特赦準則。

TS算法在IAFSA中使用時，定義其特赦準則為式(3)。

FoodDensity(X)=bestDensity

(3)

式中：X為要赦免的禁忌點；bestDensity為禁忌表中記錄的歷史候選解。

特赦的標準是，當前搜索到的解是搜索過程中找到的全局最優解。

特赦準則能夠實現高效的全局優化搜索的特點，可以確保人工魚進行全局范圍的搜索，最終搜索到全局最優值，同時可以避免重復搜索。

4 N維空間的改進人工魚群算法描述

文中提出的IAFSA算法可以直接在解空間中運行。以下對人工魚模型的建立，單條魚的覓食、追尾和聚群行為進行說明。

4.1 人工魚模型

文中取前文中描述的解向量為人工魚模型，以使IAFSA算法可以直接在解空間內運行。在網格化的解空間里，AFSA中的移動步長Step與網格單位長度意義重合，所以直接采用網格長度作為移動步長。人工魚移動時采用的網格長度計算見式(1)。

4.2 人工魚行為描述

人工魚行為描述是在原行為的基礎上在解空間內做這些行為時的適配描述。

(1)覓食行為。

假設人工魚當前位置為Xi。首先替代AFSA中隨機選擇一種行為為遍歷鄰域點尋找食物濃度最高的點，定義為Xj，然后判斷Xj是否在禁忌表中。如果在禁忌表中，就判斷其是否符合特赦準則，如果符合就移動至Xj，覓食結束。如果不符合特赦準則，就把該人工魚重新初始化，以使其重新尋優，相當于在人工魚實際數目不變的基礎上增大了尋優的人工魚個數。如果Xj不在禁忌表中，則移動至Xj并把該點加入到禁忌表，然后將該點的食物濃度與公告板的信息相比較，選較優者為公告板信息并更新公告板維持不變的次數。

覓食行為的流程圖如圖2所示。

圖2 人工魚覓食行為流程

(2)聚群行為。

設人工魚當前位置為Xi，在其視野范圍內的伙伴(其他魚)的中心位置為Xj，定義伙伴中心網格點的位置：

(4)

式中，dij為視野內其他網格點到Xi的距離。

如果中心網格點具有較高的食物濃度，且擁擠度小于閾值，則人工魚從當前位置向中心網格點移動一步；否則執行覓食行為。

(3)追尾行為。

IAFSA中的追尾行為與AFSA中的追尾行為動作相同，但把移動時的移動步長Step更改為網格長度。

4.3 最優解的獲取

AFSA可以獲取待求解問題的近似解，但不擅長獲取組合優化類問題需要的精確解。在網格化的解空間里，每一個位置都是一個精確解，這就解決了AFSA的弊端。同時通過在IAFSA中引入禁忌搜索的思想，避免了大量的迂回搜索，提高了求解問題的速度，強制把陷入局部最優的人工魚重新初始化，能夠在全局范圍內進行更廣泛的搜索，同時充分利用了歷史最優解起到的禁忌作用。在迭代過程中，如果公告板維持一定的次數沒有更新，則可認為獲得了最優解。

5 算法實現步驟

(1)給定m和r，設定公告板連續不更新次數上限Numuc和初始人工魚數量fish_num。

(2)初始化各條人工魚的位置，Xi=X0+Random()。其中，X0為m維坐標系的原點，Random()為分量取值范圍為1至r的隨機向量。如該點代表的解決方案在禁忌表中，則重新進行Random()操作；否則將此點插入禁忌表。

(3)遍歷人工魚，各人工魚依次按規則游動一次，更新禁忌表，然后與公告板信息進行比較。如當前點的解決方案優于公告板信息，則公告板進行更新操作，同時公告板信息連續不更新次數Nuc=0；否則Nuc=Nuc+1。

(4)如當前公告板信息連續不更新次數Nuc小于Numuc，則跳轉至第3步；否則算法結束，獲得最優解。

通過上述算法建立的人工魚群模型將算法展開，沒有高層的指揮者且對尋找方向完全不做限制，每條人工魚就按照自己的規則游動，運用人工魚的自主行為來尋優。運用IAFSA動態地尋找解向量的最優解，不斷更新公告板，最后公告板記錄的最優值，即為分配任務的最終策略。

6 仿真實現

文中采用云計算環境仿真平臺CloudSim 3.0[18]進行仿真實驗。通過CloudSim中的Datacenter、Cloudlet和CloudCoordinator及一些輔助類模擬云計算的計算節點和網絡資源、創建人物和虛擬機，計算節點的計算能力和網絡傳輸能力設置不同值以盡量貼近真實環境，并重寫DataCenterBroker類和Cloudlet類，構造IAFSA，與Fair算法[6]進行性能比較。實驗PC配置為Core i5處理器，6 G內存，操作系統為Windows 7。

算法實現中，IAFSA相關參數為：人工魚數量fish_num=50，公告板連續不更新次數上限Numuc=30，人工魚視野Visual=16，擁擠度因子δ=0.618。

仿真中，在由虛擬機組成的Hadoop集群上執行了三種類型的作業：Grep、WordCount和Sort。分別測試了在不同大小的輸入數據下的作業完成時間，IAFSA與Fair算法相比較測試結果如圖3～5所示。

圖3 Grep作業仿真結果

圖4 WordCount作業仿真結果

圖5 Sort作業仿真結果

仿真結果顯示，使用IAFSA比Fair算法具有更高的作業執行速度，可以提高集群整體作業執行效率。從圖3～5中還可以看出，不同作業下，IAFSA都比Fair算法效率高，說明IAFSA具有較高的穩定性。另外，隨著作業量的增長及運行時間曲線可以看出，IAFSA的效率比Fair算法的效率差異幅度更大，說明Fair算法隨著作業量的增長，效率出現了一定的下降，而IAFSA更適應海量作業的處理，效率并未降低而且增長幅度有小幅上升。IAFSA通過將解向量作為人工魚，使得計算資源和計算能力節點達到很好的匹配，有效減少了節點的閑置時間，提高了計算節點的利用率，以此大幅降低了任務的執行時間。

7 結束語

HadoopMapReduce是當前最成功的、應用最廣泛的并行計算框架和模型之一。其作業調度算法效率對整個集群的性能有著顯著影響。文中采用IAFSA對作業調度算法進行優化，利用AFSA的收斂速度，通過優化算法減少重復搜索，獲取精確解。仿真結果表明，通過IAFSA來改進Hadoop作業調度算法的方案是可行的，該算法有利于提高集群整體執行效率，降低了任務的執行時間。

[1]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.

[2]BhandarkarM.MapReduceprogrammingwithapacheHadoop[C]//ProcofIEEEinternationalsymposiumonparallel&distributedprocessing.[s.l.]:IEEE,2010.

[3] 李春艷,何一舟,戴 彬.Hadoop平臺的多隊列作業調度優化方法研究[J].計算機應用研究,2014,31(3):705-707.

[4]ApacheHadoop[EB/OL].2012-04-16.http://hadoop.apache.org.

[5] 李建鋒,彭 艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用,2011,31(1):184-186.

[6]Hadoop公平調度算法[EB/OL].2010-02-19.http://hadoop.apache.org/docs/r0.20.2/fair_scheduler.html.

[7] 羅軍舟,金嘉暉,宋愛波,等.云計算:體系架構與關鍵技術[J].通信學報,2011,32(7):3-21.

[8]RajuR,AmudhavelJ,PavithraM,etal.AheuristicfaulttolerantMapReduceframeworkforminimizingmakespaninhybridcloudenvironment[C]//Procofinternationalconferenceongreencomputingcommunicationandelectricalengineering.[s.l.]:IEEE,2014:1-4.

[9]BerkovichVG.Spectraltheoryandanalyticgeometryovernon-Archimedeanfields[M].American:AmericanMathematicalSoc.,2012.

[10]RenZ,WanJ,ShiW,etal.Workloadanalysis,implications,andoptimizationonaproductionHadoopcluster:acasestudyonTaobao[J].IEEETransactionsonServicesComputing,2014,7(2):307-321.

[11] 張 雨,李 芳,周 濤.云計算環境下基于遺傳蟻群算法的任務調度研究[J].計算機工程與應用,2014,50(6):51-55.

[12] 李曉磊.一種新型的智能優化方法-人工魚群算法[D].杭州:浙江大學,2003.

[13] 王聯國,洪 毅,趙付青,等.一種改進的人工魚群算法[J].計算機工程,2008,34(19):192-194.

[14] 易新兵，楊凱. 復合混沌-人工魚群混合算法的改進及性能研究[J]．計算機工程與科學 2013, 35(8) 89-95.

[15] 姚麗莎，王占鳳，程家興．基于人工魚群遺傳算法的異構多核系統任務調度研究[J]．計算機工程與科學，2014, 36(10) 1866-1871.

[16] 李曉磊,路 飛,田國會,等.組合優化問題的人工魚群算法應用[J].山東大學學報:工學版,2004,34(5):64-67.

[18]CalheirosRN,RanjanR,BeloglazovA,etal.CloudSim:atoolkitformodelingandsimulationofcloudcomputingenvironmentsandevaluationofresourceprovisioningalgorithms[J].Software:PracticeandExperience,2011,41(1):23-50.

Research on Composite Service Performance Optimization Based on Hadoop MapReduce

QIN Jun1,ZHAI Zhao2

(1.College of Education Science & Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Research of job scheduling in Hadoop,based on analysis of requirement for Hadoop job scheduling algorithm,the solution space in linear meaning of scheduling algorithm is proposed.Aiming at the procedure model for Hadoop,an improved Artificial Fish Swarm Algorithm (AFSA) combines tabu search is put forward.It uses total execution time as the optimized functions,and with linear coding,eachN-dimensionalvectorrepresentsaspecialschedulingscheme.ThemethodwhichtakessolutionvectorasartificialfishdirectlyisappliedtomakeAFSAcanberundirectlyinthesolutionspace.IAFSAnotonlyretainstheadvantagesofrapidconvergenceofAFSAatalargecomputingbase,alsomakesfulluseoftheadvantagesoftabusearchdoesnotfallintolocaloptima.ThroughcomparisonbetweenthealgorithmwiththeFairalgorithm,theexperimentshowsthattheimprovedAFSAinheterogeneousenvironmentscanimprovesystemperformanceandreducethecomputingtime.ItiseffectiveintheHadoopenvironment.

Hadoop;AFSA;job scheduling algorithm;combinatorial optimization

2015-08-12

2015-11-17

時間：2016-05-05

江蘇省自然科學基金項目(BK20130882)

秦 軍(1955-)，女，教授，研究方向為計算機網絡技術、多媒體技術、數據庫技術；翟 釗(1990-)，男，碩士研究生，研究方向為分布式計算機技術與應用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0828.074.html

TP

A

1673-629X(2016)05-0061-05

10.3969/j.issn.1673-629X.2016.05.013