異構(gòu)環(huán)境下MapReduce離線調(diào)度算法的研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的到來(lái),如何高效地分析處理海量數(shù)據(jù)成為了計(jì)算機(jī)學(xué)科的一個(gè)新的挑戰(zhàn)。MapReduce就是在此背景下出現(xiàn)并飛速發(fā)展的一種計(jì)算模型。在此之前,并非沒有并行計(jì)算模型,但MapReduce憑借其簡(jiǎn)便易學(xué),高效穩(wěn)定的性能贏得了學(xué)術(shù)界和工業(yè)界的廣泛認(rèn)可,在大數(shù)據(jù)時(shí)代逐漸嶄露頭角。
　　本文研究的,是異構(gòu)MapReduce環(huán)境下,大批量作業(yè)的離線調(diào)度問(wèn)題。眾所周知,在MapReduce模型應(yīng)用最廣泛的公司中,其很大一部分需求都是針

2、對(duì)周期性執(zhí)行的日常處理任務(wù)。如Google要每天對(duì)新爬取的頁(yè)面進(jìn)行分析,對(duì)用戶的日志進(jìn)行統(tǒng)計(jì)等。顯然,如何調(diào)度這些作業(yè),使其在集群中按照合理的順序執(zhí)行,對(duì)于減少作業(yè)的總運(yùn)行時(shí)間,提早釋放系統(tǒng)資源有重大意義。
　　本文的研究?jī)?nèi)容可以簡(jiǎn)要概括為:在異構(gòu)環(huán)境下,針對(duì)一個(gè)給定的獨(dú)立MapReduce作業(yè)集合,設(shè)計(jì)一個(gè)調(diào)度算法,使得系統(tǒng)的總執(zhí)行時(shí)間最小。根據(jù)我們的調(diào)研,該問(wèn)題是NP完全問(wèn)題,最優(yōu)解在現(xiàn)有計(jì)算能力下不能取得。故本文創(chuàng)新性地將該

3、問(wèn)題和兩階段流水作業(yè)調(diào)度問(wèn)題類比,提出了混合多階段調(diào)度算法。
　　本文將該調(diào)度問(wèn)題分解為兩個(gè)子問(wèn)題,以降低問(wèn)題復(fù)雜度。針對(duì)提出的排序子問(wèn)題,本文提出了基于Johnson的優(yōu)先權(quán)設(shè)置算法,從而降低了由m a p和reduce任務(wù)依賴引起的執(zhí)行時(shí)間增長(zhǎng)。針對(duì)另一個(gè)分配子問(wèn)題,我們又將其一分為二。在m ap階段,通過(guò)使用Min-Min算法平衡m ap階段集群中機(jī)器的負(fù)載。在reduce階段,我們提出了Dynamic-Min-Min算法,