Storm環(huán)境下基于權(quán)重的任務(wù)調(diào)度算法

魯 亮，于 炯，卞 琛，英昌甜,3，師康利，蒲勇霖

(1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046； 2.新疆大學(xué) 軟件學(xué)院，烏魯木齊 830008;3.新疆大學(xué) 電氣工程學(xué)科博士后科研流動(dòng)站，烏魯木齊 830047)

0 引言

隨著互聯(lián)網(wǎng)和各類智能終端的普及，數(shù)據(jù)呈現(xiàn)出井噴式發(fā)展的趨勢(shì)，MapReduce等各類大數(shù)據(jù)處理框架應(yīng)運(yùn)而生[1-2]。然而，這類傳統(tǒng)的大數(shù)據(jù)批量處理框架無(wú)法滿足部分企業(yè)的實(shí)時(shí)性業(yè)務(wù)需求。Apache Storm[3-4]作為一個(gè)開(kāi)源、實(shí)時(shí)、分布式部署、容錯(cuò)且擴(kuò)展性良好的大數(shù)據(jù)流式計(jì)算系統(tǒng)[5-6]，已成功解決這一問(wèn)題并引起了學(xué)術(shù)界和企業(yè)界的高度關(guān)注。在Storm系統(tǒng)中，只要數(shù)據(jù)源處于活動(dòng)狀態(tài)，元組便會(huì)源源不斷地發(fā)送至各工作節(jié)點(diǎn)，計(jì)算和傳輸將持續(xù)發(fā)生，無(wú)需進(jìn)行中間結(jié)果的持久化存儲(chǔ)，在實(shí)時(shí)個(gè)性化推薦、實(shí)時(shí)交通大數(shù)據(jù)分析、實(shí)時(shí)臨床數(shù)據(jù)分析等領(lǐng)域具有廣闊的應(yīng)用前景[7-9]。

Storm在進(jìn)行任務(wù)分配時(shí)采用輪詢(Round-Robin，RR)調(diào)度算法，即將用戶提交的拓?fù)渲邪拿恳粋€(gè)任務(wù)均勻分配到各工作進(jìn)程中，再將各工作進(jìn)程均勻分配到各工作節(jié)點(diǎn)上，未考慮到各任務(wù)計(jì)算開(kāi)銷的差異以及任務(wù)與任務(wù)之間不同類型的通信開(kāi)銷，這將對(duì)Storm處理的實(shí)時(shí)性產(chǎn)生較大影響。針對(duì)這一問(wèn)題，已有少量國(guó)內(nèi)外學(xué)者展開(kāi)相關(guān)研究。文獻(xiàn)[10]提出資源感知的在線調(diào)度算法R-Storm，將Storm資源分為硬約束(針對(duì)內(nèi)存)和軟約束(針對(duì)CPU和網(wǎng)絡(luò))兩類，利用任務(wù)需求的各類靜態(tài)資源和工作節(jié)點(diǎn)所能提供的靜態(tài)資源之間的關(guān)系實(shí)現(xiàn)調(diào)度，最終達(dá)到最大化資源利用率和提高集群吞吐量的效果，但該算法中各任務(wù)的資源需求完全依靠程序員人為設(shè)定而并非通過(guò)監(jiān)測(cè)獲得，不適合數(shù)據(jù)流快速變化場(chǎng)景下的在線調(diào)度。文獻(xiàn)[11]對(duì)此進(jìn)行改進(jìn)，添加了資源負(fù)載監(jiān)測(cè)模塊并將監(jiān)測(cè)結(jié)果存入數(shù)據(jù)庫(kù)，并使用調(diào)度生成器根據(jù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行實(shí)時(shí)調(diào)度，但并未評(píng)估調(diào)度自身對(duì)系統(tǒng)運(yùn)行帶來(lái)的影響以及重調(diào)度后是否能夠帶來(lái)更低的系統(tǒng)延遲。文獻(xiàn)[12]提出Storm框架下流量感知的在線調(diào)度算法T-Storm，通過(guò)監(jiān)測(cè)任務(wù)負(fù)載、工作節(jié)點(diǎn)負(fù)載以及任務(wù)與任務(wù)之間的數(shù)據(jù)傳輸負(fù)載，將通信開(kāi)銷大的任務(wù)動(dòng)態(tài)分配至空閑資源較多的節(jié)點(diǎn)上。然而，該算法并無(wú)法保證通信開(kāi)銷大的一對(duì)任務(wù)一定分配到同一個(gè)節(jié)點(diǎn)中，且一個(gè)拓?fù)湫枨蟮墓?jié)點(diǎn)數(shù)量依賴于用戶設(shè)定。此外，文獻(xiàn)[13]提出一種帶權(quán)圖的k劃分算法，文獻(xiàn)[14-16]提出流式計(jì)算框架下實(shí)時(shí)高效的資源調(diào)度算法和優(yōu)化框架。以上研究解決了流式計(jì)算環(huán)境下的任務(wù)優(yōu)化調(diào)度問(wèn)題，但無(wú)法直接移植于Storm平臺(tái)。文獻(xiàn)[17]提出并實(shí)現(xiàn)了一種服務(wù)質(zhì)量感知的Storm分布式調(diào)度器，其在網(wǎng)絡(luò)時(shí)延和可靠性等方面均優(yōu)于Storm默認(rèn)調(diào)度算法的執(zhí)行結(jié)果，但這與本文集中式數(shù)據(jù)中心的研究背景不符。文獻(xiàn)[18]將拓?fù)錈徇叺母拍钜隨torm平臺(tái)，其主要思想是將熱邊關(guān)聯(lián)的源任務(wù)和目標(biāo)任務(wù)調(diào)度到同一工作節(jié)點(diǎn)執(zhí)行，以達(dá)到減少網(wǎng)絡(luò)通信開(kāi)銷的效果。然而該算法未充分考慮拓?fù)鋬?nèi)部通信的全局性，并未將非熱邊的調(diào)度優(yōu)化考慮在內(nèi)。文獻(xiàn)[19]為了分別降低進(jìn)程間通信開(kāi)銷和節(jié)點(diǎn)間通信開(kāi)銷，在充分考慮Storm拓?fù)渲懈魅蝿?wù)通信情況的基礎(chǔ)上提出一種兩階段調(diào)度算法，但該算法并未考慮到各任務(wù)自身計(jì)算開(kāi)銷的差異性。文獻(xiàn)[20]提出Storm環(huán)境下離線和在線的兩種自適應(yīng)調(diào)度算法，其中離線調(diào)度算法用于拓?fù)溥\(yùn)行前的拓?fù)浣Y(jié)構(gòu)分析，而在線調(diào)度算法用于拓?fù)溥\(yùn)行中各節(jié)點(diǎn)的實(shí)時(shí)負(fù)載監(jiān)測(cè)和任務(wù)分配的動(dòng)態(tài)調(diào)整，其中在線調(diào)度算法效果更優(yōu)。這種自適應(yīng)調(diào)度算法解決了部分Storm環(huán)境中的通信開(kāi)銷問(wèn)題，但執(zhí)行時(shí)僅逐對(duì)考慮相互通信的任務(wù)，未將當(dāng)前任務(wù)與其直接通信的所有任務(wù)全部考慮進(jìn)來(lái)，這對(duì)于較為復(fù)雜的拓?fù)涠陨腥狈θ中?，容易陷入局部最?yōu)，且當(dāng)所有任務(wù)間的數(shù)據(jù)傳輸速率一致時(shí)，該算法無(wú)法工作。

為了改進(jìn)Storm默認(rèn)調(diào)度算法、克服已有相關(guān)研究的不足，本文提出一種Storm環(huán)境下基于權(quán)重的任務(wù)調(diào)度算法(Task Scheduling Algorithm based on Weight in Storm，TSAW-Storm)。該算法根據(jù)實(shí)時(shí)監(jiān)測(cè)到的負(fù)載數(shù)據(jù)，為拓?fù)渲邪娜蝿?wù)和數(shù)據(jù)流分別賦予不同的點(diǎn)權(quán)和邊權(quán)，并根據(jù)本文提出的負(fù)載均衡模型和最優(yōu)通信模型的要求，將任務(wù)調(diào)度到合適的工作節(jié)點(diǎn)內(nèi)。實(shí)驗(yàn)結(jié)果表明，相對(duì)于Storm默認(rèn)調(diào)度算法和文獻(xiàn)[20]的在線調(diào)度算法，TSAW-Storm在Storm集群系統(tǒng)延遲、通信開(kāi)銷和負(fù)載均衡方面均有所改進(jìn)。

1 Storm作業(yè)模型

在Storm中，一個(gè)流式作業(yè)稱為一個(gè)拓?fù)?，表示為一個(gè)有向無(wú)環(huán)圖，由組件和數(shù)據(jù)流共同構(gòu)成。組件分為Spout和Bolt兩種：其中Spout為數(shù)據(jù)源編程單元，用于為拓?fù)溥\(yùn)行提供數(shù)據(jù)；Bolt為數(shù)據(jù)處理編程單元，用于實(shí)現(xiàn)拓?fù)渲械奶幚磉壿?。?shù)據(jù)流是由無(wú)限的元組組成的序列，是Storm中對(duì)傳遞的數(shù)據(jù)進(jìn)行的抽象，可通過(guò)不同的流組模式實(shí)現(xiàn)組件之間的數(shù)據(jù)流傳輸。如圖1所示，ca和cb為數(shù)據(jù)源編程單元Spout，其余組件為數(shù)據(jù)處理編程單元Bolt，所有箭線為數(shù)據(jù)流；特別地，組件cf和cg為數(shù)據(jù)終點(diǎn)，通常用于將最終數(shù)據(jù)展示至終端或持久化至數(shù)據(jù)庫(kù)。

圖1 拓?fù)溥壿嬆Ｐ?Fig. 1 Logical model of a topology

為提高拓?fù)鋱?zhí)行的并行度，每個(gè)組件均可同時(shí)運(yùn)行多個(gè)實(shí)例，稱之為任務(wù)。任務(wù)是各組件最終執(zhí)行的代碼單元。設(shè)tij表示組件ci運(yùn)行的第j個(gè)實(shí)例，sij,kl表示任務(wù)tij向任務(wù)tkl發(fā)送的數(shù)據(jù)流。數(shù)據(jù)流通過(guò)描述拓?fù)渲袛?shù)據(jù)的流向，將上游任務(wù)和下游任務(wù)關(guān)聯(lián)起來(lái)，由此提出如下關(guān)聯(lián)任務(wù)的概念。

定義1 關(guān)聯(lián)任務(wù)。對(duì)于任意任務(wù)tgh、tij與tkl，若存在任務(wù)tgh向任務(wù)tij發(fā)送的數(shù)據(jù)流sgh,ij與任務(wù)tij向任務(wù)tkl發(fā)送的數(shù)據(jù)流sij,kl，則任務(wù)tgh與tkl統(tǒng)稱為任務(wù)tij的關(guān)聯(lián)任務(wù)。

圖2即為圖1的一種實(shí)例模型。特別地，當(dāng)組件ci的實(shí)例數(shù)量為1時(shí)，定義ti1=ti?？梢钥吹絚d的實(shí)例數(shù)量為3，cf的實(shí)例數(shù)量為2，其余組件的實(shí)例數(shù)量為1。以任務(wù)td1為例，其上游任務(wù)ta與tb以及下游任務(wù)tf1與tf2均稱為任務(wù)td1的關(guān)聯(lián)任務(wù)。

圖2 拓?fù)鋵?shí)例模型 Fig. 2 Instance model of a topology

在Storm集群中，資源池由一系列工作節(jié)點(diǎn)構(gòu)成，定義該集合為N={n1,n2,…,n|N|}。每個(gè)工作節(jié)點(diǎn)內(nèi)配置有若干個(gè)槽，每個(gè)槽只能容納一個(gè)工作進(jìn)程。文獻(xiàn)[12]通過(guò)Storm吞吐量測(cè)試[21]表明，對(duì)于單個(gè)拓?fù)涠?，若在一個(gè)工作節(jié)點(diǎn)內(nèi)分配多個(gè)工作進(jìn)程(即占用多個(gè)槽)，將會(huì)增加進(jìn)程間通信開(kāi)銷進(jìn)而導(dǎo)致運(yùn)行效率的下降。因此，本文僅在一個(gè)工作節(jié)點(diǎn)內(nèi)分配一個(gè)工作進(jìn)程，此時(shí)Storm默認(rèn)的輪詢調(diào)度算法可簡(jiǎn)化為一個(gè)拓?fù)渲邪乃腥蝿?wù)在各工作節(jié)點(diǎn)上的均勻分配，任務(wù)與工作節(jié)點(diǎn)間的對(duì)應(yīng)關(guān)系可定義如下。

定義2 任務(wù)分配法則。若任務(wù)tij分配到了工作節(jié)點(diǎn)nk上，則記f(tij)=nk或f-1(nk)=tij；若任務(wù)集合Tnk={t11,t12,…,tij,…}分配到了工作節(jié)點(diǎn)nk上，則記f(Tnk)=nk或f-1(nk)=Tnk，其中f即為任務(wù)或任務(wù)集合在工作節(jié)點(diǎn)上的分配法則。如圖3為圖2的拓?fù)溥\(yùn)行于包含有3個(gè)工作節(jié)點(diǎn)的Storm集群中的任務(wù)分配模型，若以工作節(jié)點(diǎn)n1及運(yùn)行在該工作節(jié)點(diǎn)上的任務(wù)集合為例，可表示為：f({td1,tc,tf1})=n1，f-1(n1)={td1,tc,tf1}。

圖3 任務(wù)分配模型 Fig. 3 Model for task assignment

由圖3可知，Storm系統(tǒng)中的任務(wù)之間存在兩種通信模式，分別是類似于任務(wù)td1與tf2之間的節(jié)點(diǎn)間通信以及類似于任務(wù)td1與tf1之間的節(jié)點(diǎn)內(nèi)通信。其中節(jié)點(diǎn)間通信受制于當(dāng)前環(huán)境下的網(wǎng)絡(luò)帶寬和帶寬利用率大小，開(kāi)銷往往很大；而節(jié)點(diǎn)內(nèi)通信與網(wǎng)絡(luò)無(wú)關(guān)，由于一個(gè)任務(wù)運(yùn)行于一個(gè)工作線程內(nèi)，因此其通信類型僅為進(jìn)程內(nèi)的線程級(jí)通信，開(kāi)銷很小并可忽略不計(jì)[14]。然而Storm默認(rèn)輪詢的任務(wù)調(diào)度算法并未兼顧到這兩種通信模式的差異性，從而導(dǎo)致較大的節(jié)點(diǎn)間通信開(kāi)銷。此外，由于各組件自身業(yè)務(wù)邏輯的不同，CPU占用率必然存在差異；即使是同一個(gè)組件中各個(gè)業(yè)務(wù)邏輯相同的任務(wù)，也將由于部分流組模式(如Field Grouping)的限制，并不會(huì)將其接收到的所有數(shù)據(jù)流均分到各實(shí)例中，故各任務(wù)的計(jì)算開(kāi)銷依然存在差異，輪詢的任務(wù)分配方式無(wú)法保證集群中各工作節(jié)點(diǎn)的負(fù)載均衡。為了更好地評(píng)估任務(wù)的計(jì)算開(kāi)銷和任務(wù)間傳輸?shù)臄?shù)據(jù)流大小，提出如下帶權(quán)拓?fù)涞母拍睢?/p>

定義3 帶權(quán)拓?fù)?Weighted Topology, WT)。設(shè)任務(wù)tij占用的CPU資源大小為wtij，任務(wù)tij與tkl之間傳輸?shù)臄?shù)據(jù)流大小為wsij,kl，則圖2的拓?fù)鋵?shí)例模型中各任務(wù)和任務(wù)間的數(shù)據(jù)流可分別使用wtij和wsij,kl構(gòu)成拓?fù)涞狞c(diǎn)權(quán)和邊權(quán)，其值可通過(guò)后文提出的負(fù)載監(jiān)視模塊進(jìn)行實(shí)時(shí)獲取。這樣的拓?fù)鋵?shí)例模型稱作帶權(quán)拓?fù)洹?/p>

2 問(wèn)題建模與分析

本節(jié)在帶權(quán)拓?fù)涞幕A(chǔ)之上建立負(fù)載均衡模型與最優(yōu)通信模型。其中負(fù)載均衡模型建立了各工作節(jié)點(diǎn)理想負(fù)載與實(shí)際負(fù)載間差異大小的度量指標(biāo)，可為調(diào)度算法運(yùn)行時(shí)的終止條件和運(yùn)行后的負(fù)載均衡效果評(píng)估提供理論依據(jù)；最優(yōu)通信模型則證明了節(jié)點(diǎn)間數(shù)據(jù)流傳輸代價(jià)與節(jié)點(diǎn)內(nèi)數(shù)據(jù)流傳輸代價(jià)此消彼長(zhǎng)的轉(zhuǎn)化關(guān)系，為最小化通信開(kāi)銷的任務(wù)遷移過(guò)程提供了決策原則。

2.1 負(fù)載均衡模型

設(shè)某一帶權(quán)拓?fù)渲邪娜蝿?wù)集合為T，nx為工作節(jié)點(diǎn)集合N中任意一個(gè)工作節(jié)點(diǎn)，工作節(jié)點(diǎn)nk上分配的任務(wù)集合為f-1(nk)，工作節(jié)點(diǎn)nl(k≠l)上分配的任務(wù)集合為f-1(nl)，則必然有：

(1)

且：

f-1(nk)∩f-1(nl)=?;k≠l

(2)

記Wnx為工作節(jié)點(diǎn)nx的CPU負(fù)載，其值為分配給工作節(jié)點(diǎn)nx上的所有任務(wù)需要占用的CPU資源總量，即:

(3)

記W為Storm集群的CPU負(fù)載總和，即集群中各工作節(jié)點(diǎn)的CPU負(fù)載總量。在同構(gòu)環(huán)境下，各工作節(jié)點(diǎn)的CPU負(fù)載隨任務(wù)分配模型的變化而此消彼長(zhǎng)，但W始終不變，其計(jì)算方法為:

(4)

若將集群中的CPU負(fù)載總和均勻分布到各工作節(jié)點(diǎn)上，則每個(gè)工作節(jié)點(diǎn)需容納的CPU負(fù)載為:

(5)

式(5)表示在理想狀態(tài)下達(dá)到負(fù)載均衡后各工作節(jié)點(diǎn)的CPU負(fù)載情況。事實(shí)上，集群中各工作節(jié)點(diǎn)不可能達(dá)到完全的負(fù)載均衡狀態(tài)，故使用式(6)標(biāo)準(zhǔn)差來(lái)衡量各工作節(jié)點(diǎn)的實(shí)際負(fù)載與理想負(fù)載的偏離程度。標(biāo)準(zhǔn)差越小則表示各工作節(jié)點(diǎn)間的負(fù)載差異越小，負(fù)載越為均衡。

(6)

2.2 最優(yōu)通信模型

如第1章所述，Storm系統(tǒng)中任務(wù)之間的通信模式可分為節(jié)點(diǎn)間通信和節(jié)點(diǎn)內(nèi)通信，其中節(jié)點(diǎn)間的通信開(kāi)銷遠(yuǎn)大于節(jié)點(diǎn)內(nèi)的通信開(kāi)銷。因此，若尋求Storm系統(tǒng)中通信模式的優(yōu)化途徑，需令節(jié)點(diǎn)間通信開(kāi)銷達(dá)到最小，即盡可能減少工作節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)流總和，可表示為:

(7)

定理1 最優(yōu)通信開(kāi)銷原則。最小化節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)流大小等價(jià)于最大化節(jié)點(diǎn)內(nèi)傳輸?shù)臄?shù)據(jù)流大小，即式(7)等價(jià)于:

(8)

證明 由第1章Storm作業(yè)模型可知，拓?fù)湟坏┨峤坏郊?，拓?fù)鋵?shí)例模型即固定下來(lái)，其包含的任務(wù)總數(shù)和數(shù)據(jù)流總數(shù)不可改變。因此在不發(fā)生擁塞的情況下，總數(shù)據(jù)流大小為一定值C，即:

(9)

證畢。

由定理1可知，在進(jìn)行Storm系統(tǒng)任務(wù)調(diào)度時(shí)，為了達(dá)到最優(yōu)通信模型的要求，應(yīng)盡可能地把通信頻繁的任務(wù)調(diào)度到同一個(gè)工作節(jié)點(diǎn)上，以最大限度地降低節(jié)點(diǎn)間通信開(kāi)銷。

3 基于權(quán)重的任務(wù)調(diào)度算法

為了達(dá)到上述負(fù)載均衡模型和最優(yōu)通信模型的要求，本章提出Storm環(huán)境下基于權(quán)重的任務(wù)調(diào)度算法(TSAW-Storm)，并進(jìn)行算法評(píng)估與部署。

3.1 邊權(quán)增益

TSAW-Storm旨在盡可能均衡分配各工作節(jié)點(diǎn)負(fù)載的前提下，盡量減少節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)流總和。而由最優(yōu)通信模型可知，當(dāng)任務(wù)分配法則發(fā)生變化時(shí)，節(jié)點(diǎn)間數(shù)據(jù)流與節(jié)點(diǎn)內(nèi)數(shù)據(jù)流將相互轉(zhuǎn)化。為了量化這一過(guò)程，提出如下邊權(quán)增益的概念。

定義4 邊權(quán)增益。對(duì)于任務(wù)tij，若存在任務(wù)分配法則f(tij)=np，設(shè)Ttij,np為與任務(wù)tij關(guān)聯(lián)且位于工作節(jié)點(diǎn)np上的任務(wù)集合，Ttij,nq為與任務(wù)tij關(guān)聯(lián)且位于工作節(jié)點(diǎn)nq上的任務(wù)集合，且p≠q，若將任務(wù)tij由工作節(jié)點(diǎn)np遷移至工作節(jié)點(diǎn)nq，則邊權(quán)增益可表示為：

(10)

以圖3為例，對(duì)于任務(wù)td3而言，位于該任務(wù)所在工作節(jié)點(diǎn)n3上的關(guān)聯(lián)任務(wù)集合為Ttd3,n3={ta}，位于工作節(jié)點(diǎn)n2上的關(guān)聯(lián)任務(wù)集合為Ttd3,n2={tb,tf2}，若將任務(wù)td3由工作節(jié)點(diǎn)n3遷移至工作節(jié)點(diǎn)n2，則數(shù)據(jù)流sb,d3和sd3,f2將由節(jié)點(diǎn)間數(shù)據(jù)流轉(zhuǎn)化為節(jié)點(diǎn)內(nèi)數(shù)據(jù)流，而數(shù)據(jù)流sa,d3將由節(jié)點(diǎn)內(nèi)數(shù)據(jù)流轉(zhuǎn)化為節(jié)點(diǎn)間數(shù)據(jù)流，其邊權(quán)增益的計(jì)算方法為：

Gtd3=wsb,d3+wsd3,f2-wsa,d3

(11)

可見(jiàn)，邊權(quán)增益反映了任務(wù)遷移前后節(jié)點(diǎn)間數(shù)據(jù)流的差值。邊權(quán)增益越大，則意味著將更多的節(jié)點(diǎn)間數(shù)據(jù)流轉(zhuǎn)化為了節(jié)點(diǎn)內(nèi)數(shù)據(jù)流，這符合2.2節(jié)中最優(yōu)通信模型的要求，是后續(xù)算法的設(shè)計(jì)目標(biāo)之一。

3.2 算法描述

計(jì)算邊權(quán)增益的前提是獲取帶權(quán)拓?fù)涞年P(guān)聯(lián)任務(wù)及其對(duì)應(yīng)邊權(quán)；而為了在獲取最大化邊權(quán)增益的同時(shí)不違背負(fù)載均衡模型的約束，帶權(quán)拓?fù)涞狞c(diǎn)權(quán)及各工作節(jié)點(diǎn)的CPU負(fù)載值同樣不可或缺。因此在TSAW-Storm的設(shè)計(jì)過(guò)程中，需在用戶提交拓?fù)浜笫紫葓?zhí)行Storm默認(rèn)調(diào)度算法，并當(dāng)拓?fù)溥\(yùn)行穩(wěn)定后完成上述數(shù)據(jù)的采集和存儲(chǔ)。當(dāng)工作節(jié)點(diǎn)的CPU負(fù)載持續(xù)不均，即集群中所有工作節(jié)點(diǎn)的最大CPU負(fù)載與最小CPU負(fù)載之差在時(shí)間間隔τ內(nèi)持續(xù)大于閾值ε時(shí)，則觸發(fā)算法1進(jìn)行任務(wù)的重新調(diào)度。具體步驟如下：

算法1 TSAW-Storm。

2)對(duì)于?nx∈N′，如果nx中存在拓?fù)溥\(yùn)行所需要的數(shù)據(jù)源且n|N|中分配的任務(wù)包含有Spout實(shí)例，或nx中不存在數(shù)據(jù)源但n|N|中分配的任務(wù)不包含有Bolt實(shí)例，則隨機(jī)將工作節(jié)點(diǎn)n|N|中的一個(gè)Spout實(shí)例遷移至工作節(jié)點(diǎn)nx；否則隨機(jī)將工作節(jié)點(diǎn)n|N|中的一個(gè)Bolt實(shí)例遷移至工作節(jié)點(diǎn)nx。設(shè)從工作節(jié)點(diǎn)n|N|中遷出的任務(wù)為tij，則有Tnx←{tij}，Tn|N|←Tn|N|-{tij}，同時(shí)根據(jù)式(3)更新工作節(jié)點(diǎn)CPU負(fù)載Wn|N|和Wnx。

3)獲取與Tnx中各任務(wù)關(guān)聯(lián)且位于工作節(jié)點(diǎn)n|N|上的任務(wù)集合，記為Tnx,n|N|。

4)將Tnx,n|N|中邊權(quán)增益最大的任務(wù)tkl遷移至工作節(jié)點(diǎn)nx，此時(shí)Tnx←Tnx∪{tkl}，Tn|N|←Tn|N|-{tkl}，同時(shí)根據(jù)式(3)更新工作節(jié)點(diǎn)CPU負(fù)載Wn|N|和Wnx。

6)重復(fù)第2)～5)步，逐步構(gòu)建N′中各工作節(jié)點(diǎn)上分配的任務(wù)集合。

7)執(zhí)行任務(wù)分配，即對(duì)于x∈1,2,…,|N|，實(shí)施f-1(nx)←Tnx。

3.3 算法解釋與算法評(píng)估

在算法1的執(zhí)行過(guò)程中，第1)步獲取算法后續(xù)計(jì)算所需數(shù)據(jù)，并進(jìn)行各項(xiàng)初始化操作。第2)步完成當(dāng)前工作節(jié)點(diǎn)上的第一個(gè)任務(wù)分配，這是進(jìn)行邊權(quán)增益計(jì)算的前提。在第一個(gè)任務(wù)的選擇過(guò)程中，如果待遷入任務(wù)的工作節(jié)點(diǎn)上存儲(chǔ)有數(shù)據(jù)源，則將拓?fù)渲械臄?shù)據(jù)源編程單元Spout分配到該工作節(jié)點(diǎn)上，目的是盡量避免Spout將遠(yuǎn)程數(shù)據(jù)源讀入拓?fù)鋾r(shí)帶來(lái)的節(jié)點(diǎn)間通信開(kāi)銷，提高任務(wù)本地化執(zhí)行的概率，進(jìn)而提高Storm系統(tǒng)的運(yùn)行效率。然而，將Spout中包含的所有任務(wù)均分配到數(shù)據(jù)源所在工作節(jié)點(diǎn)上的做法是不可取的，原因有以下兩點(diǎn)：其一，拓?fù)渲蠸pout的各個(gè)任務(wù)彼此之間并無(wú)關(guān)聯(lián)，若將其分配到同一個(gè)工作節(jié)點(diǎn)上，勢(shì)必導(dǎo)致更小的節(jié)點(diǎn)內(nèi)數(shù)據(jù)流，與最優(yōu)通信模型的要求不符；其二，Spout中的每一個(gè)任務(wù)均需讀取其下游Bolt運(yùn)行所需的所有數(shù)據(jù)，輸出的數(shù)據(jù)流總量必然很大，若各任務(wù)的分布過(guò)于集中，勢(shì)必給其所在工作節(jié)點(diǎn)與其下游Bolt所在工作節(jié)點(diǎn)之間帶來(lái)過(guò)多的節(jié)點(diǎn)間數(shù)據(jù)流，進(jìn)而導(dǎo)致網(wǎng)絡(luò)擁塞，效果適得其反。為了避免上述情況的發(fā)生，第2)步僅為存在數(shù)據(jù)源的每個(gè)工作節(jié)點(diǎn)初始化分配一個(gè)Spout實(shí)例。第3)～6)步嚴(yán)格遵循負(fù)載均衡模型和最優(yōu)通信模型的要求，根據(jù)最大化邊權(quán)增益原則，逐步選擇當(dāng)前情況下最合適的任務(wù)從工作節(jié)點(diǎn)n|N|上遷出，并及時(shí)更新任務(wù)遷移后相關(guān)工作節(jié)點(diǎn)CPU負(fù)載的預(yù)測(cè)值，最終確定所有工作節(jié)點(diǎn)上的任務(wù)分配法則。這一過(guò)程存在遍歷關(guān)聯(lián)任務(wù)、計(jì)算最大邊權(quán)增益等需要較大時(shí)間開(kāi)銷的重復(fù)性工作，時(shí)間復(fù)雜度為O(|S|·|N|)(S為帶權(quán)拓?fù)浒臄?shù)據(jù)流集合)；然而以上步驟實(shí)質(zhì)上并未改變?nèi)蝿?wù)分配模型，拓?fù)湟廊徽＿\(yùn)行，用戶的實(shí)時(shí)性作業(yè)需求并未受到影響。直到步驟7)時(shí)才執(zhí)行具體的任務(wù)分配，此時(shí)需重新分配拓?fù)渲懈魅蝿?wù)在各工作節(jié)點(diǎn)中的映射關(guān)系，時(shí)間開(kāi)銷為O(|T|)；在這一時(shí)刻，拓?fù)鋱?zhí)行會(huì)不可避免地存在短暫的中斷，延遲將有所增加，具體情況將在第4章實(shí)驗(yàn)中進(jìn)行評(píng)估。

3.4 算法實(shí)現(xiàn)與部署

為實(shí)現(xiàn)并部署算法1，需使用Storm為開(kāi)發(fā)人員提供的可插拔自定義任務(wù)調(diào)度器，即實(shí)現(xiàn)接口org.apache.storm.scheduler.IScheduler中的方法public void schedule(Topologies topologies, Cluster cluster)。改進(jìn)后的Storm架構(gòu)如圖4所示。需要說(shuō)明的是，一個(gè)完整的Storm分布式系統(tǒng)由運(yùn)行進(jìn)程N(yùn)imbus的主控節(jié)點(diǎn)、運(yùn)行進(jìn)程Supervisor的工作節(jié)點(diǎn)、運(yùn)行進(jìn)程UI的控制臺(tái)節(jié)點(diǎn)以及運(yùn)行進(jìn)程ZooKeeper的協(xié)調(diào)節(jié)點(diǎn)共同構(gòu)成，而圖4并未修改控制臺(tái)節(jié)點(diǎn)和協(xié)調(diào)節(jié)點(diǎn)的工作機(jī)制，故將其省略，僅保留新增模塊以及與新增模塊相關(guān)聯(lián)的部分，其中新增加的四個(gè)模塊如下：

1)負(fù)載監(jiān)視模塊。負(fù)責(zé)在一定的時(shí)間窗口內(nèi)，收集各任務(wù)占用的CPU負(fù)載信息及各任務(wù)之間的數(shù)據(jù)流大小分別作為帶權(quán)拓?fù)涞狞c(diǎn)權(quán)和邊權(quán)。由于Storm中的一個(gè)任務(wù)運(yùn)行于一個(gè)工作線程中，因此為了獲取任務(wù)執(zhí)行過(guò)程中占用的CPU資源大小以及各對(duì)任務(wù)在單位時(shí)間傳輸?shù)脑M數(shù)量，需實(shí)時(shí)追蹤各任務(wù)對(duì)應(yīng)的線程ID及其相關(guān)聯(lián)的所有線程。其中各線程的CPU資源占用大小可通過(guò)ThreadMXBean類的getThreadCpuTime(long id)方法獲取到其占用的CPU時(shí)間，并與其所處工作節(jié)點(diǎn)的CPU主頻相乘求得；各對(duì)線程間傳輸?shù)臄?shù)據(jù)流大小需使用計(jì)數(shù)器變量統(tǒng)計(jì)各線程接收到的上游線程發(fā)送的元組數(shù)量，并與時(shí)間窗口容量相除獲得數(shù)據(jù)流傳輸速率。具體實(shí)現(xiàn)需添加在組件中各Spout的open()和nextTuple()方法以及各Bolt的prepare()和execute()方法中。

2)MySQL數(shù)據(jù)庫(kù)。負(fù)責(zé)存儲(chǔ)歷次任務(wù)分配信息以及負(fù)載監(jiān)視模塊傳來(lái)的負(fù)載信息和數(shù)據(jù)流大小，并實(shí)時(shí)更新。

3)任務(wù)調(diào)度模塊。負(fù)責(zé)讀取數(shù)據(jù)庫(kù)中的信息，并在負(fù)載持續(xù)不均時(shí)觸發(fā)算法1以及時(shí)作出任務(wù)調(diào)度決策。

4)自定義調(diào)度器。覆蓋主控節(jié)點(diǎn)中Storm默認(rèn)輪詢的調(diào)度算法，負(fù)責(zé)讀取任務(wù)調(diào)度模塊生成的調(diào)度決策并執(zhí)行任務(wù)調(diào)度。

圖4 改進(jìn)的Storm系統(tǒng)架構(gòu) Fig. 4 Improved architecture of Storm

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境與分析

實(shí)驗(yàn)環(huán)境采用相同硬件配置的PC搭建一個(gè)包含有12個(gè)節(jié)點(diǎn)的Storm集群，其中共同運(yùn)行進(jìn)程N(yùn)imbus、進(jìn)程UI和數(shù)據(jù)庫(kù)服務(wù)MySQL的節(jié)點(diǎn)1個(gè)，運(yùn)行進(jìn)程ZooKeeper的協(xié)調(diào)節(jié)點(diǎn)3個(gè)，其余8個(gè)為運(yùn)行進(jìn)程Supervisor的工作節(jié)點(diǎn)。表1列出了各節(jié)點(diǎn)具體的軟硬件配置。

表1 Storm集群軟硬件配置Tab. 1 Hardware and software configuration of Storm cluster

實(shí)驗(yàn)基于Intel公司Zhang[22]發(fā)布在GitHub上的基準(zhǔn)測(cè)試storm-benchmark-master，本文選取其中CPU敏感型(CPU-Sensitive)的WordCount構(gòu)建拓?fù)?，?shù)據(jù)源為其自身提供的原版英國(guó)歷史小說(shuō)《雙城記》，格式為txt。原著中各單詞出現(xiàn)的頻率不盡相同，因此在實(shí)際生產(chǎn)環(huán)境中具有一定的代表性，若此時(shí)使用Storm默認(rèn)輪詢的調(diào)度算法，極易在計(jì)數(shù)過(guò)程中發(fā)生各工作節(jié)點(diǎn)CPU負(fù)載不均的情況，進(jìn)而觸發(fā)TSAW-Storm，便于評(píng)估算法的執(zhí)行效果。表2列出了WordCount運(yùn)行時(shí)的各項(xiàng)參數(shù)配置及其相關(guān)說(shuō)明。需要進(jìn)一步解釋的是，表2中工作進(jìn)程個(gè)數(shù)設(shè)置為8，意味著8個(gè)工作節(jié)點(diǎn)中各分配1個(gè)工作進(jìn)程，這樣便消除了同一節(jié)點(diǎn)內(nèi)工作進(jìn)程間的通信開(kāi)銷，與文中任務(wù)分配模型的描述相符；Acker用來(lái)跟蹤元組的處理結(jié)果，其值默認(rèn)設(shè)置與工作進(jìn)程個(gè)數(shù)相同；Spout緩存隊(duì)列長(zhǎng)度可對(duì)Spout的元組發(fā)射速率進(jìn)行控制，并進(jìn)而決定Storm系統(tǒng)的吞吐量，通過(guò)多次實(shí)驗(yàn)后設(shè)置該集群配置下的合適值為50；時(shí)間間隔tau和閾值epsilon即為3.2節(jié)中敘述的τ與ε，表示若集群中所有工作節(jié)點(diǎn)的最大CPU負(fù)載與最小CPU負(fù)載之差在每80 s時(shí)間間隔內(nèi)持續(xù)超過(guò)20%時(shí)，觸發(fā)TSAW-Storm，該值可根據(jù)Storm默認(rèn)調(diào)度算法的運(yùn)行結(jié)果進(jìn)行人為調(diào)整。

表2 WordCount參數(shù)配置Tab. 2 Parameter configuration of WordCount

為驗(yàn)證TSAW-Storm的有效性，文中除了與Storm默認(rèn)調(diào)度算法進(jìn)行對(duì)比之外，還部署了文獻(xiàn)[20]的Storm自適應(yīng)在線調(diào)度算法(online scheduler)。該算法在運(yùn)行后取得了較好的調(diào)度效果，其核心思想是實(shí)時(shí)監(jiān)測(cè)各工作節(jié)點(diǎn)和各任務(wù)的CPU負(fù)載情況以及各對(duì)任務(wù)之間的數(shù)據(jù)流大小，當(dāng)存在CPU負(fù)載持續(xù)超出閾值的工作節(jié)點(diǎn)時(shí)觸發(fā)任務(wù)重分配機(jī)制，即首先按照遞減的順序排列拓?fù)渲懈鲗?duì)任務(wù)之間的數(shù)據(jù)流大小，然后將任務(wù)逐對(duì)調(diào)度至那些令其重分配后產(chǎn)生最低CPU負(fù)載的工作進(jìn)程和工作節(jié)點(diǎn)中。表3列出了采用在線調(diào)度算法進(jìn)行對(duì)比實(shí)驗(yàn)時(shí)的各項(xiàng)參數(shù)配置。需要說(shuō)明的是，為了與TSAW-Storm在同等CPU負(fù)載條件下觸發(fā)任務(wù)調(diào)度，各項(xiàng)參數(shù)均通過(guò)多次實(shí)驗(yàn)進(jìn)行微調(diào)并最終確定了理想值，其中參數(shù)reschedule.timeout為在線調(diào)度算法的觸發(fā)周期，參數(shù)capacity為在線調(diào)度算法中CPU的使用率上限，這兩項(xiàng)參數(shù)分別與本文算法中的τ與ε存在對(duì)應(yīng)關(guān)系。

表3 在線調(diào)度算法參數(shù)設(shè)置Tab. 3 Parameter configuration of online scheduler

4.2 實(shí)驗(yàn)結(jié)果與分析

本節(jié)通過(guò)實(shí)驗(yàn)評(píng)估TSAW-Storm在系統(tǒng)延遲、通信開(kāi)銷和負(fù)載均衡三個(gè)方面的表現(xiàn)。為便于數(shù)據(jù)統(tǒng)計(jì)，以下各項(xiàng)測(cè)試均在基準(zhǔn)測(cè)試的配置文件中設(shè)置metrics.poll為5 000，metrics.time為300 000，其單位為ms，即每組實(shí)驗(yàn)每5 s進(jìn)行一次采樣，總時(shí)長(zhǎng)為5 min。

4.2.1 系統(tǒng)延遲測(cè)試

延遲表明一個(gè)元組從Spout發(fā)射到最終被成功處理的時(shí)間消耗，反映了拓?fù)鋱?zhí)行一次的響應(yīng)時(shí)間，刻畫了系統(tǒng)的運(yùn)行效率。圖5統(tǒng)計(jì)了WordCount在Storm默認(rèn)調(diào)度算法(圖例中Default)、在線調(diào)度算法(圖例中Online)與基于權(quán)重的任務(wù)調(diào)度算法(圖例中TSAW-Storm)下的系統(tǒng)延遲。

圖5 三種任務(wù)調(diào)度算法下的系統(tǒng)延遲對(duì)比 Fig. 5 Comparison of latency among three task scheduling algorithms

如圖5所示，從實(shí)驗(yàn)開(kāi)始到第一個(gè)峰值結(jié)束時(shí)間段表示拓?fù)涮峤粫r(shí)的初次任務(wù)分配，此時(shí)的任務(wù)分配均遵循Storm默認(rèn)調(diào)度算法。其中0～25 s的零延遲階段表示任務(wù)分配的計(jì)算與同步過(guò)程，由于此時(shí)存在未被成功調(diào)度的任務(wù)，拓?fù)鋵?shí)例模型并不完整，故無(wú)法形成一條完整的數(shù)據(jù)流；同時(shí)，Spout中的任務(wù)往往首先完成分配并開(kāi)始發(fā)射數(shù)據(jù)，在其下游Bolt中的任務(wù)未被成功調(diào)度的情況下，Spout緩存隊(duì)列中的元組因無(wú)法及時(shí)得到處理而導(dǎo)致系統(tǒng)延遲隨著運(yùn)行時(shí)間的推進(jìn)而不斷增加，進(jìn)而出現(xiàn)30～35 s的極高峰值。第一個(gè)峰值過(guò)后，系統(tǒng)延遲逐漸趨于收斂，在集群中各工作節(jié)點(diǎn)不發(fā)生意外的情況下，默認(rèn)調(diào)度算法將不再實(shí)施任務(wù)調(diào)度，系統(tǒng)延遲的保持在11.2 ms左右；而此時(shí)在線調(diào)度算法與TSAW-Storm開(kāi)始收集集群中各工作節(jié)點(diǎn)以及工作節(jié)點(diǎn)上各任務(wù)占用的CPU負(fù)載信息和各任務(wù)之間的數(shù)據(jù)流大小，為各任務(wù)未來(lái)的優(yōu)化配置提供決策依據(jù)。

隨著運(yùn)行時(shí)間的推移，第90 s時(shí)在線調(diào)度算法觸發(fā)，此時(shí)所有任務(wù)在各工作節(jié)點(diǎn)上重新分配，系統(tǒng)暫停一切數(shù)據(jù)流傳輸，故系統(tǒng)延遲在90～100 s時(shí)間間隔內(nèi)無(wú)法觀測(cè)；第105～110 s時(shí)系統(tǒng)延遲達(dá)到極高峰，隨后迅速下降，整個(gè)任務(wù)重調(diào)度過(guò)程相當(dāng)于拓?fù)涮峤粫r(shí)的初始化任務(wù)分配，執(zhí)行開(kāi)銷較大。在線調(diào)度算法觸發(fā)的原因是此時(shí)集群中已經(jīng)存在CPU負(fù)載在80 s內(nèi)超過(guò)70%的工作節(jié)點(diǎn)，而之所以圖5中第90 s才出現(xiàn)系統(tǒng)延遲的極端變化，其原因有以下幾點(diǎn)：1)主控節(jié)點(diǎn)的重調(diào)度指令分發(fā)到各工作節(jié)點(diǎn)需要消耗一定的時(shí)間；2)調(diào)度發(fā)生時(shí)，Spout雖然不再發(fā)射數(shù)據(jù)，但整個(gè)拓?fù)渲腥源嬖谏倭课幢煌耆幚淼臄?shù)據(jù)流，Acker機(jī)制仍在進(jìn)行系統(tǒng)延遲的統(tǒng)計(jì)工作；3)采樣周期為一定值，統(tǒng)計(jì)誤差不可避免。由圖5可知，在線調(diào)度算法運(yùn)行時(shí)對(duì)系統(tǒng)的影響范圍在第90～115 s，最大延遲為91.9 ms；系統(tǒng)運(yùn)行穩(wěn)定后，延遲平均值約為8.50 ms，相對(duì)于Storm默認(rèn)調(diào)度算法降低約24.1%。

TSAW-Storm的觸發(fā)和執(zhí)行過(guò)程與在線調(diào)度算法類似。第90 s時(shí)TSAW-Storm觸發(fā)，原因是在80 s的觀測(cè)周期內(nèi)存在最大CPU負(fù)載與最小CPU負(fù)載之差持續(xù)大于20%的工作節(jié)點(diǎn)。與在線調(diào)度算法不同的是，TSAW-Storm觸發(fā)后的系統(tǒng)延遲在90～95 s時(shí)間間隔內(nèi)無(wú)法觀測(cè)，僅為在線調(diào)度算法的一半左右，且隨后發(fā)生的延遲最高峰值為27.5 ms，僅為在線調(diào)度算法最大延遲的29.9%，可見(jiàn)TSAW-Storm對(duì)Storm系統(tǒng)的正常運(yùn)行并未造成較大的影響。TSAW-Storm運(yùn)行結(jié)束后，系統(tǒng)運(yùn)行迅速趨于穩(wěn)定，延遲平均值穩(wěn)定在約7.84 ms，相對(duì)于在線調(diào)度算法降低約7.76%，相對(duì)于Storm默認(rèn)調(diào)度算法降低約30.0%。TSAW-Storm觸發(fā)時(shí)之所以對(duì)系統(tǒng)整體影響較小，是因?yàn)樵撍惴ㄊ紫扔芍骺毓?jié)點(diǎn)計(jì)算更優(yōu)的任務(wù)分配方案，這一過(guò)程并未改變?nèi)蝿?wù)分配模型，拓?fù)湟廊徽＿\(yùn)行；而后再根據(jù)計(jì)算結(jié)果一次性執(zhí)行任務(wù)分配，故影響系統(tǒng)正常運(yùn)行的時(shí)間很短， Spout緩存隊(duì)列中的元組等待處理的時(shí)間也較短，不會(huì)導(dǎo)致類似在線調(diào)度算法產(chǎn)生的突發(fā)延遲。而TSAW-Storm之所以在收斂后能夠形成較低的系統(tǒng)延遲，是因?yàn)樵撍惴ú煌谠诰€調(diào)度算法中逐對(duì)任務(wù)調(diào)度的方法，它針對(duì)帶權(quán)拓?fù)渲械拿恳粋€(gè)任務(wù)，均充分考慮了與其相關(guān)聯(lián)的所有數(shù)據(jù)流，其調(diào)度更具全局性。此外，TSAW-Storm提高了任務(wù)本地化執(zhí)行的概率，消除了一部分Spout中的任務(wù)讀取遠(yuǎn)程數(shù)據(jù)源時(shí)的網(wǎng)絡(luò)開(kāi)銷，這是導(dǎo)致系統(tǒng)延遲降低的又一個(gè)重要原因。

4.2.2 通信開(kāi)銷測(cè)試

本節(jié)討論基準(zhǔn)測(cè)試WordCount在Storm默認(rèn)調(diào)度算法、在線調(diào)度算法與TSAW-Storm下的工作節(jié)點(diǎn)間通信開(kāi)銷。圖6為采用三種不同調(diào)度算法時(shí)工作節(jié)點(diǎn)間單位時(shí)間的元組傳輸總量。

圖6 三種任務(wù)調(diào)度算法下的節(jié)點(diǎn)間數(shù)據(jù)流大小對(duì)比 Fig. 6 Comparison of inter-node tuple rate among three task scheduling algorithms

與圖5中的系統(tǒng)延遲類似，圖6中節(jié)點(diǎn)間數(shù)據(jù)流大小的統(tǒng)計(jì)結(jié)果亦可清晰反映在線調(diào)度算法與TSAW-Storm的觸發(fā)情況?？梢钥闯觯瑹o(wú)論是采用Storm默認(rèn)調(diào)度算法的初始化任務(wù)分配，還是在線調(diào)度算法與TSAW-Storm觸發(fā)后的優(yōu)化調(diào)度，節(jié)點(diǎn)間數(shù)據(jù)流大小均將經(jīng)歷一個(gè)從0迅速上升到正常狀態(tài)的過(guò)程，并不存在類似圖5中的峰值情況。這是因?yàn)楸?中對(duì)WordCount的Spout緩存隊(duì)列長(zhǎng)度作了合理限制，當(dāng)未被成功處理的元組達(dá)到緩存隊(duì)列的上限時(shí)，Spout將暫停發(fā)射數(shù)據(jù)流，因此并不會(huì)發(fā)生因元組大量累積而突發(fā)傳輸?shù)那闆r。由圖6可知，Storm默認(rèn)調(diào)度算法執(zhí)行且系統(tǒng)運(yùn)行趨于穩(wěn)定后(50～300 s)，節(jié)點(diǎn)間數(shù)據(jù)流大小的平均值約為92 446 tuple/s；而當(dāng)在線調(diào)度算法和TSAW-Storm觸發(fā)且系統(tǒng)穩(wěn)定運(yùn)行后(分別為125～300 s和115～300 s)，節(jié)點(diǎn)間數(shù)據(jù)流大小的平均值約分別為70 335 tuple/s和62 026 tuple/s，相比Storm默認(rèn)調(diào)度算法分別降低了23.9%和32.9%，其中TSAW-Storm相比在線調(diào)度算法執(zhí)行后的節(jié)點(diǎn)間數(shù)據(jù)流大小下降了11.8%?？梢?jiàn)，TSAW-Storm在降低節(jié)點(diǎn)間通信開(kāi)銷方面具有更為明顯的效果，其原因是TSAW-Storm中最大化邊權(quán)增益和Spout任務(wù)本地化的思想能夠最大范圍地考慮到整個(gè)帶權(quán)拓?fù)涞娜蝿?wù)間通信情況，從而將更多的節(jié)點(diǎn)間數(shù)據(jù)流轉(zhuǎn)化為節(jié)點(diǎn)內(nèi)數(shù)據(jù)流。而之所以TSAW-Storm在4.2.1節(jié)中降低的系統(tǒng)延遲不如降低的節(jié)點(diǎn)間數(shù)據(jù)流大小效果明顯，是因?yàn)樵诟黝怱torm基準(zhǔn)測(cè)試中，WordCount屬于CPU敏感型拓?fù)鋄22]，節(jié)點(diǎn)間數(shù)據(jù)流的減小僅可作為該類拓?fù)湫阅軆?yōu)化的方向之一，未來(lái)將針對(duì)拓?fù)涞淖陨硖匦蕴剿鞲嗫赡艿膬?yōu)化方向。

4.2.3 負(fù)載均衡測(cè)試

本節(jié)討論基準(zhǔn)測(cè)試WordCount在Storm默認(rèn)調(diào)度算法、在線調(diào)度算法與TSAW-Storm下分別運(yùn)行時(shí)集群的負(fù)載均衡情況。由于Storm默認(rèn)調(diào)度算法采用輪詢的方式分配任務(wù)，因此各工作節(jié)點(diǎn)上初始化分配的任務(wù)數(shù)量相同。然而WordCount數(shù)據(jù)源中各單詞出現(xiàn)的頻率存在很大差異，當(dāng)SplitBolt采用Field Grouping方式進(jìn)行數(shù)據(jù)流分發(fā)時(shí)，各CountBolt中的任務(wù)需要處理的數(shù)據(jù)流大小差異很大，單純采用輪詢方式進(jìn)行任務(wù)分配極易導(dǎo)致各工作節(jié)點(diǎn)的負(fù)載不均。在線調(diào)度算法與TSAW-Storm在任務(wù)重調(diào)度過(guò)程中充分考慮到不同任務(wù)負(fù)載的差異性，從而克服了默認(rèn)調(diào)度算法在負(fù)載均衡方面的不足。表4為采用這三類任務(wù)調(diào)度算法執(zhí)行任務(wù)分配后各工作節(jié)點(diǎn)的CPU負(fù)載均值。

由于在線調(diào)度算法和TSAW-Storm觸發(fā)前均使用Storm默認(rèn)調(diào)度算法執(zhí)行任務(wù)分配，因此可將表4中的Storm默認(rèn)調(diào)度算法(Default)執(zhí)行后的CPU負(fù)載看成是在線調(diào)度算法(Online)和TSAW-Storm觸發(fā)前各工作節(jié)點(diǎn)的資源占用情況。由表4可知，Storm默認(rèn)調(diào)度算法執(zhí)行后，各工作節(jié)點(diǎn)的負(fù)載不均現(xiàn)象較為嚴(yán)重，標(biāo)準(zhǔn)差高達(dá)12.66%，其中6號(hào)工作節(jié)點(diǎn)的CPU負(fù)載最高，7號(hào)工作節(jié)點(diǎn)的CPU負(fù)載最低，二者差值為33.4%。因最大CPU負(fù)載超出表3中設(shè)置的CPU使用率上限(capacity=70%)，且最大CPU負(fù)載與最小CPU負(fù)載之差也超出了表2中設(shè)置的閾值(epsilon=20%)，故在線調(diào)度算法和TSAW-Storm同時(shí)觸發(fā)，這與圖5中系統(tǒng)延遲以及圖6中節(jié)點(diǎn)間數(shù)據(jù)流大小的統(tǒng)計(jì)結(jié)果也是相吻合的。在線調(diào)度算法和TSAW-Storm執(zhí)行后，集群中各工作節(jié)點(diǎn)的CPU負(fù)載均低于70%且負(fù)載基本均衡，不必再次觸發(fā)任務(wù)調(diào)度；標(biāo)準(zhǔn)差分別為3.47%和3.26%，僅為Storm默認(rèn)調(diào)度算法的27.4%和25.8%?？梢?jiàn)兩種任務(wù)調(diào)度算法均能達(dá)到負(fù)載均衡的效果，且TSAW-Storm效果略優(yōu)，其執(zhí)行后的CPU負(fù)載標(biāo)準(zhǔn)差相比在線調(diào)度算法降低了5.93%。這是因?yàn)樵谙虺詈笠粋€(gè)工作節(jié)點(diǎn)之外的其他工作節(jié)點(diǎn)逐步遷入任務(wù)的過(guò)程中，每個(gè)工作節(jié)點(diǎn)實(shí)際容納的負(fù)載大小均不能超過(guò)其理想情況下的CPU負(fù)載，這比在線調(diào)度算法中每次尋找具有最低CPU負(fù)載的工作節(jié)點(diǎn)的做法在負(fù)載均衡方面更便于控制。然而通過(guò)表4可以發(fā)現(xiàn)，使用TSAW-Storm執(zhí)行任務(wù)調(diào)度后，8號(hào)工作節(jié)點(diǎn)的CPU負(fù)載將略低于其他7個(gè)工作節(jié)點(diǎn)，這是由于該調(diào)度算法的工作機(jī)制導(dǎo)致的：在算法1的初始化過(guò)程中，帶權(quán)拓?fù)渲械乃腥蝿?wù)都被擬分配至8號(hào)工作節(jié)點(diǎn)，而后再結(jié)合Spout任務(wù)本地化和最大化邊權(quán)增益的思想，將8號(hào)工作節(jié)點(diǎn)中的任務(wù)逐一分析并遷移至其他7個(gè)節(jié)點(diǎn)，直到各工作節(jié)點(diǎn)中分配的負(fù)載大小均在剛好大于其理想情況下的CPU負(fù)載為止。這種做法雖然不易導(dǎo)致節(jié)點(diǎn)過(guò)載，且能夠較好地保證1～7號(hào)節(jié)點(diǎn)的負(fù)載均衡，但可能導(dǎo)致位于8號(hào)工作節(jié)點(diǎn)上的任務(wù)被過(guò)多地遷出，進(jìn)而發(fā)生該工作節(jié)點(diǎn)的CPU負(fù)載略低于其他工作節(jié)點(diǎn)的情況。若需解決這一問(wèn)題，可在TSAW-Storm執(zhí)行結(jié)束后，在滿足最優(yōu)通信模型的前提下進(jìn)行少量任務(wù)交換，這將在未來(lái)繼續(xù)開(kāi)展研究。

表4 三種任務(wù)調(diào)度算法下的CPU負(fù)載對(duì)比Tab. 4 Comparison of CPU load among three task scheduling algorithms

5 結(jié)語(yǔ)

Storm默認(rèn)輪詢的任務(wù)調(diào)度算法并未考慮到各任務(wù)計(jì)算開(kāi)銷的差異以及任務(wù)之間不同類型的通信模式，在負(fù)載均衡和節(jié)點(diǎn)間通信開(kāi)銷方面仍存在較大的優(yōu)化空間。針對(duì)這一問(wèn)題，本文將各任務(wù)占用的CPU資源大小作為拓?fù)涞狞c(diǎn)權(quán)，任務(wù)間的數(shù)據(jù)流大小作為拓?fù)涞倪厵?quán)，提出帶權(quán)拓?fù)涞母拍?；并在此基礎(chǔ)上建立負(fù)載均衡模型和最優(yōu)通信模型，進(jìn)而提出Storm環(huán)境下基于權(quán)重的任務(wù)調(diào)度算法(TSAW-Storm)。該算法利用最大化邊權(quán)增益的思想逐步構(gòu)建起各工作節(jié)點(diǎn)中承載的任務(wù)集合，在保證集群負(fù)載均衡的同時(shí)，盡可能將節(jié)點(diǎn)間數(shù)據(jù)流轉(zhuǎn)化為節(jié)點(diǎn)內(nèi)數(shù)據(jù)流，從而減小網(wǎng)絡(luò)開(kāi)銷，提高Storm系統(tǒng)的運(yùn)行效率。實(shí)驗(yàn)通過(guò)基準(zhǔn)測(cè)試WordCount從系統(tǒng)延遲、通信開(kāi)銷以及負(fù)載均衡三個(gè)方面論證了本文調(diào)度算法的有效性。

下一步研究工作主要集中在以下幾個(gè)方面：1)本文實(shí)驗(yàn)開(kāi)展的背景為同構(gòu)集群環(huán)境，下一步研究中將探索拓?fù)錂?quán)值與CPU性能和網(wǎng)絡(luò)帶寬的關(guān)系，將TSAW-Storm移植至異構(gòu)Storm集群環(huán)境下；2)根據(jù)TSAW-Storm調(diào)度后的任務(wù)分配結(jié)果進(jìn)一步嘗試優(yōu)化，如采用任務(wù)交換等方法，解決某一工作節(jié)點(diǎn)負(fù)載較低的問(wèn)題；3)從拓?fù)渥陨淼慕Y(jié)構(gòu)特征出發(fā)，將TSAW-Storm進(jìn)一步推廣至更為復(fù)雜的Storm商業(yè)應(yīng)用領(lǐng)域，使其適用于更為豐富的業(yè)務(wù)場(chǎng)景。

參考文獻(xiàn)(References)

[1] 孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[J].計(jì)算機(jī)研究與發(fā)展,2013,50(1):146-169. (MENG X F, CI X. Big data management: concepts, techniques and challenges [J]. Journal of Computer Research and Development, 2013, 50(1): 146-169.)

[2] CHEN C L P, ZHANG C Y. Data-intensive applications, challenges, techniques and technologies: a survey on big data [J]. Information Sciences, 2014, 275(11): 314-347.

[3] TOSHNIWAL A, TANEJA S, SHUKLA A, et al. Storm @Twitter [C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2014: 147-156.

[4] Apache. Apache Storm [EB/OL]. (2017-08-01) [2017-08-10]. http://storm.apache.org.

[5] 孫大為,張廣艷,鄭緯民.大數(shù)據(jù)流式計(jì)算:關(guān)鍵技術(shù)及系統(tǒng)實(shí)例[J].軟件學(xué)報(bào),2014,25(4):839-862. (SUN D W, ZHANG G Y, ZHENG W M. Big data stream computing: technologies and instances [J]. Journal of Software, 2014, 25(4): 839-862.)

[6] RANJAN R. Streaming big data processing in datacenter clouds [J]. IEEE Cloud Computing, 2014, 1(1): 78-83.

[7] 王銘坤,袁少光,朱永利,等.基于Storm的海量數(shù)據(jù)實(shí)時(shí)聚類[J].計(jì)算機(jī)應(yīng)用,2014,34(11):3078-3081. (WANG M K, YUAN S G, ZHU Y L, et al. Real-time clustering for massive data using Storm [J]. Journal of Computer Applications,2014,34(11):3078-3081.)

[8] 喬通,趙卓峰,丁維龍.面向套牌甄別的流式計(jì)算系統(tǒng)[J].計(jì)算機(jī)應(yīng)用,2017,37(1):153-158. (QIAO T, ZHAO Z F, DING W L. Stream computing system for monitoring copy plate vehicles [J]. Journal of Computer Applications, 2017, 37(1): 153-158.)

[9] TA V D, LIU C M, NKABINDE G W. Big data stream computing in healthcare real-time analytics [C]// Proceedings of 2016 IEEE International Conference on Cloud Computing and Big Data Analysis. Piscataway, NJ: IEEE, 2016:37-42.

[10] PENG B Y, HOSSEINI M, HONG Z H, et al. R-Storm: resource-aware scheduling in Storm [C]// Proceedings of the 16th Annual Middleware Conference. New York: ACM, 2015: 149-161.

[11] 劉月超,于炯,魯亮.Storm環(huán)境下一種改進(jìn)的任務(wù)調(diào)度策略[J].新疆大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,34(1):90-95. (LIU Y C, YU J, LU L. An improved task schedule strategy in Storm environment [J]. Journal of Xinjiang University (Natural Science Edition), 2017, 34(1): 90-95.)

[12] XU J L, CHEN Z H, TANG J, et al. T-Storm: traffic-aware online scheduling in Storm [C]// Proceedings of the 34th IEEE International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE, 2014: 535-544.

[13] 鄭麗麗,武繼剛,陳勇,等.帶權(quán)圖的均衡k劃分[J].計(jì)算機(jī)研究與發(fā)展,2015,52(3):769-776. (ZHENG L L, WU J G, CHEN Y, et al. Balancedk-way partitioning for weighted graphs [J]. Journal of Computer Research and Development, 2015, 52(3): 769-776.)

[14] SUN D W, ZHANG G Y, YANG S L, et al. Re-Stream: real-time and energy-efficient resource scheduling in big data stream computing environments [J]. Information Sciences, 2015, 319: 92-112.

[15] GHADERI J, SHAKKOTTAI S, SRIKANT R. Scheduling storms and streams in the cloud [J]. ACM SIGMETRICS Performance Evaluation Review, 2015, 43(1): 439-440.

[16] LIU Y, SHI X, JIN H. Runtime-aware adaptive scheduling in stream processing [J]. Concurrency and Computation: Practice and Experience, 2016, 28(14): 3830-3843.

[17] CARDELLINI V, GRASSI V, LO PRESTI F, et al. Distributed QoS-aware scheduling in Storm [C]// Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. New York: ACM, 2015: 344-347.

[18] 熊安萍,王賢穩(wěn),鄒洋.基于Storm拓?fù)浣Y(jié)構(gòu)熱邊的調(diào)度算法[J].計(jì)算機(jī)工程,2017,43(1):37-42.(XIONG A P, WANG X W, ZOU Y. Scheduling algorithm based on Storm topology hot-edge [J]. Computer Engineering, 2017, 43(1):37-42.)

[19] ESKANDARI L, HUANG Z, EYERS D. P-Scheduler: adaptive hierarchical scheduling in Apache Storm [C]// Proceedings of the Australasian Computer Science Week Multiconference. New York: ACM, 2016: Article No. 26.

[20] ANIELLO L, BALDONI R, QUERZONI L. Adaptive online scheduling in Storm [C]// Proceedings of the 7th ACM International Conference on Distributed Event-Based Systems. New York: ACM, 2013: 207-218.

[21] MARZ N. Public stormprocessor/storm-benchmark [EB/OL]. (2012- 08- 20) [2017- 08- 10]. https://github.com/stormprocessor/storm-Benchmark.

[22] ZHANG M. Intel-hadoop/storm-benchmark forked from manuzhang/storm-benchmark [EB/OL]. (2015- 11- 02) [2017- 08- 10]. https://github.com/intel-hadoop/storm-benchmark.

This work is partially supported by the National Natural Science Foundation of China (61462079, 61562086), the Natural Science Foundation of Xinjiang Uygur Autonomous Region of China (2017D01A20), the Educational Research Program of Xinjiang Uygur Autonomous Region of China (XJEDU2016S106), the Graduate Research and Innovation Project of Xinjiang Uygur Autonomous Region of China (XJGRI2016028).

LULiang, born in 1990, Ph. D. candidate. His research interests include distributed computing, in-memory computing.

YUJiong, born in 1964, Ph. D., professor. His research interests include grid computing, distributed computing.

BIANChen, born in 1981, Ph. D., associate professor. His research interests include distributed computing, in-memory computing.

YINGChangtian, born in 1989, Ph. D.. Her research interests include in-memory computing, green storage.

SHIKangli, born in 1990, M. S. candidate. Her research interests include distributed computing, in-memory computing.

PUYonglin, born in 1991, M. S. candidate. His research interests include in-memory computing, green computing.