基于混合蟻群遺傳算法的Hadoop集群作業(yè)調(diào)度

樓 濤，杜文才，2，鐘杰卓

( 1.海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 海口 570228 ; 2.澳門城市大學(xué)，澳門)

基于混合蟻群遺傳算法的Hadoop集群作業(yè)調(diào)度

樓 濤1，杜文才1，2，鐘杰卓1

( 1.海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228 ; 2.澳門城市大學(xué)，澳門)

提出了一種基于蟻群與遺傳算法融合的自適應(yīng)作業(yè)調(diào)度機(jī)制，將遺傳算法全局收斂、快速搜索的優(yōu)點(diǎn)與蟻群算法正反饋、高求精率的優(yōu)勢相結(jié)合，以變異策略來加快局部尋優(yōu)，提高收斂速度.實(shí)驗(yàn)結(jié)果表明本文算法可快速找到最適合當(dāng)前作業(yè)的節(jié)點(diǎn)，有效提高Hadoop集群作業(yè)調(diào)度的效率.

蟻群算法; 遺傳算法; Hadoop集群

Hadoop作為海量數(shù)據(jù)分布式處理的軟件框架，整合了包括數(shù)據(jù)庫、云計算管理和數(shù)據(jù)倉儲等一系列平臺，可靠、高效、可伸縮等特點(diǎn)使其成為工業(yè)界和學(xué)術(shù)界進(jìn)行云計算應(yīng)用和研究的標(biāo)準(zhǔn)平臺，被廣泛應(yīng)用于FaceBook，Twitter，Yahoo! 等公司.通常情況下，Hadoop集群包括數(shù)以千計的服務(wù)器和數(shù)以萬計的CPU，在如此龐大的集群中運(yùn)行著大量不同類型的作業(yè)，作業(yè)之間可能還存在依賴關(guān)系，作業(yè)調(diào)度機(jī)制直接關(guān)系到Hadoop平臺的整體性能和系統(tǒng)資源的利用情況.筆者通過研究關(guān)于Hadoop作業(yè)調(diào)度算法，提出了一種在遺傳蟻群混合算法基礎(chǔ)上的作業(yè)調(diào)度機(jī)制，從而解決現(xiàn)有算法的不足.

1 Hadoop平臺的作業(yè)調(diào)度

Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)由2個核心部分組成：分布式文件系統(tǒng)HDFS和分布式計算引擎MapReduce.其中，HDFS有著高容錯性的特點(diǎn)，可部署在低廉的硬件上，提供高吞吐量訪問應(yīng)用程序的數(shù)據(jù)，HDFS是一個主從結(jié)構(gòu)的體系，由NameNode節(jié)點(diǎn)和DataNode節(jié)點(diǎn)組成；MapReduce作為大規(guī)模集群上的簡單數(shù)據(jù)處理方式，由JobTracker節(jié)點(diǎn)和TaskTracker節(jié)點(diǎn)組成[1].MapReduce計算架構(gòu)的系統(tǒng)架構(gòu)如圖1所示.

圖1 MapReduce計算架構(gòu)的系統(tǒng)架構(gòu)圖

1.1 Hadoop平臺的作業(yè)調(diào)度流程將作業(yè)中劃分成幾個子任務(wù)并且分配到不同且合適的任務(wù)節(jié)點(diǎn)(TaskTracker)被稱為 Hadoop 平臺下的作業(yè)調(diào)度.Hadoop提供了Job方法[2]，作業(yè)提交方法中包含了執(zhí)行此任務(wù)所需的類、文件分塊的相關(guān)信息以及有關(guān)的作業(yè)配置(如輸入輸出格式的類型等).JobClient將請求傳送給JobTracker，JobTracker將請求加入作業(yè)隊(duì)列中，同時產(chǎn)生JobInProgress對象，用于維護(hù)此作業(yè)的所有信息.

TaskTracker每隔10 s與JobTracker通訊一次，通過heartbeat()方法向JobTracker發(fā)送心跳信號.JobTracker根據(jù)TaskTracker的新任務(wù)心跳請求，調(diào)用分配算法，獲取作業(yè)隊(duì)列，確定任務(wù)可分配的作業(yè)隊(duì)列，將該任務(wù)通過心跳答復(fù)傳給TaskTracker執(zhí)行.

1.2 現(xiàn)有作業(yè)調(diào)度算法在 Hadoop 0.19 版本之后，任務(wù)調(diào)度器的設(shè)計采用的是插件機(jī)制，即作業(yè)調(diào)度器是動態(tài)加載的、可插拔的，同時第三方可以開發(fā)自己的任務(wù)調(diào)度器替代Hadoop默認(rèn)的調(diào)度器.目前，Hadoop的作業(yè)調(diào)度器主要包括：默認(rèn)的FIFO算法、由Facebook提出的公平調(diào)度算法和由雅虎公司提出的計算能力調(diào)度算法.

FIFO算法采用一個FIFO隊(duì)列進(jìn)行調(diào)度，由JobTracker 根據(jù)預(yù)定義的作業(yè)優(yōu)先級選擇將被執(zhí)行的作業(yè)，雖然實(shí)現(xiàn)非常簡單、調(diào)度過程快，但只適用于單用戶和單類型作業(yè)，處理多用戶共享運(yùn)行多類型作業(yè)時效率很低.

公平調(diào)度算法和計算能力調(diào)度算法都提供了配置文件，可以實(shí)現(xiàn)對資源的動態(tài)分配，提高資源的利用率.但是，Hadoop 集群中往往有著大量 MapReduce 作業(yè)和TaskTracker，管理員要對 TaskTracker上可以同時運(yùn)行的最大任務(wù)數(shù)進(jìn)行正確設(shè)置，就必須詳細(xì)掌控 MapReduce 作業(yè)的資源需求情況和每個TaskTracker 的資源占用情況，這是很難做到的，而且容易出錯；此外，為了保證每個作業(yè)都能得到所需資源，管理員需要同每個用戶協(xié)商，才能夠正確設(shè)置作業(yè)池和作業(yè)隊(duì)列的資源配額，而在面向海量用戶的情況下同樣難以實(shí)施.

同現(xiàn)有任務(wù)調(diào)度算法對比，本文提出的算法不需要管理員進(jìn)行預(yù)設(shè)置，而是通過監(jiān)控每個TaskTracker 負(fù)載以及作業(yè)提交和完成的情況，自動地完成任務(wù)的選擇及分配，以JobClient所提交的資源需求為基礎(chǔ)，最終實(shí)現(xiàn)任務(wù)都能分配到適當(dāng)?shù)腡askTracker 節(jié)點(diǎn)上執(zhí)行.

2 基于混合蟻群遺傳算法的Hadoop任務(wù)調(diào)度

2.1 混合蟻群遺傳算法基本思想蟻群算法(Ant Colony Algorithm，ACA)適用于求解單目標(biāo)和多目標(biāo)優(yōu)化問題，但在搜索初期由于缺少信息素會導(dǎo)致信息素積累時間較長，求解速度較慢.遺傳算法(Genetic Algorithm，GA)以“物種靠不斷的演化而生成最適合生存的物種”的進(jìn)化論觀點(diǎn)為依據(jù)，對即定問題尋求最優(yōu)解，能夠?qū)崿F(xiàn)快速的全局搜索[3]，但由于該算法沒有利用系統(tǒng)中的反饋信息，會導(dǎo)致大量冗余迭代，降低求精確解的效率.為了克服以上2種算法各自的缺陷，形成優(yōu)勢互補(bǔ)，筆者針對Hadoop平臺下作業(yè)調(diào)度的特點(diǎn)和需求，基于對蟻群算法和遺傳算法融合(Mixed Ant Algorithm&Genetic Algorithm, MAG)的思想[4-5]，研究了一種高速收斂蟻群算法，算法的核心是動態(tài)信息素更新、最優(yōu)節(jié)點(diǎn)選擇和變異策略.

MAG算法的基本思想是首先利用遺傳算法全局收斂性、快速搜索、隨機(jī)性等特點(diǎn)生成初始信息素分布，根據(jù)信息素分布求得任務(wù)調(diào)度的最優(yōu)解[6-7].

2.2 Hadoop作業(yè)調(diào)度的問題描述在Hadoop平臺下，將n個相互獨(dú)立的子任務(wù)分配到m個TaskTracker節(jié)點(diǎn)上執(zhí)行(m

1)n個任務(wù)集表示為P={p1,p2, …,pn}，pi(i=1, 2, …,n)表示第i個子任務(wù)；

2)m個TaskTracker節(jié)點(diǎn)集表示為T={t1,t2, …,tm}，tj(j=1, 2, …,m)表示第j個TaskTracker節(jié)點(diǎn)；

3)設(shè)ETCij為子任務(wù)pj在節(jié)點(diǎn)ti上的期望執(zhí)行時間，則對應(yīng)的任務(wù)在節(jié)點(diǎn)上分配關(guān)系可構(gòu)成m×n的ETC[m,n]矩陣

(1)

其中，ETCij表示第i個任務(wù)在第j個TaskTracker節(jié)點(diǎn)上運(yùn)行的期望執(zhí)行時間[8].

2.3 遺傳算法規(guī)則

2.3.1 遺傳編碼 染色體的編碼方式很多，其中實(shí)數(shù)編碼精度高，便于大空間搜索，因此采用一個實(shí)數(shù)串表達(dá)資源分配情況，作為遺傳算法的染色體.假設(shè)有5個任務(wù)將分配在2個TaskTracker節(jié)點(diǎn)上，隨機(jī)產(chǎn)生的分配方案為

t1:{p2,p4,p5} ，

t2:{p1,p3}，

則對應(yīng)的實(shí)數(shù)編碼串可表示為染色體A1：{2, 1, 2, 1, 1}.由于任務(wù)p2,p4,p5分配在t1節(jié)點(diǎn)上，因此在A1串中其對應(yīng)的2，4，5位置上置為1.任務(wù)p1,p3分配在t2節(jié)點(diǎn)上，因此在A1串中其對應(yīng)的1，3位置上置為2.

2.3.2 初始種群 初始種群的生成可表示為在從1到n的每一位上產(chǎn)生一個[1, m]的隨機(jī)數(shù)，其含義是將n個任務(wù)隨機(jī)分配到m個TaskTracker節(jié)點(diǎn)上.

2.3.3 適應(yīng)度函數(shù) 本算法將目標(biāo)函數(shù)定義為Sbest=argminTimes，適應(yīng)值函數(shù)定義為fitness(s)=1/Times，其中Times表示調(diào)度時間[9-10].

2.3.4 遺傳操作 為了避免遺傳過程的收斂時間過長，本文算法將群體大小設(shè)定為50.此外，考慮到交叉概率Pc和變異概率Pm對遺傳算法性能和收斂性的影響，采用了自適應(yīng)遺傳算法，使得Pc和Pm隨著適應(yīng)度的變化自動改變.Pc和Pm按如下公式進(jìn)行自適應(yīng)調(diào)整

(2)

(3)

2.4 蟻群算法規(guī)則

2.4.1 各節(jié)點(diǎn)的信息素表示 本算法中用節(jié)點(diǎn)上的資源能力與通過遺傳算法中得到各節(jié)點(diǎn)上的任務(wù)預(yù)計執(zhí)行時間相結(jié)合，來衡量該節(jié)點(diǎn)的信息素.

通過TaskTracker與JobTracker之間通信時所提交的心跳信息，可獲知每個TaskTracker節(jié)點(diǎn)所擁有的硬件資源情況，用CPU處理能力p，m，d，b分別代表內(nèi)存、磁盤和帶寬的容量的信息素，為避免節(jié)點(diǎn)超負(fù)載，需為每個參數(shù)設(shè)置一個閾值，分別為p0，m0，d0，b0，可將各信息素初始化為

CPU計算能力信息素

τip(0)=p/p0×100%.

內(nèi)存的信息素

τim(0)=m/m0×100%.

磁盤的信息素

τid(0)=d/d0×100%.

帶寬的信息素

τib(0)=b/b0×100%.

節(jié)點(diǎn)i的信息素是各信息素的帶權(quán)和，其中，a，b，c，d代表的是對于不同的任務(wù)，所需資源的權(quán)重.例如，對于CPU密集型任務(wù)，可適當(dāng)增加CPU計算能力信息素所對應(yīng)的權(quán)重，CPU計算能力較強(qiáng)的節(jié)點(diǎn)更容易被選中.

τi(0)=aτip(0)+bτim(0)+cτid(0)+dτib(0)，

(4)

a+b+c+d=1.

結(jié)合遺傳算法階段對各節(jié)點(diǎn)上分配任務(wù)的執(zhí)行時間預(yù)計情況，可將節(jié)點(diǎn)i上的信息素初始化為

τi(t)=τi(0)+τiG(t) ，

(5)

其中，τiG(t)是從遺傳算法求解結(jié)果轉(zhuǎn)換而來的信息素值.

通常作業(yè)調(diào)度算法只考慮本次調(diào)度，選擇將資源分配至某些最優(yōu)資源節(jié)點(diǎn)，使該節(jié)點(diǎn)過于繁忙，而某些節(jié)點(diǎn)可能一直沒有被分配任務(wù)而處于資源閑置.為了實(shí)現(xiàn)負(fù)載均衡，本算法加入計算負(fù)載系數(shù)其計算公式v=Uc/Usum，其中，Uc代表已完成的任務(wù)量，Usum代表所有任務(wù)量.據(jù)此控制i節(jié)點(diǎn)信息素的更新

τi=v×τi(t) .

(6)

2.4.2 任務(wù)期望執(zhí)行時間 分布式計算的作業(yè)調(diào)度比其他調(diào)度更需要關(guān)注任務(wù)的最小完成時間，在使用蟻群調(diào)度時需計算出在所有資源上每個任務(wù)的期望執(zhí)行時間ETC，生成ETC矩陣，并將其作為蟻群算法的啟發(fā)信息之一.隨著算法的不斷進(jìn)行，節(jié)點(diǎn)上要完成的任務(wù)會減少，任務(wù)完成時間也會減少，因此，需用以下公式更新各節(jié)點(diǎn)上任務(wù)的預(yù)計執(zhí)行時間

(7)

其中，ETCjn predict(Jpredict(t2))表示t2時刻j節(jié)點(diǎn)上運(yùn)行新任務(wù)Jpredict所需的預(yù)計執(zhí)行時間，npredict表示j節(jié)點(diǎn)在t2所運(yùn)行的任務(wù)數(shù)(即節(jié)點(diǎn)的負(fù)載大小).

設(shè)置一個區(qū)間，規(guī)定如果新任務(wù)在某個節(jié)點(diǎn)上的預(yù)計完成時間在該區(qū)間范圍內(nèi)，該節(jié)點(diǎn)就是有效節(jié)點(diǎn).如果存在一個節(jié)點(diǎn)從沒有被分配過任務(wù)，則算法根據(jù)節(jié)點(diǎn)上的資源自動生成預(yù)計完成時間，若該時間在有效時間區(qū)間內(nèi)，則該節(jié)點(diǎn)是有效節(jié)點(diǎn)[11-12].

2.4.3 蟻群算法的節(jié)點(diǎn)選擇 螞蟻將按如下公式選擇下一跳節(jié)點(diǎn)

(8)

經(jīng)過時間n，所有螞蟻對有效節(jié)點(diǎn)進(jìn)行遍歷以后，當(dāng)前螞蟻所在的節(jié)點(diǎn)將置入tabuk，準(zhǔn)備下一次遍歷.此時，計算每只螞蟻所有走過的路徑Lk，并保存最佳路徑(所需時間最短的路徑)Lkmin(Lkmin=minLk，k=1，…，m)，作業(yè)調(diào)度器選擇一個信息素最多的節(jié)點(diǎn)，將任務(wù)分配給其.

2.4.4 信息素的改變 當(dāng)節(jié)點(diǎn)上資源使用率增大即被分配新任務(wù)后，信息素會相應(yīng)減小，可規(guī)定此時信息素按如下公式更新

τi(t1)=τi(t)-λτi(t) 0<λ<1 ，

(9)

其中，τi(t1)是在t1時刻，新任務(wù)到達(dá)i節(jié)點(diǎn)時節(jié)點(diǎn)上的信息素濃度，τi(t)表示i節(jié)點(diǎn)在時刻t的信息素濃度，λ為調(diào)節(jié)因子.

隨著某任務(wù)在t2時刻運(yùn)行成功或失敗，該任務(wù)所在節(jié)點(diǎn)的負(fù)載都將減輕(任務(wù)執(zhí)行失敗時將從當(dāng)前節(jié)點(diǎn)被調(diào)離)，此時可按以下公式增加信息素濃度，從而保證節(jié)點(diǎn)負(fù)載平衡

τi(t2)=τi(t1)-λ1τi(t1) 0<λ1<1.

(10)

此外，成功完成任務(wù)的節(jié)點(diǎn)，可增加該節(jié)點(diǎn)的信息素濃度作為獎勵，而任務(wù)失敗的節(jié)點(diǎn)也應(yīng)減少其信息素予以懲罰，以便引導(dǎo)前向螞蟻接下來的選擇.因此可增加一個用于增加或減少節(jié)點(diǎn)信息素濃度的調(diào)節(jié)因子

τi(t2)=(1+λ2)(τi(t1)+λ1τi(t1)) 0<λ1<1，

(11)

若任務(wù)運(yùn)行成功，則0<λ2<1；若任務(wù)運(yùn)行失敗則-1<λ2<0.

2.5 算法流程基于MAG算法的Hadoop任務(wù)調(diào)度流程如下

Step1初始化遺傳算法控制參數(shù)，讀取JobTracker上的作業(yè)隊(duì)列以及各TaskTracker節(jié)點(diǎn)通過心跳信號提交的任務(wù)執(zhí)行和資源負(fù)載情況；

Step2設(shè)置遺傳算法結(jié)束條件；

Step3隨機(jī)生成初始種群A(0)；

Step4計算A(0)中個體的適應(yīng)度及ETCij；

Step5根據(jù)個體適應(yīng)度和選擇策略確定A(g)代解群，其中g(shù)為遺傳代數(shù)；

Step6根據(jù)式(2)所示的交叉概率Pc執(zhí)行內(nèi)部交叉操作；

Step7根據(jù)公式執(zhí)行變異操作；

Step8計算ETCij和A(g+1)的個體適應(yīng)度.保留最優(yōu)解g+1；

Step9重復(fù)Step5～8，直到滿足遺傳算法結(jié)束條件；

Step10從A(g)中選擇適應(yīng)度值高的前n%個個體，放入集合，作為優(yōu)化解集合；生成ETC矩陣并根據(jù)集合中的優(yōu)化解，轉(zhuǎn)換出各節(jié)點(diǎn)的信息素參數(shù) ；

Step11初始化蟻群算法控制參數(shù)，根據(jù)式(6)設(shè)置各節(jié)點(diǎn)上的信息素；

Step12設(shè)置蟻群算法結(jié)束條件；

Step13將n只螞蟻隨機(jī)發(fā)送到m個資源節(jié)點(diǎn)上；

Step14每只螞蟻根據(jù)式(7)所示的期望時間閾值限制，和式(8)所示的節(jié)點(diǎn)選擇概率選擇下一節(jié)點(diǎn)；

Step15完成所有任務(wù)調(diào)度后，根據(jù)適應(yīng)度的值通過式(11)更新全局信息素.否則，跳轉(zhuǎn)至Step14；

Step16直到算法達(dá)到最大迭代次數(shù)輸出最優(yōu)解，否則轉(zhuǎn)至Step13.

2.6 算法復(fù)雜度分析在蟻群算法中，可以分析得到影響算法的復(fù)雜度的因素為節(jié)點(diǎn)數(shù)n，螞蟻數(shù)量m,迭代次數(shù)T，時間復(fù)雜度time=n×(n-1)×m×T/2，一般來說在具體實(shí)驗(yàn)中，m是n的2/3，T是n的倍數(shù)，分別設(shè)為m=n×2/3，T=k×n，于是time=n×(n-1)×n×2/3×n×k/2，當(dāng)n趨于無窮大時，k遠(yuǎn)小于n，time約等于n4，因此蟻群算法時間復(fù)雜度為O(n4)，同理可得空間復(fù)雜度為O(n2).同理分析可得遺傳算法屬于一個二重迭代，時間復(fù)雜度為O(n2).

本文提出的基于MAG算法從流程分析可知該算法的復(fù)雜度為O(n).

3 實(shí)驗(yàn)與分析

3.1 MAG算法仿真實(shí)驗(yàn)為了檢驗(yàn)本算法的優(yōu)越性，首先在MATLAB中進(jìn)行了MAG算法與GA，ACA算法完成搜索最求解的仿真實(shí)驗(yàn).模擬環(huán)境以20～100個任務(wù)，10個資源點(diǎn)為例進(jìn)行測試.其中，GA算法和ACA算法中控制參數(shù)的設(shè)置與MAG中相應(yīng)的設(shè)置相同，為了保證實(shí)驗(yàn)結(jié)果不失一般性，仿真數(shù)據(jù)在10個資源點(diǎn)上同時進(jìn)行.

圖2 時間-任務(wù)曲線圖3 迭代-任務(wù)曲線

圖2顯示了MAG，GA和ACA算法在調(diào)度30～100個任務(wù)時所消耗的時間情況.GA在處理前50個任務(wù)時的搜索能力較強(qiáng)，搜索時間較短，但隨著迭代次數(shù)增多，搜索時間也越來越長.與之相反，ACA算法在搜索的初期由于缺少信息素，搜索速度緩慢，但隨著信息素的積累搜索最優(yōu)解的速度迅速提高，時間增加幅度小于GA算法.圖3給出了3種算法在調(diào)度30～100個任務(wù)時獲得最優(yōu)解所需要迭代的次數(shù)，通過對3組數(shù)據(jù)的比較可見，GA算法的迭代次數(shù)最多，計算勢必耗費(fèi)大量時間.相比之下，MAG算法在搜索的前期借助GA算法能夠快速獲得初始信息素分布，在達(dá)到最佳點(diǎn)之后再結(jié)合ACA算法可高效求得任務(wù)調(diào)度的最優(yōu)解，無論是時間上還是迭代次數(shù)上都表現(xiàn)出較明顯的優(yōu)勢.

3.2 基于Hadoop平臺的作業(yè)調(diào)度測試為了測試MAG算法在Hadoop平臺下對作業(yè)調(diào)度的影響，筆者在海南大學(xué)云計算實(shí)驗(yàn)室配置了30個測試節(jié)點(diǎn)，基本配置：4個處理核心，8G內(nèi)存，1TB硬盤.其中一個節(jié)點(diǎn)作為主控節(jié)點(diǎn)，同時承擔(dān)HDFS文件系統(tǒng)的NameNode節(jié)點(diǎn)以及MapReduce集群的JobTracker節(jié)點(diǎn)角色，另外29個節(jié)點(diǎn)作為工作節(jié)點(diǎn)(DataNode及TaskTracker節(jié)點(diǎn))，每個計算節(jié)點(diǎn)分配6個Map計算槽、2個Reduce計算槽，主要實(shí)驗(yàn)參數(shù)如表1所示.

表1 Hadoop 參數(shù)設(shè)置

實(shí)驗(yàn)通過模擬真實(shí)作業(yè)來評估算法的使用情況，選擇了3種基于Hadoop平臺下的典型應(yīng)用

DataSorting：實(shí)現(xiàn)了對文本數(shù)據(jù)的全局排序.

WebCrawl：模仿爬蟲行為，抓取網(wǎng)頁內(nèi)容并生成索引，屬網(wǎng)絡(luò)密集型應(yīng)用.

CPUIntensive：對輸入的每個key-value對進(jìn)行一次大整數(shù)乘法計算，屬于CPU密集型.

數(shù)字1～10代表資源使用量，各作業(yè)的估計資源使用值如表2所示.

表2 各作業(yè)估計資源使用值

在Hadoop平臺下常用的作業(yè)調(diào)度方法中，公平調(diào)度算法和計算能力調(diào)度算法需由管理員權(quán)衡作業(yè)的資源使用情況和集群中各TaskTracker節(jié)點(diǎn)的資源負(fù)載情況，手工設(shè)定配置文件相關(guān)參數(shù)，無法實(shí)現(xiàn)作業(yè)的自適應(yīng)調(diào)度，與本文所設(shè)計的自適應(yīng)算法沒有可比性.因此僅針對Hadoop默認(rèn)的FIFO作業(yè)調(diào)度器進(jìn)行了比較測試，3種不同類型作業(yè)在2種調(diào)度方式下完成時間情況如圖4所示.

圖4 MAG 與FIFO 算法作業(yè)調(diào)度時間比較

在FIFO調(diào)度機(jī)制下不考慮不同作業(yè)不同用戶的在資源需求和占用上的差別，而只是按照提交作業(yè)的時間順序來進(jìn)行調(diào)度，會嚴(yán)重降低系統(tǒng)資源利用率，例如當(dāng)一個CPU密集型作業(yè)長時間占用計算資源時，會造成隨后提交的某些交互型作業(yè)無法得到快速反饋，影響用戶體驗(yàn)[17].基于MAG的調(diào)度算法雖然在作業(yè)調(diào)度初期會耗費(fèi)一些時間搜集信息素并進(jìn)行迭代操作，但能夠根據(jù)作業(yè)需求和節(jié)點(diǎn)上資源負(fù)載的情況，得出任務(wù)調(diào)度的最優(yōu)解.整體時間相比FIFO算法有著明顯優(yōu)勢.

4 結(jié)束語

針對Hadoop集群作業(yè)調(diào)度方式的展開研究，提出一種基于遺傳算法和蟻群算法融合求解任務(wù)分配最優(yōu)解的方法，實(shí)現(xiàn)根據(jù)Hadoop集群各節(jié)點(diǎn)的負(fù)載情況以及對子任務(wù)完成時間的預(yù)計，將任務(wù)調(diào)度到最適合的節(jié)點(diǎn)上執(zhí)行.本算法相對于目前應(yīng)用于Hadoop平臺的3種常用調(diào)度器，不僅提高了作業(yè)調(diào)度的效率，而且由于其自適應(yīng)的特點(diǎn)，可以降低管理員對TaskTracker節(jié)點(diǎn)的管理成本，除Hadoop集群管理平臺外，本算法也可應(yīng)用于其他云計算環(huán)境下的作業(yè)調(diào)度.

[1]HadoopWT.TheDefinitiveGuide[M].[S.l.]：O’Reilly, 2009:1-60.

[2]ApacheHadoop[EB/OL].[2015-05-15].http://hadoop.apache.org

[3] 王小平, 曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安：西安交通大學(xué)出版社, 2002.

[4]DebK，BeyerHG．Self-adaptivegeneticalgorithmswithsimulatedbinarycrossover[J]．EvolutionaryComputation， 2001，9(2):137-221．

[5]DorigoM,CaroGD.Antcolonyoptimizationanewmeta-heuristic：proceedingsofthe1999CongressonEvolutionaryComputation，WashingtonD.C.,July6-9，1999[C].[S.l.]：IEEE， 1999.

[6]BonabeauE，DorigoM，TheraulazG.SwarmIntelligence:fromnaturaltoartificialsystem[M].Oxford:OxfordUniversityPress, 1999.

[7]L?mmelR.Google’sMapReduceprogrammingmodel-Revisited[J].ScienceComputerProgram， 2008,70(1):22-30.

[8]LamC.HadoopinAction[M].Stamford：ManningPublications, 2010:86-110

[9] 李士勇.蟻群優(yōu)化算法及其應(yīng)用研究進(jìn)展[J].計算機(jī)測量與控制， 2003, 11(12): 911-913.

[10] 李鑫,張鵬.Hadoop集群公平調(diào)度算法的改進(jìn)與實(shí)現(xiàn)[J].電腦知識與技術(shù)， 2012,8(1): 166-168.

[11] 許丞, 劉洪,譚良.Hadoop云平臺的一種新的任務(wù)調(diào)度和監(jiān)控機(jī)制[J].計算機(jī)科學(xué)， 2013(1)：112-117.

[12] 賀曉麗. 一種用于任務(wù)調(diào)度的廣義遺傳算法[J].計算機(jī)工程，2010(17)：184-186.

[13] 劉琨,肖琳,趙海燕.Hadoop中云數(shù)據(jù)負(fù)載均衡算法的研究及優(yōu)化[J].微電子學(xué)與計算機(jī)， 2012(9)：18-22.

[14] 宋昕,宋歡歡. 云計算環(huán)境下的流量控制和負(fù)載均衡策略[J].電子設(shè)計工程， 2011(12)：112-115.

[15] 許昌,常會友,徐俊，等. 一種新的融合分布估計的蟻群優(yōu)化算法[J].計算機(jī)科學(xué)， 2010(2)：186-190.

[16] 李德啟,田素貞.一種基于云環(huán)境下蟻群優(yōu)化算法的改進(jìn)研究[J].陜西科技大學(xué)學(xué)報(自然科學(xué)版)， 2012(1)：64-67.

[17] 李彬.基于Hadoop框架的TF-IDF算法改進(jìn)[J].微型機(jī)與應(yīng)用， 2012(7)：14-16.

Hadoop Clusters of Job Scheduling Based on Mixed Ant Algorithm Genetic Algorithm

Lou Tao1, Du Wencai1,2, Zhong Jiezhuo1

(1. College of Information Science and Technology, Hainan University, Haikou 570228, China; 2. City University of Macau, Macau, China)

In our report, a kind of self-adaptive job scheduling mechanism based on ant algorithm and genetic algorithm was proposed, which integrated the advantages of genetic algorithm, the global convergence and fast search, with the characteristics of ant algorithm, the positive feedback and efficient refinement, and the mutation strategy was performed to accelerate the speed of local optimization and convergence. The results indicated that the algorithm can obtain the most suitable nodes for current jobs and effectively improve the efficiency of job scheduling on Hadoop clusters.

Ant Algorithm; Genetic Algorithm; Hadoop Clusters

2015-06-03

國家自然科學(xué)基金(61162010)；海南大學(xué)青年基金(Qnjj1186)

樓濤(1991-)，男，浙江紹興人，2013級碩士研究生，研究方向：數(shù)據(jù)與知識工程,無線移動計算等，E-mail：lou19910526@163.com

杜文才(1953- ),男,江蘇徐州人,博士,教授,主要研究方向:e-Service,云計算，網(wǎng)絡(luò)通信等，E-mail：georgedu@cityu.edu.mo,wencai@hainu.edu.cn

1004-1729(2015)04-0340-07

TP 311

A DOl：10.15886/j.cnki.hdxbzkb.2015.0060