Hadoop中任務調(diào)度算法的改進

蘇小會，何婧媛

（西安工業(yè)大學 計算機科學與工程學院，陜西 西安 710032）

云計算技術(shù)發(fā)展到現(xiàn)在，已經(jīng)出現(xiàn)了很多云計算的軟件平臺，但是功能強、性能穩(wěn)定的基本都是商業(yè)軟件，目前只有Hadoop是可實現(xiàn)大規(guī)模分布式計算的開源軟件平臺[1]，因此對于Hadoop的應用和研究也最多。

Hadoop旨在構(gòu)建一個具有高可靠性和良好擴展性的分布式系統(tǒng)，在很多大型網(wǎng)站上都已經(jīng)得到了應用，可以說是目前最為廣泛應用的開源云計算軟件平臺[1]。Hadoop有以下優(yōu)點：擴容能力強、成本低廉、效率高、高可靠性、免費開源及良好的可移植性。

Hadoop0.20.0中的任務調(diào)度算法包括FIFO調(diào)度算法（First In First Out）、公平調(diào)度算法（Fair Scheduler）和計算能力調(diào)度算法（Capacity Scheduler）。FIFO算法的整體性能和系統(tǒng)資源的利用率不高；公平調(diào)度算法負載不均衡，系統(tǒng)的響應時間長，配置文件的好壞影響整個系統(tǒng)的性能；計算能力調(diào)度算法中隊列設置和隊列組無法自動進行從而影響系統(tǒng)整體性能的提高。因此對于Hadoop中任務調(diào)度算法的改進和優(yōu)化一直就沒有停息，文中根據(jù)對任務執(zhí)行過程的實時監(jiān)控，依據(jù)任務執(zhí)行結(jié)果放的反饋，動態(tài)調(diào)整后續(xù)任務的分配和執(zhí)行，在現(xiàn)有任務調(diào)度算法的基礎上提出一種基于改進遺傳算法（IGA）的任務調(diào)度算法，該算法最大特點是利用遺傳算法的群體搜索技術(shù)使得群體進化到包含或接近最優(yōu)解，從而解決現(xiàn)有任務調(diào)度算法收斂速度慢、任務完成時間長、負載不均、資源利用率低、系統(tǒng)整體性能低等缺點。

1 問題分析

任務調(diào)度算法作為Hadoop平臺的核心技術(shù)之一，直接關系到Hadoop平臺的整體性能和對系統(tǒng)資源的利用，本文的研究目標是改進和完善任務調(diào)度算法以提高平臺的整體性能和系統(tǒng)資源使用率。

1.1 Hadoop中的任務調(diào)度算法

Hadoop的MapReduce任務調(diào)度[2]是一個主動請求的任務，其任務請求調(diào)度過程如圖1所示。slave的SubTaskTracker主動向master的TaskTracker請求任務，當SubTaskTracker接到任務后，通過自身調(diào)度在本slave建立起SubTask，執(zhí)行任務。

這個過程可以簡單地概括為以下4個步驟：

1）TaskClient提交任務；

2）TaskTracker接收任務生成子任務；

3）SubTaskTracker申請子任務；

4）TaskTracker分配并監(jiān)控子任務。

對Hadoop中調(diào)度算法的改進也已經(jīng)有很多研究，文獻[3]中作者提出了一種基于樸素貝葉斯分類的作業(yè)調(diào)度算法。改進遺傳算法的并行任務調(diào)度[4]中提出了一種基于改進遺傳算法的并行任務調(diào)度算法。文獻 [5]中HP實驗室開發(fā)的Dynamic Priority schedule調(diào)度，允許用戶不斷地增加或更改他們的隊列優(yōu)先順序來滿足當前負載的需要。文獻[6]中介紹了延遲調(diào)度并提出了一種基于特征加權(quán)的樸素貝葉斯分類器算法來解決公平調(diào)度算法中需要對隊列和資源池進行資源配置的問題，

圖1 Hadoop的任務請求調(diào)度過程示意圖Fig.1 Process schematic diagram of the task request scheduling in hadoop

1.2 問題分析

Hadoop0.20.0中公平調(diào)度算法和計算能力調(diào)度算法都需要在分配任務資源之前進行一些配置工作，比如管理員需要對SubTaskTracker上可以同時運行的最大子任務數(shù)進行正確設置。但要準確設置最大子任務數(shù)，需要管理員深入掌握Hadoop平臺上運行的MapReduce任務和SubTaskTracker兩者各自資源使用特點。公平調(diào)度算法和計算能力調(diào)度算法雖然比FIFO調(diào)度算法有很大程度上的提高，但仍然需要預先設置任務池和用戶池的容量或是權(quán)重，實際操作中遇到多用戶、多任務情況下預先設置任務池和用戶池的容量或是權(quán)重難度很大。

文中研究不預先設置最大子任務數(shù)以及任務池和用戶池的容量或是權(quán)重，而對任務執(zhí)行過程進行實時監(jiān)控，根據(jù)任務執(zhí)行結(jié)果的反饋，對后續(xù)任務進行動態(tài)調(diào)度，在現(xiàn)有任務調(diào)度算法的基礎上對最大子任務數(shù)以及任務池和用戶池的容量或是權(quán)重的取值使用遺傳算法進行動態(tài)計算，得到最佳取值后再應用公平調(diào)度算法或者計算能力調(diào)度算法進行調(diào)度。IGA任務調(diào)度算法試圖做出以下一些改進：

1）對遺傳算法的初始種群生成方式進行改進，以達到減少迭代次數(shù)，并提高運行速度的目的；

2）用兩個適應度來選擇種群，以便達到總?cè)蝿盏耐瓿蓵r間和任務平均所用時間都較短的目的；

3）在選擇、交叉、變異等遺傳操作過程中，有可能會破壞當前種群中適應度最高的個體，加入最優(yōu)保留策略來更好的對種群進行優(yōu)勝劣汰以提高算法的收斂精度；

4）采用規(guī)則約束的交叉和變異操作以提高個體質(zhì)量；

5）引入加速進化策略以避免早熟而使得算法停滯的問題。

2 基于改進遺傳算法的設計

2.1 初始種群生成

基于均勻分布策略的初始種群生成方式可以保證隨機產(chǎn)生的個體間有明顯的差異，使它們比較均勻地分布在解空間上，保證初始種群有較豐富的模式，從而提高搜索收斂于全局最優(yōu)解的可能，再進行幾代進化，使得種群中解的質(zhì)量逐漸提高，然后通過尋找提交給遺傳算法的任務間的相似性，重復使用先前相似任務的解決方案作為當前任務的種群染色體個體，以此來形成當前任務的初始種群，從總體上減少總的進化次數(shù)。IGA的初始種群采用基于均勻分布策略通過隨機方式產(chǎn)生整個算法的第一代種群，以保證有足夠的個體差異性。

為實現(xiàn)改進遺傳算法的初始種群選擇性建立問題，本文引入一個歷史表用來存儲對任務的描述和對應的調(diào)度方案。

定義1：任務的描述是任務在資源上執(zhí)行時間的矩陣ETC[i，j]，ETC矩陣表示各個子任務在每個資源上執(zhí)行時間，ETC[i，j]表示第i個子任務在第j個資源上執(zhí)行完成所需要的時間。

定義2：不同樣本之間的相似性度量（Similarity Measurement）通常采用計算樣本間“距離”（Distance） 的方法，任務的相似性判斷可以通過輸入任務的期望執(zhí)行時間矩陣ETC與表中存儲的歷史任務執(zhí)行時間矩陣計算得到，兩個含有k個元素的向量 a（x11，x12，…，x1k）與 b（x21，x22，…，x2k），則兩向量的相似性可由下式得出：

2.2 最優(yōu)保留策略

最優(yōu)保留策略，即在群體交叉、變異之前，先選出本代適應度最高的兩個個體進行保留，不參加選擇、交叉、變異等遺傳操作。而等本代個體完成遺傳操作之后，用先前保留的兩個個體與完成遺傳操作的種群中適應度最小的兩個個體進行替換，這使得種群更好的進化，提高了優(yōu)勝劣汰的質(zhì)量。

2.3 規(guī)則約束的交叉和變異操作

交叉將選中個體的基因進行交叉，從而生成包含更優(yōu)良結(jié)構(gòu)的新個體。交叉操作在解空間中進行有效的搜索，同時降低對有效模式的破壞概率。變異隨機地改變選中個體串結(jié)構(gòu)數(shù)據(jù)中某個串的值來產(chǎn)生新個體，以改善算法的局部搜索能力并維持種群多樣性。由于目前云計算中任務調(diào)度的特點，傳統(tǒng)的單點、多點和順序等交叉變異方法不再適用，所以本文采用規(guī)則約束的交叉和變異操作。

假設a和b是進行交叉操作的兩個個體，則根據(jù)以下規(guī)則進行交叉：任意將a和b中的一個或者多個串值進行對換，且對換的串值最好是不同的。

變異操作針對選中個體的串結(jié)構(gòu)數(shù)據(jù)，任意選擇n個串中的一個或者多個根據(jù)以下規(guī)則進行變異：

1）將該串值變異為串結(jié)構(gòu)數(shù)據(jù)中任意的一個值；

2）將任意串移動到距其所在串結(jié)構(gòu)的前一不同串值的任意位置。

2.4 加速進化策略

算法后期的種群中容易導致早熟局部收斂，為了避免早熟而使得算法停滯的問題，本文引入了加速進化策略，即在檢測到算法的早熟指標Dp≤$后，則將交叉和變異的概率均臨時性的提高k倍，文中將k取值為10，以保證在加速進化后的交叉和變異概率達到100%；當早熟指標Dp＞$后，又將交叉和變異的概率恢復正常。其中$為早熟判斷門限值，其值由求解中某代個體平均適應度的量級確定，即1×10x。若50個任務，由平均適應度的量級確定x=-2，則$=0.01。

其中，fmax表示本代個體最大適應度值，fmin表示本代個體最小適應度值，favg表示本代個體平均適應度值。

3 基于改進遺傳算法的實現(xiàn)

3.1 算法流程

根據(jù)第2節(jié)的描述，算法的求解過程如下：

1）初始化控制參數(shù)；

2）對基因進行編碼，并隨機產(chǎn)生初始種群；

3）評價群體中每個個體的適應度函數(shù)值；

4）選出適應度最高的個體進行保留；

5）根據(jù)定義的遺傳算子，分別對種群進行選擇、交叉、變異操作，產(chǎn)生下一代子群；

6）將保留的個體與新種群中適應度最小的個體進行替換；

7）根據(jù)加速進化策略對種群進行進化；

8）若滿足收斂條件，返回最優(yōu)解，結(jié)束算法；否則，返回到步驟 3）。

根據(jù)上述描述，可以得到基于IGA的任務調(diào)度算法流程圖如圖2所示。

3.2 算法實現(xiàn)

根據(jù)3.1節(jié)給出的算法流程圖，將基于IGA的任務調(diào)度算法的過程概括如下：

1）客戶端提交MapReduee任務；

2）初始化任務，創(chuàng)建運行子任務列表；

圖2 基于IGA的任務調(diào)度算法流程圖Fig.2 Flow chart of the task scheduling algorithm based on IGA

3）SubTaskTraeker空閑時， 主動發(fā)出心跳請求TaskTraeker分配任務；

4）TaskTracker采用基于IGA的任務調(diào)度算法選擇一個最優(yōu)的任務；

5）選擇該任務的一個子任務分配給發(fā)送心跳請求的SubTaskTracker；

6）SubTaskTracker被分配了子任務后開始運行子任務，子任務完成時告知TaskTracker；

7）TaskTracker在接到子任務完成的通知后，把任務的狀態(tài)設置為“成功”，并顯示一條消息告訴用戶。

3.3 實驗驗證

由于實驗條件有限，本實驗平臺是由3臺機器構(gòu)成的集群，其中一臺作為 Master，負責 NameNode和 TaskTracker的工作，另兩臺作為Slave，負責DataNode和SubTaskTracker的工作。每臺實驗機器上均運行Ubuntu 10.10系統(tǒng)，java版本1.6，Hadoop版本0.20.2。實驗中的三臺機器分別設置主機名為 hadoop1、hadoop2、hadoop3，其中 hadoop1 為 Master，其他為Slave，圖3為Hadoop平臺結(jié)構(gòu)示意圖，具體配置過程簡單概括為以下3步：

圖3 Hadoop平臺結(jié)構(gòu)示意圖Fig.3 Schematic diagram of the Hadoop platform

1）下載 Linux環(huán)境下的 JDK安裝包 jdk-6u27-linuxi586.bin進行安裝，并配置環(huán)境變量。

2）配置SSH及無密碼登陸本機

3）安裝并配置Hadoop：

使用前面搭建的Hadoop集群來評估算法的性能。將本文提出的IGA任務調(diào)度算法與Hadoop平臺現(xiàn)有的3種算法進行性能比較實驗，選取同一個任務，每次用不同的算法運行這個任務，總共運行10次，記錄每次算法運行的時間。初始條件：任務數(shù)量為50；收斂條件：1）達到最大進化代數(shù)MaxGen（這里取 MaxGen=100）；2）如果連續(xù) 50代總?cè)蝿胀瓿蓵r間和任務平均完成時間都沒有變化，認為算法基本收斂，終止算法。在生成初始種群時若相似度Simlarity（a，b）的取值大于或等于0.75就認為任務a和b相似。實驗參數(shù)如表1所示。

表1 實驗主要參數(shù)Tab.1 Test main parameters of experiment

要將調(diào)度算法從Hadoop平臺現(xiàn)有的調(diào)度算法配置為本文IGA任務調(diào)度算法，需要將已經(jīng)編寫好的IGA任務調(diào)度程序拷貝到Hadoop_Home/lib下，然后在Hadoop中修改配置文件并加入IGA任務調(diào)度模塊，最后檢查調(diào)度算法是否運行。對實驗結(jié)果進行分析后得到圖4。

圖4 性能比較實驗Fig.4 Performance comparison test

由上圖可知，F(xiàn)IFO算法的運行時間最長，且效率低，但是運行時間比較穩(wěn)定。公平算法和計算能力算法隨著SubTaskTracker上最多可同時運行的子任務數(shù)以及任務池或者任務隊列的設置不同而存在較大的波動。總的來說公平調(diào)度算法和計算能力調(diào)度算法的運行時間是低于IGA算法的。本文提出的IGA算法雖存在波動，但是運行幾次后算法開始收斂并趨于穩(wěn)定。

4 結(jié) 論

文中通過對Hadoop現(xiàn)有調(diào)度算法和IGA任務調(diào)度算法的性能比較實驗可知，IGA任務調(diào)度算法的性能比FIFO算法要高的多，相對公平算法和計算能力算法存在著優(yōu)勢，不僅提供非常不錯的性能同時減輕了管理員和用戶的負擔、提高了管理效率。通過仿真實驗也表明IGA算法可以對Hadoop下編程模式實現(xiàn)較為理想的任務調(diào)度，滿足了實際操作中多用戶、多任務的需求動態(tài)變化，解決了公平調(diào)度算法和計算能力調(diào)度算法中預先設置困難的問題，使得改進的任務調(diào)度算法迭代次數(shù)少、收斂速度快、任務完成時間少、負載均衡、資源利用率高、系統(tǒng)整體性能高，是一種有效的任務調(diào)度算法。

[1]Hadoop[EB/OL].（2011-04-16）http://www.Hadoop.org.

[2]宋坤芳.基于蟻群算法的云計算資源調(diào)度策略研究[D].武漢：武漢紡織大學，2011.

[3]夏袆.Hadoop平臺下的作業(yè)調(diào)度算法研究與改進 [D].廣州：華南理工大學，2010.

[4]袁雪莉，鐘明洋.改進遺傳算法的并行任務調(diào)度[J].計算機工程與應用，2011，47（10） :56-59.

YUAN Xue-li，ZHONG Ming-yang.Parallel task scheduling algorithm using improved genetic algorithm[J].Computer Engineering and Applications，2011，47（10）:56-59.

[5]Sandholm T，Lai K.Dynamic proportional share scheduling in Hadoop[J].In:Springer:2010:110-131.

[6]余正祥.基于hadoop平臺作業(yè)調(diào)度算法研究[D].昆明：云南大學，2011.