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

秦 軍，翟 釗

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

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

秦 軍1，翟 釗2

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

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

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

1 概 述

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

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

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

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

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

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

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

(1)

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

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

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

(2)

式中,cost(i)表示分配到第i個(gè)Reducer節(jié)點(diǎn)上的任務(wù)的執(zhí)行時(shí)間花費(fèi)。

3 人工魚(yú)群算法及禁忌搜索

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

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

3.1 人工魚(yú)群算法

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

(1)覓食行為。

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

(2)聚群行為。

(3)追尾行為。

3.2 禁忌搜索算法

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

(1)鄰域點(diǎn)。

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

圖1 二維解空間的鄰域點(diǎn)顯示

(2)特赦準(zhǔn)則。

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

FoodDensity(X)=bestDensity

(3)

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

特赦的標(biāo)準(zhǔn)是，當(dāng)前搜索到的解是搜索過(guò)程中找到的全局最優(yōu)解。

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

4 N維空間的改進(jìn)人工魚(yú)群算法描述

文中提出的IAFSA算法可以直接在解空間中運(yùn)行。以下對(duì)人工魚(yú)模型的建立，單條魚(yú)的覓食、追尾和聚群行為進(jìn)行說(shuō)明。

4.1 人工魚(yú)模型

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

4.2 人工魚(yú)行為描述

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

(1)覓食行為。

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

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

圖2 人工魚(yú)覓食行為流程

(2)聚群行為。

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

(4)

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

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

(3)追尾行為。

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

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

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

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

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

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

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

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

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

6 仿真實(shí)現(xiàn)

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

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

仿真中，在由虛擬機(jī)組成的Hadoop集群上執(zhí)行了三種類(lèi)型的作業(yè)：Grep、WordCount和Sort。分別測(cè)試了在不同大小的輸入數(shù)據(jù)下的作業(yè)完成時(shí)間，IAFSA與Fair算法相比較測(cè)試結(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算法效率高，說(shuō)明IAFSA具有較高的穩(wěn)定性。另外，隨著作業(yè)量的增長(zhǎng)及運(yùn)行時(shí)間曲線可以看出，IAFSA的效率比Fair算法的效率差異幅度更大，說(shuō)明Fair算法隨著作業(yè)量的增長(zhǎng)，效率出現(xiàn)了一定的下降，而IAFSA更適應(yīng)海量作業(yè)的處理，效率并未降低而且增長(zhǎng)幅度有小幅上升。IAFSA通過(guò)將解向量作為人工魚(yú)，使得計(jì)算資源和計(jì)算能力節(jié)點(diǎn)達(dá)到很好的匹配，有效減少了節(jié)點(diǎn)的閑置時(shí)間，提高了計(jì)算節(jié)點(diǎn)的利用率，以此大幅降低了任務(wù)的執(zhí)行時(shí)間。

7 結(jié)束語(yǔ)

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

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

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

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

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

[5] 李建鋒,彭 艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,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] 羅軍舟,金嘉暉,宋愛(ài)波,等.云計(jì)算:體系架構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報(bào),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ì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(6):51-55.

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

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

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

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

[16] 李曉磊,路 飛,田國(guó)會(huì),等.組合優(yōu)化問(wèn)題的人工魚(yú)群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào):工學(xué)版,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

時(shí)間：2016-05-05

江蘇省自然科學(xué)基金項(xiàng)目(BK20130882)

秦 軍(1955-)，女，教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)、多媒體技術(shù)、數(shù)據(jù)庫(kù)技術(shù)；翟 釗(1990-)，男，碩士研究生，研究方向?yàn)榉植际接?jì)算機(jī)技術(shù)與應(yīng)用。

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