[發(fā)明專利]一種面向分布式流計(jì)算系統(tǒng)的動(dòng)態(tài)任務(wù)調(diào)度優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201710997546.2
• 申請日: 2017-10-24
• 公開（公告）號: CN107832129B
• 公開（公告）日: 2020-05-19
• 發(fā)明（設(shè)計(jì)）人: 吳松;金海;柳密
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 華中科技大學(xué)專利中心 42201
• 代理人: 李智;曹葆青

本發(fā)明提供一種面向分布式流計(jì)算環(huán)境下的任務(wù)調(diào)度優(yōu)化方法，在運(yùn)行時(shí)周期性地采集任務(wù)之間傳輸?shù)臄?shù)據(jù)量，通過分組機(jī)制，將通信量大的任務(wù)劃分到一個(gè)組，一個(gè)組的任務(wù)在后續(xù)的調(diào)度過程中，會(huì)被當(dāng)成一個(gè)整體進(jìn)行調(diào)度。本發(fā)明的方法有很好的擴(kuò)展性，當(dāng)任務(wù)拓?fù)浣Y(jié)構(gòu)非常大的時(shí)候，本發(fā)明可以采用多層次組合方法，將上一層得到的組進(jìn)行再次合并，得到更大的組，從而啟用更少的調(diào)度單元，進(jìn)一步減少調(diào)度規(guī)模。當(dāng)規(guī)模足夠小的時(shí)候，再將這些組調(diào)度到進(jìn)程，降低網(wǎng)絡(luò)通信開銷。進(jìn)一步地，本發(fā)明在調(diào)度時(shí)還依據(jù)負(fù)載大小調(diào)用進(jìn)程，從而在確保降低網(wǎng)絡(luò)通信開銷的同時(shí)達(dá)到負(fù)載平衡。

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

本發(fā)明屬于分布式流計(jì)算領(lǐng)域，更具體地，涉及一種面向分布式流計(jì)算系統(tǒng)的動(dòng)態(tài)任務(wù)調(diào)度優(yōu)化方法，用于像Storm這種基于操作符的流計(jì)算系統(tǒng)在分布式環(huán)境下如何優(yōu)化任務(wù)調(diào)度方法來滿足負(fù)載平衡和降低處理延時(shí)，進(jìn)而提高系統(tǒng)的性能。

背景技術(shù)

在過去幾年中，信息產(chǎn)業(yè)以前所未有的高速發(fā)展，傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)不再能夠滿足大數(shù)據(jù)所具有的挑戰(zhàn)性的要求。根據(jù)數(shù)據(jù)是靜態(tài)還是動(dòng)態(tài)，我們可以將計(jì)算分類為批處理和流處理。在前者中，用于處理的數(shù)據(jù)應(yīng)該在計(jì)算開始之前實(shí)現(xiàn)，而后者用于處理的數(shù)據(jù)是沒有約束的連續(xù)流。其中Hadoop是Map-Reduce最具代表性的開源實(shí)現(xiàn)，已經(jīng)成為最流行的離線批處理框架。然而，當(dāng)數(shù)據(jù)是無界流時(shí)，需要及時(shí)處理它，這是Map-Reduce這一類框架幾乎不能滿足的一個(gè)要求。因此，需要一種新的框架。為了滿足流處理的要求，很多新的框架被提出來。Storm是當(dāng)前最流行的分布式流處理引擎之一，能夠?qū)崟r(shí)對高吞吐量數(shù)據(jù)流進(jìn)行分析。Storm現(xiàn)在被許多公司廣泛使用，如Twitter和阿里巴巴。

在Storm每個(gè)shuffling階段，在任務(wù)之間有大量的tuple(即消息)流傳輸，這是主要的通信開銷。如果通信的任務(wù)之間的網(wǎng)絡(luò)距離盡可能短，則通信開銷將顯著降低。即使任務(wù)的分配如此重要，任務(wù)分配問題在Storm中仍然沒有解決。Storm中的默認(rèn)調(diào)度程序稱為均衡調(diào)度器，它主要可以分為兩個(gè)步驟：第一步，它使用循環(huán)策略將執(zhí)行程序分配給工作程序，然后使用相同的方法將workers分發(fā)到集群的節(jié)點(diǎn)。這種調(diào)度算法的目的是保證負(fù)載平衡，而且易于實(shí)現(xiàn)，但它有三個(gè)明顯的缺點(diǎn)。首先，它不考慮任務(wù)之間的數(shù)據(jù)傳輸，這可能導(dǎo)致高通信延遲，從而導(dǎo)致執(zhí)行性能降低。第二，它不考慮工作負(fù)載平衡。第三，它會(huì)讓每個(gè)topology盡可能多使用群集中的節(jié)點(diǎn)，而不考慮負(fù)載，這種不必要的分布會(huì)進(jìn)一步加劇通信開銷。因此，需要一個(gè)能很好解決上述缺陷的調(diào)度方法。

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

針對分布式流計(jì)算環(huán)境下通信開銷的問題，本發(fā)明提出了一種動(dòng)態(tài)的基于組劃分的動(dòng)態(tài)任務(wù)調(diào)度優(yōu)化方法，該方法能在運(yùn)行時(shí)周期性地采集任務(wù)之間傳輸?shù)臄?shù)據(jù)量，然后利用這些數(shù)據(jù)關(guān)系，在調(diào)度的時(shí)候能考慮到任務(wù)間的精確的通信開銷，在對應(yīng)用層完全透明的前提下，自動(dòng)選擇最佳的調(diào)度優(yōu)化方案，顯著地降低網(wǎng)絡(luò)通信開銷。

為實(shí)現(xiàn)本發(fā)明技術(shù)目的，本發(fā)明采用了以下技術(shù)方案：

一種面向分布式流計(jì)算環(huán)境下的任務(wù)調(diào)度優(yōu)化方法，包括如下步驟：

(1)依據(jù)當(dāng)前周期內(nèi)任務(wù)間的通信量預(yù)測下一周期內(nèi)任務(wù)間的通信量；

(2)將下一周期內(nèi)預(yù)測通信量大的兩個(gè)任務(wù)組合為一個(gè)任務(wù)組；

(3)啟動(dòng)進(jìn)程并以任務(wù)組為單位進(jìn)行調(diào)度。

進(jìn)一步地，所述步驟(2)的具體實(shí)現(xiàn)過程為：

從任務(wù)i的所有鄰居未訪問任務(wù)中，選取一個(gè)任務(wù)i與它之間的預(yù)測通信量最大的任務(wù)，將其與任務(wù)i組合為任務(wù)組parentTask，如果任務(wù)i的所有鄰居任務(wù)均已被訪問，僅將任務(wù)i獨(dú)立組合為任務(wù)組parentTask，完成第一層組合；