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

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

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

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