[發(fā)明專利]一種面向Map/Reduce型海量數(shù)據(jù)處理平臺的作業(yè)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410531590.0
• 申請日: 2014-10-10
• 公開（公告）號: CN104317650B
• 公開（公告）日: 2018-05-01
• 發(fā)明（設(shè)計(jì)）人: 梁毅;王玉鳳;樊明璐;張辰
• 申請（專利權(quán)）人: 北京工業(yè)大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 北京思海天達(dá)知識產(chǎn)權(quán)代理有限公司11203
• 代理人: 張慧

技術(shù)領(lǐng)域

本發(fā)明屬于海量數(shù)據(jù)處理領(lǐng)域，特別涉及Map/Reduce型海量數(shù)據(jù)處理平臺中的作業(yè)調(diào)度和資源管理。

背景技術(shù)

Map/Reduce型海量數(shù)據(jù)處理平臺是海量數(shù)據(jù)處理領(lǐng)域的最新技術(shù)進(jìn)展，主要服務(wù)于具有一次寫入，多次讀取的數(shù)據(jù)訪問模式以及易并行(Embarrassing Parallel)計(jì)算模式的大數(shù)據(jù)應(yīng)用。Map/Reduce平臺提供Map/Reduce并行計(jì)算模型及其相應(yīng)的運(yùn)行時(shí)環(huán)境。Map/Reduce并行計(jì)算模型將應(yīng)用的數(shù)據(jù)處理流程抽象為Map階段和Reduce階段。Map階段和Reduce階段可分別映射為多個(gè)Map任務(wù)和Reduce任務(wù)并行執(zhí)行。其中Map階段主要進(jìn)行數(shù)據(jù)轉(zhuǎn)置和變形，Reduce階段主要進(jìn)行數(shù)據(jù)規(guī)約操作。從數(shù)據(jù)流的角度，Map階段從分布式文件系統(tǒng)中，讀取需要處理的輸入數(shù)據(jù)，進(jìn)行數(shù)據(jù)處理，并存入本地文件系統(tǒng)中；Reduce階段獲取Map階段輸出的文件，進(jìn)行數(shù)據(jù)規(guī)約操作并將結(jié)果存入分布式文件系統(tǒng)中。通過上述分析可知，Map階段和Reduce階段具有數(shù)據(jù)依賴關(guān)系，即Reduce階段以Map階段處理結(jié)果作為輸入數(shù)據(jù)。

作業(yè)是Map/Reduce平臺中應(yīng)用的基本組成單位。一個(gè)Map/Reduce作業(yè)的執(zhí)行通常包含一個(gè)Map階段和一個(gè)Reduce階段。作業(yè)調(diào)度是Map/Reduce平臺的核心功能之一，作業(yè)調(diào)度統(tǒng)一管理Map/Reduce平臺的計(jì)算資源，為Map/Reduce作業(yè)所包含的多個(gè)Map和Reduce任務(wù)分配其運(yùn)行所需的計(jì)算資源，保證作業(yè)公平合理地共享Map/Reduce平臺資源，提高作業(yè)執(zhí)行效率。

目前針對Map/Reduce作業(yè)的調(diào)度方法包括先來先服務(wù)、能力調(diào)度等。這些方法通常將Map任務(wù)與Reduce任務(wù)分離調(diào)度，采用不同的調(diào)度策略。對于Map任務(wù)，上述調(diào)度方法通常優(yōu)先選擇其處理數(shù)據(jù)所在的節(jié)點(diǎn)作為該Map任務(wù)的運(yùn)行節(jié)點(diǎn)，從而減少M(fèi)ap任務(wù)運(yùn)行中海量數(shù)據(jù)傳輸?shù)臅r(shí)間開銷。對于Reduce任務(wù)則根據(jù)其所屬作業(yè)的執(zhí)行進(jìn)度，從當(dāng)前空閑資源中為該Reduce任務(wù)隨機(jī)或者按照讀取Map任務(wù)輸出數(shù)據(jù)代價(jià)最小化原則選取運(yùn)行節(jié)點(diǎn)。

由于Map/Reduce作業(yè)中Map任務(wù)與Reduce任務(wù)間存在數(shù)據(jù)依賴關(guān)系，現(xiàn)有調(diào)度方法對于一個(gè)Map/Reduce作業(yè)的調(diào)度均為首先調(diào)度Map任務(wù)，當(dāng)已執(zhí)行完成的Map任務(wù)的數(shù)量達(dá)到一定閾值(如20％，計(jì)算方法為完成的Map任務(wù)數(shù)除以總Map任務(wù)數(shù))時(shí)，調(diào)度Reduce任務(wù)。Reduce任務(wù)被調(diào)度后，首先讀取已完成Map任務(wù)產(chǎn)生的輸出數(shù)據(jù)，當(dāng)所有Map任務(wù)所產(chǎn)生的輸出數(shù)據(jù)均讀取完畢后，Reduce任務(wù)執(zhí)行其數(shù)據(jù)處理邏輯。在實(shí)際Map/Reduce平臺中，屬于同一作業(yè)的多個(gè)Map任務(wù)由于執(zhí)行時(shí)間不同，或由于平臺資源競爭使得Map任務(wù)的啟動時(shí)間不同，導(dǎo)致Map任務(wù)具有不同的執(zhí)行結(jié)束時(shí)間。這使得當(dāng)部分Map任務(wù)執(zhí)行結(jié)束，Reduce任務(wù)完成從這些Map任務(wù)拷貝輸出數(shù)據(jù)后，仍需要等待其他未完成的Map任務(wù)執(zhí)行結(jié)束才能繼續(xù)工作(即拷貝輸出數(shù)據(jù))，而此期間Reduce任務(wù)處于空閑等待狀態(tài)。在現(xiàn)有的調(diào)度方法中，當(dāng)Reduce任務(wù)處于空閑等待狀態(tài)時(shí)，并不釋放分配給它的計(jì)算資源，這大大降低了Map/Reduce平臺資源利用率。

基于以上不足，本發(fā)明提出基于Reduce任務(wù)資源搶占的作業(yè)調(diào)度方法。該方法可以在Reduce任務(wù)空閑時(shí)將Reduce任務(wù)的資源暫時(shí)分配給Map任務(wù)，從而提高系統(tǒng)的資源利用率，最終縮短作業(yè)的運(yùn)行時(shí)間。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種面向Map/Reduce型海量數(shù)據(jù)處理平臺的作業(yè)調(diào)度方法，該方法能夠在Reduce任務(wù)等待獲取Map任務(wù)的輸出數(shù)據(jù)時(shí)，搶占其所占用的計(jì)算資源，并分配給待調(diào)度的Map任務(wù)使用，從而提升平臺資源的使用率，提高作業(yè)的執(zhí)行效率。本發(fā)明所述的計(jì)算資源是支撐Map/Reduce作業(yè)所包含的Map任務(wù)或Reduce任務(wù)運(yùn)行的物理資源，包括物理內(nèi)存、CPU等。