秦 軍，翟 釗

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

基于Hadoop MapReduce的組合服務性能優(yōu)化研究

秦 軍1，翟 釗2

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

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

Hadoop；人工魚群算法；作業(yè)調(diào)度算法；組合優(yōu)化

1 概 述

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

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

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

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

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

2 Hadoop作業(yè)調(diào)度策略的解空間

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

(1)

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

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

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

(2)

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

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

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

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

3.1 人工魚群算法

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

(1)覓食行為。

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

(2)聚群行為。

(3)追尾行為。

3.2 禁忌搜索算法

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

(1)鄰域點。

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

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

(2)特赦準則。

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

FoodDensity(X)=bestDensity

(3)

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

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

特赦準則能夠?qū)崿F(xiàn)高效的全局優(yōu)化搜索的特點，可以確保人工魚進行全局范圍的搜索，最終搜索到全局最優(yōu)值，同時可以避免重復搜索。

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

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

4.1 人工魚模型

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

4.2 人工魚行為描述

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

(1)覓食行為。

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

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

圖2 人工魚覓食行為流程

(2)聚群行為。

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

(4)

式中，dij為視野內(nèi)其他網(wǎng)格點到Xi的距離。

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

(3)追尾行為。

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

4.3 最優(yōu)解的獲取

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

5 算法實現(xiàn)步驟

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

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

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

(4)如當前公告板信息連續(xù)不更新次數(shù)Nuc小于Numuc，則跳轉(zhuǎn)至第3步；否則算法結(jié)束，獲得最優(yōu)解。

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

6 仿真實現(xiàn)

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

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

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

圖3 Grep作業(yè)仿真結(jié)果

圖4 WordCount作業(yè)仿真結(jié)果

圖5 Sort作業(yè)仿真結(jié)果

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

7 結(jié)束語

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

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

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

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

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

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

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

[7] 羅軍舟,金嘉暉,宋愛波,等.云計算:體系架構(gòu)與關(guān)鍵技術(shù)[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] 張 雨,李 芳,周 濤.云計算環(huán)境下基于遺傳蟻群算法的任務調(diào)度研究[J].計算機工程與應用,2014,50(6):51-55.

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

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

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

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

[16] 李曉磊,路 飛,田國會,等.組合優(yōu)化問題的人工魚群算法應用[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-)，女，教授，研究方向為計算機網(wǎng)絡技術(shù)、多媒體技術(shù)、數(shù)據(jù)庫技術(shù)；翟 釗(1990-)，男，碩士研究生，研究方向為分布式計算機技術(shù)與應用。

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