劉 粟，于 炯，魯 亮，李梓楊

(新疆大學(xué) 信息科學(xué)與工程學(xué)院，烏魯木齊 830046)(*通信作者電子郵箱yujiong@xju.edu.cn)

0 引言

隨著互聯(lián)網(wǎng)+時(shí)代來(lái)臨，全球數(shù)據(jù)量急劇增長(zhǎng)。國(guó)際數(shù)據(jù)公司(International Data Corporation, IDC)發(fā)布的白皮書(shū)《數(shù)據(jù)時(shí)代2025》中提出，預(yù)計(jì)到2025年全球數(shù)據(jù)量將達(dá)到163 ZB，其中超過(guò)25%的數(shù)據(jù)將成為實(shí)時(shí)數(shù)據(jù)，而物聯(lián)網(wǎng)實(shí)時(shí)數(shù)據(jù)將占到95%[1]，面對(duì)如此龐大的實(shí)時(shí)數(shù)據(jù)量，需要時(shí)效性高、可擴(kuò)展性和穩(wěn)定性強(qiáng)的流式計(jì)算框架。與批量計(jì)算不同，流式計(jì)算不再對(duì)數(shù)據(jù)的中間結(jié)果進(jìn)行存儲(chǔ)，數(shù)據(jù)直接在各個(gè)工作節(jié)點(diǎn)的內(nèi)存中進(jìn)行計(jì)算。在這種應(yīng)用場(chǎng)景下，以Twitter公司的Storm系統(tǒng)為代表的幾種實(shí)時(shí)計(jì)算框架應(yīng)運(yùn)而生，也將流式計(jì)算的應(yīng)用范圍逐漸擴(kuò)展到物聯(lián)網(wǎng)、金融、社交媒體以及實(shí)時(shí)交通等實(shí)時(shí)性要求高的領(lǐng)域[2]。其中在Storm環(huán)境下，針對(duì)套牌車識(shí)別具有時(shí)效性約束的問(wèn)題，相關(guān)學(xué)者提出了一種基于實(shí)時(shí)車牌識(shí)別的流式并行檢測(cè)方法，并且該方法的準(zhǔn)確率達(dá)到了98.7%[3]，實(shí)時(shí)獲取車輛的動(dòng)態(tài)信息已經(jīng)成為可能。

Storm平臺(tái)在時(shí)效性、擴(kuò)展性和穩(wěn)定性等各方面均有著良好的表現(xiàn)，但是其采用的默認(rèn)輪詢調(diào)度策略(Round-Robin Scheduling, RRS)，將需要計(jì)算的任務(wù)平均分配到集群中的各個(gè)工作節(jié)點(diǎn)上，忽略了集群中各個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)通信開(kāi)銷，在一定程度上增加了通信延遲。針對(duì)Storm缺乏智能調(diào)度機(jī)制的問(wèn)題，本文根據(jù)已有的研究工作，將Storm環(huán)境下的優(yōu)化調(diào)度策略分為以下三類[4]：第一類是通過(guò)改變拓?fù)浣M件中任務(wù)實(shí)例的通信方式減小通信開(kāi)銷。由于Storm平臺(tái)中，通信方式在很大程度上決定了任務(wù)間通信開(kāi)銷的大小，因此，降低通信開(kāi)銷的核心做法是盡可能地降低節(jié)點(diǎn)間通信與進(jìn)程間通信開(kāi)銷。這類文獻(xiàn)的做法主要分為全局性和局部性的任務(wù)調(diào)度優(yōu)化策略。其中，文獻(xiàn)[5-9]采用的是全局性的任務(wù)調(diào)度優(yōu)化策略，根據(jù)對(duì)各類資源和數(shù)據(jù)流的動(dòng)態(tài)監(jiān)測(cè)，對(duì)所提交拓?fù)渲械乃腥蝿?wù)進(jìn)行一次性的全局重新部署，調(diào)度過(guò)后，集群的整體通信開(kāi)銷降低。但由于全局性的任務(wù)調(diào)度優(yōu)化策略是對(duì)全部的任務(wù)進(jìn)行重部署，影響作業(yè)的實(shí)時(shí)運(yùn)行，進(jìn)而出現(xiàn)集群短暫不可用的現(xiàn)象，且全局調(diào)度的開(kāi)銷比較大。而局部性的任務(wù)調(diào)度優(yōu)化策略則選取部分任務(wù)進(jìn)行重部署，對(duì)作業(yè)處理的實(shí)時(shí)性影響較小。文獻(xiàn)[10-11]采用局部性的任務(wù)調(diào)度優(yōu)化策略，對(duì)任務(wù)所需的各類資源進(jìn)行限制或是對(duì)數(shù)據(jù)流的傳輸速率設(shè)定閾值，以便選擇需要重部署的任務(wù),從而減少需要重部署的任務(wù)數(shù)量，降低算法執(zhí)行開(kāi)銷，減少對(duì)系統(tǒng)實(shí)時(shí)性的影響。第二類優(yōu)化策略的核心思想是通過(guò)合理的資源分配，優(yōu)化資源分配結(jié)構(gòu)，提高系統(tǒng)運(yùn)算效率。文獻(xiàn)[12]提出R-Storm策略，利用任務(wù)所需的資源和工作節(jié)點(diǎn)可提供資源之間的關(guān)系實(shí)現(xiàn)調(diào)度；優(yōu)點(diǎn)是可以基本滿足節(jié)點(diǎn)對(duì)CPU、內(nèi)存和網(wǎng)絡(luò)帶寬的約束，但缺陷是該策略無(wú)法從監(jiān)控中直接獲取以上資源且只適合同構(gòu)環(huán)境。文獻(xiàn)[13-14]將圖形處理器(Graphics Processing Unit, GPU)作為一類資源，利用其在并行處理方面的優(yōu)勢(shì)，將GPU運(yùn)用到Storm框架中，實(shí)現(xiàn)大幅度的性能優(yōu)化。文獻(xiàn)[15]將能耗作為一類資源，提出了高性能低延遲的實(shí)時(shí)流式計(jì)算系統(tǒng)Re-Stream，但Re-Stream本身度量資源的維度比較單一。文獻(xiàn)[16-17]提出了服務(wù)質(zhì)量感知的調(diào)度優(yōu)化策略，基于CPU和內(nèi)存資源的狀態(tài)信息，構(gòu)建成本空間模型，以尋求新任務(wù)的最優(yōu)放置策略。第三類是根據(jù)集群運(yùn)行的實(shí)時(shí)狀況對(duì)集群進(jìn)行調(diào)度，從而實(shí)現(xiàn)負(fù)載均衡。在Flink平臺(tái)中，節(jié)點(diǎn)對(duì)數(shù)據(jù)元組的廣播、輪詢和隨機(jī)三種路由策略同Storm環(huán)境下的輪詢調(diào)度策略一樣，均未考慮節(jié)點(diǎn)負(fù)載不均衡的問(wèn)題。文獻(xiàn)[18]針對(duì)這一弊端，提出Flink環(huán)境下的基于負(fù)載感知算法的動(dòng)態(tài)負(fù)載均衡策略。文獻(xiàn)[19-21]根據(jù)節(jié)點(diǎn)資源情況，提出合理的數(shù)學(xué)模型進(jìn)而找出更優(yōu)的任務(wù)調(diào)度策略。

以上三類均為在線的調(diào)度策略，這些調(diào)度策略的觸發(fā)階段發(fā)生在拓?fù)溥\(yùn)行過(guò)程中，通過(guò)監(jiān)控獲取集群的實(shí)時(shí)運(yùn)行狀態(tài)，因此調(diào)度的精確性較高。然而，這些調(diào)度策略不可避免地會(huì)對(duì)用戶作業(yè)運(yùn)行的實(shí)時(shí)性帶來(lái)不良影響，因此有學(xué)者提出作用于拓?fù)洳渴痣A段的離線調(diào)度策略[5]。文獻(xiàn)[5]通過(guò)分析拓?fù)浣Y(jié)構(gòu)，盡可能地將相互關(guān)聯(lián)的一對(duì)任務(wù)放置在同一個(gè)進(jìn)程中，進(jìn)而將所有的進(jìn)程通過(guò)輪詢調(diào)度策略放置到各個(gè)工作節(jié)點(diǎn)。但該策略忽略了任務(wù)關(guān)聯(lián)的緊密程度以及由節(jié)點(diǎn)異構(gòu)性帶來(lái)的任務(wù)分配不均衡問(wèn)題?？紤]Storm默認(rèn)調(diào)度策略和已有研究工作的不足，本文提出一種Storm環(huán)境下基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略(Task Scheduling Strategy based on Topology Structure, TS2)。該策略作用于異構(gòu)環(huán)境下的拓?fù)洳渴痣A段，建立CPU資源限制模型和通信開(kāi)銷最小化模型，通過(guò)分析拓?fù)浣Y(jié)構(gòu)，考慮任務(wù)關(guān)聯(lián)關(guān)系的緊密程度，盡可能地將任務(wù)均勻分配至各個(gè)工作節(jié)點(diǎn)，達(dá)到優(yōu)化進(jìn)程和線程部署的效果。實(shí)驗(yàn)結(jié)果表明，相比于Storm默認(rèn)任務(wù)調(diào)度策略與文獻(xiàn)[5]離線任務(wù)調(diào)度策略，TS2在Storm集群通信開(kāi)銷、延遲時(shí)間和吞吐量方面均有所改進(jìn)。

1 Storm拓?fù)淠Ｐ?/h2>

Storm作為分布式的流式計(jì)算平臺(tái)，其作業(yè)是用戶實(shí)現(xiàn)業(yè)務(wù)邏輯的應(yīng)用程序。在Storm中，作業(yè)對(duì)應(yīng)的是拓?fù)?，而拓?fù)涞谋憩F(xiàn)形式為由組件和數(shù)據(jù)流構(gòu)成的有向無(wú)環(huán)圖(Directed Acyclic Graph, DAG)。根據(jù)處理邏輯的不同，組件分為Spout和Bolt兩種。其中Spout組件作為Storm中的數(shù)據(jù)源編程單元，為拓?fù)渖a(chǎn)消息(數(shù)據(jù))，負(fù)責(zé)從外部數(shù)據(jù)源(關(guān)系型數(shù)據(jù)庫(kù)、非關(guān)系型數(shù)據(jù)庫(kù)NoSQL、Kafka、實(shí)時(shí)日志以及Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System, HDFS)等)中不間斷地讀取數(shù)據(jù)，并作為一定的結(jié)構(gòu)的數(shù)據(jù)項(xiàng)(元組)傳遞給拓?fù)溥M(jìn)行處理。Bolt組件作為Storm中的數(shù)據(jù)處理編程單元，實(shí)現(xiàn)拓?fù)渲袛?shù)據(jù)的處理邏輯，如對(duì)數(shù)據(jù)的過(guò)濾、聚合、查詢等操作，并將處理結(jié)果傳遞給下游的組件。而拓?fù)涞臄?shù)據(jù)流是Storm對(duì)組件間數(shù)據(jù)通信的抽象，表現(xiàn)為無(wú)限的元組序列，且數(shù)據(jù)流在組件中傳輸時(shí)具有多種流組模式。在拓?fù)涞倪\(yùn)行過(guò)程中，為提高拓?fù)涞牟⑿卸?，每一個(gè)組件均可實(shí)例化成多份任務(wù)，其數(shù)量由組件的數(shù)目和配置情況而定，每個(gè)線程會(huì)執(zhí)行一個(gè)或多個(gè)任務(wù)，而一般情況下，一個(gè)線程只執(zhí)行一個(gè)任務(wù)。因此，任務(wù)調(diào)度實(shí)質(zhì)上與線程的調(diào)度相同。在此基礎(chǔ)上，本文對(duì)基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略進(jìn)行研究。對(duì)拓?fù)潢P(guān)系圖的定義如下所示。

定義1 拓?fù)潢P(guān)系圖。拓?fù)涠M可以表示為(C,S)，其中C={c1,c2,…,c|C|}是拓?fù)渲兴薪M件的集合，每一個(gè)元素代表一個(gè)Spout組件或Bolt組件。對(duì)于?ci∈C，?Eci={e1,e2,…,e|Eci|}，其中ej表示拓?fù)渲薪M件ci在運(yùn)行實(shí)例化的第j個(gè)線程。另一個(gè)為邊的集合S，S={se1,e3,se2,e3,…,sek,el,…,se6,e11}，其中sek,el表示從任務(wù)實(shí)例ek到el的數(shù)據(jù)流。這種由組件、線程以及數(shù)據(jù)流構(gòu)成的有向無(wú)環(huán)圖稱為拓?fù)潢P(guān)系圖。

由組件、數(shù)據(jù)流和任務(wù)構(gòu)成的拓?fù)潢P(guān)系圖如圖1所示。

圖1 Storm的拓?fù)潢P(guān)系圖Fig. 1 Relationship diagram of Storm topology

觀察圖1可知，度大的組件反映了與該組件中的任務(wù)存在通信的任務(wù)數(shù)量較多，而這種通信方式會(huì)帶來(lái)較高的節(jié)點(diǎn)間通信開(kāi)銷。考慮到如果可以將這些互相通信的任務(wù)盡可能地部署到同一個(gè)節(jié)點(diǎn)上，可以降低節(jié)點(diǎn)間通信開(kāi)銷，基于這一思想，提出關(guān)聯(lián)任務(wù)的定義。

定義3 關(guān)聯(lián)任務(wù)。對(duì)于拓?fù)渲腥我獾娜蝿?wù)ef、eg和eh，若任務(wù)ef和eg之間存在數(shù)據(jù)流sef,eg，并且任務(wù)eg和eh之間存在數(shù)據(jù)流seg,eh，則任務(wù)ef、eh均為任務(wù)eg的關(guān)聯(lián)任務(wù)。如圖1所示，以任務(wù)e3為例，Spout組件中的任務(wù)e1、e2以及Bolt B組件中的任務(wù)e10、e11均為任務(wù)e3的關(guān)聯(lián)任務(wù)。

當(dāng)圖1所示的拓?fù)潢P(guān)系圖提交到集群后，根據(jù)Storm默認(rèn)調(diào)度策略，以輪詢的方式進(jìn)行任務(wù)分配，進(jìn)而形成拓?fù)涞娜蝿?wù)分配圖，如圖2所示。

圖2 拓?fù)涞娜蝿?wù)分配Fig. 2 Task assignment of topology

一般情況下，在Storm集群中存在三種通信方式，分別為節(jié)點(diǎn)間通信、節(jié)點(diǎn)內(nèi)進(jìn)程間通信和進(jìn)程內(nèi)線程間通信，不同的通信方式其通信開(kāi)銷也各不相同。由于節(jié)點(diǎn)間通信開(kāi)銷需要占用網(wǎng)絡(luò)帶寬資源，其通信開(kāi)銷最大，而線程間通信開(kāi)銷最小且不可避免。文獻(xiàn)[6]提出在單拓?fù)洵h(huán)境中，如果每個(gè)節(jié)點(diǎn)上只分配一個(gè)槽，即一個(gè)節(jié)點(diǎn)上只部署一個(gè)進(jìn)程，可以避免節(jié)點(diǎn)內(nèi)進(jìn)程間通信方式，有效降低通信開(kāi)銷?；谶@種方法，本文考慮通過(guò)拓?fù)潢P(guān)系圖向集群分配任務(wù)時(shí)，在各節(jié)點(diǎn)上僅分配一個(gè)槽，此時(shí)，默認(rèn)輪詢調(diào)度策略便簡(jiǎn)化為拓?fù)渲腥烤€程在各節(jié)點(diǎn)上的均勻分配。在此基礎(chǔ)上，任務(wù)與節(jié)點(diǎn)之間的映射關(guān)系定義如下。

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

本章基于Storm的拓?fù)潢P(guān)系圖建立了CPU資源限制模型和通信開(kāi)銷最小化模型。CPU資源限制模型從工作節(jié)點(diǎn)的理論CPU資源出發(fā)， 通過(guò)設(shè)定閾值為節(jié)點(diǎn)保留一定的CPU資源。同時(shí)，根據(jù)節(jié)點(diǎn)剩余CPU資源對(duì)各節(jié)點(diǎn)最多可放置的線程數(shù)量進(jìn)行限制。通信開(kāi)銷最小化模型基于拓?fù)涞娜蝿?wù)數(shù)量和數(shù)據(jù)流數(shù)量不變的原則，盡可能將高通信開(kāi)銷的節(jié)點(diǎn)間通信轉(zhuǎn)化為低通信開(kāi)銷的節(jié)點(diǎn)內(nèi)線程間通信，為實(shí)現(xiàn)通信開(kāi)銷最小化提供了理論依據(jù)。

2.1 CPU資源限制模型

根據(jù)Storm環(huán)境下流式計(jì)算模型的特征，考慮集群中各個(gè)節(jié)點(diǎn)的CPU資源需求。設(shè)Storm集群包含的工作節(jié)點(diǎn)集合為M={m1,m2,…,m|M|}，其中mk表示集群中第k個(gè)節(jié)點(diǎn)。為簡(jiǎn)便，下文中出現(xiàn)的“節(jié)點(diǎn)”均指工作節(jié)點(diǎn)。各工作節(jié)點(diǎn)理論可用的CPU資源構(gòu)成了集合R={rm1,rm2,…,rm|M|}(單位為Hz)。在集群運(yùn)行過(guò)程中，各節(jié)點(diǎn)的CPU資源主要用于處理提交的拓?fù)?，即服?wù)于拓?fù)浣M件中分配到該節(jié)點(diǎn)的線程ei，只有當(dāng)節(jié)點(diǎn)在非滿負(fù)荷的狀態(tài)下運(yùn)行，才能保證節(jié)點(diǎn)處于最佳的工作狀態(tài)，因而設(shè)閾值α(0<α<1)，在理論條件下為節(jié)點(diǎn)保留一定的CPU資源。故：對(duì)于?mk∈M，rei代表線程ei在運(yùn)行過(guò)程中所需要的CPU資源，故有:

(1)

考慮到各工作節(jié)點(diǎn)的CPU資源是有限的，且在異構(gòu)環(huán)境下，為了達(dá)到一定的負(fù)載均衡效果，各個(gè)節(jié)點(diǎn)最多可以承載的線程數(shù)量也是不同的。為滿足式(1)提出的限制條件，節(jié)點(diǎn)上部署的線程數(shù)量應(yīng)低于其可承載最大線程數(shù)。

定義5 節(jié)點(diǎn)可承載最大線程數(shù)。假設(shè)將集群中工作節(jié)點(diǎn)按照剩余CPU資源排序后的節(jié)點(diǎn)集合記為M′= {m1′,m2′,…,m|M|′}，其中|M′|=|M|，每個(gè)工作節(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前剩余CPU資源依次為Rsurplus={rm1′surplus,rm2′surplus,…,rm|M|′surplus}。根據(jù)用戶設(shè)定的工作節(jié)點(diǎn)數(shù)量，選擇前|Mτp|個(gè)節(jié)點(diǎn)為用戶提供計(jì)算服務(wù)，即Mτp={m1′,m2′,…,m|Mτp|′}，其中Mτp?M′，對(duì)應(yīng)的當(dāng)前各節(jié)點(diǎn)的CPU剩余資源為Rτpsurplus={rm1′surplus,rm2′surplus,…,rm|Mτp|′surplus}。拓?fù)洇觩的線程總數(shù)應(yīng)為該拓?fù)浞峙湓诟鱾€(gè)節(jié)點(diǎn)上的線程數(shù)量之和，即:

|eτp|=|em1′τp|+|em2′τp|+…+|em|Mτp|′τp|=

(2)

其中，|emi′τp|表示拓?fù)洇觩分配到第mi′個(gè)節(jié)點(diǎn)上的線程數(shù)量的個(gè)數(shù)。為保證在異構(gòu)環(huán)境下各節(jié)點(diǎn)在分配工作任務(wù)時(shí)遵循一定的分配均衡性，每個(gè)節(jié)點(diǎn)分配的線程數(shù)量應(yīng)該與其剩余CPU資源成正比，即擁有更多CPU資源的節(jié)點(diǎn)承擔(dān)更多的工作任務(wù)，故有如下計(jì)算式：

(3)

此時(shí)X·rm|Mτp|′surplus即為Storm集群中各個(gè)工作節(jié)點(diǎn)的節(jié)點(diǎn)最大可承載線程數(shù)。

2.2 通信開(kāi)銷最小化模型

在Storm集群中，不同種類通信方式的開(kāi)銷差異較大。如果集群中每個(gè)節(jié)點(diǎn)只配置一個(gè)槽，即每個(gè)節(jié)點(diǎn)最多運(yùn)行一個(gè)進(jìn)程，避免節(jié)點(diǎn)內(nèi)進(jìn)程間的通信，因此，在此基礎(chǔ)上進(jìn)一步降低節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)流總和，能有效降低集群的通信開(kāi)銷。

定理1 通信開(kāi)銷最小化原則。當(dāng)Storm集群中不存在節(jié)點(diǎn)內(nèi)進(jìn)程間通信時(shí)，最小化節(jié)點(diǎn)間傳輸?shù)臄?shù)據(jù)流的個(gè)數(shù)等同于最大化節(jié)點(diǎn)內(nèi)線程間傳輸?shù)臄?shù)據(jù)流的個(gè)數(shù)，即：

證明 由Storm的拓?fù)潢P(guān)系圖得知，拓?fù)湟坏┨峤坏郊和瓿刹渴鸷?，拓?fù)潢P(guān)系圖便是固定的，每個(gè)組件包含的任務(wù)數(shù)量和數(shù)據(jù)流總量都是不會(huì)發(fā)生改變的。因此設(shè)總數(shù)據(jù)流的大小為定值，記為C。即：

(4)

得證

由定理1可得出，為滿足通信開(kāi)銷最小化的條件，應(yīng)該最大限度地把通信頻繁的任務(wù)分配到同一個(gè)節(jié)點(diǎn)上，盡可能地實(shí)現(xiàn)通信開(kāi)銷最小化。

3 基于拓?fù)浣Y(jié)構(gòu)的任務(wù)部署策略

為實(shí)現(xiàn)上述CPU資源限制模型和通信開(kāi)銷最小化模型的目標(biāo)，本章主要對(duì)提出的Storm環(huán)境下基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略(TS2)中的兩個(gè)算法進(jìn)行闡述和評(píng)估。

3.1 基于拓?fù)浣Y(jié)構(gòu)的進(jìn)程部署算法

由于Storm中默認(rèn)的輪詢調(diào)度策略并不考慮各個(gè)工作節(jié)點(diǎn)的異構(gòu)性，忽略了節(jié)點(diǎn)自身可能存在的性能差異。但在實(shí)際應(yīng)用中，Storm集群多為節(jié)點(diǎn)異構(gòu)性集群，針對(duì)傳統(tǒng)調(diào)度策略存在的缺陷，考慮各節(jié)點(diǎn)在處理任務(wù)的同時(shí)，也要有良好的計(jì)算性能。為克服傳統(tǒng)缺陷，基于CPU資源限制模型，實(shí)現(xiàn)了基于拓?fù)浣Y(jié)構(gòu)的進(jìn)程部署算法。在拓?fù)涮峤贿^(guò)后的部署階段，該進(jìn)程部署算法觸發(fā)，即在工作節(jié)點(diǎn)具有較為充分的CPU資源和可用槽的條件下，利用默認(rèn)的輪詢調(diào)度策略為滿足這兩種條件的節(jié)點(diǎn)分配一個(gè)進(jìn)程。具體算法描述如下。

算法1 基于拓?fù)浣Y(jié)構(gòu)的進(jìn)程部署算法。

輸入 集群中工作節(jié)點(diǎn)集合M←{m1,m2,…,m|M|};|Mτp|為用戶設(shè)置的對(duì)于運(yùn)行拓?fù)洇觩所需的工作節(jié)點(diǎn)個(gè)數(shù)；

輸出 運(yùn)行拓?fù)洇觩所需的工作節(jié)點(diǎn)Mτp←{m1′,m2′,…,mMτp′} 及各個(gè)節(jié)點(diǎn)的可用槽。

1)

M′←sortByCPURemainingResource(M);

/*根據(jù)剩余CPU資源對(duì)集群中所有節(jié)點(diǎn)排序*/

2)

if needsScheduling(τp)=true then

/*如果拓?fù)洇觩即將調(diào)度*/

3)

Mτp←{m1′,m2′,…,m|Mτp|′} ;

/*分配M′中前|Mτp|個(gè)節(jié)點(diǎn)運(yùn)行拓?fù)洇觩*/

4)

/*未被分配的節(jié)點(diǎn)*/

5)

for eachi∈Mτpdo

6)

if availableSlots(i)=NULL then

/*如果節(jié)點(diǎn)i沒(méi)有可用槽*/

7)

Mτp.remove(i);

8)

16)

end for

17)

end if

18)

assign(availableSlots(i)[0],i);

/*每個(gè)節(jié)點(diǎn)分配一個(gè)進(jìn)程*/

19)

end for

20)

end if

3.2 基于拓?fù)浣Y(jié)構(gòu)的線程部署算法

算法1完成了對(duì)執(zhí)行拓?fù)涞墓?jié)點(diǎn)選取與進(jìn)程部署。接下來(lái)根據(jù)拓?fù)潢P(guān)系圖，考慮如何將組件中的線程部署到已選取的節(jié)點(diǎn)進(jìn)程上，即得到優(yōu)化部署后的拓?fù)淙蝿?wù)分配圖。由于Storm默認(rèn)的任務(wù)調(diào)度策略在部署線程時(shí)，沒(méi)有兼顧到不同通信方式的開(kāi)銷差異，導(dǎo)致較高的通信開(kāi)銷。針對(duì)該問(wèn)題，本節(jié)提出基于拓?fù)浣Y(jié)構(gòu)的線程部署算法，利用節(jié)點(diǎn)可承載線程最大數(shù)的思想對(duì)部署在同一節(jié)點(diǎn)上的線程數(shù)量進(jìn)行約束，基于通信開(kāi)銷最小化模型，盡可能將度較大的組件中的線程部署到同一節(jié)點(diǎn)上，進(jìn)一步降低節(jié)點(diǎn)間通信開(kāi)銷，完成負(fù)載較為均衡、通信開(kāi)銷較低的線程部署。具體算法描述如算法2所示。

算法2 基于拓?fù)浣Y(jié)構(gòu)的線程部署算法。

輸入 根據(jù)算法1輸出的運(yùn)行拓?fù)洇觩所需的工作節(jié)點(diǎn)Mτp←{m1′,m2′,…,mMτp′} 及各個(gè)節(jié)點(diǎn)的可用槽;拓?fù)洇觩中所有組件以及各個(gè)組件的度；

輸出 各工作節(jié)點(diǎn)部署的工作線程。

初始化EULnowτp←{0,0,…,0};

/*設(shè)置每個(gè)節(jié)點(diǎn)當(dāng)前分配的線程個(gè)數(shù)均為0*/

1)

Cτp←getComponent(τp);

2)

Dτp←getDegree(Cτp);

3)

/*獲取度最大的組件*/

4)

/*獲取該組件包含的所有實(shí)例(線程)*/

5)

6)

Cτp′←BFSComponentTraversal(cτp*);

/*以度最大的

組件cτp*為根，對(duì)拓?fù)潢P(guān)系圖進(jìn)行廣度優(yōu)先遍歷*/

7)

/*對(duì)于除cτp*以外的

所有組件按照廣度優(yōu)先遍歷結(jié)果依次執(zhí)行以下部署算法*/

8)

/*獲取該組件的所有線程*/

9)

/*獲取其前驅(qū)線程所在的所有節(jié)點(diǎn)*/

10)

/*每個(gè)節(jié)點(diǎn)上當(dāng)前

分配的線程個(gè)數(shù)小于該節(jié)點(diǎn)上應(yīng)分配的線程上限*/

11)

12)

else

/*該節(jié)點(diǎn)當(dāng)前分配的線程個(gè)數(shù)已達(dá)上限*/

13)

ifMk≠? then

14)

Mk←Mk-{mk};

15)

/*除去不符合條件的

16)

Mτp←Mτp-{mk};

17)

else

18)

配線程個(gè)數(shù)的上限，則將其輪詢分配到其他節(jié)點(diǎn)上*/

19)

end if

20)

end if

21)

22)

end for

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

為驗(yàn)證基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略的有效性，本章將通過(guò)以下實(shí)驗(yàn)進(jìn)行評(píng)估和分析。

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

在Storm集群中一共設(shè)置9個(gè)節(jié)點(diǎn)，包括1個(gè)主控節(jié)點(diǎn)和8個(gè)工作節(jié)點(diǎn)，其中集群中各個(gè)節(jié)點(diǎn)的軟件配置情況如表1所示。

表1 Storm集群各節(jié)點(diǎn)的軟件配置Tab. 1 Software configuration of nodes in Storm cluster

表2所示為集群中各節(jié)點(diǎn)的硬件配置，其中:Supervisor1,2為高配節(jié)點(diǎn);Supervisor3,4,5,6為中配節(jié)點(diǎn);Supervisor7,8為低配節(jié)點(diǎn)?？傮w硬件配置信息表明該集群為異構(gòu)集群。

表2 Storm集群各節(jié)點(diǎn)的硬件配置Tab. 2 Hardware configuration of nodes in Storm cluster

為更好觀測(cè)在異構(gòu)環(huán)境下TS2的有效性，文中不僅與Storm默認(rèn)調(diào)度策略進(jìn)行了對(duì)比，同時(shí)還在集群中部署了文獻(xiàn)[5]中的離線調(diào)度策略。實(shí)驗(yàn)中，離線任務(wù)調(diào)度策略的各項(xiàng)參數(shù)配置信息如下：alpha為0.5，beta為1.0，epsilon為0.5。

實(shí)驗(yàn)數(shù)據(jù)取自GitHub上的storm-benchmark-master提供的基準(zhǔn)測(cè)試用例，一共是3組，分別為WordCount、SOL、RollingCount。除表1、表2所示參數(shù)之外還有一些通用的參數(shù)配置，這些參數(shù)在通過(guò)多次實(shí)驗(yàn)后確定如下：1)為消除進(jìn)程間通信開(kāi)銷，在基準(zhǔn)測(cè)試中各節(jié)點(diǎn)內(nèi)僅分配一個(gè)進(jìn)程，即topology.workers的值為8。2)為保證數(shù)據(jù)流傳輸?shù)目煽啃?，各個(gè)進(jìn)程不僅要運(yùn)行分配的線程，還要運(yùn)行一個(gè)Acker Bolt實(shí)例，即topology.acker.executors的值為8。3)為對(duì)Spout組件的元組發(fā)射頻率進(jìn)行控制，防止元組因超時(shí)而重傳，設(shè)置Spout組件的緩存隊(duì)列長(zhǎng)度topology.max.spout.pending的值為50，并以此決定Storm系統(tǒng)的吞吐量。此外，各基準(zhǔn)測(cè)試用例的參數(shù)配置如表3所示，對(duì)參數(shù)的說(shuō)明如下：1)component.xxx_num表示組件的并行度，即一個(gè)Spout或Bolt組件在運(yùn)行時(shí)的線程數(shù)量。2)在SOL中，topology.level表示拓?fù)涞膶哟危O(shè)置為3。message.size表示元組的大小為100 B。3)在RollingCount中，window.length表示窗口長(zhǎng)度為150 s，emit.frequency為每隔30 s發(fā)送一次數(shù)據(jù)。

表3 基準(zhǔn)測(cè)試參數(shù)配置Tab. 3 Benchmark test parameter configuration

4.2 結(jié)果分析

實(shí)驗(yàn)分別選用Storm默認(rèn)的輪詢?nèi)蝿?wù)調(diào)度策略(圖例中Default)、文獻(xiàn)[5]中的離線任務(wù)調(diào)度策略(圖例中Offline)和本文中提出的基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略(圖例中TS2)進(jìn)行對(duì)比，并選取以下四項(xiàng)指標(biāo)，系統(tǒng)延遲時(shí)間、CPU資源占用率、工作節(jié)點(diǎn)之間的數(shù)據(jù)流傳輸速率和平均吞吐量來(lái)衡量、分析TS2的性能優(yōu)劣。同時(shí)，利用Nmon對(duì)集群中的各工作節(jié)點(diǎn)進(jìn)行監(jiān)控。

4.2.1 系統(tǒng)延遲時(shí)間評(píng)估

系統(tǒng)延遲時(shí)間統(tǒng)計(jì)的是一個(gè)元組從Spout消息源頭發(fā)出，直至最終被系統(tǒng)成功處理所需的時(shí)間，反映了系統(tǒng)運(yùn)行拓?fù)涞奶幚硇?。本組實(shí)驗(yàn)所設(shè)置的取樣周期為10 s，采樣時(shí)間長(zhǎng)度為10 min。由圖3可知，三個(gè)基準(zhǔn)測(cè)試在三種不同策略下的延遲時(shí)間的趨勢(shì)大致相同。當(dāng)拓?fù)涮峤恢螅谶\(yùn)行時(shí)間0 s開(kāi)始之后的一段時(shí)間內(nèi)，延遲時(shí)間先是陡增，隨后下降，并逐漸趨于平緩。在零延遲時(shí)間階段，由于拓?fù)渲胁淮嬖诔晒φ{(diào)度的任務(wù)，因而沒(méi)有完整的數(shù)據(jù)流，Acker無(wú)法獲取到系統(tǒng)延遲時(shí)間的信息。在50 s之前，Spout組件的緩存隊(duì)列中存放著大量未處理的元組，且元組的數(shù)量源源不斷地增加。任務(wù)部署完成意味著短時(shí)間內(nèi)需要處理大量的元組，因而系統(tǒng)延遲時(shí)間會(huì)出現(xiàn)一個(gè)峰值。隨著大量的元組處理過(guò)后，負(fù)載逐漸趨于穩(wěn)定，系統(tǒng)的延遲時(shí)間也隨之降低，并趨于平穩(wěn)。圖3充分地反映了提交拓?fù)?、任?wù)調(diào)度到運(yùn)行穩(wěn)定這三個(gè)階段的運(yùn)行效率。

圖3(a)表示的是WordCount執(zhí)行3種不同任務(wù)調(diào)度策略的系統(tǒng)延遲時(shí)間。由圖3(a)可知，在執(zhí)行Storm默認(rèn)的輪詢調(diào)度策略和離線調(diào)度策略時(shí)，系統(tǒng)的延遲時(shí)間分別在50 s、40 s時(shí)大幅度上升，并在110 s時(shí)達(dá)到峰值；而TS2的調(diào)度過(guò)程則相對(duì)緩慢，在第50 s之后延遲時(shí)間迅速上升，在120 s達(dá)到峰值，峰值為819.2 ms，并在較長(zhǎng)一段時(shí)間段內(nèi)維持在較高水平，延遲時(shí)間的回落速度相比較于默認(rèn)調(diào)度策略和離線調(diào)度策略較慢。分析該現(xiàn)象可得，TS2的調(diào)度開(kāi)銷較大，但由于調(diào)度過(guò)程是在拓?fù)溥\(yùn)行之前，所以并不會(huì)對(duì)用戶作業(yè)運(yùn)行產(chǎn)生影響。三種策略執(zhí)行過(guò)后，系統(tǒng)延遲時(shí)間迅速收斂。拓?fù)溥\(yùn)行穩(wěn)定后，Storm默認(rèn)調(diào)度策略、離線調(diào)度策略和TS2在第180 s～600 s的平均延遲時(shí)間分別為391.5 ms、345.5 ms和328 ms。TS2相比于Storm默認(rèn)調(diào)度策略和離線調(diào)度策略的延遲時(shí)間分別降低了16.22%和5.07%。由此可見(jiàn)，TS2在系統(tǒng)延遲方面的效果更佳，更符合流式計(jì)算環(huán)境的實(shí)時(shí)性要求。

圖3 不同任務(wù)調(diào)度策略下的系統(tǒng)延遲對(duì)比Fig. 3 Comparison of system delays under different task scheduling strategies

圖3(b)表示SOL在執(zhí)行三種不同調(diào)度策略下的系統(tǒng)延遲時(shí)間，曲線走勢(shì)與圖3(a)相類似，與Storm默認(rèn)調(diào)度策略和離線調(diào)度策略相比，TS2的調(diào)度過(guò)程略微緩慢，部署開(kāi)銷略大。在拓?fù)鋱?zhí)行穩(wěn)定后，三種調(diào)度策略在第130 s～600 s內(nèi)的延遲均值分別為182.1 ms、157.1 ms和148.9 ms。TS2相比于Storm默認(rèn)調(diào)度策略和離線調(diào)度策略的延遲時(shí)間分別降低了18.23%和6.49%，優(yōu)化效果略高于WordCount的優(yōu)化效果。

圖3(c)表示RollingCount在執(zhí)行三種不同調(diào)度策略下的系統(tǒng)延遲時(shí)間，與Storm默認(rèn)調(diào)度策略和離線調(diào)度策略相比，TS2的調(diào)度過(guò)程較為緩慢，進(jìn)入峰值的時(shí)間略晚于默認(rèn)調(diào)度策略和離線調(diào)度策略，部署開(kāi)銷略大。在拓?fù)鋱?zhí)行穩(wěn)定后，三種調(diào)度策略在第170 s～600 s內(nèi)的延遲時(shí)間均值分別為377.5 ms、334.3 ms和315.9 ms。TS2相比于Storm默認(rèn)調(diào)度策略和離線調(diào)度策略的延遲時(shí)間分別降低了16.32%和5.50%。優(yōu)化效果略低于在執(zhí)行SOL時(shí)的優(yōu)化效果。

綜上所述，對(duì)于任何調(diào)度策略而言，可用節(jié)點(diǎn)和可用槽的選擇都是一個(gè)不可回避的過(guò)程。由于算法1在執(zhí)行過(guò)程中有無(wú)法避免的系統(tǒng)延遲存在，因此，拓?fù)洳渴鸪跗跁?huì)出現(xiàn)系統(tǒng)延遲陡增的現(xiàn)象。雖然TS2延長(zhǎng)了拓?fù)洳渴饡r(shí)間，但部署完成后系統(tǒng)延遲時(shí)間會(huì)逐步降低，其最終收斂時(shí)間會(huì)略低于默認(rèn)調(diào)度策略和離線調(diào)度策略。實(shí)驗(yàn)結(jié)果表明，WordCount和RollingCount的系統(tǒng)延遲時(shí)間要高于SOL，即優(yōu)化結(jié)果略低于SOL。由于WordCount和RollingCount兩個(gè)基準(zhǔn)測(cè)試中存在按域分組的流組模式，那么上游的組件包含的任務(wù)流向下游時(shí)，各數(shù)據(jù)流元組速率也是不同的，因此，使用任務(wù)間的關(guān)系進(jìn)行調(diào)度存在一定的不精確性，但由于該調(diào)度策略實(shí)現(xiàn)簡(jiǎn)單，開(kāi)銷較小，在不影響用戶作業(yè)的正常運(yùn)行的條件下，還能有效降低系統(tǒng)延遲時(shí)間。綜上所述，就不同的基準(zhǔn)測(cè)試而言，TS2均具有更低的系統(tǒng)延遲時(shí)間，并且對(duì)于各基準(zhǔn)測(cè)試而言，TS2相比于Storm默認(rèn)調(diào)度策略和離線調(diào)度策略的平均優(yōu)化率分別為16.91%和5.69%。該實(shí)驗(yàn)證明了基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略在降低系統(tǒng)延遲方面的有效性。

4.2.2 CPU資源占用率評(píng)估

WordCount、SOL和RollingCount這三組基準(zhǔn)測(cè)試在不同任務(wù)調(diào)度策略下的CPU資源占用率如圖4所示。

由圖4可知，在默認(rèn)的輪詢調(diào)度策略下，每個(gè)工作節(jié)點(diǎn)的CPU資源占用率差別較為明顯，高配節(jié)點(diǎn)的CPU資源占用率較低，低配節(jié)點(diǎn)的CPU資源占用率較高，中配節(jié)點(diǎn)的CPU資源占用率維持在中間水平。造成這種現(xiàn)象的原因是，Storm的默認(rèn)調(diào)度策略在分發(fā)任務(wù)時(shí)，不考慮節(jié)點(diǎn)的自身資源可用情況，忽略異構(gòu)環(huán)境下的節(jié)點(diǎn)性能差異，直接將任務(wù)經(jīng)過(guò)輪詢調(diào)度策略放置在各節(jié)點(diǎn)上，導(dǎo)致各節(jié)點(diǎn)的負(fù)載不均衡。因此，低配節(jié)點(diǎn)在自身資源不充足的條件下，承載較多的線程數(shù)量，需要耗費(fèi)大量系統(tǒng)CPU資源，故低配節(jié)點(diǎn)的CPU資源占用率較高。而高配節(jié)點(diǎn)的自身可用CPU資源較為充足，在執(zhí)行輪詢策略時(shí)，即使放置在該節(jié)點(diǎn)的線程數(shù)量和低配節(jié)點(diǎn)相同，也不會(huì)對(duì)自身的CPU資源產(chǎn)生過(guò)多的影響，所以高配節(jié)點(diǎn)的CPU資源占用率偏低。三個(gè)基準(zhǔn)測(cè)試中，WordCount和RollingCount均屬于CPU敏感型的測(cè)試，因此其整體CPU資源占用率略高于SOL的CPU資源占用率。

同時(shí)由圖4可以看出，執(zhí)行離線調(diào)度策略時(shí)，各節(jié)點(diǎn)的CPU資源占用率的整體水平較為均衡，高配和中配節(jié)點(diǎn)的CPU資源占用率較為接近，低配節(jié)點(diǎn)的CPU資源占用率則略高于其他兩種節(jié)點(diǎn)。由于離線調(diào)度策略通過(guò)對(duì)節(jié)點(diǎn)CPU資源的限制，控制各個(gè)節(jié)點(diǎn)上放置的線程個(gè)數(shù)，改善集群中各個(gè)節(jié)點(diǎn)的負(fù)載。因此，在離線調(diào)度策略的作用下，三個(gè)基準(zhǔn)測(cè)試的各節(jié)點(diǎn)CPU資源占用率整體較為平均，集群的負(fù)載均衡效果明顯優(yōu)于默認(rèn)調(diào)度策略。但是由于該策略未考慮到各類節(jié)點(diǎn)中擁有資源總量的差異性，因而會(huì)出現(xiàn)低配節(jié)點(diǎn)上的CPU資源占用率比其他兩類節(jié)點(diǎn)的CPU資源占用率高的現(xiàn)象。

圖4 不同任務(wù)調(diào)度策略下的CPU資源占用率對(duì)比Fig. 4 Comparison of CPU utilization under different task scheduling strategies

在執(zhí)行TS2時(shí)，圖4中的負(fù)載均衡效果明顯優(yōu)于默認(rèn)調(diào)度策略，但與離線策略的整體趨勢(shì)明顯不同。高配節(jié)點(diǎn)Supervisor 1,2具有更高的CPU負(fù)載，而低配節(jié)點(diǎn)Supervisor 7,8節(jié)點(diǎn)的CPU負(fù)載較低。由于算法優(yōu)先將組件中的線程部署在其前驅(qū)線程所在的工作節(jié)點(diǎn)上，導(dǎo)致一些關(guān)聯(lián)緊密的后繼線程更傾向于分配至資源較為豐富的高配節(jié)點(diǎn)，故CPU資源占用率會(huì)持續(xù)增加，進(jìn)而超過(guò)其他兩類工作節(jié)點(diǎn)。而低配節(jié)點(diǎn)上初始化分配的線程數(shù)量較少，其后繼線程傾向于分配至該節(jié)點(diǎn)上的可能性較小，因而其CPU資源占用率略低。TS2充分考慮到了異構(gòu)環(huán)境下的節(jié)點(diǎn)間計(jì)算資源的差異性，盡可能地將關(guān)聯(lián)線程部署在同一個(gè)節(jié)點(diǎn)上，雖無(wú)法保證完全的負(fù)載均衡，但為了滿足線程分配的平均性的同時(shí)兼顧通信開(kāi)銷的最小化，這一現(xiàn)象是不可避免的。由算法2可知，度最大的組件會(huì)被優(yōu)先調(diào)度，該組件中的線程會(huì)在輪詢調(diào)度策略的作用下均勻地分配至集群中剩余CPU資源充足的高配節(jié)點(diǎn)上。相比于其他組件，這種度較大的組件所需的計(jì)算和通信資源較大，為保證拓?fù)涞膱?zhí)行效率，對(duì)于這樣的組件更傾向于設(shè)置更多的線程數(shù)量，以便提高拓?fù)涞奶幚硭俣?。因此，這些線程將會(huì)近似均衡地分布到各工作節(jié)點(diǎn)，由于任務(wù)間的關(guān)聯(lián)性，其后繼線程也會(huì)均勻地分配到集群的各節(jié)點(diǎn)，達(dá)到任務(wù)整體分配的平衡。因而執(zhí)行TS2時(shí)，集群規(guī)模的大小并不會(huì)對(duì)任務(wù)分配的均衡性造成影響。

4.2.3 節(jié)點(diǎn)間通信開(kāi)銷評(píng)估

本節(jié)統(tǒng)計(jì)并分析在WordCount、SOL、RollingCount三個(gè)基準(zhǔn)測(cè)試中，工作節(jié)點(diǎn)間的平均數(shù)據(jù)流傳輸速率情況。10次實(shí)驗(yàn)中各基準(zhǔn)測(cè)試在運(yùn)行平穩(wěn)的狀況下，單位時(shí)間內(nèi)各節(jié)點(diǎn)間數(shù)據(jù)流傳輸總量的平均值如圖5所示。

圖5 不同任務(wù)調(diào)度策略下的節(jié)點(diǎn)間平均數(shù)據(jù)流速率對(duì)比Fig. 5 Comparison of average data flow rates between nodes under different task scheduling strategies

由圖5可以看出，在采用了離線調(diào)度策略和TS2之后，三組基準(zhǔn)測(cè)試工作節(jié)點(diǎn)間的平均數(shù)據(jù)流速率均有所下降。離線調(diào)度策略執(zhí)行之后，工作節(jié)點(diǎn)間的數(shù)據(jù)流傳輸速率的均值為37 853 tuple/s、12 190 tuple/s、33 478 tuple/s，相比較于默認(rèn)輪詢調(diào)度策略的結(jié)果分別降低了10.58%、13.41%、11.24%；而TS2執(zhí)行之后，工作節(jié)點(diǎn)間的數(shù)據(jù)流傳輸速率的均值在36 192 tuple/s、11 575 tuple/s、32 069 tuple/s，相比較于默認(rèn)輪詢調(diào)度策略，分別降低了14.50%、17.78%、14.97%，效果優(yōu)于默認(rèn)調(diào)度策略。TS2相比于默認(rèn)調(diào)度策略在節(jié)點(diǎn)間通信開(kāi)銷方面平均降低了14.21%。實(shí)驗(yàn)結(jié)果表明，SOL的優(yōu)化率明顯高于WordCount和RollingCount，其原因和系統(tǒng)延遲時(shí)間的實(shí)驗(yàn)結(jié)果相同。即在拓?fù)渲?，如果使用了按域分組的流組模式，再使用TS2中數(shù)據(jù)流的數(shù)量評(píng)估任務(wù)彼此關(guān)聯(lián)的緊密程度具有一定的局限性，未來(lái)將結(jié)合在線任務(wù)調(diào)度的監(jiān)控手段進(jìn)行調(diào)度優(yōu)化的微調(diào)。

4.2.4 平均吞吐量評(píng)估

本節(jié)統(tǒng)計(jì)并分析在WordCount、SOL以及RollingCount三個(gè)基準(zhǔn)測(cè)試中其節(jié)點(diǎn)的平均吞吐量信息。吞吐量代表著在單位時(shí)間內(nèi)成功傳輸?shù)脑M數(shù)量，反映了系統(tǒng)的負(fù)載能力。由圖6可知，WordCount在執(zhí)行這三種調(diào)度策略時(shí)，平均吞吐量的值分別為51 877.78 tuple/s、57 518.50 tuple/s和59 578.63 tuple/s，離線調(diào)度策略的平均吞吐量比默認(rèn)調(diào)度策略提高了9.81%，而TS2的平均吞吐量比默認(rèn)調(diào)度策略提高了12.93%。在SOL的三種調(diào)度策略對(duì)比實(shí)驗(yàn)時(shí)，平均吞吐量的值分別為20 034.23 tuple/s、22 798.10 tuple/s和27 381.36 tuple/s，離線調(diào)度策略的平均吞吐量相比于默認(rèn)調(diào)度策略提高了12.12%，而TS2相比于默認(rèn)的調(diào)度策略的平均吞吐量提高了16.74%。RollingCount在執(zhí)行Storm默認(rèn)的調(diào)度策略、離線調(diào)度策略和TS2這三種調(diào)度策略時(shí)，平均吞吐量的值分別為50 726.60 tuple/s、56 445.20 tuple/s和64 852.27 tuple/s，離線調(diào)度策略的平均吞吐量相比于默認(rèn)調(diào)度策略提高了10.13%，而TS2的平均吞吐量相比于默認(rèn)的調(diào)度策略提高了12.96%。TS2相比于默認(rèn)調(diào)度策略在吞吐量方面的優(yōu)化率平均提高了14.21%。結(jié)合圖5分析可知，SOL的節(jié)點(diǎn)間數(shù)據(jù)流速率的優(yōu)化效果高于WordCount和RollingCount，這意味著在SOL中節(jié)點(diǎn)間通信開(kāi)銷降低的幅度大于WordCount和RollingCount。由于Storm集群中存在三種類型的通信開(kāi)銷，且由定理1通信開(kāi)銷最小化原則可知，在節(jié)點(diǎn)間通信開(kāi)銷降低的情況下，節(jié)點(diǎn)內(nèi)的通信開(kāi)銷會(huì)有所增加。因而SOL的平均吞吐量提升幅度明顯。

圖6 不同任務(wù)調(diào)度策略下的平均吞吐量對(duì)比Fig. 6 Comparison of average throughput under different task scheduling strategies

5 結(jié)語(yǔ)

隨著大數(shù)據(jù)時(shí)代的到來(lái)，對(duì)數(shù)據(jù)處理的實(shí)時(shí)性要求越來(lái)越高，流式計(jì)算已經(jīng)成為大數(shù)據(jù)研究領(lǐng)域的一大熱點(diǎn)。Storm作為實(shí)時(shí)性較強(qiáng)的開(kāi)源分布式大數(shù)據(jù)流式計(jì)算平臺(tái)，有著廣泛的應(yīng)用場(chǎng)景。但其采用的默認(rèn)調(diào)度策略忽略了由通信方式帶來(lái)的系統(tǒng)延遲的增加，同時(shí)也沒(méi)有考慮在異構(gòu)環(huán)境下工作節(jié)點(diǎn)之間不同的資源狀況對(duì)Storm集群性能的影響。針對(duì)該問(wèn)題，本文提出基于拓?fù)浣Y(jié)構(gòu)的任務(wù)調(diào)度策略，通過(guò)選取CPU資源較為充足且可用的節(jié)點(diǎn)，消除節(jié)點(diǎn)內(nèi)進(jìn)程間通信開(kāi)銷，同時(shí)將關(guān)聯(lián)程度較為緊密的線程分配到同一個(gè)節(jié)點(diǎn)，優(yōu)化了拓?fù)涞娜蝿?wù)部署。實(shí)驗(yàn)結(jié)果表明，本文算法可以有效減少異構(gòu)環(huán)境下集群中各個(gè)工作節(jié)點(diǎn)之間的網(wǎng)絡(luò)通信開(kāi)銷，降低系統(tǒng)的延遲時(shí)間，改善負(fù)載均衡的狀態(tài)，提高系統(tǒng)吞吐量。

下一步的研究工作主要集中于將離線調(diào)度和在線調(diào)度相結(jié)合，即考慮在異構(gòu)環(huán)境下，將TS2與輕量級(jí)的在線調(diào)度策略相結(jié)合，彌補(bǔ)TS2在調(diào)度精確性方面的不足；同時(shí)優(yōu)化TS2的調(diào)度思想，使得該策略可以適用于更加復(fù)雜的業(yè)務(wù)場(chǎng)景。