蒲勇霖 ,于 炯 ,魯 亮 ,李梓楊 ,卞 琛 ,廖 彬

1(新疆大學(xué) 信息科學(xué)與工程學(xué)院,新疆 烏魯木齊 830046)

2(中國民航大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300300)

3(廣東金融學(xué)院 互聯(lián)網(wǎng)金融與信息工程學(xué)院,廣東 廣州 510521)

4(新疆財經(jīng)大學(xué) 統(tǒng)計與數(shù)據(jù)科學(xué)學(xué)院,新疆 烏魯木齊 830012)

目前,隨著互聯(lián)網(wǎng)的高速發(fā)展與平民化,智能醫(yī)療、智能汽車、智能家居以及智能工業(yè)等物聯(lián)網(wǎng)場景[1]下產(chǎn)生的數(shù)據(jù)量日益增多,并與互聯(lián)網(wǎng)共同成為了各行各業(yè)大數(shù)據(jù)的主要來源.但是隨著大數(shù)據(jù)的飛速發(fā)展,大規(guī)模的數(shù)據(jù)中心在全球范圍內(nèi)廣泛的部署,使其高能耗、高污染的問題日漸突出[2].據(jù)2014 年數(shù)據(jù)中心能耗現(xiàn)狀白皮書指出:全球數(shù)據(jù)中心2013 年的耗電量為8 102.5 億kWh,其中IT 設(shè)備與軟件的能耗占數(shù)據(jù)中心總能耗的45.5%[3].而到2015 年,Gartner 統(tǒng)計全球大型數(shù)據(jù)中心的電費(fèi)支出超過1 262 億美元[4].我國數(shù)據(jù)中心電力的消耗同樣驚人,截止到2011 年底,我國數(shù)據(jù)中心的總量達(dá)到43 萬個,其中數(shù)據(jù)中心的耗電量,占據(jù)全國電力總消耗的1.5%,并且所占比例仍在逐年上升[5].綜上所述,解決大數(shù)據(jù)處理的高能耗問題已經(jīng)刻不容緩.

希捷(Seagate)公司與IDC 聯(lián)合發(fā)布的《數(shù)據(jù)時代2025》白皮書中預(yù)測:2025 年,全球數(shù)據(jù)量將達(dá)到163ZB,比2016 年創(chuàng)造出的數(shù)據(jù)量增加10 倍.其中,超過25%的數(shù)據(jù)將成為實時數(shù)據(jù),而物聯(lián)網(wǎng)實時數(shù)據(jù)占比將達(dá)到實時數(shù)據(jù)的95%[6].針對大數(shù)據(jù)處理的高性能集群一般分為批量計算框架與流計算框架兩類,其中,批量計算框架由于存在先存儲后計算的特性,無法滿足實時數(shù)據(jù)的處理需求;而流計算框架由于其強(qiáng)大的實時性,為實時大數(shù)據(jù)分析提供了良好的平臺層解決方案.但是流式計算在高速處理實時數(shù)據(jù)的同時伴隨著高能耗的問題[7],已經(jīng)給產(chǎn)業(yè)界帶來了巨大的能耗開銷.特別在2017 年后,針對大數(shù)據(jù)流式處理節(jié)能計算的研究[8]已經(jīng)逐漸增多,其研究價值已被廣大的科研人員認(rèn)可.因此,大數(shù)據(jù)流式處理節(jié)能計算不僅減少了能源消耗保護(hù)環(huán)境,而且具有廣闊的研究價值與應(yīng)用前景.

目前,主流IT 企業(yè)(如華為、百度以及小米等)針對大數(shù)據(jù)流式處理的業(yè)務(wù)主要以Apache Storm 框架[9]為主.雖然主流IT 企業(yè)的部分流式處理業(yè)務(wù)已被遷移至Flink[10]、Spark Streaming[11]和Heron[12]等框架,但其核心的流式處理業(yè)務(wù)還是基于Storm 完成的.這是由于與目前主流的Flink 與后起之秀Heron 相比,Storm 具有更成熟的平臺架構(gòu)和更廣泛的產(chǎn)業(yè)基礎(chǔ);與屬于微批的框架Spark Streaming 相比,Storm 具有更好地實時性;與不開源的Puma[13]以及社區(qū)冷淡的S4[14]相比,Storm 具有更廣闊的發(fā)展前景.此外,Storm 為適應(yīng)業(yè)界的需求而不斷更新其版本,展現(xiàn)出強(qiáng)大的生命力.Storm 是一個主從式架構(gòu)、開源、橫向擴(kuò)展性良好且容錯能力強(qiáng)的分布式實時處理平臺,其編程模型簡單,支持包含Java 在內(nèi)的多種編程語言,且數(shù)據(jù)處理高效.目前,Storm 已經(jīng)廣泛運(yùn)用到銀行金融[15]、臨床醫(yī)療[16]、社交網(wǎng)絡(luò)[17]等行業(yè)進(jìn)行實時大數(shù)據(jù)分析,并廣泛運(yùn)用到機(jī)器學(xué)習(xí)算法、分布式遠(yuǎn)程調(diào)用等領(lǐng)域進(jìn)行理論研究[18].Storm 因其廣泛的業(yè)界認(rèn)可度,而被譽(yù)為“實時處理領(lǐng)域的Hadoop”.

在Storm 集群中,通常使用有向無環(huán)圖(directed acyclic graph,簡稱DAG)表示一個流式作業(yè)(拓?fù)?內(nèi)數(shù)據(jù)的相互關(guān)聯(lián)性,其中,DAG 的頂點表示工作線程及數(shù)據(jù)的處理,DAG 的邊表示數(shù)據(jù)的相互依存性及頂點間的通信.Storm 集群采用輪詢調(diào)度策略(round-robin,簡稱RR),并將DAG 中的任務(wù)平均分配到各工作節(jié)點之中.然而,Storm 的發(fā)展也面臨著一定的挑戰(zhàn).首先,Storm 通過RR 將任務(wù)均勻分配到各節(jié)點中,但是不同的任務(wù)對于節(jié)點計算資源的需求有所差異,如果節(jié)點的計算資源無法滿足任務(wù)的需求,則會導(dǎo)致節(jié)點資源溢出與集群計算延遲升高的問題,進(jìn)而影響集群的性能,并產(chǎn)生高能耗的問題.因此,通過研究任務(wù)調(diào)度優(yōu)化策略從而最大化利用Storm 集群的實時計算能力,是目前亟待解決的問題.其次大多數(shù)任務(wù)調(diào)度優(yōu)化策略主要通過遷移計算負(fù)載來提高集群性能,但是無法對降低流式處理的高能耗帶來幫助.因此,本文通過降低集群節(jié)點間的通信開銷,在減少集群計算延遲的基礎(chǔ)上,有效節(jié)約了能耗.

本文針對上述問題,其主要工作如下.

(1) 通過研究Storm 集群的拓?fù)?topology)結(jié)構(gòu),建立DAG、線程內(nèi)的數(shù)據(jù)分配與路徑開銷這3 個基本模型,從邏輯上將Storm 集群的拓?fù)溥\(yùn)行情況與數(shù)據(jù)分配策略表示出來,為尋找最優(yōu)的數(shù)據(jù)遷移方式創(chuàng)造了條件,并為節(jié)能策略的提出奠定了理論基礎(chǔ).

(2) 根據(jù)3 個基本邏輯模型以及集群內(nèi)數(shù)據(jù)的傳輸及處理情況,建立了資源約束模型,通過3 個條件證明了資源約束模型的必要性,并進(jìn)一步建立最優(yōu)線程重分配模型,其中,線程的最優(yōu)分配由資源約束模型、通信成本、RR 與CPU 優(yōu)先級決定.在滿足資源約束的條件下,實現(xiàn)了數(shù)據(jù)的遷移.

(3) 通過對集群內(nèi)的數(shù)據(jù)進(jìn)行分析,根據(jù)資源約束模型與最優(yōu)線程重分配模型,提出了Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略(energy-efficient strategy based on executor reallocation and data migration in Storm,簡稱ERDM),該策略包括資源約束算法與數(shù)據(jù)遷移算法,其中,資源約束算法根據(jù)節(jié)點資源約束判斷工作節(jié)點是否允許數(shù)據(jù)遷移;數(shù)據(jù)遷移算法根據(jù)資源約束模型和最優(yōu)線程重新分配模型,確定了集群中數(shù)據(jù)的遷移情況.此外,實驗通過4 組基準(zhǔn)測試[19],從不同角度驗證了算法的有效性.

本文第1 節(jié)針對目前國內(nèi)外節(jié)能計算的相關(guān)研究進(jìn)行總結(jié)與分析.第2 節(jié)對Storm 平臺進(jìn)行建模并給出相關(guān)定義.第3 節(jié)詳細(xì)介紹ERDM 的算法并建立能耗模型.第4 節(jié)進(jìn)行實驗對比并對實驗結(jié)果進(jìn)行分析.第5 節(jié)對本文進(jìn)行總結(jié)并對下一步工作進(jìn)行展望.

1 相關(guān)工作

傳統(tǒng)的大數(shù)據(jù)平臺一直專注于延遲、容錯性以及彈性計算等方面,但是隨著IT 行業(yè)能耗的不斷增加,高能耗以及散熱問題已經(jīng)開始制約大數(shù)據(jù)平臺性能的進(jìn)一步發(fā)展.因此,大數(shù)據(jù)平臺的發(fā)展目標(biāo)已經(jīng)逐步轉(zhuǎn)移到功耗與能效方面.目前,用于大數(shù)據(jù)流處理平臺的節(jié)能策略主要集中在硬件[20]與軟件[21]兩個方面.

硬件的節(jié)能策略主要體現(xiàn)在替換高能耗的電子元件[22]與對集群電源電壓進(jìn)行縮放管理[23],以達(dá)到節(jié)能的效果.該方法節(jié)能效果顯著且操作簡單,但其價格高昂不適合部署于大規(guī)模的集群當(dāng)中.Wang 等人[24]使用了動態(tài)電壓頻率縮放技術(shù)(dynamic voltage frequency scaling,簡稱DVFS),通過動態(tài)管理集群節(jié)點CPU 的電壓,以實現(xiàn)節(jié)能的目的.Pietri 等人[25]通過將流式處理平臺的部分CPU 替換成GPU,使得CPU 與GPU 進(jìn)行混合,從而減少了集群處理圖數(shù)據(jù)的能耗.實驗結(jié)果表明,在節(jié)約9.69%能耗的前提下,減少了8.63%訪問時間.文獻(xiàn)[26?28]通過替換高能耗的電子元件,從而提高了集群的能效,以達(dá)到節(jié)能的目的.軟件的節(jié)能策略主要體現(xiàn)在建立能耗模型[29]以及通過資源調(diào)度[30]提高集群的能效,以達(dá)到節(jié)能的效果.Cordeschi 等人[31]從虛擬化數(shù)據(jù)中心(virtualized networked data center,簡稱VNetDC)的角度出發(fā),提出一種在SaaS 模型下,針對實時處理應(yīng)用的最小化能耗調(diào)度策略.該研究針對流式大數(shù)據(jù)傳輸不穩(wěn)定、不可控以及實時數(shù)據(jù)量大等特性,在不影響響應(yīng)時間約束條件的前提下,計算了最小化網(wǎng)絡(luò)傳輸?shù)目偰芎?Cheng 等人[8]從流計算平臺的本質(zhì)出發(fā),提出一種基于Spark Streaming自適應(yīng)調(diào)度作業(yè)的節(jié)能策略.該策略通過在集群中構(gòu)建一個實時能耗分析模型,并對數(shù)據(jù)流信息進(jìn)行實時的捕捉分析,根據(jù)分析結(jié)果對數(shù)據(jù)進(jìn)行預(yù)處理,以此提高了集群性能并減少了部分時間開銷,達(dá)到了節(jié)能的效果.文獻(xiàn)[32]提出一種作用于Spark Streaming 的能耗分析基準(zhǔn)測試方法,該方法通過使用機(jī)器學(xué)習(xí)算法,查找集群內(nèi)數(shù)據(jù)流的大小與通信開銷的平衡.實驗結(jié)果表明,當(dāng)集群內(nèi)數(shù)據(jù)流的大小與通信開銷達(dá)到平衡時,集群執(zhí)行任務(wù)的功耗最小.Maroulis 等人[33]根據(jù)分析Spark Streaming 在執(zhí)行任務(wù)時性能與能耗的權(quán)衡,提出一種基于調(diào)度工作負(fù)載的高效節(jié)能策略.該策略通過建立時間序列預(yù)測模型來捕獲任務(wù)的執(zhí)行時間與能耗,并通過使用DVFS技術(shù)來將集群的能耗降至最低.Veiga 等人[34]設(shè)計了一種作用于Flink 的能耗評估工具,該工具通過分析集群執(zhí)行任務(wù)的工作負(fù)載,以找到不同條件下的集群能耗,為后期設(shè)計基于Flink 的節(jié)能策略奠定了基礎(chǔ).文獻(xiàn)[35]提出一種可同時兼顧低延遲與低能耗的彈性數(shù)據(jù)流處理策略(keep calm and react with foresight:strategies for lowlatency and energy-efficient elastic data stream processing,簡稱LEEDSP),該策略通過使用DVFS 技術(shù),建立了一種彈性自適應(yīng)性的能耗感知模型.該模型通過合理分配集群資源,在提高集群的吞吐量的同時,減少任務(wù)執(zhí)行的延遲,以此節(jié)約了集群的能耗.

文獻(xiàn)[7]提出一種流式大數(shù)據(jù)處理環(huán)境下的實時資源調(diào)度節(jié)能策略(re-stream),該策略通過構(gòu)建CPU 利用率、響應(yīng)時間以及能耗間的數(shù)學(xué)關(guān)系,以此獲得了滿足高能效與低響應(yīng)時間的條件,從而實現(xiàn)了節(jié)能的目的.然而,該節(jié)能策略仍存在以下兩點值得討論:(1) 該策略僅考慮集群CPU 的能耗問題,但對于集群其他電子元件的能耗并未做敘述;(2) 該策略僅使用自己定義的拓?fù)?并非公認(rèn)的測試數(shù)據(jù)集.此外,除了集群自身算法,并未作其他對比實驗,因此節(jié)能策略缺乏一定的通用性.

文獻(xiàn)[36]針對Storm 在遭遇資源瓶頸與網(wǎng)絡(luò)報錯時,缺乏合理應(yīng)對手段,提出了基于數(shù)據(jù)恢復(fù)的節(jié)能策略.該策略通過監(jiān)控集群拓?fù)鋬?nèi)任務(wù)的執(zhí)行吞吐量,判斷任務(wù)的實際運(yùn)行情況,確定是否終止集群內(nèi)的任務(wù),并根據(jù)數(shù)據(jù)恢復(fù)模型還原集群內(nèi)的數(shù)據(jù).該策略不僅有效降低了集群因資源瓶頸與網(wǎng)絡(luò)報錯而帶來的額外資源與能耗的開銷,而且提高了集群任務(wù)處理的性能.此外,該策略具有兩個明顯的優(yōu)點:(1) 從內(nèi)存重新恢復(fù)讀取數(shù)據(jù),有效地避免了從磁盤讀取數(shù)據(jù)資源與能耗的峰值問題;(2) 該策略可以與其他節(jié)能策略進(jìn)行融合,達(dá)到雙重節(jié)能的效果.但也存在集群未發(fā)生資源瓶頸與網(wǎng)絡(luò)報錯,導(dǎo)致節(jié)能策略失效的問題.

文獻(xiàn)[37]根據(jù)Storm 平臺在進(jìn)行數(shù)據(jù)處理時存在高能耗的問題,提出了工作節(jié)點內(nèi)存電壓調(diào)控節(jié)能策略(energy-efficient strategy for work node by DRAM voltage regulation in Storm,簡稱WNDVR-Storm).該策略通過對集群內(nèi)的數(shù)據(jù)流設(shè)置閾值,從而對集群工作節(jié)點數(shù)據(jù)處理能力進(jìn)行判別,動態(tài)調(diào)節(jié)工作節(jié)點的內(nèi)存電壓,以達(dá)到節(jié)能的目的.該節(jié)能策略不僅有效降低了集群的能耗,而且在一定程度上對集群的負(fù)載均衡進(jìn)行了優(yōu)化,但是還存在以下兩點不足:(1) 動態(tài)調(diào)節(jié)工作節(jié)點的內(nèi)存電壓存在一定的偶然性,且實現(xiàn)難度較高;(2) 若集群規(guī)模較大且工作節(jié)點過多,存在節(jié)能算法失效的可能.

與已有成果相比,本文的不同之處在于.

(1) 文獻(xiàn)[8,31?35]均是從集群整體的特性進(jìn)行分析,并未細(xì)化各部件對集群的影響,如網(wǎng)絡(luò)帶寬、CPU 等部件對集群的影響.本文從網(wǎng)絡(luò)帶寬、CPU 以及內(nèi)存這3 個方面進(jìn)行分析建模,確定因數(shù)據(jù)遷移而對集群各部件造成的影響,從而確保在不同場景下均能使節(jié)能策略順利執(zhí)行.

(2) 文獻(xiàn)[7]通過對集群進(jìn)行任務(wù)遷移調(diào)度而達(dá)到節(jié)能的效果,但并未考慮因任務(wù)遷移調(diào)度而帶來各工作節(jié)點計算資源不足的問題,存在資源溢出的風(fēng)險.本文通過建立資源約束模型,預(yù)防了集群數(shù)據(jù)處理的資源溢出問題.

(3) 文獻(xiàn)[37]通過對工作節(jié)點的內(nèi)存電壓進(jìn)行動態(tài)調(diào)節(jié)而達(dá)到了節(jié)能的效果,但是動態(tài)調(diào)節(jié)工作節(jié)點的內(nèi)存電壓存在較大誤差,且會對集群性能造成一定的影響.本文由于是軟件方面的節(jié)能策略,因此不存在動態(tài)調(diào)壓的問題.此外,本文通過數(shù)據(jù)遷移算法減少了節(jié)點間的通信開銷,在降低集群計算延遲的前提下節(jié)約了能耗.

(4) 實驗選取Intel 公司Zhang 等人[19]發(fā)布在GitHub 上的Storm-benchmark-master 基準(zhǔn)測試,而非已有文獻(xiàn)中作者自己定義的拓?fù)浣Y(jié)構(gòu),因此更具有通用性.此外,將ERDM 與大數(shù)據(jù)流式計算框架Storm 的任務(wù)遷移策略(task migration strategy in big data stream computing with Storm,簡稱TMSH-Storm)[18]、LEEDSP[35]以及WNDVR-Storm[37]進(jìn)行對比,驗證了策略的有效性.

2 問題建模與分析

為了確定Storm 集群默認(rèn)調(diào)度策略的能耗問題,建立了DAG、線程內(nèi)數(shù)據(jù)分配與路徑開銷這3 個基本模型,并進(jìn)一步設(shè)計了資源約束模型、最優(yōu)線程重分配模型與數(shù)據(jù)遷移模型,為節(jié)能策略的設(shè)計與實現(xiàn)提供了理論依據(jù).

2.1 基礎(chǔ)邏輯模型

在流式處理中,通常用數(shù)據(jù)流圖處理多個連續(xù)并行的任務(wù),將其表示為DAG.則在Storm 集群中的流式作業(yè)可用定義1 表示.

定義1(DAG).在Storm 集群中,每個流應(yīng)用程序的邏輯通常由DAG[7]描述,而DAG 由頂點與邊構(gòu)成.則令DAG=(C(G),B(G)),其中,C(G)={c1,c2,…,cn}表示由n個組件(component)構(gòu)成的集合,包括數(shù)據(jù)源編程單元(spout)與數(shù)據(jù)處理編程單元(bolt)兩類;B(G)={b1,2,b1,3,…,bn?1,n}為有向邊的集合,表示各組件間的數(shù)據(jù)傳輸鏈路.如果?bi,j∈B(G)且i≠j,則ci,cj∈C(G)表示數(shù)據(jù)從ci發(fā)出由cj接收.則組件與有向邊的對應(yīng)關(guān)系可通過圖1 表示.

Fig.1 A logical DAG of a stream application圖1 流應(yīng)用的邏輯DAG

為提高Storm 集群的執(zhí)行效率,需要滿足同一時刻執(zhí)行多個組件,即?cj∈C(G),E(C)={ej1,ej2,…,ejn}.其中,每個元素eji為一個線程(executor),且eji表示組件cj運(yùn)行第i個線程.圖2 為Storm 集群數(shù)據(jù)處理及傳輸示意圖,由11 個線程與20 條有向邊組成.其中,{ea,eb,…,ei}為線程集合,且線程ea與eb通過拓?fù)滏溌钒l(fā)送數(shù)據(jù),而后續(xù)線程接收上游線程發(fā)送的數(shù)據(jù).以此類推,完成整個拓?fù)?

Fig.2 Data processing and transmission in Storm cluster圖2 Storm 集群數(shù)據(jù)處理及傳輸

此外,令線程ea為線程{ec,ed1,ed2}的父線程,則線程{ec,ed1,ed2}是線程ea的子線程.線程eb為線程{ed1,ed2,ee}的父線程,則線程{ed1,ed2,ee}是線程eb的子線程.以此類推,完成父線程與子線程間的對應(yīng)關(guān)系.

定義2(線程內(nèi)的數(shù)據(jù)分配).令N(C)={n1,n2,…,nm}為集群工作節(jié)點集合,且每個工作節(jié)點內(nèi)存在多個線程,由定義1 可知,工作節(jié)點的數(shù)據(jù)均勻分配到集群的線程上.記工作節(jié)點分配給線程eji的數(shù)據(jù)為dji(若線程的并行度為1,則該線程上的數(shù)據(jù)為dj),則集合Dn={dj1,dj2,…,djn}表示工作節(jié)點分配到線程上的數(shù)據(jù)集合.圖3 為線程內(nèi)數(shù)據(jù)的分配示意圖,由3 個節(jié)點與11 個線程組成.其中,N={n1,n2,n3}表示工作節(jié)點的集合,而線程內(nèi)的數(shù)據(jù)為

此外,為消除節(jié)點內(nèi)部進(jìn)程間通信開銷,圖3 為各工作節(jié)點僅分配一個工作進(jìn)程(worker),因此,拓?fù)渲械耐ㄐ砰_銷可分為兩類:一類為類似于數(shù)據(jù)dd1與數(shù)據(jù)df1之間的節(jié)點內(nèi)部線程間通信;一類為類似于數(shù)據(jù)dd2與數(shù)據(jù)df1之間的節(jié)點間通信.無論集群拓?fù)鋬?nèi)如何傳輸數(shù)據(jù),凡存在直接對應(yīng)關(guān)系,都符合上述傳輸方式.

定義3(路徑開銷).令集合B(p(eji,emn))存在一條子路徑p(eji,emn),表示從頂點eji開始到頂點emn結(jié)束.則需要滿足的條件為:如果?k,則bj,k∈p(eji,emn),bk,i∈p(eji,emn).由此,對于?bj,i∈p(eji,emn)都存在.此外,對于?bk,l∈p(eji,emn),如果k≠j,則?m與bm,k∈p(eji,emn);如果i≠j,則?m與bl,m∈p(eji,emn).

Fig.3 Allocation of data in executor圖3 線程內(nèi)的數(shù)據(jù)分配

路徑開銷lp(eji,emn)表示從頂點eji到頂點emn內(nèi)所有線程與有向邊的開銷之和,則

令整個拓?fù)浯嬖趎條路徑,則拓?fù)鋱?zhí)行關(guān)鍵路徑l(Gp)為

此外,根據(jù)工作節(jié)點是否位于關(guān)鍵路徑上,將工作節(jié)點分為關(guān)鍵節(jié)點與非關(guān)鍵節(jié)點;根據(jù)線程是否位于關(guān)鍵節(jié)點,將線程分為關(guān)鍵節(jié)點上的線程與非關(guān)鍵節(jié)點上線程,簡稱關(guān)鍵線程與非關(guān)鍵線程.

以圖4 為例,定義一條拓?fù)鋱?zhí)行關(guān)鍵路徑為ea→ed1→ef2→eh,則工作節(jié)點n1與n2為關(guān)鍵節(jié)點,工作節(jié)點n3為非關(guān)鍵節(jié)點.

Fig.4 Topology execution of critical path data transmission and processing圖4 拓?fù)鋱?zhí)行關(guān)鍵路徑的數(shù)據(jù)傳輸及處理

2.2 資源約束模型

定義4(資源約束).為滿足Storm集群進(jìn)行數(shù)據(jù)遷移時各工作節(jié)點的資源需求,需設(shè)置工作節(jié)點計算資源集合為,則工作節(jié)點CPU、內(nèi)存以及網(wǎng)絡(luò)帶寬這3 類計算資源占用的極限為其中,表示工作節(jié)點CPU 資源占用率的極限為表示工作節(jié)點內(nèi)存資源占用率的極限為表示工作節(jié)點網(wǎng)絡(luò)帶寬資源占用率的極限為.若線程所在工作節(jié)點的CPU 資源占用率為(單位%),內(nèi)存資源占用率為(單位%),網(wǎng)絡(luò)帶寬資源占用率為(單位%),由于Storm 集群拓?fù)湟坏┨峤粩?shù)據(jù)將源源不斷產(chǎn)生,且持續(xù)運(yùn)行下去,因此為確保集群的高效運(yùn)行,且工作節(jié)點的資源不會溢出,這3 類資源需要滿足如下條件:

為保證集群拓?fù)淠軌蛘＿\(yùn)行,則集群工作節(jié)點各類計算資源需要滿足資源約束.本文將滿足工作節(jié)點CPU 的正常計算稱為符合CPU 資源臨界原則,將滿足工作節(jié)點內(nèi)存的正常計算稱為符合內(nèi)存資源臨界原則,將滿足工作節(jié)點網(wǎng)絡(luò)帶寬的正常傳輸稱為符合網(wǎng)絡(luò)帶寬資源臨界原則.此外,具體結(jié)果在第4.2 節(jié)體現(xiàn).

定理1.當(dāng)集群準(zhǔn)備進(jìn)行數(shù)據(jù)遷移時,判斷被選中節(jié)點資源是否滿足CPU 資源臨界原則、內(nèi)存資源臨界原則以及網(wǎng)絡(luò)帶寬資源臨界原則:若滿足,則允許節(jié)點遷入數(shù)據(jù).即,數(shù)據(jù)遷入原則tr 需要滿足如下條件:

證明:根據(jù)定義4 可知,當(dāng)節(jié)點遷入數(shù)據(jù)后,該工作節(jié)點CPU 的計算資源占用率小于極限值時,工作節(jié)點的CPU 可以正常計算.則稱滿足CPU 資源臨界原則,即

由于當(dāng)流式處理集群執(zhí)行任務(wù)時,拓?fù)湟坏┨峤粚⒊掷m(xù)運(yùn)行下去,即

同理可得,滿足內(nèi)存資源臨界原則,即

同理可得,滿足網(wǎng)絡(luò)帶寬資源臨界原則,即

僅符合以上3 條原則,允許節(jié)點遷入數(shù)據(jù),即得到定理1.□

2.3 最優(yōu)線程重分配模型

根據(jù)第2.1 節(jié)與第2.2 節(jié)建立最優(yōu)線程重分配模型,該模型通過定義3 與定義4 確定非關(guān)線程的分配情況,并生成新的拓?fù)渎窂?為建立數(shù)據(jù)遷移模型做鋪墊.

根據(jù)定義3 可知,集群內(nèi)的工作節(jié)點包括關(guān)鍵節(jié)點與非關(guān)鍵節(jié)點兩類,集群內(nèi)的線程包括關(guān)鍵線程與非關(guān)鍵線程兩類,而集群拓?fù)鋬?nèi)的通信開銷由節(jié)點間通信開銷、節(jié)點內(nèi)部進(jìn)程間通信開銷與節(jié)點內(nèi)部線程間的通信開銷這3 部分組成.

定義5(最優(yōu)線程重分配).現(xiàn)對非關(guān)鍵線程進(jìn)行重分配,首先需要考慮集群內(nèi)工作節(jié)點的資源占用率,在滿足資源約束的條件下,為減少節(jié)點間的通信開銷,需要將非關(guān)鍵線程重新分配到運(yùn)行其父線程的關(guān)鍵節(jié)點上.此外,在進(jìn)行非關(guān)鍵線程重新分配時,除了需要滿足資源約束模型,還需要防止非關(guān)鍵線程分配出現(xiàn)扎堆現(xiàn)象.其原因為線程在進(jìn)行重分配時,一般傾向于往通信開銷較小的節(jié)點分配.由于上游非關(guān)鍵線程已經(jīng)進(jìn)行重分配,則下游非關(guān)鍵線程優(yōu)先考慮分配到上游非關(guān)鍵線程所在的關(guān)鍵節(jié)點上.為避免上述情況,故非關(guān)鍵線程重分配需要加入RR 與CPU 優(yōu)先級(工作節(jié)點中CPU 的利用率最低)兩個限制條件.

如果一個非關(guān)鍵子線程僅存在一個關(guān)鍵父線程,則將非關(guān)鍵子線程重新分配到運(yùn)行其關(guān)鍵父線程的關(guān)鍵節(jié)點上;如果一個非關(guān)鍵子線程存在兩個或多個關(guān)鍵父線程,則為防止扎堆現(xiàn)象的出現(xiàn),首先需要考慮RR,在滿足RR 的條件下,優(yōu)先將非關(guān)鍵子線程重新分配到CPU 利用率最低的關(guān)鍵父線程所在的關(guān)鍵節(jié)點上;如果運(yùn)行父線程的關(guān)鍵節(jié)點的資源利用率達(dá)到極限,則同樣為防止扎堆現(xiàn)象的出現(xiàn),在滿足RR 的條件下,優(yōu)先將非關(guān)鍵子線程重新分配到CPU 利用率最低的關(guān)鍵節(jié)點上.

以圖4 為例,n1與n2為關(guān)鍵節(jié)點,n3為非關(guān)鍵節(jié)點,且n1存在3 個線程,n2存在4 個線程,則非關(guān)鍵子線程ec被分配到n1,而非關(guān)鍵子線程ei被分配到n1,即

如果n1與n2內(nèi)的線程數(shù)量相等,且n1的CPU 占用率高于n2,則非關(guān)鍵子線程ei被分配到n2,即

如果n1的資源占用率已達(dá)到極限,則非關(guān)鍵子線程ec在滿足RR 與CPU 優(yōu)先級的前提下分配到關(guān)鍵節(jié)點ni,即

此外,選擇CPU 優(yōu)先級為評判指標(biāo),是由于CPU 的利用率對集群的性能影響最大.

2.4 數(shù)據(jù)遷移模型

根據(jù)第2.3 節(jié)可知,集群已生成新的拓?fù)渎窂?現(xiàn)通過最優(yōu)線程重分配模型建立數(shù)據(jù)遷移模型,將原非關(guān)鍵線程上的數(shù)據(jù)遷移到對應(yīng)的關(guān)鍵線程中.

若父線程eab傳輸給非關(guān)鍵子線程eji數(shù)據(jù)的大小為dji,在完成非關(guān)鍵子線程重分配后,父線程對子線程的數(shù)據(jù)分配發(fā)生改變,類似數(shù)據(jù)流dji從eji遷移到e′ji,即

根據(jù)定義4 可知,數(shù)據(jù)遷入存在資源約束的問題,需要滿足數(shù)據(jù)遷入原則tr,即

定理2.根據(jù)定義3 可知,原集群的路徑成本為Wcost,數(shù)據(jù)遷移完成后集群的路徑成本為Wc′ost,則

證明:根據(jù)定義3 可知,集群的路徑成本由節(jié)點間通信開銷、節(jié)點內(nèi)部進(jìn)程間通信開銷、節(jié)點內(nèi)部線程間的通信開銷與線程的計算開銷這4 部分組成.其中,節(jié)點間通信開銷為;節(jié)點內(nèi)部線程間的通信開銷為;線程的計算開銷為;由于每個節(jié)點僅分配一個進(jìn)程,則節(jié)點內(nèi)部進(jìn)程間的通信開銷為0.令節(jié)點間存在n條路徑,節(jié)點內(nèi)部線程間存在m條路徑.集群拓?fù)鋽?shù)據(jù)遷移完成后,共有s條節(jié)點間路徑發(fā)生改變,其中有d條節(jié)點間路徑變?yōu)楣?jié)點內(nèi)部線程間路徑,有c條節(jié)點間路徑變?yōu)樾碌墓?jié)點間路徑.則當(dāng)前節(jié)點間的通信成本為,即

此外,根據(jù)定理2 可知,集群內(nèi)節(jié)點間的通信開銷降低.由于集群內(nèi)所有的線程都是通過路徑相互關(guān)聯(lián)的,而非關(guān)鍵線程被重新分配,則在拓?fù)浣Y(jié)構(gòu)上,位于非關(guān)鍵線程下游所有線程(包括位于關(guān)鍵路徑上的線程)的數(shù)據(jù)都將提前到達(dá).因此集群內(nèi)所有路徑的計算延遲降低,進(jìn)而達(dá)到提高集群性能的目的.

3 節(jié)能策略分析

基于以上理論分析,提出Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略,該節(jié)能策略包括資源約束算法與數(shù)據(jù)遷移算法,在減少通信開銷的前提下,提高了集群性能,并節(jié)約了集群的總能耗.圖5 為節(jié)能策略流程圖.

Fig.5 Flowchart of energy-efficient strategy圖5 節(jié)能策略流程圖

該策略主要分為以下5 個步驟.

步驟1:通過負(fù)載監(jiān)控器獲得原系統(tǒng)拓?fù)渎窂揭约皵?shù)據(jù)傳輸與處理的基本信息.

步驟2:根據(jù)集群內(nèi)數(shù)據(jù)的傳輸與處理,確定工作節(jié)點的資源約束.

步驟3:根據(jù)資源約束、通信成本、RR 與CPU 優(yōu)先級,確定非關(guān)鍵線程的分配情況.

步驟4:根據(jù)資源約束模型與最優(yōu)線程重分配模型,確定集群內(nèi)數(shù)據(jù)的遷移情況.

步驟5:根據(jù)節(jié)能策略計算集群的路徑成本與總能耗.

3.1 資源約束算法

為確定集群內(nèi)工作節(jié)點的資源約束,采用資源約束算法,其中需要考慮工作節(jié)點CPU、內(nèi)存與網(wǎng)絡(luò)帶寬的資源占用率.該算法保證集群關(guān)鍵節(jié)點在滿足資源約束的條件下進(jìn)行數(shù)據(jù)遷移.此外,當(dāng)關(guān)鍵節(jié)點的一類資源占用率達(dá)到極限時,則將該節(jié)點設(shè)置為極限節(jié)點,表示無法再將數(shù)據(jù)遷入該節(jié)點,因此需要重新選擇關(guān)鍵節(jié)點.具體的算法描述在算法1 中體現(xiàn).

算法1 的輸入?yún)?shù)為關(guān)鍵節(jié)點的極限資源、關(guān)鍵節(jié)點的初始資源與關(guān)鍵節(jié)點遷入數(shù)據(jù)后增加的資源;輸出參數(shù)為允許關(guān)鍵節(jié)點遷入數(shù)據(jù);初始化為極限節(jié)點集合.算法的第1 行、第2 行表示對關(guān)鍵節(jié)點ni是否為極限節(jié)點進(jìn)行判斷:若為極限節(jié)點,則該節(jié)點不能被遷入數(shù)據(jù);否則,需要判斷工作節(jié)點數(shù)據(jù)遷入是否滿足3 條原則.算法的第5 行～第9 行表示對關(guān)鍵節(jié)點是否滿足CPU 資源臨界原則進(jìn)行判斷:若滿足,則判斷之后的兩條原則;否則,節(jié)點數(shù)據(jù)遷入不滿足tr.算法的第10 行～第14 行表示在滿足CPU 資源臨界原則后,對關(guān)鍵節(jié)點是否滿足內(nèi)存資源臨界原則進(jìn)行判斷:若滿足內(nèi)存資源臨界原則,進(jìn)入下一環(huán)節(jié);否則,節(jié)點數(shù)據(jù)遷入不滿足tr.算法的第15 行～第19 行表示在滿足之前的兩條原則后,對關(guān)鍵節(jié)點是否滿足網(wǎng)絡(luò)帶寬資源臨界原則進(jìn)行判斷:若滿足,則被選節(jié)點允許數(shù)據(jù)遷入;否則,節(jié)點數(shù)據(jù)遷入不滿足tr.

Storm 框架節(jié)能策略首先需要考慮算法對集群性能的影響,原集群內(nèi)拓?fù)涮幚砣蝿?wù)為輪詢調(diào)度算法,其時間復(fù)雜度為O(n).算法1 首先需要對關(guān)鍵節(jié)點是否為極限節(jié)點進(jìn)行判斷,其時間復(fù)雜度為O(1);其次,算法1 的本質(zhì)為依次判斷數(shù)據(jù)遷入節(jié)點是否滿足3 條原則,其時間復(fù)雜度為3O(1);最后,由于需要遍歷整個集群滿足3 條原則的關(guān)鍵節(jié)點,類似于輪詢調(diào)度算法,因此時間復(fù)雜度為O(n).則算法1 的時間復(fù)雜度T(A)為

3.2 數(shù)據(jù)遷移算法

數(shù)據(jù)遷移算法主要包括兩部分組成:其一為數(shù)據(jù)的遷移需要滿足資源約束條件;其二為接收數(shù)據(jù)的節(jié)點需要滿足最優(yōu)線程重分配.該調(diào)度算法可以根據(jù)重寫Storm 平臺的IScheduler 接口[9]來實現(xiàn).具體的算法描述在算法2 中體現(xiàn).

算法2 的輸入?yún)?shù)為重分配后的線程集合與關(guān)鍵節(jié)點CPU 的優(yōu)先級;輸出參數(shù)為生成一條新的拓?fù)渎窂接糜跀?shù)據(jù)的傳輸與處理.算法的第1 行表示判斷關(guān)鍵節(jié)點是否滿足資源約束條件;算法的第3 行～第10 行表示需要減少集群內(nèi)節(jié)點間的通信開銷,并預(yù)防非關(guān)鍵線程重分配出現(xiàn)扎堆現(xiàn)象;算法的第11 行～第15 行表示避免關(guān)鍵節(jié)點出現(xiàn)資源溢出現(xiàn)象,并預(yù)防非關(guān)鍵線程重分配出現(xiàn)扎堆現(xiàn)象;算法的第16 行表示重新計算Zookeeper內(nèi)狀態(tài)信息到節(jié)點的映射關(guān)系,為保證數(shù)據(jù)遷移后數(shù)據(jù)處理的一致性做鋪墊;算法的第 19 行表示更新Zookeeper 的配置文件,防止因拓?fù)涞挠洃浌δ芏绊懙郊簲?shù)據(jù)的傳輸與處理.

為保證數(shù)據(jù)遷移后數(shù)據(jù)處理的一致性與正確性,在將數(shù)據(jù)從非關(guān)鍵線程內(nèi)遷出時,第一,需要選擇合適的關(guān)鍵節(jié)點并建立關(guān)鍵線程;第二,通過非關(guān)鍵線程的父線程將待處理的數(shù)據(jù)復(fù)制兩份分別發(fā)送至兩個子線程中,并由原非關(guān)鍵線程繼續(xù)處理數(shù)據(jù),實時產(chǎn)生計算結(jié)果并發(fā)送至新增的關(guān)鍵線程;第三,將集群拓?fù)鋬?nèi)的狀態(tài)信息存儲至HDFS;第四,修改Zookeeper 內(nèi)狀態(tài)信息到節(jié)點的映射關(guān)系,同時,由新增的關(guān)鍵線程以異步的方式從HDFS中拉取對應(yīng)的狀態(tài)信息,并執(zhí)行狀態(tài)的合并;第五,通過非關(guān)鍵線程的父線程將待處理的數(shù)據(jù)發(fā)送至新增的關(guān)鍵線程中,由新增的關(guān)鍵線程執(zhí)行數(shù)據(jù)處理并向下游線程輸出計算結(jié)果,以此來保證數(shù)據(jù)遷移后數(shù)據(jù)處理的一致性與正確性.

為確定數(shù)據(jù)遷移算法對時間開銷帶來的影響,算法2 首先判斷了關(guān)鍵節(jié)點是否滿足算法1,其時間復(fù)雜度為O(1);其次,算法2 通過遍歷整個集群查找合適的關(guān)鍵節(jié)點來解決非關(guān)鍵子線程的重分配問題,其時間復(fù)雜度為O(n);此外,算法2 在遍歷整個集群過程中,通過不同的限制條件確定最合適的關(guān)鍵節(jié)點來進(jìn)行非關(guān)鍵子線程的重分配,其時間復(fù)雜度為3O(1);最后,算法2 在非關(guān)鍵子線程分配完成后,將數(shù)據(jù)遷入相對應(yīng)的關(guān)鍵線程,并更新Zookeeper 的配置文件,其時間復(fù)雜度為O(1).則算法2 的時間復(fù)雜度T(B)為

此外,ERDM 由算法1 與算法2 組成,則ERDM 的時間復(fù)雜度T(C)為

3.3 節(jié)能模型

在Storm 集群中,能耗一般分為基礎(chǔ)能耗與動態(tài)能耗兩種.其中,基礎(chǔ)能耗為物理機(jī)的待機(jī)能耗,一般來說,同一類型物理機(jī)的待機(jī)能耗是一個固定常量;動態(tài)能耗是任務(wù)執(zhí)行時集群產(chǎn)生的能耗,通常根據(jù)任務(wù)、功率與時間的不同,產(chǎn)生的動態(tài)能耗不同,因此動態(tài)能耗是一個變量.令單位時間t(s)內(nèi)基礎(chǔ)能耗為,動態(tài)能耗為,則集群的總能耗Et為

其中,式(33)中的相關(guān)參數(shù)與式(4)與式(23)相同.式(33)表示集群拓?fù)鋱?zhí)行節(jié)能策略后節(jié)約的能耗.

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

一個完整的Storm 集群由主控節(jié)點、工作節(jié)點與關(guān)聯(lián)節(jié)點這3 類節(jié)點組成,其中,主控節(jié)點上運(yùn)行Nimbus后臺服務(wù),是Storm 集群的中心,負(fù)責(zé)接受用戶提交的拓?fù)洳楣ぷ鞴?jié)點分配任務(wù);工作節(jié)點上運(yùn)行Supervisor后臺服務(wù),負(fù)責(zé)監(jiān)聽主控節(jié)點分配的數(shù)據(jù)并開啟工作進(jìn)程及工作線程;關(guān)聯(lián)節(jié)點上運(yùn)行Zookeeper 后臺服務(wù),負(fù)責(zé)主控節(jié)點和工作節(jié)點間所有的關(guān)聯(lián)協(xié)調(diào),存儲整個集群的狀態(tài)信息與數(shù)據(jù)分配信息.為部署與實現(xiàn)Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略,需要重寫Storm 平臺org.apache.storm.scheduler.IScheduler 接口[9]中的schedule 方法,其原型為public void schedule(topologies topologies,cluster cluster).本文在Storm 集群原有框架的基礎(chǔ)上新增了6 個模塊,如圖6 所示.

Fig.6 Improved architecture of Storm圖6 改進(jìn)后的Storm 框架

新增模塊的功能介紹如下.

(1) 負(fù)載監(jiān)控器:在一定的時間窗口內(nèi),收集各線程CPU、內(nèi)存和網(wǎng)絡(luò)帶寬的資源占用信息以及各線程間數(shù)據(jù)流的大小.由于每個工作節(jié)點僅分配一個進(jìn)程,因此可用線程監(jiān)測的方法對任務(wù)運(yùn)行時的各類信息進(jìn)行采樣與分析.各線程的CPU 資源占用大小,可通過Java API 函數(shù)中ThreadMXBean 類的getThreadCpuTime(long id)方法獲得其CPU 的占用時間,并與其所處工作節(jié)點的CPU 主頻相乘獲得;各線程的內(nèi)存資源占用大小,可通過jmap -heap 指令進(jìn)行檢測;各線程的網(wǎng)絡(luò)帶寬占用信息,可通過實際測得的線程間數(shù)據(jù)流傳輸速率與實驗中設(shè)置的元組大小進(jìn)行累加,并由簡單估算求得;線程間傳輸?shù)臄?shù)據(jù)流大小可使用計數(shù)器變量統(tǒng)計各線程接收到的上游線程發(fā)送的元組數(shù)量,并與時間窗口容量相除獲得數(shù)據(jù)流傳輸速率.最后,CPU 的占用率與數(shù)據(jù)傳輸速率通過nmon[38]軟件獲取,并由Excel 表格導(dǎo)出.具體實現(xiàn)需添加在拓?fù)浣M件中各Spout 的open(?)和nextTuple(?)方法以及各Bolt 的prepare(?)和execute(?)方法中.

(2) 數(shù)據(jù)庫:存儲主控節(jié)點傳來的數(shù)據(jù)分配信息和負(fù)載監(jiān)控器傳來的各類資源占用信息以及集群拓?fù)湫畔?并實時更新.

(3) 配置文件更新:針對算法2 造成的集群路徑的改變,實時更新Zookeeper 的配置文件,防止因Zookeeper的記憶功能而出現(xiàn)數(shù)據(jù)傳輸錯誤的問題.

(4) 數(shù)據(jù)遷移模塊:部署算法1 與算法2,負(fù)責(zé)讀取數(shù)據(jù)庫中的各類信息,并執(zhí)行數(shù)據(jù)遷移算法.該模塊為本文算法部署的核心環(huán)節(jié),亦是集群執(zhí)行節(jié)能策略的基礎(chǔ).

(5) 分布式存儲:存儲集群拓?fù)鋬?nèi)的狀態(tài)信息,并在算法2 執(zhí)行過程中,以異步的方式從HDFS 中拉取對應(yīng)的狀態(tài)信息,保證了數(shù)據(jù)遷移后數(shù)據(jù)處理的一致性和正確性.

(6) 自定義調(diào)度器:覆蓋Nimbus 節(jié)點默認(rèn)的調(diào)度策略,讀取數(shù)據(jù)遷移模塊內(nèi)的決策并執(zhí)行.此外,代碼編譯完成后,將其打jar 包至主控節(jié)點Nimbus 的STORM_HOME/lib 目錄下,并在/conf/storm.yaml 中配置好相關(guān)參數(shù)后運(yùn)行.

此外,本文的負(fù)載監(jiān)控器與工作節(jié)點上運(yùn)行的任務(wù)分別位于同一臺物理節(jié)點的兩個不同進(jìn)程中,由于兩個進(jìn)程之間的內(nèi)存區(qū)域互相隔離,負(fù)載監(jiān)控進(jìn)程并不會使用工作進(jìn)程的內(nèi)存區(qū)域,故對節(jié)點的內(nèi)存資源開銷沒有影響;負(fù)載監(jiān)控器與節(jié)點的工作進(jìn)程位于相同的工作節(jié)點,則不存在網(wǎng)絡(luò)帶寬的開銷;負(fù)載監(jiān)控器收集信息所占用的CPU 資源非常少,因此對節(jié)點CPU 資源開銷的影響可忽略不計;負(fù)載監(jiān)控器收集信息會上傳至數(shù)據(jù)庫,且負(fù)載監(jiān)控器與數(shù)據(jù)庫位于不同的工作節(jié)點,故存在一定網(wǎng)絡(luò)帶寬的開銷,該網(wǎng)絡(luò)帶寬的開銷與時間窗口設(shè)置的大小相關(guān),具體結(jié)果在第4.1 節(jié)體現(xiàn).

本文提出了算法1 與算法2,設(shè)計并實現(xiàn)了Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略,減少了集群內(nèi)的通信開銷,提高了集群性能,并節(jié)約了能耗.

4 實驗結(jié)果及數(shù)據(jù)分析

為評估集群執(zhí)行ERDM 的性能與能耗,本節(jié)首先討論了集群的實驗環(huán)境與參數(shù)集,然后對實驗結(jié)果進(jìn)行討論與分析.

4.1 實驗環(huán)境

為驗證ERDM 的有效性,實驗搭建的Storm 集群包括19 臺PC 機(jī),其中1 臺PC 機(jī)上運(yùn)行1 個Nimbus 進(jìn)程、1 個UI 進(jìn)程與數(shù)據(jù)庫.16 臺PC 機(jī)上運(yùn)行Supervisor 進(jìn)程,3 臺PC 機(jī)上運(yùn)行Zookeeper 進(jìn)程.此外,每臺PC 機(jī)的網(wǎng)卡統(tǒng)一為100Mb/s LAN,且內(nèi)存統(tǒng)一為8GB.根據(jù)不同節(jié)點的運(yùn)行狀況,具體環(huán)境配置見表1 和表2.

Table 1 Hardware configuration of Storm cluster表1 Storm 集群的硬件配置

Table 2 Software configuration of Storm cluster表2 Storm 集群的軟件配置

此外,為在各類不同資源開銷下驗證ERDM 的有效性,實驗選取Intel 公司Zhang 等人[19]發(fā)布在GitHub 上的4 組基準(zhǔn)測試,分別為CPU 敏感型(CPU-sensitive)的WordCount、網(wǎng)絡(luò)帶寬敏感型(network-sensitive)的Sol、內(nèi)存敏感型(memory-sensitive)的RollingSort 以及Storm 在真實場景下的應(yīng)用RollingCount.為消除節(jié)點內(nèi)部進(jìn)程間的通信開銷,執(zhí)行各基準(zhǔn)測試需滿足工作節(jié)點與工作進(jìn)程的數(shù)量保持一致(即一個工作節(jié)點內(nèi)僅分配一個工作進(jìn)程),其余參數(shù)保留其默認(rèn)值,具體的參數(shù)配置見表3.

表3 中的component.xxx_num為基準(zhǔn)測試的組件并行度,Sol 中的topology.level為拓?fù)涞膶哟?需要與component.xxx_num結(jié)合在一起分析.由于拓?fù)浯嬖赟pout 與Bolt 兩種組件,且1 個Spout 對應(yīng)2 個Bolt,因此拓?fù)涞膶哟卧O(shè)置為3.其中,1 個Spout 組件運(yùn)行著50 個實例,2 個Bolt 組件運(yùn)行著100 個實例.topology.works統(tǒng)一設(shè)置為16,表示各基準(zhǔn)測試運(yùn)行時,一個工作節(jié)點內(nèi)僅分配一個工作進(jìn)程;topology.acker.executors統(tǒng)一設(shè)置為 16,表示保證集群內(nèi)數(shù)據(jù)流的可靠傳輸;此外,為防止數(shù)據(jù)傳輸因超時而發(fā)生重傳,需要通過多次實驗驗證結(jié)果,實驗結(jié)果為topology.max.spout.pending統(tǒng)一設(shè)置為200;最后,統(tǒng)一設(shè)置每個message.size等于一個tuple 的大小.

Table 3 Configuration of benchmarks表3 基準(zhǔn)測試參數(shù)配置

為了驗證ERDM 的效果,本文還與TMSH-Storm[18]、LEEDSP[35]和WNDVR-Storm[37]進(jìn)行了對比實驗.其中,

?TMSH-Storm 的核心思想是:對集群的任務(wù)調(diào)度進(jìn)行優(yōu)化,繼而達(dá)到提高集群性能的目的.

?LEEDSP 的核心思想是:彈性調(diào)節(jié)集群節(jié)點的資源,并通過DVFS 技術(shù)動態(tài)調(diào)節(jié)節(jié)點CPU 的電壓,以此達(dá)到節(jié)能的效果.且該策略為流式處理節(jié)能策略的主要代表,適用于大多數(shù)流式處理平臺(如Storm、Flink[10]以及Spark Streaming[11]等).

?WNDVR-Storm 的核心思想為:通過動態(tài)調(diào)節(jié)工作節(jié)點的內(nèi)存電壓而達(dá)到節(jié)能的效果,且WNDVRStorm 由非關(guān)鍵路徑內(nèi)存電壓調(diào)節(jié)(DRAM voltage regulation on non-critical path,簡稱DVRNP)與關(guān)鍵路徑內(nèi)存電壓調(diào)節(jié)(DRAM voltage regulation on critical path,簡稱DVRCP)兩種算法組成.

此外,為保證在同等條件下驗證本文策略的效果,TMSH-Storm、LEEDSP 以及WNDVR-Storm 的相關(guān)參數(shù)與ERDM 保持一致.

為選擇合適的時間窗口用于監(jiān)控集群內(nèi)各節(jié)點資源的負(fù)載信息,本文以WordCount 為例,在系統(tǒng)默認(rèn)調(diào)度策略下,根據(jù)額外增加的網(wǎng)絡(luò)開銷與系統(tǒng)延遲為條件選擇合適的時間窗口取值,具體的結(jié)果見表4.

Table 4 Choose of time windows表4 時間窗口的選擇

根據(jù)表4 可知,當(dāng)時間窗口為10s 與20s 時,集群內(nèi)額外增加的網(wǎng)絡(luò)開銷較大.其原因為:時間窗口取值較低而導(dǎo)致集群內(nèi)數(shù)據(jù)庫的讀寫過于頻繁,讀寫數(shù)據(jù)庫產(chǎn)生的網(wǎng)絡(luò)開銷相對較大,從而影響集群拓?fù)鋬?nèi)任務(wù)的正常執(zhí)行,造成無法觸發(fā)ERDM 的問題.當(dāng)時間窗口為40s 和50s 時,集群內(nèi)額外增加的系統(tǒng)延遲較高,已影響到集群拓?fù)鋬?nèi)的任務(wù)正常執(zhí)行.其原因為:集群內(nèi)數(shù)據(jù)庫的讀寫過于緩慢而延后了ERDM 的觸發(fā)時機(jī),進(jìn)而影響集群拓?fù)鋬?nèi)的任務(wù)執(zhí)行效率,造成影響集群性能的問題.綜上所述,時間窗口的取值設(shè)置為30s,在該時間窗口下能夠較好滿足實驗的執(zhí)行.此外,同理可得Sol、RollingSort 以及RollingCount 的時間窗口取值.

4.2 數(shù)據(jù)遷移有效性測試

為便于觀察集群內(nèi)數(shù)據(jù)遷移完成后,關(guān)鍵節(jié)點的資源占用情況,首先需要確定集群內(nèi)的節(jié)點類型,即關(guān)鍵節(jié)點與非關(guān)鍵節(jié)點.根據(jù)表1 可知,共存在16 個工作節(jié)點.為查找集群內(nèi)關(guān)鍵節(jié)點與非關(guān)鍵節(jié)點的分布情況,則通過Storm UI 檢測集群執(zhí)行4 個基準(zhǔn)測試后的實驗結(jié)果,具體實驗結(jié)果如圖7 所示.

Fig.7 Node distribution under different benchmarks圖7 不同基準(zhǔn)測試下的節(jié)點分布情況

由圖7 可以看出:集群執(zhí)行不同的基準(zhǔn)測試關(guān)鍵節(jié)點與非關(guān)鍵節(jié)點分布并不相同,WordCount 下集群存在2個非關(guān)鍵節(jié)點與14 個關(guān)鍵節(jié)點,Sol 下集群存在3 個非關(guān)鍵節(jié)點與13 個關(guān)鍵節(jié)點,RollingSort 下集群存在2 個非關(guān)鍵節(jié)點與14 個關(guān)鍵節(jié)點,RollingCount 下集群存在2 個非關(guān)鍵節(jié)點與14 個關(guān)鍵節(jié)點.此外,為對比數(shù)據(jù)遷移完成后,各工作節(jié)點資源占用率的變化,需要對原集群各工作節(jié)點的資源占用率進(jìn)行檢測,具體結(jié)果如圖8 所示.

Fig.8 Resources utilization of 16 work nodes in the original cluster圖8 原集群16 個工作節(jié)點的資源占用率

圖8 為原集群運(yùn)行4 個基準(zhǔn)后,16 個工作節(jié)點(關(guān)鍵節(jié)點和非關(guān)鍵節(jié)點)的平均資源占用率.如圖8 所示,原集群16 個工作節(jié)點3 類資源的平均占用率主要集中在50%～70%,這為集群執(zhí)行數(shù)據(jù)遷移奠定了基礎(chǔ).數(shù)據(jù)遷移完成后,各基準(zhǔn)測試根據(jù)節(jié)點分布對16 個工作節(jié)點資源占用率的平均值進(jìn)行觀測,驗證資源約束算法的實際效果.具體結(jié)果如圖9 所示.

Fig.9 Resources utilization of 16 work nodes after the cluster data migration圖9 集群數(shù)據(jù)遷移后16 個工作節(jié)點的資源占用率

如圖9 所示,數(shù)據(jù)遷移完成后,集群16 個工作節(jié)點3 類資源的平均占用率主要集中在80%～100%.圖9 中缺失的部分為非關(guān)鍵節(jié)點,表示非關(guān)鍵線程重分配后,非關(guān)鍵節(jié)點已不存在線程與數(shù)據(jù),因此予以刪除.此外,非關(guān)鍵節(jié)點在集群拓?fù)渲械姆植疾⒉幌嗤?表示運(yùn)行不同基準(zhǔn)測試下的拓?fù)洳⒉幌嗤?

為確定集群在執(zhí)行算法時,算法的響應(yīng)時間對集群性能的影響,現(xiàn)通過測試一個元組從Spout 出發(fā)到最終被集群拓?fù)涮幚硗瓿珊笏a(chǎn)生的時長,以此反映集群數(shù)據(jù)的處理效率.

圖10 統(tǒng)計了WordCount、Sol 與RollingSort 這3 種基準(zhǔn)測試在系統(tǒng)默認(rèn)的調(diào)度策略與ERDM 下的延遲.

Fig.10 Comparison of system latency under different benchmarks圖10 在不同的基準(zhǔn)測試下系統(tǒng)延遲的比較

如圖10 所示,3 種基準(zhǔn)測試下集群執(zhí)行ERDM 的平均延遲為801.33ms,279.28ms,131.02ms,與Storm 默認(rèn)的調(diào)度策略相比,平均降低了6.3%,8.7%,10.4%.這是由于節(jié)點間的通信開銷降低而導(dǎo)致集群路徑的延遲下降.在105s 前存在一個峰值,且Storm 默認(rèn)的調(diào)度策略與ERDM 的延遲基本相同,表示集群在提交各拓?fù)鋾r的部署過程,并且105s 前集群統(tǒng)一遵循Storm 默認(rèn)的調(diào)度策略.在105s 時,集群觸發(fā)數(shù)據(jù)遷移算法,數(shù)據(jù)的傳輸延遲出現(xiàn)峰值.這是由于數(shù)據(jù)遷移算法根據(jù)集群CPU、網(wǎng)絡(luò)帶寬與內(nèi)存的負(fù)載以及線程間數(shù)據(jù)流的大小情況,對所有包含線程的工作節(jié)點資源進(jìn)行重新分配,相當(dāng)于對集群的任務(wù)進(jìn)行初始化分配,此時集群的開銷較大,因此導(dǎo)致數(shù)據(jù)流因無法被及時處理而使延遲急劇上升.根據(jù)圖10 可知,3 種基準(zhǔn)測試下集群觸發(fā)數(shù)據(jù)遷移算法后,其平均延遲高于Storm 默認(rèn)的調(diào)度策略的時長為[105s,135s],共耗時約30s;但是由于時間間隔相對較短,故對整個集群拓?fù)鋽?shù)據(jù)處理性能造成的影響可忽略不計.此外,3 種基準(zhǔn)測試的延遲并不相同,這是由于不同的基準(zhǔn)測試,組件中包含的線程數(shù)量并不相同,但對實驗的結(jié)果不會造成影響.綜上所述,數(shù)據(jù)遷移算法在執(zhí)行過程中并不會對集群數(shù)據(jù)傳輸與處理的實時性造成影響.

此外,可通過使用布隆過濾器對集群拓?fù)鋬?nèi)的數(shù)據(jù)進(jìn)行預(yù)處理,刪除數(shù)據(jù)集內(nèi)的重復(fù)數(shù)據(jù),導(dǎo)致集群拓?fù)鋯挝粫r間內(nèi)處理及傳輸?shù)臄?shù)據(jù)量減少,從而降低了在執(zhí)行ERDM 過程中集群拓?fù)鋽?shù)據(jù)傳輸延遲過長的問題.

4.3 節(jié)能策略的實驗結(jié)果與分析

ERDM 的評估標(biāo)準(zhǔn)主要體現(xiàn)在集群性能與能耗兩個指標(biāo).

(1) 集群性能

集群執(zhí)行ERDM 后的性能由集群節(jié)點間的通信開銷判斷,集群性能可通過單位時間內(nèi)數(shù)據(jù)的傳輸與處理速率決定.具體結(jié)果如圖11 所示.此外,集群性能也可由Storm UI(Storm 平臺提供)進(jìn)行計算.引入TMSH-Storm與ERDM 作對比,以驗證ERDM 的實際效果.

Fig.11 Comparison of data processing and transmission rate under different benchmarks圖11 在不同的基準(zhǔn)測試下比較數(shù)據(jù)傳輸與處理速率

如圖11 所示,集群在執(zhí)行ERDM 后,各基準(zhǔn)測試(WordCount、SOL、RollingSort)在單位時間內(nèi)的數(shù)據(jù)傳輸與處理速率得到了改善.執(zhí)行ERDM 后,集群中數(shù)據(jù)傳輸與處理速率的平均值為77 572(tuple/s),76 471(tuple/s)和59 763(tuple/s),與Storm 默認(rèn)的調(diào)度策略相比提高了13.7%,13.3%和18.2%.其原因為:與Storm 默認(rèn)的調(diào)度策略相比,由于執(zhí)行ERDM 減少了節(jié)點間的通信開銷,降低了路徑的計算延遲,從而導(dǎo)致集群數(shù)據(jù)傳輸與處理的總時間減少.因此,集群中數(shù)據(jù)傳輸與處理的速率得到了改善,單位時間內(nèi)使集群增加了數(shù)據(jù)流的大小.集群執(zhí)行TMSH-Storm 后,數(shù)據(jù)傳輸與處理速率的平均值為80 170(tuple/s),81 639(tuple/s)和62 647(tuple/s),與ERDM相比提高了3.3%,4.9%和5.3%.但是執(zhí)行TMSH-Storm 時,集群數(shù)據(jù)傳輸與處理速率的波動較大.這是由于TMSH-Storm 在任務(wù)遷移過程中并未考慮線程遷移出現(xiàn)扎堆現(xiàn)象,導(dǎo)致任務(wù)并未按照原定計劃進(jìn)行遷移,從而增加了額外的節(jié)點間通信開銷,故對集群數(shù)據(jù)傳輸與處理的速率造成了一定的影響.此外,從優(yōu)化的角度來看,拓?fù)鋬?nèi)線程的總數(shù)為326 個、286 個和318 個.執(zhí)行ERDM 后,集群重新分配非關(guān)鍵線程的個數(shù)為17 個、21 個和15 個,其中,從節(jié)點間的數(shù)據(jù)傳輸改變?yōu)榫€程之間數(shù)據(jù)傳輸?shù)木€程個數(shù)為14 個、18 個和12 個,且平均完成一次線程之間數(shù)據(jù)傳輸?shù)母淖兛山档凸?jié)點間的通信成本為0.8%,1.1%和1.5%.因此,集群平均節(jié)約的通信成本為11.2%,19.8%和18%.圖12 顯示了在實際應(yīng)用場景下集群拓?fù)鋬?nèi)數(shù)據(jù)傳輸與處理速率.

如圖12 所示,在執(zhí)行ERDM 運(yùn)行RollingCount 后,集群中數(shù)據(jù)傳輸與處理速率的平均值為57 530(tuple/s),與Storm 默認(rèn)的調(diào)度策略相比提高了12.5%.在執(zhí)行TMSH-Storm 運(yùn)行RollingCount 后,由于集群數(shù)據(jù)傳輸與處理速率波動較大的原因,其平均值為59 800(tuple/s),相比于Storm 默認(rèn)的調(diào)度策略提高了15.8%.兩種策略的差距較小,但是ERDM 的穩(wěn)定性更佳.此外,拓?fù)鋬?nèi)線程的總數(shù)為266 個,執(zhí)行ERDM 后,集群重新分配非關(guān)鍵線程的個數(shù)為14 個,其中,從節(jié)點間的數(shù)據(jù)傳輸改變?yōu)榫€程之間數(shù)據(jù)傳輸?shù)木€程個數(shù)為11 個,且平均完成一次線程之間數(shù)據(jù)傳輸?shù)母淖兛山档凸?jié)點間的通信成本為1.3%,則集群平均節(jié)約的通信成本為14.3%.因此,相比于Storm 默認(rèn)的調(diào)度策略,本文提出的ERDM 具有更好的集群性能.

Fig.12 Comparison of data processing and transmission rate under the RollingCount圖12 在RollingCount 下比較數(shù)據(jù)傳輸與處理速率

(2) 集群能耗

集群能耗反映了集群中數(shù)據(jù)傳輸與處理總的能量消耗.本文通過集群拓?fù)渲袛?shù)據(jù)傳輸與處理的功率與總成本開銷相乘,以計算集群能耗.具體節(jié)約的能耗可通過式(33)計算.此外,引入WNDVR-Storm、LEEDSP 與ERDM 作對比,以驗證ERDM 的實際效果.具體的實驗結(jié)果如圖13 所示.

Fig.13 Comparison of power on RollingCount among different strategies圖13 RollingCount 在不同策略下的功率對比

如圖13 所示,在執(zhí)行ERDM 運(yùn)行RollingCount 后,集群的平均功率為1 065.37W,執(zhí)行Storm 默認(rèn)調(diào)度策略的平均功率為1 063.15W,執(zhí)行DVRNP 與DVRCP 的平均功率為1 045.32W 與1023.17W,執(zhí)行LEEDSP 的平均功率為1 073.71W.相比于Storm 默認(rèn)的調(diào)度策略,在105s 前,兩種算法的功率基本相等,其原因為數(shù)據(jù)遷移算法尚未觸發(fā).但在[105,115s]內(nèi)執(zhí)行ERDM,功率急劇升高.其原因為:在[105s,115s]內(nèi)集群拓?fù)鋱?zhí)行數(shù)據(jù)遷移算法,工作節(jié)點的資源占用率消耗巨大,導(dǎo)致集群功率急速上升.而115s 后,數(shù)據(jù)遷移算法執(zhí)行完畢,集群功率逐漸降低,并于130s 后趨于穩(wěn)定,因此不會對單位時間內(nèi)的集群功率造成影響.與WNDVR-Storm 相比,執(zhí)行ERDM 的平均功率高于WNDVR-Storm,但是執(zhí)行WNDVR-Storm 的功率波動較大,非常不穩(wěn)定,且策略實現(xiàn)較為困難,不適合在大規(guī)模集群中使用.與LEEDSP 相比,執(zhí)行ERDM 的平均功率略低于LEEDSP.其原因為:LEEDSP 并未考慮除CPU 之外部件(如內(nèi)存與網(wǎng)絡(luò)帶寬等)的功率問題,然而Storm 集群拓?fù)湓趫?zhí)行任務(wù)時,內(nèi)存與網(wǎng)絡(luò)帶寬的功率相對較高是不容忽視的.此外,使用DVFS技術(shù)調(diào)節(jié)節(jié)點CPU電壓存在較大的偶然性,非常不穩(wěn)定,且技術(shù)實現(xiàn)較為困難,同樣不適合部署在大規(guī)模地集群當(dāng)中.為計算集群的能耗,需要對集群內(nèi)的功率進(jìn)行積分,具體結(jié)果如圖14 所示.

Fig.14 Comparison of energy consumption on RollingCount among different strategies圖14 RollingCount 在不同策略下的能耗對比

圖14 為RollingCount 在不同策略下集群處理相同數(shù)據(jù)量的能耗,其中,執(zhí)行ERDM 集群的能耗為5 286.8KJ,執(zhí)行Storm 默認(rèn)調(diào)度策略的能耗為7 270.3KJ,執(zhí)行DVRNP 與DVRCP 的能耗為6 317.3KJ 與6 031.5KJ,執(zhí)行LEEDSP 的能耗為 5 934.7KJ.與 Storm 默認(rèn)調(diào)度策略相比,執(zhí)行 ERDM 集群能耗節(jié)約了 27.3%.但是在[4300000tuple,6000000tuple]內(nèi),集群執(zhí)行ERDM 的能耗高于Storm 默認(rèn)的調(diào)度策略.其原因為在[4300000tuple,6000000tuple]內(nèi)集群拓?fù)鋱?zhí)行數(shù)據(jù)遷移算法,導(dǎo)致集群能耗升高.而在[9000000tuple,15000000tuple]執(zhí)行ERDM的能耗遠(yuǎn)低于Storm 默認(rèn)的調(diào)度策略,其原因為數(shù)據(jù)遷移算法執(zhí)行完畢,由于路徑的計算延遲減少導(dǎo)致集群拓?fù)鋬?nèi)的數(shù)據(jù)傳輸與處理速率高于Storm 默認(rèn)的調(diào)度策略,因此相同數(shù)據(jù)量下能耗遠(yuǎn)低于Storm 默認(rèn)的調(diào)度策略.與WNDVR-Storm 相比,執(zhí)行ERDM 集群的能耗略低于WNDVR-Storm,但是執(zhí)行WNDVR-Storm 的能耗上升幅度不斷變化且逐漸升高.這是由于隨著集群數(shù)據(jù)量的不斷增大,數(shù)據(jù)量始終超過額定閾值,導(dǎo)致 WNDVR-Storm 基本失效.與LEEDSP 相比,執(zhí)行ERDM 集群的能耗始終低于LEEDSP.這是由于LEEDSP 并未考慮內(nèi)存與網(wǎng)絡(luò)帶寬等部件的能耗,且執(zhí)行LEEDSP 內(nèi)資源調(diào)度算法的能耗高于執(zhí)行ERDM 內(nèi)數(shù)據(jù)遷移算法的能耗.此外,隨著節(jié)點數(shù)的增加,集群內(nèi)存與網(wǎng)絡(luò)帶寬的能耗比重會不斷增大,從而始終影響LEEDSP 的節(jié)能效果.為量化集群內(nèi)數(shù)據(jù)的傳輸與處理時間與能耗的關(guān)系,需要集群在相同數(shù)據(jù)量下對ERDM 與Storm 默認(rèn)調(diào)度策略進(jìn)行對比,具體的實驗結(jié)果如圖15 所示.

Fig.15 Comparison of data processing and transmission time under the RollingCount圖15 在RollingCount 下比較數(shù)據(jù)傳輸與處理時間

圖15 為RollingCount 在相同數(shù)據(jù)量下兩種策略的時間對比,其中,15 000 000 tuple 下執(zhí)行ERDM 集群的時間為216s,而執(zhí)行Storm 默認(rèn)調(diào)度策略的時間為300s.與Storm 默認(rèn)調(diào)度策略相比,相同數(shù)據(jù)量下執(zhí)行ERDM 集群拓?fù)渲袛?shù)據(jù)的傳輸與處理時間提高了28%.因此可以確定:在相同條件下,集群數(shù)據(jù)傳輸與處理的時間每提高1%,則集群的能耗降低1%.綜上所述,相比于Storm 默認(rèn)的調(diào)度策略,本文提出的ERDM 具有更好的節(jié)能效果.

5 總結(jié)與展望

高能耗問題,是限制大數(shù)據(jù)流式處理平臺發(fā)展的主要障礙之一.Storm 是大數(shù)據(jù)流式處理中最具代表性的平臺之一,但是在最初的設(shè)計中并未考慮能耗問題,從而導(dǎo)致目前高能耗問題始終制約其發(fā)展.針對這一問題,本文通過研究Storm 集群的拓?fù)浣Y(jié)構(gòu),建立了資源約束模型與最優(yōu)線程重分配模型,并進(jìn)一步提出了Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略.該策略由資源約束算法與數(shù)據(jù)遷移算法組成,使集群在減少節(jié)點間通信成本的前提下,縮短了數(shù)據(jù)傳輸與處理的時間,并節(jié)約了能耗.最后,實驗通過4 組基準(zhǔn)測試,從資源占用、性能與能耗的角度驗證了策略的有效性.

下一步的研究工作主要包括以下4 個方面:(1) 將ERDM 進(jìn)一步部署到更為復(fù)雜的商業(yè)應(yīng)用領(lǐng)域,使其可以在更廣闊的應(yīng)用場景下使用;(2) 將布隆過濾器運(yùn)用到集群,通過對集群拓?fù)鋬?nèi)的數(shù)據(jù)進(jìn)行預(yù)處理,刪除數(shù)據(jù)集內(nèi)的重復(fù)數(shù)據(jù),使集群單位時間內(nèi)處理及傳輸?shù)臄?shù)據(jù)量減少,從而降低了集群延遲,并節(jié)約了能耗;(3) 目前,Storm 集群內(nèi)部的電子元件限制了性能與能效的發(fā)展,可通過替換高能效的電子元件,以提高集群的性能,并節(jié)約能耗;(4) 目前,集群拓?fù)鋬?nèi)的進(jìn)程與線程的數(shù)量需要用戶手動設(shè)置,研究拓?fù)鋬?nèi)組件并行度自適應(yīng)調(diào)節(jié)的調(diào)度算法,由此提高了資源利用率,并節(jié)約了能耗.