大規(guī)模數(shù)據(jù)處理系統(tǒng)中MapReduce任務(wù)劃分與調(diào)度關(guān)鍵技術(shù)研究.pdf

1、近年來，隨著信息時代的飛速發(fā)展，海量的數(shù)據(jù)被產(chǎn)生和存儲。特別是在大數(shù)據(jù)時代的背景下，人們對于海量數(shù)據(jù)的挖掘和運用正在成為重要的生產(chǎn)因素。在這種迫切需求下，利用大規(guī)模數(shù)據(jù)系統(tǒng)高效分析和處理海量數(shù)據(jù)成為了這一領(lǐng)域的關(guān)鍵問題。其中，以MapReduce為代表的海量數(shù)據(jù)分析軟件架構(gòu)扮演著越來越重要的角色。MapReduce軟件架構(gòu)充分利用分布式系統(tǒng)特點，將問題劃分為若干子問題并行求解成為海量數(shù)據(jù)處理的主流方法。因此，子任務(wù)的合理劃分和協(xié)同調(diào)度是

2、當前學術(shù)界和工業(yè)界研究大規(guī)模數(shù)據(jù)處理技術(shù)的核心目標。
　　已有的MapReduce研究成果主要集中于任務(wù)的劃分算法，系統(tǒng)容錯機制，執(zhí)行時間預(yù)測，作業(yè)與任務(wù)的調(diào)度等方面。隨著系統(tǒng)規(guī)模和數(shù)據(jù)規(guī)模的不斷增大，傳統(tǒng)的任務(wù)劃分與調(diào)度方法已經(jīng)不能滿足海量數(shù)據(jù)處理的需求。大規(guī)模數(shù)據(jù)處理系統(tǒng)不僅對系統(tǒng)的容錯性提出了更高的要求，海量數(shù)據(jù)本身的數(shù)據(jù)特性也將深刻影響MapReduce中的任務(wù)劃分與調(diào)度問題。因此當前利用MapReduce分析處理海量數(shù)據(jù)

3、暴露出許多難以克服的問題：第一，任務(wù)執(zhí)行時間難以預(yù)測導致調(diào)度策略難以優(yōu)化。目前MapReduce中已有的多數(shù)工作主要采用模型的方法來預(yù)測任務(wù)的精確執(zhí)行時間，并以此作為調(diào)度算法的依據(jù)。但是在大規(guī)模系統(tǒng)中采用復(fù)雜模型方法往往開銷過大，簡單模型預(yù)測又不準確。第二，基于精確時間調(diào)度算法與實際執(zhí)行時間存在誤差。已有的多數(shù)調(diào)度算法研究都是基于精確執(zhí)行時間為基礎(chǔ)。然而，任務(wù)的執(zhí)行時間往往帶有一定的不確定性，隨著系統(tǒng)規(guī)模和復(fù)雜度的增加，這種不準確性越來

4、越嚴重，成為導致系統(tǒng)性能不能充分發(fā)揮的主要瓶頸。第三，無法處理數(shù)據(jù)分布特性對調(diào)度帶來的影響?，F(xiàn)有的任務(wù)劃分和調(diào)度算法不考慮數(shù)據(jù)本身特點對任務(wù)執(zhí)行時間的影響，而在實際應(yīng)用中，數(shù)據(jù)的部分特征，比如數(shù)據(jù)傾斜等，會嚴重造成務(wù)之間工作量的不合理劃分，部分工作量較重的任務(wù)執(zhí)行時間會拖長整個作業(yè)的執(zhí)行時間。第四，為充分考慮數(shù)據(jù)局部性問題。目前對于Reduce任務(wù)的數(shù)據(jù)局部性關(guān)注較少。不合理的Reduce任務(wù)調(diào)度往往不僅會增加網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量，還有可

5、能造成擁塞現(xiàn)象加大了數(shù)據(jù)傳輸過程的難度。
　　針對上述技術(shù)瓶頸，本文結(jié)合大數(shù)據(jù)和處理系統(tǒng)本身特征，系統(tǒng)地研究了大規(guī)模數(shù)據(jù)處理系統(tǒng)中MapReduce任務(wù)劃分與調(diào)度關(guān)鍵技術(shù)，從以下幾個方面展開研究：
　　針對現(xiàn)有基于模型的預(yù)測算法精確度差、復(fù)雜度高，不適于大規(guī)模數(shù)據(jù)處理系統(tǒng)實際使用的問題，本文深入研究了MapReduce中作業(yè)及任務(wù)的執(zhí)行特點，并提出了一種基于異構(gòu)環(huán)境非精確預(yù)測的任務(wù)風險調(diào)度RiskI，RiskI首先設(shè)計了一種

6、基于任務(wù)屬性和環(huán)境特征的相似度算法，在此基礎(chǔ)上設(shè)計了基于歷史相似度匹配的執(zhí)行時間預(yù)測算法。最后特別針對預(yù)測結(jié)果是帶有概率分布的時間段和MapReduce中任務(wù)單位時間收益不統(tǒng)一這些特征，RiskI利用風險決策理論實現(xiàn)了非精確時間的調(diào)度算法。該方法比LATE提高了46％的系統(tǒng)吞吐率，極力避免了執(zhí)行時間不確定性對系統(tǒng)性能帶來的損失。
　　針對數(shù)據(jù)分布特征影響系統(tǒng)性能的問題，本文首先發(fā)現(xiàn)傳統(tǒng)的前瞻備份執(zhí)行方法不能有效縮短工作量較重任務(wù)的

7、執(zhí)行時間，而這類任務(wù)往往是由于數(shù)據(jù)傾斜所造成，并成為拖慢作業(yè)執(zhí)行響應(yīng)時間的直接原因。在此發(fā)現(xiàn)的基礎(chǔ)上，本文提出了基于數(shù)據(jù)特征檢測的前瞻執(zhí)行SkewSeize。通過對網(wǎng)絡(luò)傳輸數(shù)據(jù)量的監(jiān)測以及特征分析，SkewSeize分析了造成最慢任務(wù)的原因，特別設(shè)計了數(shù)據(jù)傾斜造成的最慢任務(wù)識別算法。通過對任務(wù)資源競爭關(guān)系分析，SkewSeize識別出與其具有競爭關(guān)系的非最慢任務(wù)，并通過調(diào)度算法選擇最適合被遷移的任務(wù)和遷移到的節(jié)點，并證明其不會造成新的最

8、慢任務(wù)。實驗結(jié)果表明SkewSeize能夠有效的將作業(yè)的執(zhí)行時間縮短14%并且有效的避免了資源浪費。
　　針對被動處理最慢任務(wù)會帶來額外調(diào)度開銷和資源浪費問題，本文通過對真實數(shù)據(jù)的特征分析，發(fā)現(xiàn)了數(shù)據(jù)傾斜往往在具有動態(tài)性的同時在某一范圍內(nèi)也具有一定的穩(wěn)定性。利用此特征，本文提出了基于數(shù)據(jù)傾斜感知的動態(tài)任務(wù)劃分SkewControl。SkewControl通過分析數(shù)據(jù)特征，首先實現(xiàn)了動態(tài)預(yù)測數(shù)據(jù)分布算法。利用此預(yù)測，系統(tǒng)能夠在缺少先

9、驗知識的情況下動態(tài)主動地將任務(wù)的工作量更合理的劃分和調(diào)度到不同的異構(gòu)節(jié)點。最后，SkewControl設(shè)計了執(zhí)行結(jié)果的反饋機制和調(diào)度優(yōu)化算法，對可能變化的計算環(huán)境，不斷地精化和細化調(diào)整任務(wù)之間的劃分，從而使得調(diào)度效果不斷優(yōu)化。實驗表明，與LATE算法和SkewTune算法相比，SkewControl能夠?qū)⑾到y(tǒng)執(zhí)行效率分別提高了23.8%和17%。
　　針對數(shù)據(jù)局部性制約系統(tǒng)性能的問題，本文首先分析了MapReduce系統(tǒng)中不同Re

10、duce任務(wù)調(diào)度方式對Shuffle階段數(shù)據(jù)傳輸可能帶來的變化以及對最終執(zhí)行時間所帶來的影響，分析得到了系統(tǒng)中節(jié)點內(nèi)部，機柜內(nèi)部和機柜之間不同數(shù)據(jù)傳輸帶寬的特征?；谝陨戏治?，本文提出了基于數(shù)據(jù)局部化的Reduce任務(wù)調(diào)度Jinking，Jinking主要實現(xiàn)了最大化機柜內(nèi)部網(wǎng)絡(luò)流量和最大化節(jié)點內(nèi)部網(wǎng)絡(luò)流量的貪心調(diào)度算法。特別針對了在中間數(shù)據(jù)不可知或者部分可知的情況下，又提出了通過延遲調(diào)度和立即次優(yōu)調(diào)度兩種算法，來降低網(wǎng)絡(luò)中數(shù)據(jù)的傳輸，