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

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

0 引言

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

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

為了改進(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ù)實時監(jiān)測到的負(fù)載數(shù)據(jù)，為拓?fù)渲邪娜蝿?wù)和數(shù)據(jù)流分別賦予不同的點權(quán)和邊權(quán)，并根據(jù)本文提出的負(fù)載均衡模型和最優(yōu)通信模型的要求，將任務(wù)調(diào)度到合適的工作節(jié)點內(nèi)。實驗結(jié)果表明，相對于Storm默認(rèn)調(diào)度算法和文獻(xiàn)[20]的在線調(diào)度算法，TSAW-Storm在Storm集群系統(tǒng)延遲、通信開銷和負(fù)載均衡方面均有所改進(jìn)。

1 Storm作業(yè)模型

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

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

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

定義1 關(guān)聯(lián)任務(wù)。對于任意任務(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的一種實例模型。特別地，當(dāng)組件ci的實例數(shù)量為1時，定義ti1=ti。可以看到cd的實例數(shù)量為3，cf的實例數(shù)量為2，其余組件的實例數(shù)量為1。以任務(wù)td1為例，其上游任務(wù)ta與tb以及下游任務(wù)tf1與tf2均稱為任務(wù)td1的關(guān)聯(lián)任務(wù)。

圖2 拓?fù)鋵嵗Ｐ?Fig. 2 Instance model of a topology

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

定義2 任務(wù)分配法則。若任務(wù)tij分配到了工作節(jié)點nk上，則記f(tij)=nk或f-1(nk)=tij；若任務(wù)集合Tnk={t11,t12,…,tij,…}分配到了工作節(jié)點nk上，則記f(Tnk)=nk或f-1(nk)=Tnk，其中f即為任務(wù)或任務(wù)集合在工作節(jié)點上的分配法則。如圖3為圖2的拓?fù)溥\行于包含有3個工作節(jié)點的Storm集群中的任務(wù)分配模型，若以工作節(jié)點n1及運行在該工作節(jié)點上的任務(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é)點間通信以及類似于任務(wù)td1與tf1之間的節(jié)點內(nèi)通信。其中節(jié)點間通信受制于當(dāng)前環(huán)境下的網(wǎng)絡(luò)帶寬和帶寬利用率大小，開銷往往很大；而節(jié)點內(nèi)通信與網(wǎng)絡(luò)無關(guān)，由于一個任務(wù)運行于一個工作線程內(nèi)，因此其通信類型僅為進(jìn)程內(nèi)的線程級通信，開銷很小并可忽略不計[14]。然而Storm默認(rèn)輪詢的任務(wù)調(diào)度算法并未兼顧到這兩種通信模式的差異性，從而導(dǎo)致較大的節(jié)點間通信開銷。此外，由于各組件自身業(yè)務(wù)邏輯的不同，CPU占用率必然存在差異；即使是同一個組件中各個業(yè)務(wù)邏輯相同的任務(wù)，也將由于部分流組模式(如Field Grouping)的限制，并不會將其接收到的所有數(shù)據(jù)流均分到各實例中，故各任務(wù)的計算開銷依然存在差異，輪詢的任務(wù)分配方式無法保證集群中各工作節(jié)點的負(fù)載均衡。為了更好地評估任務(wù)的計算開銷和任務(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ù)鋵嵗Ｐ椭懈魅蝿?wù)和任務(wù)間的數(shù)據(jù)流可分別使用wtij和wsij,kl構(gòu)成拓?fù)涞狞c權(quán)和邊權(quán)，其值可通過后文提出的負(fù)載監(jiān)視模塊進(jìn)行實時獲取。這樣的拓?fù)鋵嵗Ｐ头Q作帶權(quán)拓?fù)洹?/p>

2 問題建模與分析

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

2.1 負(fù)載均衡模型

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

(1)

且：

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

證畢。

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

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

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

3.1 邊權(quán)增益

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

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

(10)

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

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

(11)

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

3.2 算法描述

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

算法1 TSAW-Storm。

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

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

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

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

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

3.3 算法解釋與算法評估

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

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

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

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

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

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

4)自定義調(diào)度器。覆蓋主控節(jié)點中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 實驗與分析

4.1 實驗環(huán)境與分析

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

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

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

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

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

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

4.2 實驗結(jié)果與分析

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

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

延遲表明一個元組從Spout發(fā)射到最終被成功處理的時間消耗，反映了拓?fù)鋱?zhí)行一次的響應(yīng)時間，刻畫了系統(tǒng)的運行效率。圖5統(tǒng)計了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)延遲對比 Fig. 5 Comparison of latency among three task scheduling algorithms

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

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

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

4.2.2 通信開銷測試

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

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

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

4.2.3 負(fù)載均衡測試

本節(jié)討論基準(zhǔn)測試WordCount在Storm默認(rèn)調(diào)度算法、在線調(diào)度算法與TSAW-Storm下分別運行時集群的負(fù)載均衡情況。由于Storm默認(rèn)調(diào)度算法采用輪詢的方式分配任務(wù)，因此各工作節(jié)點上初始化分配的任務(wù)數(shù)量相同。然而WordCount數(shù)據(jù)源中各單詞出現(xiàn)的頻率存在很大差異，當(dāng)SplitBolt采用Field Grouping方式進(jìn)行數(shù)據(jù)流分發(fā)時，各CountBolt中的任務(wù)需要處理的數(shù)據(jù)流大小差異很大，單純采用輪詢方式進(jìn)行任務(wù)分配極易導(dǎo)致各工作節(jié)點的負(fù)載不均。在線調(diào)度算法與TSAW-Storm在任務(wù)重調(diào)度過程中充分考慮到不同任務(wù)負(fù)載的差異性，從而克服了默認(rèn)調(diào)度算法在負(fù)載均衡方面的不足。表4為采用這三類任務(wù)調(diào)度算法執(zhí)行任務(wù)分配后各工作節(jié)點的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é)點的資源占用情況。由表4可知，Storm默認(rèn)調(diào)度算法執(zhí)行后，各工作節(jié)點的負(fù)載不均現(xiàn)象較為嚴(yán)重，標(biāo)準(zhǔn)差高達(dá)12.66%，其中6號工作節(jié)點的CPU負(fù)載最高，7號工作節(jié)點的CPU負(fù)載最低，二者差值為33.4%。因最大CPU負(fù)載超出表3中設(shè)置的CPU使用率上限(capacity=70%)，且最大CPU負(fù)載與最小CPU負(fù)載之差也超出了表2中設(shè)置的閾值(epsilon=20%)，故在線調(diào)度算法和TSAW-Storm同時觸發(fā)，這與圖5中系統(tǒng)延遲以及圖6中節(jié)點間數(shù)據(jù)流大小的統(tǒng)計結(jié)果也是相吻合的。在線調(diào)度算法和TSAW-Storm執(zhí)行后，集群中各工作節(jié)點的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%?？梢妰煞N任務(wù)調(diào)度算法均能達(dá)到負(fù)載均衡的效果，且TSAW-Storm效果略優(yōu)，其執(zhí)行后的CPU負(fù)載標(biāo)準(zhǔn)差相比在線調(diào)度算法降低了5.93%。這是因為在向除最后一個工作節(jié)點之外的其他工作節(jié)點逐步遷入任務(wù)的過程中，每個工作節(jié)點實際容納的負(fù)載大小均不能超過其理想情況下的CPU負(fù)載，這比在線調(diào)度算法中每次尋找具有最低CPU負(fù)載的工作節(jié)點的做法在負(fù)載均衡方面更便于控制。然而通過表4可以發(fā)現(xiàn)，使用TSAW-Storm執(zhí)行任務(wù)調(diào)度后，8號工作節(jié)點的CPU負(fù)載將略低于其他7個工作節(jié)點，這是由于該調(diào)度算法的工作機制導(dǎo)致的：在算法1的初始化過程中，帶權(quán)拓?fù)渲械乃腥蝿?wù)都被擬分配至8號工作節(jié)點，而后再結(jié)合Spout任務(wù)本地化和最大化邊權(quán)增益的思想，將8號工作節(jié)點中的任務(wù)逐一分析并遷移至其他7個節(jié)點，直到各工作節(jié)點中分配的負(fù)載大小均在剛好大于其理想情況下的CPU負(fù)載為止。這種做法雖然不易導(dǎo)致節(jié)點過載，且能夠較好地保證1～7號節(jié)點的負(fù)載均衡，但可能導(dǎo)致位于8號工作節(jié)點上的任務(wù)被過多地遷出，進(jìn)而發(fā)生該工作節(jié)點的CPU負(fù)載略低于其他工作節(jié)點的情況。若需解決這一問題，可在TSAW-Storm執(zhí)行結(jié)束后，在滿足最優(yōu)通信模型的前提下進(jìn)行少量任務(wù)交換，這將在未來繼續(xù)開展研究。

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

5 結(jié)語

Storm默認(rèn)輪詢的任務(wù)調(diào)度算法并未考慮到各任務(wù)計算開銷的差異以及任務(wù)之間不同類型的通信模式，在負(fù)載均衡和節(jié)點間通信開銷方面仍存在較大的優(yōu)化空間。針對這一問題，本文將各任務(wù)占用的CPU資源大小作為拓?fù)涞狞c權(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é)點中承載的任務(wù)集合，在保證集群負(fù)載均衡的同時，盡可能將節(jié)點間數(shù)據(jù)流轉(zhuǎn)化為節(jié)點內(nèi)數(shù)據(jù)流，從而減小網(wǎng)絡(luò)開銷，提高Storm系統(tǒng)的運行效率。實驗通過基準(zhǔn)測試WordCount從系統(tǒng)延遲、通信開銷以及負(fù)載均衡三個方面論證了本文調(diào)度算法的有效性。

下一步研究工作主要集中在以下幾個方面：1)本文實驗開展的背景為同構(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é)點負(fù)載較低的問題；3)從拓?fù)渥陨淼慕Y(jié)構(gòu)特征出發(fā)，將TSAW-Storm進(jìn)一步推廣至更為復(fù)雜的Storm商業(yè)應(yīng)用領(lǐng)域，使其適用于更為豐富的業(yè)務(wù)場景。

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

[1] 孟小峰,慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)[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ù)流式計算:關(guān)鍵技術(shù)及系統(tǒng)實例[J].軟件學(xué)報,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ù)實時聚類[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] 喬通,趙卓峰,丁維龍.面向套牌甄別的流式計算系統(tǒng)[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é)報(自然科學(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].計算機研究與發(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].計算機工程,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.