異構環(huán)境下MapReduce離線調度算法的研究.pdf

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

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

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