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

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

Hadoop分布式系統(tǒng)基礎(chǔ)架構(gòu)由2個(gè)核心部分組成：分布式文件系統(tǒng)HDFS和分布式計(jì)算引擎MapReduce.其中，HDFS有著高容錯(cuò)性的特點(diǎn)，可部署在低廉的硬件上，提供高吞吐量訪問應(yīng)用程序的數(shù)據(jù)，HDFS是一個(gè)主從結(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計(jì)算架構(gòu)的系統(tǒng)架構(gòu)如圖1所示.

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

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

TaskTracker每隔10 s與JobTracker通訊一次，通過heartbeat()方法向JobTracker發(fā)送心跳信號(hào).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ì)采用的是插件機(jī)制，即作業(yè)調(diào)度器是動(dòng)態(tài)加載的、可插拔的，同時(shí)第三方可以開發(fā)自己的任務(wù)調(diào)度器替代Hadoop默認(rèn)的調(diào)度器.目前，Hadoop的作業(yè)調(diào)度器主要包括：默認(rèn)的FIFO算法、由Facebook提出的公平調(diào)度算法和由雅虎公司提出的計(jì)算能力調(diào)度算法.

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

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

同現(xiàn)有任務(wù)調(diào)度算法對(duì)比，本文提出的算法不需要管理員進(jìn)行預(yù)設(shè)置，而是通過監(jiān)控每個(gè)TaskTracker 負(fù)載以及作業(yè)提交和完成的情況，自動(dòng)地完成任務(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)化問題，但在搜索初期由于缺少信息素會(huì)導(dǎo)致信息素積累時(shí)間較長，求解速度較慢.遺傳算法(Genetic Algorithm，GA)以“物種靠不斷的演化而生成最適合生存的物種”的進(jìn)化論觀點(diǎn)為依據(jù)，對(duì)即定問題尋求最優(yōu)解，能夠?qū)崿F(xiàn)快速的全局搜索[3]，但由于該算法沒有利用系統(tǒng)中的反饋信息，會(huì)導(dǎo)致大量冗余迭代，降低求精確解的效率.為了克服以上2種算法各自的缺陷，形成優(yōu)勢互補(bǔ)，筆者針對(duì)Hadoop平臺(tái)下作業(yè)調(diào)度的特點(diǎn)和需求，基于對(duì)蟻群算法和遺傳算法融合(Mixed Ant Algorithm&Genetic Algorithm, MAG)的思想[4-5]，研究了一種高速收斂蟻群算法，算法的核心是動(dòng)態(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平臺(tái)下，將n個(gè)相互獨(dú)立的子任務(wù)分配到m個(gè)TaskTracker節(jié)點(diǎn)上執(zhí)行(m

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

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

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

(1)

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

2.3 遺傳算法規(guī)則

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

t1:{p2,p4,p5} ，

t2:{p1,p3}，

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

2.3.2 初始種群 初始種群的生成可表示為在從1到n的每一位上產(chǎn)生一個(gè)[1, m]的隨機(jī)數(shù)，其含義是將n個(gè)任務(wù)隨機(jī)分配到m個(gè)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)度時(shí)間[9-10].

2.3.4 遺傳操作 為了避免遺傳過程的收斂時(shí)間過長，本文算法將群體大小設(shè)定為50.此外，考慮到交叉概率Pc和變異概率Pm對(duì)遺傳算法性能和收斂性的影響，采用了自適應(yīng)遺傳算法，使得Pc和Pm隨著適應(yīng)度的變化自動(dò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ù)計(jì)執(zhí)行時(shí)間相結(jié)合，來衡量該節(jié)點(diǎn)的信息素.

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

CPU計(jì)算能力信息素

τ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代表的是對(duì)于不同的任務(wù)，所需資源的權(quán)重.例如，對(duì)于CPU密集型任務(wù)，可適當(dāng)增加CPU計(jì)算能力信息素所對(duì)應(yīng)的權(quán)重，CPU計(jì)算能力較強(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é)合遺傳算法階段對(duì)各節(jié)點(diǎn)上分配任務(wù)的執(zhí)行時(shí)間預(yù)計(jì)情況，可將節(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ù)載均衡，本算法加入計(jì)算負(fù)載系數(shù)其計(jì)算公式v=Uc/Usum，其中，Uc代表已完成的任務(wù)量，Usum代表所有任務(wù)量.據(jù)此控制i節(jié)點(diǎn)信息素的更新

τi=v×τi(t) .

(6)

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

(7)

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

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

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

(8)

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

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

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

(9)

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

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

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

(10)

此外，成功完成任務(wù)的節(jié)點(diǎn)，可增加該節(jié)點(diǎn)的信息素濃度作為獎(jiǎng)勵(lì)，而任務(wù)失敗的節(jié)點(diǎn)也應(yīng)減少其信息素予以懲罰，以便引導(dǎo)前向螞蟻接下來的選擇.因此可增加一個(gè)用于增加或減少節(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)通過心跳信號(hào)提交的任務(wù)執(zhí)行和資源負(fù)載情況；

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

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

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

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

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

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

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

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

Step10從A(g)中選擇適應(yīng)度值高的前n%個(gè)個(gè)體，放入集合，作為優(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個(gè)資源節(jié)點(diǎn)上；

Step14每只螞蟻根據(jù)式(7)所示的期望時(shí)間閾值限制，和式(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，時(shí)間復(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趨于無窮大時(shí)，k遠(yuǎn)小于n，time約等于n4，因此蟻群算法時(shí)間復(fù)雜度為O(n4)，同理可得空間復(fù)雜度為O(n2).同理分析可得遺傳算法屬于一個(gè)二重迭代，時(shí)間復(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個(gè)任務(wù)，10個(gè)資源點(diǎn)為例進(jìn)行測試.其中，GA算法和ACA算法中控制參數(shù)的設(shè)置與MAG中相應(yīng)的設(shè)置相同，為了保證實(shí)驗(yàn)結(jié)果不失一般性，仿真數(shù)據(jù)在10個(gè)資源點(diǎn)上同時(shí)進(jìn)行.

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

[16] 李德啟,田素貞.一種基于云環(huán)境下蟻群優(yōu)化算法的改進(jìn)研究[J].陜西科技大學(xué)學(xué)報(bào)(自然科學(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級(jí)碩士研究生，研究方向：數(shù)據(jù)與知識(shí)工程,無線移動(dòng)計(jì)算等，E-mail：lou19910526@163.com

杜文才(1953- ),男,江蘇徐州人,博士,教授,主要研究方向:e-Service,云計(jì)算，網(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