[發(fā)明專利]一種基于Storm的流式計算二分圖任務(wù)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201611203987.2
• 申請日: 2016-12-23
• 公開（公告）號: CN108241530A
• 公開（公告）日: 2018-07-03
• 發(fā)明（設(shè)計）人: 馬力;吳江;田小偉
• 申請（專利權(quán)）人: 西北大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京科億知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11350
• 代理人: 湯東鳳

本發(fā)明公開了基于Storm的流式計算二分圖任務(wù)調(diào)度方法，其特征在于：將Storm作業(yè)有向無環(huán)圖DAJG(Directed Acyclic Job Graph)節(jié)點(diǎn)和集群物理機(jī)節(jié)點(diǎn)無向圖(Undirected Node Graph)節(jié)點(diǎn)看作二分圖的兩類頂點(diǎn)，構(gòu)建二分圖模型，綜合集群物理機(jī)各節(jié)點(diǎn)的計算能力以及集群中網(wǎng)絡(luò)傳輸延遲，根據(jù)任務(wù)與節(jié)點(diǎn)資源之間的可調(diào)度關(guān)系，采用解決二分圖最大權(quán)值匹配算法進(jìn)行任務(wù)調(diào)度，本發(fā)明方法在保證集群物理機(jī)資源負(fù)載均衡的情況下，減少任務(wù)執(zhí)行中數(shù)據(jù)流遷移過程中的網(wǎng)絡(luò)延遲，從而提升系統(tǒng)整體性能。

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

本發(fā)明涉及一種基于Storm的流式計算二分圖任務(wù)調(diào)度方法。

背景技術(shù)

隨著信息科學(xué)技術(shù)的飛速發(fā)展，云計算和物聯(lián)網(wǎng)環(huán)境下的應(yīng)用呈現(xiàn)出數(shù)據(jù)量大，數(shù)據(jù)流連續(xù)，表現(xiàn)出多源并發(fā)，實(shí)時處理等特征。針對這些流數(shù)據(jù)的實(shí)時處理，稱為流式數(shù)據(jù)處理或流式計算。在大數(shù)據(jù)流式計算系統(tǒng)Storm中，多任務(wù)調(diào)度是影響流式計算系統(tǒng)Storm性能的關(guān)鍵因素。流式計算系統(tǒng)中的任務(wù)具備兩個典型的特征：

(1)多任務(wù)多階段特性。

從理論模型上來說，提交到系統(tǒng)中的任務(wù)在處理過程可用一個有向無環(huán)圖(DAG)表示[1]。即表示的任務(wù)調(diào)度是多任務(wù)分多階段執(zhí)行，不同的階段之間的任務(wù)需要協(xié)同執(zhí)行，同一階段的任務(wù)則需要獨(dú)立并行地執(zhí)行。

(2)時間特性

由于需要較集中的對數(shù)據(jù)進(jìn)行計算，傳統(tǒng)的批式大數(shù)據(jù)計算在計算耗時上的要求比較寬松。但在流式計算中，數(shù)據(jù)從數(shù)據(jù)源到計算結(jié)果都是在內(nèi)存中，為了保證計算的時效性，往往對計算耗時要求比較苛刻，甚至達(dá)到毫秒級[2]。

流式計算的這些典型的特征，使得分布式環(huán)境中的多作業(yè)調(diào)度成為流式計算處理過程中的關(guān)鍵問題之一[3]。分布式環(huán)境下的作業(yè)調(diào)度早已被證明是一個NP難問題[4，5]。如何將待處理的作業(yè)合理地調(diào)度到相應(yīng)的計算節(jié)點(diǎn)上執(zhí)行，是作業(yè)調(diào)度的主要目的。

流式計算的任務(wù)調(diào)度和資源管理問題是流式計算的關(guān)鍵技術(shù)之一。目前的大數(shù)據(jù)流式計算構(gòu)架中，多采用Hadoop Yarn、Amazon EC2和Apache Mesos這種細(xì)粒度的資源管理方式來管理資源，通過系統(tǒng)構(gòu)架中的默認(rèn)任務(wù)調(diào)度機(jī)制來為任務(wù)分配資源。在通用的流式計算架構(gòu)中，默認(rèn)的調(diào)度策略為了滿足多場景的應(yīng)用往往未考慮應(yīng)用的實(shí)際需求以及集群的物理環(huán)境。如Storm作為流式計算業(yè)界最具影響力的系統(tǒng)所采用的默認(rèn)調(diào)度策略是將所有作業(yè)實(shí)例化為執(zhí)行線程作為任務(wù)調(diào)度單位，將所有的執(zhí)行線程按照集群所擁有的資源均勻的分配到各個物理計算節(jié)點(diǎn)上。

Storm默認(rèn)的任務(wù)調(diào)度機(jī)制可以應(yīng)對一般的應(yīng)用場景，但卻存在以下問題：

(1)某一類的任務(wù)對CPU或內(nèi)存敏感，如果將同樣對CPU敏感的任務(wù)調(diào)度在同一物理機(jī)器上，則可能使該機(jī)器的多維資源利用不均衡，如CPU資源負(fù)載過高，而內(nèi)存資源卻空閑；

(2)在異構(gòu)集群中，不同物理機(jī)擁有的資源(CPU、內(nèi)存、網(wǎng)絡(luò)帶寬等)不同，將任務(wù)線程按照簡單的均勻分配策略有可能導(dǎo)致資源稀缺的物理負(fù)載過重而導(dǎo)致系統(tǒng)吞吐率下降；

(3)某個任務(wù)的數(shù)據(jù)在A節(jié)點(diǎn)上，但卻被調(diào)度到B節(jié)點(diǎn)上執(zhí)行，這無疑增加了讀取數(shù)據(jù)的帶寬延遲開銷，這在數(shù)據(jù)不落地(磁盤不參與緩存)的流式計算中的影響不可忽略；

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

本發(fā)明的目的在于克服現(xiàn)有技術(shù)中存在的上述不足，而提供一種基于Storm的流式計算二分圖任務(wù)調(diào)度方法。本基于Storm的流式計算二分圖任務(wù)調(diào)度方法可以在保證集群物理機(jī)資源負(fù)載均衡的情況下，減少任務(wù)執(zhí)行中數(shù)據(jù)流遷移過程中的網(wǎng)絡(luò)延遲，從而提升系統(tǒng)整體性能。

本發(fā)明解決上述問題所采用的技術(shù)方案是：