最小化多MapReduce任務(wù)總完工時(shí)間的分析模型及其應(yīng)用＊

田文洪，陳 瑜，王心陽(yáng)，薛瑞尼，趙 勇

（1.電子科技大學(xué)信息與軟件工程學(xué)院，四川 成都 610054；2.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731）

1 引言

在云計(jì)算和大數(shù)據(jù)處理時(shí)代，MapReduce的開源實(shí)現(xiàn)Hadoop以其通用性和方便實(shí)用等特征得到了迄今為止最為廣泛的應(yīng)用。在云計(jì)算研究中，MapReduce環(huán)境的作業(yè)調(diào)度帶來(lái)了一個(gè)新的課題和挑戰(zhàn)，引起了越來(lái)越多的重視。最初，Hadoop默認(rèn)的FIFO（先入先出）調(diào)度器是專為周期性執(zhí)行大規(guī)模批量作業(yè)而設(shè)計(jì)的。隨著MapReduce集群的用戶數(shù)量的增加，計(jì)算能力調(diào)度器［1］和Hadoop公平調(diào)度器HFS（Hadoop Fair Scheduling）［2］的出現(xiàn)，提供了更高效的集群共享方式。業(yè)界已有少數(shù)研究Hadoop的調(diào)度原型的研究小組，旨在優(yōu)化一些明確給定的調(diào)度標(biāo)準(zhǔn)，例如FLEX［3］、ARIA［4］。MapReduce的模擬器SimMR［5］也被開發(fā)出用于模擬不同的工作量下MapReduce的性能。但是，正如文獻(xiàn)［6］中指出的，現(xiàn)有的調(diào)度器還不能提供對(duì)最小化作業(yè)集完工時(shí)間的支持。Tian等［7］針對(duì)離線多任務(wù)調(diào)度提出了幾種高效的最小化總完工時(shí)間的調(diào)度算法并進(jìn)行了對(duì)比分析，文獻(xiàn)［8］針對(duì)在線多任務(wù)節(jié)能調(diào)度提出了一種高效動(dòng)態(tài)劃分算法，以最小化總完工時(shí)間。Tian等［9］提出了一種云數(shù)據(jù)中心動(dòng)態(tài)負(fù)載均衡調(diào)度算法，該算法同時(shí)考慮CPU內(nèi)存和網(wǎng)絡(luò)帶寬的利用率。

Herodotou H等［10］提出了一種工作流－感知調(diào)度器，通過(guò)把數(shù)據(jù)位置與任務(wù)調(diào)度相結(jié)合，優(yōu)化工作流完工時(shí)間。Moseley B等［11］將MapReduce調(diào)度轉(zhuǎn)化為經(jīng)典的具有相同機(jī)器的兩階段工作車間作業(yè)問(wèn)題，在離線情況下，他們提出了一個(gè)對(duì)于最小化總完成時(shí)間近似比為12的近似算法。文獻(xiàn)［6，12］提出了一種通過(guò)在Hadoop集群中創(chuàng)建兩個(gè)資源池（pools）的啟發(fā)式算法—BalancedPools算法，以負(fù)載均衡并最小化任務(wù)的總完工時(shí)間。該算法當(dāng)任務(wù)請(qǐng)求的資源低于系統(tǒng)可提供的最大資源時(shí)不進(jìn)行動(dòng)態(tài)資源分配調(diào)整，而是運(yùn)行多個(gè)任務(wù)共享系統(tǒng)資源，因而不滿足經(jīng)典Johnson算法的條件。經(jīng)典Johnson算法［13］要求一個(gè)物品必須通過(guò)一個(gè)生產(chǎn)階段（或者一個(gè)機(jī)器），然后通過(guò)第二個(gè)階段，每個(gè)階段只有一個(gè)機(jī)器，一個(gè)機(jī)器上任何時(shí)刻一次最多處理一個(gè)物品，在此種情況下可以利用經(jīng)典Johnson算法安排出一批任務(wù)的執(zhí)行順序，并計(jì)算出最小總完工時(shí)間。

本文總結(jié)已有研究成果的優(yōu)缺點(diǎn)，旨在將MapReduce兩階段與經(jīng)典Johnson算法的兩階段條件完全匹配，從而利用Johnson算法計(jì)算出一批任務(wù)的最小總完工時(shí)間，并應(yīng)用于集群節(jié)能、負(fù)載均衡等問(wèn)題。

2 問(wèn)題描述與建模

定義1 MapReduce時(shí)隙（MapReduce slots），是指在給定的一個(gè)Hadoop集群中，其總的MapReduce資源時(shí)隙，本文與文獻(xiàn)［5］一樣，設(shè)定一個(gè)Hadoop集群節(jié)點(diǎn)同時(shí)具有一個(gè)MapReduce slot，例如一個(gè)Hadoop集群具有60個(gè)節(jié)點(diǎn)，可以表示其總的MapReduce slots為60×60。當(dāng)然這也可以依據(jù)具體情況動(dòng)態(tài)設(shè)定。

定義2 一個(gè)作業(yè)在一個(gè)給定Hadoop集群中的執(zhí)行次數(shù)，用waves來(lái)表示，例如一個(gè)任務(wù)請(qǐng)求使用30個(gè)Map slots和30個(gè)Reduce slots，在一個(gè)具有20×20MapReduce slots的Hadoop集群，其執(zhí)行Map階段的waves為2，其執(zhí)行Reduce階段的waves為2，其它的類推。圖1展示了一個(gè)MapReduce wordcount運(yùn)行的例子。

Figure 1 An execution example in 20×20MapReduce slots圖1 一個(gè)在20×20MapReduce slots執(zhí)行的例子

定義3 一批任務(wù)在Hadoop集群中的總完工時(shí)間（Total Makespan），是指按照一定的順序執(zhí)行完該批任務(wù)的所有Map／Reduce階段從第一個(gè)任務(wù)Map階段開始到最后一個(gè)任務(wù)Reduce結(jié)束所花的總時(shí)間。

文獻(xiàn)［4，6，12］介紹了一個(gè)Map／Reduce性能模型。該模型可通過(guò)輸入數(shù)據(jù)大小和分配資源作為函數(shù)的參數(shù)，預(yù)測(cè)Map和Reduce階段的完工時(shí)間。考慮一個(gè)由n個(gè)任務(wù)組成的作業(yè)，在k個(gè)MapReduce的slots中執(zhí)行的Hadoop環(huán)境，任務(wù)安排在slots中執(zhí)行時(shí)采用離線貪心算法：每次選擇完工時(shí)間最早的任務(wù)安排。設(shè)avg和max分別為n個(gè)任務(wù)的平均時(shí)間和最大時(shí)間，則在貪心算法下，作業(yè)的總完工時(shí)間最少為n×avg／k，最多為（n－1）×avg／k＋max，每個(gè)作業(yè)由特定數(shù)量的Map和Reduce任務(wù)組成。該作業(yè)的執(zhí)行時(shí)間和具體的執(zhí)行依賴于分配所得的資源量（Map slots和Reduce slots）。我們采用文獻(xiàn)［6］中的一個(gè)簡(jiǎn)單抽象，將一個(gè)MapReduce作業(yè)Ji的Map和Reduce過(guò)程定義為mi和ri，即Ji＝（mi，ri），對(duì)于任何兩個(gè)獨(dú)立的MapReduce作業(yè)J1和J2，這兩個(gè)作業(yè)之間沒有數(shù)據(jù)依賴關(guān)系。只有當(dāng)?shù)谝粋€(gè)作業(yè)完成Map階段并開始Reduce階段的處理時(shí)，第二個(gè)作業(yè)才可以開始使用釋放的資源來(lái)執(zhí)行Map，參見圖3。下一個(gè)作業(yè)的Map階段可能會(huì)與前一個(gè)作業(yè)的Reduce階段在時(shí)間上“重疊”（Overlapped）。我們進(jìn)一步考慮以下問(wèn)題：設(shè)J＝｛J1，J2，…，Jn｝是一個(gè)n個(gè)數(shù)據(jù)相互獨(dú)立的MapReduce作業(yè)。Ji需要Ni×Nr個(gè)MapReduce slots，Map和Reduce的時(shí)間分別是（mi，ri），系統(tǒng)調(diào)度器依據(jù)可用資源可以改變一個(gè)作業(yè)的MapReduce slots分配。假設(shè)T是所有n個(gè)作業(yè)的總完工時(shí)間，我們的目標(biāo)是對(duì)于Ji∈J確定一個(gè)順序，使得所有作業(yè)的總完工時(shí)間最小。我們假設(shè)一個(gè)作業(yè)Ji，其Map結(jié)束時(shí)間和Reduce開始時(shí)間分別為，實(shí)際分配的MapReduce slots為Pi×Pi，而Hadoop集群中最大的MapReduce slots為P×P。因此，最小化總完工時(shí)間問(wèn)題可以表示如下：

其中，不等式（2）由可用資源限定，實(shí)際分配的資源（Pi）不能超過(guò)系統(tǒng)可用資源（P）；不等式（3）由單個(gè)作業(yè)Map和Reduce過(guò)程不能重疊限定，對(duì)于任何一個(gè)作業(yè)，其Reduce開始時(shí)間不應(yīng)比其Map的完工時(shí)間早。

3 最小化總完工時(shí)間問(wèn)題解決方案：更新的經(jīng)典Johnson算法

經(jīng)典Johnson算法［13］描述有n個(gè)物品必須通過(guò)一個(gè)生產(chǎn)階段（或者一個(gè)機(jī)器），然后通過(guò)第二個(gè)階段，每個(gè)階段只有一個(gè)機(jī)器，一個(gè)機(jī)器上任何時(shí)刻一次最多處理一個(gè)物品。為了讓其能夠用于MapReduce模型，我們將Map和Reduce階段的資源看做一個(gè)整體，來(lái)表示MapReduce的slots資源。然后我們可以使用Johnson算法，考慮一個(gè)n個(gè)作業(yè)的集合，每個(gè)作業(yè)使用一個(gè)用Map和Reduce時(shí)間組成的數(shù)據(jù)（mi，ri）表示，每一個(gè)作業(yè)Ji＝（mi，ri）的屬性Ai定義如下：

Ai的第一個(gè)參數(shù)稱為持續(xù)時(shí)間，表示為A1；第二個(gè)稱為階段類型（Map或Reduce），表示為A2。注意到如果當(dāng)所有的ri＝0時(shí)，Johnson算法簡(jiǎn)化為短作業(yè)優(yōu)先算法（SPT），該算法是已知的可用于找到所有作業(yè)最小總完成時(shí)間的最優(yōu)值的方法。MapReduce改進(jìn)的Johnson算法的偽代碼如下所示：

算法1 改進(jìn)的Johnson算法

輸入 所有作業(yè)的Map和Reduce階段的持續(xù)時(shí)間mi、ri，Hadoop集群的機(jī)器數(shù)量，系統(tǒng)Map／Reduce slots總數(shù)P。

輸出 所有調(diào)度任務(wù)的安排順序和這批任務(wù)總的完工時(shí)間。

步驟1 將所有任務(wù)的Map和Reduce階段的持續(xù)時(shí)間列出；

步驟2 對(duì)于所有持續(xù)時(shí)間；

步驟3 找出其最短者；

步驟4 若出現(xiàn)多個(gè)最短者相同的情況，則按任務(wù)編號(hào)順序處理。

步驟5 若Map階段與Reduce階段持續(xù)時(shí)間相同，則優(yōu)先考慮為Map類型；

步驟6 若任務(wù)類型為Map型，則置于第一個(gè)位置處理；

步驟7 否則任務(wù)類型為Reduce型，則置于最后一個(gè)位置處理；

步驟8 移除已經(jīng)分配的任務(wù)；

步驟9 對(duì)剩余的任務(wù)重復(fù)步驟3～步驟8，直到所有任務(wù)分配完。

首先將在作業(yè)J中的n個(gè)作業(yè)按照下列方式排 序：Ji在Ji＋1之 前 當(dāng) 且 僅 當(dāng)min（mi，ri）≤min（mi＋1，ri＋1）。它尋 找 的 是 持 續(xù) 時(shí) 間 最 短 的 作業(yè)，如果階段類型Ai是m，它代表Map類型，則Ji被放置在調(diào)度表頭，否則Ji被放置在尾部。然后移除Ji，對(duì)剩下的作業(yè)采取同樣操作直到所有作業(yè)分配完。Johnson算法的時(shí)間復(fù)雜度主要在于排序n個(gè)任務(wù)，因而是O（nlogn）。

定理1 在兩階段生產(chǎn)系統(tǒng)中，如果所有作業(yè)經(jīng)歷相同階段，且任何時(shí)刻任何一個(gè)階段的資源只能由一個(gè)任務(wù)占用，則Johnson算法可以獲得系統(tǒng)總完工時(shí)間的最小值。

該定理的詳細(xì)證明參考文獻(xiàn)［13］。

使用Johnson算法我們可以通過(guò)如下方式計(jì)算出系統(tǒng)最小總完工時(shí)間?？紤]有Map和Reduce階段的n個(gè)任務(wù)，設(shè)在給定的有P個(gè)節(jié)點(diǎn)的Hadoop集群中，mi為第i個(gè)任務(wù)Map階段持續(xù)時(shí)間，ri為Reduce階段的持續(xù)時(shí)間，則系統(tǒng)的最小總完工時(shí)間為：

觀察結(jié)果1 如果每個(gè)工作能夠完全利用Map或者Reduce過(guò)程中的slots，那么MapReduce作業(yè)的處理可與經(jīng)典Johnson算法的兩階段生產(chǎn)系統(tǒng)完全匹配，則Johnson算法就可用來(lái)尋找所有MapReduce作業(yè)的最小總完工時(shí)間的最優(yōu)解。

例1 在文獻(xiàn)［2］中給定的五個(gè)MapReduce作業(yè)例子，我們重新繪制如圖2所示。

Figure 2 Example of five MapReduce jobs圖2 五個(gè)MapReduce作業(yè)例子

圖2a為五個(gè)作業(yè)Map和Reduce階段的持續(xù)時(shí)間列表，圖2b為五個(gè)作業(yè)使用Johnson算法由排序后的執(zhí)行順序。根據(jù)Johnson算法，最優(yōu)順序?yàn)棣模剑?，5，1，3，4），由式（6）可計(jì)算出，此序列的總延遲時(shí)間為4個(gè)單位時(shí)間，總完工時(shí)間是47個(gè)單位時(shí)間（由式（5）計(jì)算出）。如果將此序列翻轉(zhuǎn)，即（4，3，1，5，2），則得到最壞的結(jié)果（上限），為78個(gè)單位時(shí)間。

觀察結(jié)果2 假設(shè)當(dāng)作業(yè)要求分配MapReduce的slots比系統(tǒng)可用的MapReduce的slots少，系統(tǒng)調(diào)度器不給MapReduce增加slots；同時(shí)，每一個(gè)階段若允許兩個(gè)或兩個(gè)以上的作業(yè)共享slots，例如文獻(xiàn)［6］所介紹的方法則違反了Johnson算法要求任何時(shí)刻在機(jī)器上只能有一個(gè)作業(yè)在執(zhí)行的條件。

圖3和圖4分別給出了一個(gè)不滿足和滿足Johnson算法條件的任務(wù)執(zhí)行情況。

例2 讓作業(yè)J1、J2和J5請(qǐng)求30個(gè)Map和30個(gè)Reduce slots任務(wù)，作業(yè)J3和J4請(qǐng)求20個(gè)Map和20個(gè)Reduce slots任務(wù)。圖3展示了這五個(gè)MapReduce作業(yè)依據(jù)Johnson算法的執(zhí)行順序δ＝（J2，J5，J1，J4，J3）的 執(zhí) 行 過(guò) 程。當(dāng) 可 用 的MapReduce的slots的數(shù)量比請(qǐng)求的MapReduce slots的數(shù)量大的時(shí)候，如果我們不把作業(yè)分為兩個(gè)池，同時(shí)不增加slots的數(shù)量為系統(tǒng)最大可用值（如J3和J4需要20×20個(gè)slots而系統(tǒng)作為整體有30×30個(gè)slots），如圖3所示，使用Johnson算法，調(diào)度總共的完工時(shí)間（Makespan）是44個(gè)單位，這比通過(guò)文獻(xiàn)［6］中兩個(gè)池的方法得到的結(jié)果（40）大了10%。注意到，J4用20×20個(gè)slots，Map和Reduce階段分別有6和30個(gè)單位的持續(xù)時(shí)間；J3的Map階段在時(shí)間段［7，13］使用10個(gè)Map slots與J4共享系統(tǒng)資源，在時(shí)間段［13，40］使用20個(gè)Map slots繼續(xù)執(zhí)行，然后J3的Reduce階段在時(shí)刻40開始，在時(shí)刻44結(jié)束。

觀察結(jié)果3 作業(yè)的階段持續(xù)時(shí)間取決于分配資源的數(shù)量（Map和Reduce的slots）。若系統(tǒng)調(diào)度分配MapReduce slots的數(shù)量不同，作業(yè)運(yùn)行的總時(shí)間就可能不同。

Figure 3 Execution result of five MapReduce jobs（not using max available slots）圖3 五個(gè)MapReduce作業(yè)在一個(gè)集群中執(zhí)行

例3 考慮在文獻(xiàn)［6］中的情景2：作業(yè)J1、J2和J5申請(qǐng)30個(gè)Map和30個(gè)Reduce slots，作業(yè)J3和J4申請(qǐng)20個(gè)Map和20個(gè)Reduce slots，且J3＝（m3，r3）＝（30，4），J4＝（6，30）。我們?cè)趫D3中展示了這五個(gè)MapReduce作業(yè)根據(jù)生成的Johnson調(diào)度順序δ＝（J2，J5，J1，J4，J3）的執(zhí)行過(guò)程。對(duì)于作業(yè)J3和J4，文獻(xiàn)［6］假設(shè)即使系統(tǒng)中有30×30個(gè)MapReduce slots可用的情況下，他們只用了20×20個(gè)MapReduce slots。然而，如果我們?cè)试S作業(yè)可以使用系統(tǒng)中所有可用的MapReduce slots來(lái)執(zhí)行（這在Hadoop中很容易實(shí)現(xiàn)，如將大的輸入文件基于可用的MapReduce slots數(shù)量進(jìn)行分片），得出的結(jié)果和文獻(xiàn)［1］中得出的很不相同。使用在文獻(xiàn)［1］的情景2中的同樣示例，則現(xiàn)在作業(yè)J3和J4可以使用所有可用的30×30個(gè)MapReduce slots，那么J3將有Map和Reduce的持續(xù)時(shí)間分別為（20，8／3），J4將有Map和Reduce的持續(xù)時(shí)間分別為（4，20），它們都比使用20×20個(gè)MapReduce slots用時(shí)少，如圖4所示的執(zhí)行結(jié)果。因此，總的Makespan將為其中X1＝1。這個(gè)結(jié)果比通過(guò)兩個(gè)池［2］所得結(jié)果要小約12%。

Figure 4 Execution result of five MapReduce jobs（using max available slots）圖4 五個(gè)MapReduce作業(yè)在一個(gè)集群中執(zhí)行（利用系統(tǒng)最大資源滿足經(jīng)典Johnson算法條件）

引理1 如果作業(yè)請(qǐng)求的MapReduceslots數(shù)量比系統(tǒng)中總的可用MapReduceslot數(shù)量多或少，調(diào)度系統(tǒng)可以減少或者增加分配給作業(yè)的MapReduceslots數(shù)量，以最大限度利用Hadoop資源，從而最小化系統(tǒng)總完工時(shí)間。

證明 這一動(dòng)態(tài)調(diào)整滿足了經(jīng)典Johnson算法兩個(gè)階段的執(zhí)行條件，即任何時(shí)刻任何一個(gè)階段的資源只能由一個(gè)任務(wù)占用，所以我們可以使用經(jīng)典Johnson算法來(lái)安排任務(wù)執(zhí)行順序，并使用公式（5）～公式（6）計(jì)算出系統(tǒng)最小總完工時(shí)間?！?/p>

算法2依據(jù)引理1的動(dòng)態(tài)分配系統(tǒng)MapReduce slots資源方法的偽代碼如下所示：

算法2 動(dòng)態(tài)MapReduce slots分配方法

輸入 所有作業(yè)的Map和Reduce階段的持續(xù)時(shí)間mi，ri，Hadoop集群的機(jī)器數(shù)量，系統(tǒng)MapReduce slots總數(shù)P。

輸出 所有作業(yè)實(shí)際分配的MapReduce slots。

步驟1 將所有任務(wù)的Map和Reduce階段的持續(xù)時(shí)間列出；

步驟2 對(duì)于所有作業(yè)請(qǐng)求的MapReduce slots；

步驟3 若作業(yè)請(qǐng)求的slots與系統(tǒng)可分配的最大slots相同，則分配給其最大slots；

步驟4 若作業(yè)請(qǐng)求的slots大于系統(tǒng)可分配的最大slots，則按照系統(tǒng)可分配的最大slots分配（將大的輸入文件基于可用的MapReduce slots數(shù)量進(jìn)行分片后執(zhí)行多個(gè)waves），并重新計(jì)算其各階段的持續(xù)時(shí)間；

步驟5 若作業(yè)請(qǐng)求的slots小于系統(tǒng)可分配的最大slots，則按照系統(tǒng)可分配的最大slots分配（將大的輸入文件基于可用的MapReduce slots數(shù)量進(jìn)行分片），并重新計(jì)算其各階段的持續(xù)時(shí)間；

步驟6 將新的結(jié)果提交調(diào)度系統(tǒng)使用。

4 最小化多MapReduce任務(wù)總完工時(shí)間應(yīng)用于Hadoop集群節(jié)能

利用前述結(jié)果，可以在調(diào)度系統(tǒng)設(shè)計(jì)時(shí)優(yōu)化多任務(wù)的總完工時(shí)間，從而提高響應(yīng)速度和服務(wù)質(zhì)量。利用前述結(jié)果和能耗模型，我們還可以建立集群總能耗與多任務(wù)總完工時(shí)間的關(guān)系，從而進(jìn)行能耗優(yōu)化設(shè)計(jì)?？紤]CPU為主的能耗模型，一個(gè)節(jié)點(diǎn)一段時(shí)間內(nèi)的能耗可以表示如下［14，15］：

本文考慮Hadoop集群節(jié)點(diǎn)同構(gòu)的情況，其中Pi為Hadoop集群節(jié)點(diǎn)i（一個(gè)服務(wù)器）的功率，Pmin是節(jié)點(diǎn)的利用率為0時(shí)的功率，Pmax是節(jié)點(diǎn)利用率為100%時(shí)的功率，Ui為節(jié)點(diǎn)CPU的平均利用率。

節(jié)點(diǎn)i在一段時(shí)間［t0，t1］內(nèi)的總能耗Ei可表示為：

其中，Pi（Ui（t））為功率函數(shù)；而Ui（t）為CPU在時(shí)刻t的利用率，若使用一段時(shí)間Ti（＝t1－t0）內(nèi)的平均利用率，則公式（8）可以簡(jiǎn)化為：

則一段時(shí)間內(nèi)的Hadoop集群的總能耗可表示為：

其中，m為Hadoop集群中的節(jié)點(diǎn)數(shù)。

定理2 對(duì)于給定的一組作業(yè)，Hadoop集群的總能耗是由其運(yùn)行總時(shí)間（總完工時(shí)間）決定的。

證明 設(shè)置α＝Pmin，β＝Pmax－Pmin，T＝∑Ti，L是Hadoop集群的總負(fù)載，由公式（10）我們可以得到：

對(duì)于給定的一組任務(wù)，集群的總工作負(fù)載L是固定的，α和β都是常數(shù)，那么集群的總能耗是由其總完工時(shí)間（總運(yùn)行時(shí)間）確定的。 □

定理2告訴我們，在設(shè)計(jì)多MapReduce任務(wù)時(shí)，為了降低能耗，應(yīng)盡可能降低所有任務(wù)的總完工時(shí)間，這正是本文提出分析模型的一個(gè)應(yīng)用出發(fā)點(diǎn)。

5 資源池負(fù)載均衡問(wèn)題的優(yōu)化解決方案

在文獻(xiàn)［6，12］中，作者提出了一個(gè)叫做BalancedPools的啟發(fā)算法。這個(gè)算法迭代地將任務(wù)分配到兩個(gè)池中，然后嘗試對(duì)每一個(gè)池進(jìn)行適當(dāng)?shù)馁Y源分配，以保證這些池的Makespan是均衡的。在每一個(gè)池中應(yīng)用Johnson算法進(jìn)行作業(yè)調(diào)度，此時(shí)Map和Reduce階段的持續(xù)時(shí)間被估算出來(lái)。一個(gè)池中的Makespan是通過(guò)模擬器SimMR［5］進(jìn)行預(yù)估的，BalancedPools算法的時(shí)間復(fù)雜度為Ο（n2lognlogm），其中，n是任務(wù)總數(shù)，m是在Hadoop中的節(jié)點(diǎn)數(shù)［6，12］。文獻(xiàn)［6］指出了在系統(tǒng)可分配slots資源大于作業(yè)請(qǐng)求的slots資源進(jìn)行作業(yè)共享資源時(shí)，該問(wèn)題是NP－h(huán)ard問(wèn)題（關(guān)于NPhard問(wèn)題參考文獻(xiàn)［16］）。

定理3 使用引理1，對(duì)于兩個(gè)池中的MapReduce作業(yè)集，平衡系統(tǒng)的MapReduce slots以實(shí)現(xiàn)兩個(gè)池的Makespan平衡的問(wèn)題不是NPhard，而是可在線性時(shí)間內(nèi)解決的。

證明 這是因?yàn)榘凑找?，分配MapReduce slots可以基于系統(tǒng)中可用的MapReduce slots進(jìn)行動(dòng)態(tài)調(diào)整。假設(shè)在給定的Hadoop集群中有P×P個(gè)MapReduce slots，所有請(qǐng)求（作業(yè)）可以根據(jù)池A和池B進(jìn)行分組，每一個(gè)請(qǐng)求MapReduce slots（RA，RB），持續(xù)時(shí)間為（TA，TB）。注意到TA和TB可以通過(guò)Johnson算法很輕易地計(jì)算出來(lái)。假設(shè)整個(gè)Hadoop集群分為P1和P2slots兩個(gè)池，以達(dá)到負(fù)載均衡。在理想負(fù)載均衡條件下，對(duì)于池A和池B中平衡后的Makespan（完工時(shí)間），我們可建立以下關(guān)系：

結(jié)合式（12）和式（13），我們可以解出P1和P2：

其中round（）是就近取整函數(shù)，根據(jù)定義round（X）可以取得離X最近的整數(shù)。這是兩組作業(yè)分配給兩個(gè)池的最優(yōu)化結(jié)果。注意到分配資源的數(shù)量（P1，P2）是基于負(fù)載均衡的，所以結(jié)果可能與它們請(qǐng)求的MapReduce slots數(shù)量不同?！?/p>

例4 假設(shè)有兩組請(qǐng)求，使用與例2相同的示例，我們知道R1＝30，R2＝20，P＝30。對(duì)于每一個(gè)池（組），我們通過(guò)使用公式（5）計(jì)算出其總的完工時(shí)間，分別為T1＝14，T2＝40。通過(guò)式（12）和式（13），可以得到P1＝10，P2＝20，池1和池2的Makespan分別是39和40個(gè)單位時(shí)間。這與文獻(xiàn)［2］中得到的結(jié)果相一致。我們?cè)谙旅嫣峁┝硗庖粋€(gè)示例。

例5 我們?cè)趦蓚€(gè)池中隨機(jī)生成4個(gè)任務(wù)，

A：J1＝（mi，ri）＝（3 ，5），J2＝（7 ，11），R1＝R2＝10×10個(gè)MapReduce slots；

B：J3＝（13 ，17），J4＝（23 ，29），R3＝R4＝20×20個(gè)MapReduce slots；P＝30。通過(guò)對(duì)每個(gè)池使用Johnson算法，我們可以計(jì)算出T1＝21和T2＝65。通過(guò)式（12）和式（13），我們可以得到P1＝4，P2＝26，池A和池B的Makespan在平衡過(guò)后分別為53和50個(gè)單位時(shí)間。如果我們應(yīng)用引理1，對(duì)所有的作業(yè)增加MapReduce slot到30×30個(gè)slots（這也是所有可用的slots的總數(shù)）。這樣它們的Map和Reduce持續(xù)時(shí)間將為J′1＝（1，5／3），J′2＝（7／3，11／3），J′3＝（26／3，34／3），J′4＝（46／3，58／3）?，F(xiàn)在我們?cè)賾?yīng)用Johnson算法，將得到所有的Makespan為，這個(gè)結(jié)果比用兩個(gè)池所得出的結(jié)果（53）小。

例6 讓我們使用文獻(xiàn)［6］中的示例。考慮兩個(gè)相同的作業(yè)J1和J2，J1＝J2＝（10，10），他們?cè)贖adoop集群中請(qǐng)求30×30個(gè)Map和Reduce slots。假設(shè)兩個(gè)作業(yè)都可使用集群上最大可用的30×30個(gè)Map和Reduce slots。

（1）使用兩個(gè)池：通過(guò)對(duì)池1和池2進(jìn)行負(fù)載均衡，應(yīng)用式（12）和式（13），我們可以得到T1＝T2＝10，P1＝P2＝15；每一個(gè)池的Makespan是40個(gè)單位時(shí)間，這和文獻(xiàn)［6］中使用HFS調(diào)度器得到的結(jié)果相一致。

（2）在單個(gè)集群上使用引理1和Johnson算法，J1先執(zhí)行，J2緊接其后，我們可以輕松計(jì)算出總Makespan為30個(gè)單位時(shí)間。這和文獻(xiàn)［2］中應(yīng)用FIFO調(diào)度器得出的結(jié)果相一致。這個(gè)例子再一次說(shuō)明，通過(guò)Johnson算法和引理1得出的總的Makespan比文獻(xiàn)［6］中使用兩個(gè)池方法得出的結(jié)果小。通過(guò)大量的例子和研究，我們得出下面的觀察結(jié)果。

觀察結(jié)果4 使用資源池可以使兩組池的完工時(shí)間更加平衡，但未必會(huì)讓所有作業(yè)的總完工時(shí)間最少，使用引理1和Johnson算法在單個(gè)Hadoop集群中總能保證總完工時(shí)間最小。

引理1、定理1、定理2、定理3和觀察結(jié)果4告訴我們：

（1）在滿足Johnson算法的條件下，我們?nèi)匀豢梢詫?duì)單Hadoop集群使用Johnson算法來(lái)獲取總完工時(shí)間的最小值；

（2）針對(duì)兩個(gè)池完工時(shí)間的平衡，可以在線性時(shí)間內(nèi)解決，遠(yuǎn)低于文獻(xiàn)［6］中模擬方法的復(fù)雜度（其計(jì)算復(fù)雜度為O（n2lognlogm），其中n為任務(wù)數(shù)，m為Hadoop集群節(jié)點(diǎn)數(shù)）。

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

本文通過(guò)分析經(jīng)典Johnson算法與MapReduce模型兩個(gè)階段的特征，改進(jìn)MapReduce調(diào)度系統(tǒng)設(shè)計(jì)使其與經(jīng)典Johnson應(yīng)用條件相互匹配，因Hadoop為開源軟件，這使得引理1容易實(shí)現(xiàn)，從而使用該算法來(lái)準(zhǔn)確求解一批任務(wù)的最小總完工時(shí)間。為此，我們提出一個(gè)更好的調(diào)度策略，依據(jù)系統(tǒng)總的可用資源動(dòng)態(tài)調(diào)整分配給不同任務(wù)的資源，以便最大化利用系統(tǒng)資源和滿足用戶請(qǐng)求。該模型可以非常方便地應(yīng)用于提高系統(tǒng)總的響應(yīng)效率、降低總體能耗、實(shí)現(xiàn)多個(gè)資源池的負(fù)載均衡等領(lǐng)域。

針對(duì)提出的模型，我們正在進(jìn)行一些拓展研究：

（1）在真實(shí)Hadoop集群環(huán)境下，使用真實(shí)或模擬產(chǎn)生的數(shù)據(jù)進(jìn)行大量分析測(cè)試，以修正理論模型與實(shí)踐經(jīng)驗(yàn)之間可能存在的差異；

（2）分析不同種類MapReduce任務(wù)的特征，對(duì)Hadoop集群多任務(wù)調(diào)度進(jìn)行更好的管理，提高服務(wù)質(zhì)量并兼顧節(jié)能以及負(fù)載均衡等策略；

（3）本文主要考慮Hadoop集群節(jié)點(diǎn)同構(gòu)的情況，當(dāng)集群節(jié)點(diǎn)不同構(gòu)時(shí)，如何修正完善分析模型是另一個(gè)拓展方向。

［1］ http：／／hadoop.apache.org／common／docs／ro.20.1／capacityscheduler.htm.

［2］ Zaharia M，Borthakur D，Sarma J S，et al.Delay scheduling：A simple technique for achieving locality and fairness in cluster scheduling［C］∥Proc of EuroSys，2010：265－278.

［3］ Wolf J，Rajan D，Hildrum K，et al.FLEX：A slot allocation scheduling optimizer for MapReduce workloads［C］∥Proc of ACM／IFIP／USENIX International Middleware Conference，2010：1－20.

［4］ Verma A，Cherkasova L，Campbell R H.ARIA：Automatic resource inference and allocation for MapReduce environments［C］∥Proc of ICAC’11，2011：235－244.

［5］ Verma A，Cherkasova L，Campbell R H.Play it again，Sim－MR?。跜］∥Proc of Intl.IEEE Cluster’11，2011：253－261.

［6］ Verma A，Cherkasova L，Campbell R H.Orchestrating an ensemble of MapReduce jobs for minimizing their makespan［J］.IEEE Transactions on Dependable and Secure Computing，2013，10（5）：314－327.

［7］ Tian Wen－h(huán)ong，Yeo C S，Xue Rui－ni，et al.Power－aware scheduling of real－time virtual machines in cloud data centers considering fixed processing intervals［C］∥Proc of IEEE CCIS’12，2012：337－341.

［8］ Tian Wen－h(huán)ong，Xue Rui－ni，Xiong Qing，et al.An energyefficient online parallel scheduling algorithm for cloud data centers［C］∥Proc of IEEE Services 2013，2013：1.

［9］ Tian Wen－h(huán)ong，Zhao Yong，Zhong Yuan－liang，et al.Dynamic and integrated load－balancing scheduling algorithms for cloud data centers［J］.Journal of China Communications，2011，8（6）：117－126.

［10］ Herodotou H，Babu S.Profiling，what－if analysis，and cost based optimization of MapReduce programs［J］.Proc of the VLDB Endowment，2011，4（11）：1111－1122.

［11］ Moseley B，Dasgupta A，Kumar R，et al.On scheduling in Map－Reduce and flow－shops［C］∥Proc of SPAA’11，2011：289－298.

［12］ Verma A，Cherkasova L，Campbell R H.Two sides of a coin：Optimizing the schedule of MapReduce jobs to minimize their makespan and improve cluster performance［C］∥Proc of MASCOTS’12，2012：11－18.

［13］ Johnson S.Optimal two－and three－stage production schedules with setup times included［J］.Naval Research Logistics Quarterly，1954，1（1）：61－68.

［14］ Beloglazov A，Abawajy J，Buyya R.Energy－aware resource allocation heuristics for efficient management of data centers for cloud computing［J］.Future Generation Computer Systems，2012，28（5）：755－768.

［15］ Chen Y，Keys L，Katz R H.Towards energy efficient MapReduce［R］∥Technical Report No.UCB／EECS－2009－109，Berkeley：University of California，2009.

［16］ Garey M，Johnson D.Computers and intractability：A guide to the theory of NP－completeness［M］.USA：WH Freeman＆Co，1979.