Map/Reduce下快速剪枝算法在復(fù)雜任務(wù)調(diào)度中的應(yīng)用*

裴樹軍，宋冬梅，孔德凱

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

隨著計(jì)算、存儲(chǔ)以及通信等技術(shù)的快速發(fā)展，云計(jì)算[1-2]已經(jīng)成為一種新興的商業(yè)計(jì)算模式。云計(jì)算通過對分布處理（distributed computing）、并行處理（parallel computing）、網(wǎng)格計(jì)算（grid computing）、虛擬化技術(shù)和分布式數(shù)據(jù)庫等計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的整合和改進(jìn)，實(shí)現(xiàn)了對基礎(chǔ)資源的共享，并提供更為靈活的彈性服務(wù)。目前IBM、Google、Amazon、Microsoft等知名公司都加大對云計(jì)算的研究，比如Google公司的Google搜索[3]，Amazon的EC2。近些年國內(nèi)學(xué)者對云計(jì)算也進(jìn)行了卓有成效的研究，比如阿里巴巴的云計(jì)算平臺(tái)，中國移動(dòng)的OneNet平臺(tái)?，F(xiàn)今國內(nèi)外云計(jì)算大部分采用Google提出的Map/Reduce編程模型，Map/Reduce是Google公司開發(fā)的用于解決大規(guī)模數(shù)據(jù)集（大于1 TB）分布式存儲(chǔ)和并行計(jì)算的一種軟件架構(gòu)，是處理海量數(shù)據(jù)的并行編程模型。這種編程模型是一種線性的、可伸縮的編程模型，主要擅長于對半結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)進(jìn)行分析，具有容錯(cuò)能力強(qiáng)而且基礎(chǔ)設(shè)施可以靈活擴(kuò)展的特點(diǎn)，因此現(xiàn)在任務(wù)調(diào)度模型大都基于Map/Reduce開發(fā)。

任務(wù)調(diào)度問題[4]一直是云計(jì)算系統(tǒng)關(guān)注的核心問題，影響任務(wù)調(diào)度效率的因素很多，其中復(fù)雜任務(wù)的處理是影響任務(wù)調(diào)度效率的一個(gè)關(guān)鍵因素。復(fù)雜任務(wù)是指任務(wù)之間存在一定偏序或依賴關(guān)系，即后一個(gè)任務(wù)必須在前一個(gè)任務(wù)完成之后才能開始執(zhí)行，這種依賴關(guān)系可能具有迭代性，也可能不具有迭代性，如Fibonacci函數(shù)Fk+2=Fk+Fk+1,前后數(shù)據(jù)項(xiàng)之間存在很強(qiáng)的依賴關(guān)系。傳統(tǒng)任務(wù)調(diào)度算法對復(fù)雜任務(wù)沒有明確的限定，因此缺少合理的復(fù)雜任務(wù)調(diào)度策略。

因?yàn)閭鹘y(tǒng)的Map/Reduce任務(wù)調(diào)度模型的并行化處理模式?jīng)]有對復(fù)雜任務(wù)的明確處理策略，所以在任務(wù)執(zhí)行時(shí)可能會(huì)由于某一個(gè)子任務(wù)無法正常執(zhí)行導(dǎo)致整個(gè)任務(wù)執(zhí)行效率較低，甚至?xí)捎谌蝿?wù)阻塞導(dǎo)致程序無法正常運(yùn)行。因此如何提高復(fù)雜任務(wù)的處理效率成為提高任務(wù)調(diào)度整體效率的核心問題。本文主要針對復(fù)雜多任務(wù)調(diào)度[5]提出了一種在Map/Reduce框架下基于剪枝算法的任務(wù)調(diào)度算法，以抽樣法[6]獲得節(jié)點(diǎn)處理任務(wù)的時(shí)間，再將其與節(jié)點(diǎn)處理任務(wù)的能力（計(jì)算能力、網(wǎng)絡(luò)帶寬能力等）的比值作為時(shí)間預(yù)測，即處理時(shí)間與節(jié)點(diǎn)處理能力成反比，而抽樣的任務(wù)處理時(shí)間與真實(shí)任務(wù)處理時(shí)間成正比。其中節(jié)點(diǎn)處理能力Γij=ti.l/rj.c為任務(wù)長度與資源計(jì)算能力的比值。將得到的任務(wù)處理時(shí)間進(jìn)行量化，建立任務(wù)和節(jié)點(diǎn)處理時(shí)間的n×n矩陣，通過使用剪枝算法先獲得任務(wù)分配局部最優(yōu)解，之后逐步剪枝獲得任務(wù)分配全局最優(yōu)解，并按照復(fù)雜任務(wù)預(yù)處理產(chǎn)生的最佳拓?fù)渑判驅(qū)ψ罴逊峙渚仃囍械娜蝿?wù)進(jìn)行分配，從而使復(fù)雜任務(wù)高效準(zhǔn)確地執(zhí)行。其與Spark中的DAG（directed acyclic graph）相比：首先每個(gè)節(jié)點(diǎn)都充分考慮內(nèi)存資源的使用情況，減少了因不確定因素導(dǎo)致的內(nèi)存溢出，產(chǎn)生任務(wù)執(zhí)行失敗的情況；其次本文任務(wù)排序是根據(jù)任務(wù)之間的依賴關(guān)系大小而產(chǎn)生的最佳拓?fù)渑判?，很大程度上使任?wù)之間的關(guān)聯(lián)更明確，并且如果某個(gè)任務(wù)執(zhí)行失敗，可以根據(jù)依賴關(guān)系的大小依次從父節(jié)點(diǎn)的內(nèi)存中取出需要的信息與現(xiàn)有內(nèi)存數(shù)據(jù)一起重新執(zhí)行該任務(wù)，如果依賴關(guān)系強(qiáng)的父節(jié)點(diǎn)數(shù)據(jù)足夠執(zhí)行該任務(wù)，則不再獲取其他依賴節(jié)點(diǎn)數(shù)據(jù)，因此提升了任務(wù)的調(diào)度效率和容錯(cuò)性能。本文使用Hadoop平臺(tái)進(jìn)行任務(wù)調(diào)度實(shí)驗(yàn)，證明了算法能夠提高任務(wù)調(diào)度的整體效率，具有一定的理論和實(shí)際應(yīng)用價(jià)值。

2 Map/Reduce模型

2.1 Map/Reduce作業(yè)執(zhí)行過程

Map/Reduce[7]是面向大數(shù)據(jù)處理的并行計(jì)算模型和方法，最初的提出是為了解決搜索引擎中大規(guī)模網(wǎng)頁數(shù)據(jù)的并行化處理問題。其設(shè)計(jì)思想是對大數(shù)據(jù)并行處理分而治之，通過借鑒函數(shù)式程序設(shè)計(jì)語言Lisp的設(shè)計(jì)思想，將處理過程抽象為Map和Reduce兩個(gè)基本操作，即映射（Map）和規(guī)約（Reduce）。Map/Reduce執(zhí)行過程如圖1所示。

Map階段：首先分割函數(shù)把輸入的文件分割為一系列數(shù)據(jù)塊即子任務(wù)（Split），每個(gè)數(shù)據(jù)塊一般為64 MB，其存儲(chǔ)位置按照一定的策略進(jìn)行布局，每個(gè)數(shù)據(jù)塊都有備份且保存在不同的節(jié)點(diǎn)上。然后Master將N個(gè)任務(wù)分配給N個(gè)空閑的Map節(jié)點(diǎn)，使已分配任務(wù)的Map節(jié)點(diǎn)讀取Split的內(nèi)容并分析出Key/Value對，由Map函數(shù)產(chǎn)生中間Key/Value結(jié)果緩存在內(nèi)存中，并周期性地寫到本地磁盤，再由分割函數(shù)把它們寫入不同區(qū)域，并將結(jié)果傳輸給Reduce。

Reduce階段：Reduce worker根據(jù)Master節(jié)點(diǎn)傳輸?shù)闹虚g結(jié)果存儲(chǔ)位置讀取中間結(jié)果，通過排序使具有相同Key的內(nèi)容聚合在一起。由Reduce節(jié)點(diǎn)迭代排過序的中間結(jié)果產(chǎn)生唯一的中間Key，然后對遇到的每個(gè)唯一的中間Key，把Key和相關(guān)中間Value集傳遞給用戶自定義的Reduce函數(shù)。最后將Reduce函數(shù)的輸出結(jié)果添加到最終輸出的文件中。

2.2 傳統(tǒng)任務(wù)調(diào)度算法的不足及改進(jìn)

傳統(tǒng)的任務(wù)調(diào)度[8-10]過程可分為Map-Shuffle-Reduce階段（圖2），這3個(gè)階段產(chǎn)生的關(guān)鍵數(shù)據(jù)通常是以文件的形式存放在本地磁盤，雖然這樣存放增加了任務(wù)的本地性和安全性，但卻導(dǎo)致了大量的I/O操作，嚴(yán)重影響了任務(wù)處理的整體效率。例如Map節(jié)點(diǎn)在形成中間結(jié)果時(shí)，因?yàn)镾pill溢寫產(chǎn)生中間文件數(shù)量過多，進(jìn)而會(huì)導(dǎo)致后期處理文件的時(shí)間過長；又如Reduce端的Shuffle，當(dāng)Merge過程產(chǎn)生的數(shù)據(jù)量達(dá)到閾值時(shí)，會(huì)啟動(dòng)內(nèi)存到磁盤的Merge過程，將文件存入磁盤，之后執(zhí)行Reduce就需要將文件存入內(nèi)存，在此過程中涉及大量的I/O操作，嚴(yán)重影響任務(wù)處理的整體效率。

Fig.1 Map/Reduce execution process圖1 Map/Reduce執(zhí)行過程圖

傳統(tǒng)的任務(wù)調(diào)度模型[11]在處理具體作業(yè)時(shí)效率較低，因此在后期國內(nèi)外很多學(xué)者紛紛改進(jìn)了任務(wù)調(diào)度模型，如Yang等人提出了Map Reduce Merge模型[12]，通過在Map/Reduce執(zhí)行后添加一個(gè)Merge處理，使數(shù)據(jù)能夠快速均衡地合并輸出（圖3）。這樣做對于一些小的無約束任務(wù)處理具有極高的效率，但是對于大量且具有復(fù)雜關(guān)系的任務(wù)在處理效率上就會(huì)變得較低，并且沒有充分考慮I/O問題。

針對上述問題，本文提出了一種在輸入任務(wù)到達(dá)Map節(jié)點(diǎn)前將復(fù)雜任務(wù)進(jìn)行預(yù)處理的方法，先由Master節(jié)點(diǎn)將復(fù)雜任務(wù)的子任務(wù)表示為AOV（activity on vertex network）網(wǎng)并產(chǎn)生最佳拓?fù)渑判?，按排序結(jié)果由Master對每個(gè)子任務(wù)的執(zhí)行順序進(jìn)行標(biāo)記，并結(jié)合剪枝算法產(chǎn)生的最佳分配矩陣實(shí)現(xiàn)對復(fù)雜任務(wù)的合理調(diào)度。通過在任務(wù)調(diào)度Map端創(chuàng)建內(nèi)存資源池，收集Map處理過程中因?yàn)镾pill溢寫而產(chǎn)生的數(shù)據(jù)，在Map任務(wù)執(zhí)行結(jié)束后將所有結(jié)果匯總寫入中間結(jié)果集。此外在Reduce端增加Shuffle內(nèi)存緩存區(qū)大小并提高閾值，使Copy來的數(shù)據(jù)逐步在內(nèi)存中進(jìn)行Merge，直到數(shù)據(jù)Merge結(jié)束，將結(jié)果傳入Reduce輸出最終結(jié)果。通過這種方式改進(jìn)傳統(tǒng)數(shù)據(jù)處理模式，減少了內(nèi)存與磁盤以及磁盤與磁盤之間的數(shù)據(jù)交換，從而減少任務(wù)數(shù)據(jù)交換的處理時(shí)間。并且在整個(gè)Map/Reduce任務(wù)調(diào)度過程不用考慮復(fù)雜任務(wù)的相互制約以及內(nèi)存磁盤數(shù)據(jù)交換時(shí)間過長等問題，而在任務(wù)執(zhí)行失敗時(shí)，Master節(jié)點(diǎn)可直接根據(jù)最佳拓?fù)渑判蛞来位厮莸皆摴?jié)點(diǎn)的父節(jié)點(diǎn)，獲取所需數(shù)據(jù)，直到滿足任務(wù)調(diào)度需求為止，這樣減少了遍歷所有依賴關(guān)系節(jié)點(diǎn)所需的時(shí)間，從而提高任務(wù)調(diào)度的整體效率。

Fig.2 Map-Shuffle-Reduce process圖2 Map-Shuffle-Reduce過程

Fig.3 Map Reduce Merge chart圖3 Map Reduce Merge架構(gòu)圖

3 剪枝算法任務(wù)調(diào)度理論和步驟

3.1 剪枝算法理論

云環(huán)境下基于剪枝算法[13]的復(fù)雜任務(wù)調(diào)度算法，是一種采用剪枝策略逐步縮小調(diào)度規(guī)模，最終實(shí)現(xiàn)復(fù)雜任務(wù)合理調(diào)度的全局最優(yōu)算法。系統(tǒng)由Master節(jié)點(diǎn)將輸入的復(fù)雜任務(wù)依次分解為N個(gè)子任務(wù)，每個(gè)Map節(jié)點(diǎn)處理子任務(wù)的時(shí)間已知，即形成子任務(wù)和Map節(jié)點(diǎn)之間的n×n時(shí)間矩陣，依據(jù)該矩陣進(jìn)行任務(wù)分配。任務(wù)調(diào)度要求確定子任務(wù)和Map節(jié)點(diǎn)之間的分配調(diào)度方案以達(dá)到效率最優(yōu)時(shí)間最短的目的，且同時(shí)必須滿足兩個(gè)約束條件：每個(gè)任務(wù)都必須要執(zhí)行，并且一個(gè)Map節(jié)點(diǎn)只處理一個(gè)子任務(wù)。

記矩陣

為任務(wù)分配矩陣（初始值為0），元素mij的值為1或0，1為true，0為false。記矩陣

為任務(wù)分配的時(shí)間代價(jià)矩陣，xij表示第i個(gè)任務(wù)由第j個(gè)Map節(jié)點(diǎn)執(zhí)行所用的時(shí)間代價(jià)。因此以最高效率完成任務(wù)分配可以表示為：

函數(shù)約束條件為：

即一個(gè)Map節(jié)點(diǎn)完成一個(gè)任務(wù)；

即一個(gè)任務(wù)只能被一個(gè)Map節(jié)點(diǎn)完成。對于任務(wù)分配可能存在N種分配方案。設(shè)T為所有可能的任務(wù)分配集合，M∈T，其中

Ri→Mapj表示第i個(gè)任務(wù)被第j個(gè)節(jié)點(diǎn)處理；Fmin表示最優(yōu)目標(biāo)函數(shù)值；M′表示最優(yōu)的目標(biāo)分配方案。

3.2 相關(guān)定義

（1）F=FminM∈T(M,C)為全局最優(yōu)任務(wù)分配的目標(biāo)函數(shù)。

（2）T1={M|mrt=1}表示部分分配mrt=1已確定的可剪枝的局部最優(yōu)方案，T1∈T,Ri表示第i個(gè)任務(wù)。

其中，r為時(shí)間代價(jià)矩陣C中列相減的最小值對應(yīng)的行號(hào)；t為第一列的列號(hào)：

并且確保形成的局部任務(wù)分配矩陣函數(shù)值小于等于全局分配矩陣函數(shù)值：

以后M1中的0元素將不再進(jìn)行任務(wù)分配。以

對M進(jìn)行任務(wù)剔除。這樣就很明顯可以看出C變?yōu)橐粋€(gè)n-1階的任務(wù)分配問題，則任務(wù)的分配空間將縮小，依次進(jìn)行任務(wù)的剔除直到矩陣C只剩下一個(gè)元素為止。最后一個(gè)任務(wù)將直接進(jìn)行分配，可以得到任務(wù)分配的最佳方案，每次對任務(wù)進(jìn)行剔除的過程就是剪枝[14]。

（4）減法器（subtractor）：由Master節(jié)點(diǎn)對產(chǎn)生的任務(wù)分配矩陣按照式（6）進(jìn)行處理，是剪枝算法任務(wù)選取的依據(jù)。

（5）定義(T,→,A)為復(fù)雜任務(wù)，指輸入的任務(wù)具有一定依賴關(guān)系的任務(wù)組合，即在對用戶輸入的作業(yè)進(jìn)行分割后產(chǎn)生的子任務(wù)之間具有一定偏序關(guān)系。其中T=(t1,t2,…,tn)是一組具有依賴關(guān)系的子任務(wù)，→是T中子任務(wù)的一種依賴關(guān)系，用來表示子任務(wù)之間的優(yōu)先約束關(guān)系，如ti→tj,則表示ti必須在tj之前開始執(zhí)行。A表示任務(wù)的計(jì)算量，Ai＞0（1≤i≤n）為第i個(gè)任務(wù)的計(jì)算量。

3.3 復(fù)雜任務(wù)的預(yù)處理

云計(jì)算中，組成復(fù)雜任務(wù)的子任務(wù)之間存在一定的優(yōu)先約束關(guān)系，因此可以將復(fù)雜任務(wù)表示為一個(gè)AOV網(wǎng)V=(T,E),其中T表示網(wǎng)中節(jié)點(diǎn)的集合，E表示邊的集合，邊的權(quán)值表示節(jié)點(diǎn)之間的依賴關(guān)系，權(quán)值越大依賴關(guān)系越大，如權(quán)值為0，則兩個(gè)任務(wù)可并行處理。AOV網(wǎng)的約束關(guān)系表示為一個(gè)節(jié)點(diǎn)在沒有獲得其前序節(jié)點(diǎn)信息之前是不能執(zhí)行的。由Master節(jié)點(diǎn)將復(fù)雜任務(wù)轉(zhuǎn)換為AOV網(wǎng)并記錄任務(wù)的關(guān)聯(lián)關(guān)系及權(quán)值（圖4），再將AOV網(wǎng)用拓?fù)渑判蚍ㄞD(zhuǎn)換為最佳拓?fù)渑判颍╫ptimum topological-sort，OTS）（圖5）。其中AOV網(wǎng)中V與T的節(jié)點(diǎn)數(shù)相同，V中有足夠的邊能連接所有節(jié)點(diǎn)且沒有回路。最后由Master節(jié)點(diǎn)按照OTS順序，對每個(gè)子任務(wù)的優(yōu)先順序進(jìn)行標(biāo)記，實(shí)現(xiàn)剪枝前任務(wù)順序的初始化。

Fig.4 AOV net圖4 AOV網(wǎng)

Fig.5 Optimum topological-sort圖5 最佳拓?fù)渑判?/p>

3.4 剪枝算法復(fù)雜任務(wù)調(diào)度具體步驟

首先由Map/Reduce庫函數(shù)對用戶提交的任務(wù)請求進(jìn)行劃分，對生成的子任務(wù)進(jìn)行識(shí)別、分類，將具有依賴關(guān)系的子任務(wù)分為一類。簡單任務(wù)分為一類。其次將具有依賴關(guān)系的子任務(wù)進(jìn)行復(fù)雜任務(wù)預(yù)處理，使任務(wù)具有順序標(biāo)記，將具有依賴關(guān)系的子任務(wù)按照剪枝算法[15]進(jìn)行分配。實(shí)現(xiàn)復(fù)雜任務(wù)分配最優(yōu)、代價(jià)最小的調(diào)度過程如下：

（1）將所有任務(wù)看成簡單任務(wù)，由Master將任務(wù)分配矩陣M初始化，令所有元素為0代表為false，即不可執(zhí)行狀態(tài)mij=0,i,j=1,2,…,n。

（3）進(jìn)行剪枝，將選取的坐標(biāo)(r,t)對應(yīng)初始化矩陣M,將對應(yīng)元素值改為1，即為true，該元素對應(yīng)的行和列值不變：

則該坐標(biāo)對應(yīng)的行和列除本元素外全部剪掉，使矩陣規(guī)模減小1階，這就是一次剪枝過程。

（4）對于剪枝后的矩陣重復(fù)執(zhí)行（2）、（3）兩步，進(jìn)行n-1次迭代，使矩陣最后只有一個(gè)元素，該元素的狀態(tài)改為可執(zhí)行狀態(tài)，即為true，矩陣值為1。

（5）到此所有的復(fù)雜任務(wù)都進(jìn)行了最優(yōu)分配，每個(gè)節(jié)點(diǎn)對應(yīng)每個(gè)任務(wù)的剪枝過程結(jié)束，最后按照復(fù)雜任務(wù)預(yù)處理產(chǎn)生的OTS順序，結(jié)合最優(yōu)分配方案矩陣M′,由Master交給對應(yīng)的Map節(jié)點(diǎn)進(jìn)行處理。而簡單任務(wù)因?yàn)闆]有相互約束關(guān)系，直接由Master節(jié)點(diǎn)按照節(jié)點(diǎn)預(yù)測時(shí)間與節(jié)點(diǎn)計(jì)算能力的比值矩陣依次提交給Map節(jié)點(diǎn)執(zhí)行。

（6）至此復(fù)雜任務(wù)經(jīng)剪枝算法處理后產(chǎn)生了最優(yōu)的任務(wù)分配方案，并按此方案進(jìn)行最終任務(wù)調(diào)度。在Map端首先為每個(gè)處理機(jī)根據(jù)Map節(jié)點(diǎn)的數(shù)量與內(nèi)存緩沖區(qū)大小建立適當(dāng)?shù)膬?nèi)存資源池（大于單個(gè)Map節(jié)點(diǎn)內(nèi)存緩沖區(qū)大小，且可適當(dāng)調(diào)整）。然后將任務(wù)傳入Map節(jié)點(diǎn)進(jìn)行任務(wù)處理，當(dāng)產(chǎn)生的數(shù)據(jù)量達(dá)到Map節(jié)點(diǎn)內(nèi)存緩存區(qū)閾值時(shí)，將Map節(jié)點(diǎn)產(chǎn)生的鍵值對進(jìn)行Merge并傳入內(nèi)存資源池，直到所有Map任務(wù)處理結(jié)束，開啟進(jìn)程將數(shù)據(jù)寫入本地磁盤。

（7）在任務(wù)調(diào)度過程中由TaskTracker實(shí)時(shí)監(jiān)測每個(gè)任務(wù)的執(zhí)行狀態(tài)，如果任務(wù)執(zhí)行成功，則將每個(gè)Map節(jié)點(diǎn)數(shù)據(jù)緩存區(qū)數(shù)據(jù)存入資源池，并記錄在資源池的存儲(chǔ)位置，再將其恢復(fù)到初始狀態(tài)并請求下次執(zhí)行任務(wù)；如果任務(wù)處理失敗，保留當(dāng)前節(jié)點(diǎn)數(shù)據(jù)，并根據(jù)Master節(jié)點(diǎn)存儲(chǔ)的每個(gè)任務(wù)的OTS以及任務(wù)依賴關(guān)系的大小，依次回溯到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，獲取父節(jié)點(diǎn)在資源池中數(shù)據(jù)，直到在父節(jié)點(diǎn)中獲取的數(shù)據(jù)能夠滿足當(dāng)前任務(wù)的數(shù)據(jù)需求為止，結(jié)合當(dāng)前任務(wù)，按照節(jié)點(diǎn)處理能力重新分配任務(wù)節(jié)點(diǎn)進(jìn)行任務(wù)處理。

（8）在Map節(jié)點(diǎn)任務(wù)執(zhí)行完成后，向JobTracker發(fā)送任務(wù)完成指令，然后執(zhí)行Reduce前的Shuffle過程。此時(shí)Shuffle的緩存區(qū)容量遠(yuǎn)遠(yuǎn)大于Reduce節(jié)點(diǎn)的緩存區(qū)，將所有已完成的Map節(jié)點(diǎn)緩存區(qū)的數(shù)據(jù)直接拉取Copy到Shuffle緩存區(qū)，并將獲取的數(shù)據(jù)進(jìn)行Merge，直到獲取所有已完成的Map節(jié)點(diǎn)數(shù)據(jù)為止。此時(shí)調(diào)用進(jìn)程將產(chǎn)生數(shù)據(jù)存入磁盤進(jìn)行備份，同時(shí)將數(shù)據(jù)傳入Reduce端進(jìn)行最后的Reduce過程，并將最終產(chǎn)生的文件存入HDFS（Hadoop distributed file system），整個(gè)任務(wù)調(diào)度過程完成。

由剪枝步驟可知，該算法對于求解一個(gè)n×n矩陣的分配問題時(shí)，只需要進(jìn)行n-1次循環(huán)就可以求得最優(yōu)解。該過程解決了復(fù)雜任務(wù)的資源和順序最優(yōu)的處理問題，并且該過程減少了大量的數(shù)據(jù)I/O操作，使數(shù)據(jù)能夠在內(nèi)存中進(jìn)行交換，能夠在很大程度上提升程序的運(yùn)行效率。根據(jù)對Map/Reduce模型的分析并結(jié)合任務(wù)的處理過程，實(shí)現(xiàn)了對原有的任務(wù)調(diào)度的合理簡化，提高了任務(wù)調(diào)度的分配效率。

3.5 剪枝算法實(shí)例具體實(shí)現(xiàn)過程

對于復(fù)雜任務(wù)分解后每個(gè)Map節(jié)點(diǎn)處理子任務(wù)的具體時(shí)間與任務(wù)形成的矩陣為（以3×3矩陣為例）首先初始化矩陣為，然后采用減法器對矩陣C進(jìn)行取差得到矩陣C′=取C′最小值-5，得到r=1,t=1,根據(jù)(r,t)對M進(jìn)行剪枝，進(jìn)行第一次剪枝得到的結(jié)果為M=同時(shí)對C′同樣剪枝后取最小值為-4，得到r=2,t=2,進(jìn)行第二次剪枝得到的結(jié)果為M′=這樣取得的最優(yōu)任務(wù)分配方案為（1,4,1）。復(fù)雜任務(wù)的剪枝過程結(jié)束，一個(gè)三階任務(wù)分配兩次就可以得到最優(yōu)解。結(jié)合OTS排序結(jié)果使任務(wù)按順序執(zhí)行。這樣任務(wù)調(diào)度完成。

4 算法的驗(yàn)證與比較

為了驗(yàn)證本文算法的性能，將算法與公平份額調(diào)度算法[16]、遺傳算法[17]及GRAPHENE算法進(jìn)行對比驗(yàn)證。

實(shí)驗(yàn)環(huán)境：使用Hadoop1.2.1，由6個(gè)節(jié)點(diǎn)組成集群環(huán)境，其中1個(gè)為Master節(jié)點(diǎn)，其余5個(gè)為Slaver節(jié)點(diǎn)，集群之間是同構(gòu)的，具體的集群配置情況見表1。在實(shí)驗(yàn)中為集群配置了默認(rèn)的負(fù)載均衡策略，并且采用Ganglia來監(jiān)測集群狀態(tài)，主要是監(jiān)測內(nèi)存利用率。

Table 1 Cluster related configuration表1 集群相關(guān)配置情況

實(shí)驗(yàn)1驗(yàn)證使用抽樣法對Map節(jié)點(diǎn)處理任務(wù)的時(shí)間進(jìn)行估計(jì)是可行的。實(shí)驗(yàn)使用Hadoop自帶的基準(zhǔn)測試用例wordcount和terasort作為測試程序，并且為了確保任務(wù)處理時(shí)間的準(zhǔn)確性，將程序運(yùn)行4次并取平均值作為最終值。獨(dú)立運(yùn)行wordcount和terasort采用不同數(shù)目的Map任務(wù)進(jìn)行對比，結(jié)果如圖6所示。由圖可知，隨著Map節(jié)點(diǎn)的增加，任務(wù)的處理時(shí)間沒有明顯的變化，這說明在一個(gè)大作業(yè)中使用少量Map任務(wù)處理時(shí)間作為Map節(jié)點(diǎn)的處理時(shí)間進(jìn)行預(yù)測是合理的。復(fù)雜任務(wù)只是任務(wù)之間具有依賴關(guān)系，在獲得必要數(shù)據(jù)后對節(jié)點(diǎn)處理時(shí)間影響不大，因此同樣可以進(jìn)行預(yù)測。

Fig.6 Task independent execution time圖6 任務(wù)獨(dú)立執(zhí)行時(shí)間

實(shí)驗(yàn)2驗(yàn)證剪枝算法能夠提高任務(wù)調(diào)度整體效率和資源使用率。任務(wù)調(diào)度整體效率主要通過任務(wù)調(diào)度平均響應(yīng)時(shí)間、任務(wù)調(diào)度執(zhí)行時(shí)間以及不同算法的吞吐量進(jìn)行衡量；資源使用率主要通過內(nèi)存使用率進(jìn)行衡量。采用Hadoop自帶的terasort基準(zhǔn)測試程序進(jìn)行測試，選取100,150,…,350個(gè)任務(wù)進(jìn)行任務(wù)調(diào)度，4種不同算法的平均任務(wù)響應(yīng)時(shí)間以及任務(wù)調(diào)度執(zhí)行時(shí)間進(jìn)行對比驗(yàn)證，結(jié)果如圖7、圖8所示。

Fig.7 Task scheduling average response time圖7 任務(wù)調(diào)度平均響應(yīng)時(shí)間

Fig.8 Task scheduling execution time圖8 任務(wù)調(diào)度執(zhí)行時(shí)間

由圖7可知，隨著任務(wù)數(shù)量的增加，任務(wù)調(diào)度平均響應(yīng)時(shí)間都在增加，遺傳算法的任務(wù)響應(yīng)時(shí)間在任務(wù)較少時(shí)明顯低于公平調(diào)度算法，任務(wù)較大時(shí)任務(wù)執(zhí)行效率略有下降，但明顯高于本文算法。在GRAPHENE算法仿真實(shí)驗(yàn)中，因?yàn)闊o論任務(wù)數(shù)量的多少，都要先找出TroublesomeTasks，然后剩余部分被分為TroublesomeTasks的祖先、同輩和后代，最后再依據(jù)數(shù)據(jù)依賴關(guān)系進(jìn)行分配，所以在任務(wù)較少時(shí)任務(wù)調(diào)度的響應(yīng)時(shí)間相比本文算法相對較高，隨著任務(wù)數(shù)量的增加效率有很大提升。由圖8可知，隨著任務(wù)數(shù)量的增加，任務(wù)調(diào)度的執(zhí)行時(shí)間變化趨勢與任務(wù)調(diào)度響應(yīng)時(shí)間基本一致。

由圖9可知，剪枝算法的吞吐量在不同的數(shù)據(jù)流負(fù)載量下，均要高于其他的3種算法。其中公平調(diào)度算法以及遺傳算法的實(shí)驗(yàn)結(jié)果隨著數(shù)據(jù)流負(fù)載量的改變，沒有太大波動(dòng)，GRAPHENE算法隨著數(shù)據(jù)流負(fù)載量的增加逐步增大。當(dāng)流量負(fù)載參數(shù)SL（stream load）從2.0增加到2.4時(shí)，剪枝算法的平均吞吐量有很大的提升，說明剪枝算法在任務(wù)請求與吞吐量之間是一種正相關(guān)關(guān)系，這也證明了剪枝算法具有較強(qiáng)的任務(wù)處理能力。

Fig.9 Average throughput of different algorithms圖9 不同算法的平均吞吐量

在資源利用率方面，選取算法在任務(wù)調(diào)度過程中100～500 s內(nèi)的內(nèi)存使用率情況進(jìn)行對比（圖10），其中開始以及結(jié)束的內(nèi)存使用率數(shù)據(jù)沒有截取。從圖10中可以看出，隨著時(shí)間的增加因?yàn)槿蝿?wù)的大小以及內(nèi)存使用情況等因素的影響，使得內(nèi)存的使用率一直處在波動(dòng)狀態(tài)。因?yàn)镚RAPHENE算法是在內(nèi)存中處理任務(wù)，而剪枝算法在任務(wù)調(diào)度過程中減少了內(nèi)存與磁盤之間的數(shù)據(jù)交換，增加了數(shù)據(jù)在內(nèi)存中處理的過程，所以在任務(wù)調(diào)度過程中剪枝算法的內(nèi)存使用率與GRAPHENE算法的內(nèi)存使用率基本一致，都要高于公平調(diào)度算法以及遺傳算法。根據(jù)任務(wù)調(diào)度處理時(shí)間、平均吞吐量以及內(nèi)存使用率的對比可以得出，剪枝算法能夠提高任務(wù)調(diào)度的整體效率，提高資源的使用率。

Fig.10 Memory utilization圖10 內(nèi)存利用率

5 結(jié)論

本文主要論述了在Map/Reduce框架下的復(fù)雜任務(wù)的處理過程，通過Master節(jié)點(diǎn)將具有依賴關(guān)系的復(fù)雜任務(wù)的子任務(wù)轉(zhuǎn)化為AOV網(wǎng)，并按照依賴關(guān)系的大小產(chǎn)生最佳拓?fù)渑判?，?shí)現(xiàn)對子任務(wù)處理順序的預(yù)處理。根據(jù)節(jié)點(diǎn)處理任務(wù)的時(shí)間建立任務(wù)與節(jié)點(diǎn)的時(shí)間度量矩陣，使用剪枝算法進(jìn)行任務(wù)分配，得到全局最優(yōu)分配方案，并結(jié)合OTS對任務(wù)進(jìn)行調(diào)度。任務(wù)調(diào)度過程中，采用增加內(nèi)存資源池與增大Shuffle緩存區(qū)大小等方法，使數(shù)據(jù)在內(nèi)存中進(jìn)行處理，減少了內(nèi)存與磁盤以及磁盤與磁盤之間的數(shù)據(jù)交換，從而解決了處理時(shí)間過長、任務(wù)調(diào)度效率低的問題，提高了任務(wù)調(diào)度的效率。使用Hadoop平臺(tái)分別從任務(wù)調(diào)度效率與資源使用率角度，將剪枝算法與公平調(diào)度算法、遺傳算法以及GRAPHENE算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明剪枝算法能明顯提高復(fù)雜任務(wù)調(diào)度整體效率，具有一定的理論指導(dǎo)意義。

[1]Vaquero L M,Rodero-Merino L,Caceres J,et al.A break in the cloud:towards a cloud definition[J].ACM SIGCOMM Computer Communication Review,2009,39(1):50-55.

[2]Armbrust M,Fox A.Above the clouds:a Berkeley view of cloud computing,UCB/EECS-2009-28[R].Berkeley:University of California,2009.

[3]Barroso LA,Dean J,H?lzle U.Web search for a planet:the Google cluster architecture[J].IEEE Micro,2003,32(2):22-28.

[4]Selvarani S,Sadhasivam G S.Improved cost-based algorithm for task scheduling in cloud computing[C]//Proceedings of the 2010 International Conference on Computational Intelligence and Computing Research,Coimbatore,Dec 28-29,2010.Piscataway:IEEE,2010:620-624.

[5]Karthick A V,Ramaraj E,Subramanian R G.An efficient multi queue job scheduling for cloud computing[C]//Proceedings of the 2014 World Congress on Computing and Communication Technologie,Tiruchirappalli,Feb 27-Mar 1,2014.Washington:IEEE Computer Society,2014:164-166.

[6]Dong Xicheng,Wang Ying,Liao Huaming.Scheduling mixed real-time and non-real-time applications in MapReduce environment[C]//Proceedings of the 17th International Conference on Parallel and Distributed Systems,Tainan,China,Dec 7-9,2011.Washington:IEEE Computer Society,2011:9-16.

[7]Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communication of the ACM,2008,51(1):107-113.

[8]Shi Hengliang.Research of job scheduling on cloud computing[D].Nanjing:Nanjing University of Science and Technology,2012.

[9]Mathew T,Sekaran K C,Jose J.Study and analysis of various task scheduling algorithms in the cloud computing envi-ronment[C]//Proceedings of the 3rd International Conference on Advances in Computing,Communications and Informatics,Delhi,Sep 24-27,2014.Piscataway:IEEE,2014:658-664.

[10]Lu Lu,Shi Xuanhua,Jin Hai,et al.Morpho:a decoupled MapReduce framework for elastic cloud computing[J].Future Generation Computer Systems,2014,36:80-90.

[11]Zarei M H,Shirsavar MA,Yazdani N.AQoS-aware task allocation model for mobile cloud computing[C]//Proceedings of the 2nd International Conference on Web Research,Tehran,Apr 27-28,2016.Piscataway:IEEE,2016:43-47.

[12]Yang H C,Dasdan A,Hsiao R L,et al.Map-reduce-merge:simplified relational data processing on large clusters[C]//Proceedings of the 2007 International Conference on Management of Data,Beijing,Jun 12-14,2007.New York:ACM,2007:1029-1040.

[13]Rong H J,Ong Y S,Tan A H,et al.A fast pruned-extreme learning machine for classification problem[J].Neurocomputing,2008,72(1/3):359-366.

[14]Ma Yunhong,Jing Zhe,Zhou Deyun.A faster pruning optimization algorithm for task assignment[J].Journal of Nothwestern Polytechnical University,2013,31(1):40-43.

[15]Zheng Wei,Ma Nan.An improved post-pruning algorithm for decision tree[J].Computer&Digital Engineering,2015,43(6):960-966.

[16]Ma Xiaoyan,Hong Jue.A multi-resource fair scheduler of Hadoop[J].Journal of Integration Technology,2012,1(3):66-71.

[17]Hu Yanhua,Tang Xinlai.A task scheduling algorithm based on improved genetic algorithm in cloud computing environment[J].Computer Technology and Development,2016,26(10):137-141.

附中文參考文獻(xiàn)：

[8]史恒亮.云計(jì)算任務(wù)調(diào)度研究[D].南京:南京理工大學(xué),2012.

[14]馬云紅,井哲,周德云.一種任務(wù)分配問題的快速剪枝優(yōu)化算法[J].西北工業(yè)大學(xué)學(xué)報(bào),2013,31(1):40-43.

[15]鄭偉,馬楠.一種改進(jìn)的決策樹后剪枝算法[J].計(jì)算機(jī)與數(shù)字工程,2015,43(6):960-966.

[16]馬肖燕,洪爵.多資源公平調(diào)度器在Hadoop中的實(shí)現(xiàn)[J].集成技術(shù),2012,1(3):66-71.

[17]胡艷華,唐新來.基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(10):137-141.