Storm 平臺下的線程重分配與數(shù)據(jù)遷移節(jié)能策略?

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

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

2(中國民航大學 計算機科學與技術學院,天津 300300)

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

4(新疆財經(jīng)大學 統(tǒng)計與數(shù)據(jù)科學學院,新疆 烏魯木齊 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ù)中心在全球范圍內廣泛的部署,使其高能耗、高污染的問題日漸突出[2].據(jù)2014 年數(shù)據(jù)中心能耗現(xiàn)狀白皮書指出:全球數(shù)據(jù)中心2013 年的耗電量為8 102.5 億kWh,其中IT 設備與軟件的能耗占數(shù)據(jù)中心總能耗的45.5%[3].而到2015 年,Gartner 統(tǒng)計全球大型數(shù)據(jù)中心的電費支出超過1 262 億美元[4].我國數(shù)據(jù)中心電力的消耗同樣驚人,截止到2011 年底,我國數(shù)據(jù)中心的總量達到43 萬個,其中數(shù)據(jù)中心的耗電量,占據(jù)全國電力總消耗的1.5%,并且所占比例仍在逐年上升[5].綜上所述,解決大數(shù)據(jù)處理的高能耗問題已經(jīng)刻不容緩.

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

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

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

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

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

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

(3) 通過對集群內的數(shù)據(jù)進行分析,根據(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 組基準測試[19],從不同角度驗證了算法的有效性.

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

1 相關工作

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

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

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

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

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

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

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

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

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

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

2 問題建模與分析

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

2.1 基礎邏輯模型

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

定義1(DAG).在Storm 集群中,每個流應用程序的邏輯通常由DAG[7]描述,而DAG 由頂點與邊構成.則令DAG=(C(G),B(G)),其中,C(G)={c1,c2,…,cn}表示由n個組件(component)構成的集合,包括數(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接收.則組件與有向邊的對應關系可通過圖1 表示.

Fig.1 A logical DAG of a stream application圖1 流應用的邏輯DAG

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

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的子線程.以此類推,完成父線程與子線程間的對應關系.

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

此外,為消除節(jié)點內部進程間通信開銷,圖3 為各工作節(jié)點僅分配一個工作進程(worker),因此,拓撲中的通信開銷可分為兩類:一類為類似于數(shù)據(jù)dd1與數(shù)據(jù)df1之間的節(jié)點內部線程間通信;一類為類似于數(shù)據(jù)dd2與數(shù)據(jù)df1之間的節(jié)點間通信.無論集群拓撲內如何傳輸數(shù)據(jù),凡存在直接對應關系,都符合上述傳輸方式.

定義3(路徑開銷).令集合B(p(eji,emn))存在一條子路徑p(eji,emn),表示從頂點eji開始到頂點emn結束.則需要滿足的條件為:如果?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 線程內的數(shù)據(jù)分配

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

令整個拓撲存在n條路徑,則拓撲執(zhí)行關鍵路徑l(Gp)為

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

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

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

2.2 資源約束模型

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

為保證集群拓撲能夠正常運行,則集群工作節(jié)點各類計算資源需要滿足資源約束.本文將滿足工作節(jié)點CPU 的正常計算稱為符合CPU 資源臨界原則,將滿足工作節(jié)點內存的正常計算稱為符合內存資源臨界原則,將滿足工作節(jié)點網(wǎng)絡帶寬的正常傳輸稱為符合網(wǎng)絡帶寬資源臨界原則.此外,具體結果在第4.2 節(jié)體現(xiàn).

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

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

由于當流式處理集群執(zhí)行任務時,拓撲一旦提交將持續(xù)運行下去,即

同理可得,滿足內存資源臨界原則,即

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

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

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

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

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

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

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

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

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

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

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

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

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

若父線程eab傳輸給非關鍵子線程eji數(shù)據(jù)的大小為dji,在完成非關鍵子線程重分配后,父線程對子線程的數(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é)點內部進程間通信開銷、節(jié)點內部線程間的通信開銷與線程的計算開銷這4 部分組成.其中,節(jié)點間通信開銷為;節(jié)點內部線程間的通信開銷為;線程的計算開銷為;由于每個節(jié)點僅分配一個進程,則節(jié)點內部進程間的通信開銷為0.令節(jié)點間存在n條路徑,節(jié)點內部線程間存在m條路徑.集群拓撲數(shù)據(jù)遷移完成后,共有s條節(jié)點間路徑發(fā)生改變,其中有d條節(jié)點間路徑變?yōu)楣?jié)點內部線程間路徑,有c條節(jié)點間路徑變?yōu)樾碌墓?jié)點間路徑.則當前節(jié)點間的通信成本為,即

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

3 節(jié)能策略分析

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

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

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

步驟1:通過負載監(jiān)控器獲得原系統(tǒng)拓撲路徑以及數(shù)據(jù)傳輸與處理的基本信息.

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

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

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

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

3.1 資源約束算法

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

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

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

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

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

算法2 的輸入?yún)?shù)為重分配后的線程集合與關鍵節(jié)點CPU 的優(yōu)先級;輸出參數(shù)為生成一條新的拓撲路徑用于數(shù)據(jù)的傳輸與處理.算法的第1 行表示判斷關鍵節(jié)點是否滿足資源約束條件;算法的第3 行～第10 行表示需要減少集群內節(jié)點間的通信開銷,并預防非關鍵線程重分配出現(xiàn)扎堆現(xiàn)象;算法的第11 行～第15 行表示避免關鍵節(jié)點出現(xiàn)資源溢出現(xiàn)象,并預防非關鍵線程重分配出現(xiàn)扎堆現(xiàn)象;算法的第16 行表示重新計算Zookeeper內狀態(tài)信息到節(jié)點的映射關系,為保證數(shù)據(jù)遷移后數(shù)據(jù)處理的一致性做鋪墊;算法的第 19 行表示更新Zookeeper 的配置文件,防止因拓撲的記憶功能而影響到集群數(shù)據(jù)的傳輸與處理.

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

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

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

3.3 節(jié)能模型

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

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

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

一個完整的Storm 集群由主控節(jié)點、工作節(jié)點與關聯(lián)節(jié)點這3 類節(jié)點組成,其中,主控節(jié)點上運行Nimbus后臺服務,是Storm 集群的中心,負責接受用戶提交的拓撲并為工作節(jié)點分配任務;工作節(jié)點上運行Supervisor后臺服務,負責監(jiān)聽主控節(jié)點分配的數(shù)據(jù)并開啟工作進程及工作線程;關聯(lián)節(jié)點上運行Zookeeper 后臺服務,負責主控節(jié)點和工作節(jié)點間所有的關聯(lián)協(xié)調,存儲整個集群的狀態(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 集群原有框架的基礎上新增了6 個模塊,如圖6 所示.

Fig.6 Improved architecture of Storm圖6 改進后的Storm 框架

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

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

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

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

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

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

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

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

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

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

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

4.1 實驗環(huán)境

為驗證ERDM 的有效性,實驗搭建的Storm 集群包括19 臺PC 機,其中1 臺PC 機上運行1 個Nimbus 進程、1 個UI 進程與數(shù)據(jù)庫.16 臺PC 機上運行Supervisor 進程,3 臺PC 機上運行Zookeeper 進程.此外,每臺PC 機的網(wǎng)卡統(tǒng)一為100Mb/s LAN,且內存統(tǒng)一為8GB.根據(jù)不同節(jié)點的運行狀況,具體環(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 組基準測試,分別為CPU 敏感型(CPU-sensitive)的WordCount、網(wǎng)絡帶寬敏感型(network-sensitive)的Sol、內存敏感型(memory-sensitive)的RollingSort 以及Storm 在真實場景下的應用RollingCount.為消除節(jié)點內部進程間的通信開銷,執(zhí)行各基準測試需滿足工作節(jié)點與工作進程的數(shù)量保持一致(即一個工作節(jié)點內僅分配一個工作進程),其余參數(shù)保留其默認值,具體的參數(shù)配置見表3.

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

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

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

?TMSH-Storm 的核心思想是:對集群的任務調度進行優(yōu)化,繼而達到提高集群性能的目的.

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

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

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

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

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

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

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

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

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

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

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

圖8 為原集群運行4 個基準后,16 個工作節(jié)點(關鍵節(jié)點和非關鍵節(jié)點)的平均資源占用率.如圖8 所示,原集群16 個工作節(jié)點3 類資源的平均占用率主要集中在50%～70%,這為集群執(zhí)行數(shù)據(jù)遷移奠定了基礎.數(shù)據(jù)遷移完成后,各基準測試根據(jù)節(jié)點分布對16 個工作節(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 中缺失的部分為非關鍵節(jié)點,表示非關鍵線程重分配后,非關鍵節(jié)點已不存在線程與數(shù)據(jù),因此予以刪除.此外,非關鍵節(jié)點在集群拓撲中的分布并不相同,表示運行不同基準測試下的拓撲并不相同.

為確定集群在執(zhí)行算法時,算法的響應時間對集群性能的影響,現(xiàn)通過測試一個元組從Spout 出發(fā)到最終被集群拓撲處理完成后所產(chǎn)生的時長,以此反映集群數(shù)據(jù)的處理效率.

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

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

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

此外,可通過使用布隆過濾器對集群拓撲內的數(shù)據(jù)進行預處理,刪除數(shù)據(jù)集內的重復數(shù)據(jù),導致集群拓撲單位時間內處理及傳輸?shù)臄?shù)據(jù)量減少,從而降低了在執(zhí)行ERDM 過程中集群拓撲數(shù)據(jù)傳輸延遲過長的問題.

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

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

(1) 集群性能

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

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

如圖11 所示,集群在執(zhí)行ERDM 后,各基準測試(WordCount、SOL、RollingSort)在單位時間內的數(shù)據(jù)傳輸與處理速率得到了改善.執(zhí)行ERDM 后,集群中數(shù)據(jù)傳輸與處理速率的平均值為77 572(tuple/s),76 471(tuple/s)和59 763(tuple/s),與Storm 默認的調度策略相比提高了13.7%,13.3%和18.2%.其原因為:與Storm 默認的調度策略相比,由于執(zhí)行ERDM 減少了節(jié)點間的通信開銷,降低了路徑的計算延遲,從而導致集群數(shù)據(jù)傳輸與處理的總時間減少.因此,集群中數(shù)據(jù)傳輸與處理的速率得到了改善,單位時間內使集群增加了數(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 在任務遷移過程中并未考慮線程遷移出現(xiàn)扎堆現(xiàn)象,導致任務并未按照原定計劃進行遷移,從而增加了額外的節(jié)點間通信開銷,故對集群數(shù)據(jù)傳輸與處理的速率造成了一定的影響.此外,從優(yōu)化的角度來看,拓撲內線程的總數(shù)為326 個、286 個和318 個.執(zhí)行ERDM 后,集群重新分配非關鍵線程的個數(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 顯示了在實際應用場景下集群拓撲內數(shù)據(jù)傳輸與處理速率.

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

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

(2) 集群能耗

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

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

如圖13 所示,在執(zhí)行ERDM 運行RollingCount 后,集群的平均功率為1 065.37W,執(zhí)行Storm 默認調度策略的平均功率為1 063.15W,執(zhí)行DVRNP 與DVRCP 的平均功率為1 045.32W 與1023.17W,執(zhí)行LEEDSP 的平均功率為1 073.71W.相比于Storm 默認的調度策略,在105s 前,兩種算法的功率基本相等,其原因為數(shù)據(jù)遷移算法尚未觸發(fā).但在[105,115s]內執(zhí)行ERDM,功率急劇升高.其原因為:在[105s,115s]內集群拓撲執(zhí)行數(shù)據(jù)遷移算法,工作節(jié)點的資源占用率消耗巨大,導致集群功率急速上升.而115s 后,數(shù)據(jù)遷移算法執(zhí)行完畢,集群功率逐漸降低,并于130s 后趨于穩(wěn)定,因此不會對單位時間內的集群功率造成影響.與WNDVR-Storm 相比,執(zhí)行ERDM 的平均功率高于WNDVR-Storm,但是執(zhí)行WNDVR-Storm 的功率波動較大,非常不穩(wěn)定,且策略實現(xiàn)較為困難,不適合在大規(guī)模集群中使用.與LEEDSP 相比,執(zhí)行ERDM 的平均功率略低于LEEDSP.其原因為:LEEDSP 并未考慮除CPU 之外部件(如內存與網(wǎng)絡帶寬等)的功率問題,然而Storm 集群拓撲在執(zhí)行任務時,內存與網(wǎng)絡帶寬的功率相對較高是不容忽視的.此外,使用DVFS技術調節(jié)節(jié)點CPU電壓存在較大的偶然性,非常不穩(wěn)定,且技術實現(xiàn)較為困難,同樣不適合部署在大規(guī)模地集群當中.為計算集群的能耗,需要對集群內的功率進行積分,具體結果如圖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 默認調度策略的能耗為7 270.3KJ,執(zhí)行DVRNP 與DVRCP 的能耗為6 317.3KJ 與6 031.5KJ,執(zhí)行LEEDSP 的能耗為 5 934.7KJ.與 Storm 默認調度策略相比,執(zhí)行 ERDM 集群能耗節(jié)約了 27.3%.但是在[4300000tuple,6000000tuple]內,集群執(zhí)行ERDM 的能耗高于Storm 默認的調度策略.其原因為在[4300000tuple,6000000tuple]內集群拓撲執(zhí)行數(shù)據(jù)遷移算法,導致集群能耗升高.而在[9000000tuple,15000000tuple]執(zhí)行ERDM的能耗遠低于Storm 默認的調度策略,其原因為數(shù)據(jù)遷移算法執(zhí)行完畢,由于路徑的計算延遲減少導致集群拓撲內的數(shù)據(jù)傳輸與處理速率高于Storm 默認的調度策略,因此相同數(shù)據(jù)量下能耗遠低于Storm 默認的調度策略.與WNDVR-Storm 相比,執(zhí)行ERDM 集群的能耗略低于WNDVR-Storm,但是執(zhí)行WNDVR-Storm 的能耗上升幅度不斷變化且逐漸升高.這是由于隨著集群數(shù)據(jù)量的不斷增大,數(shù)據(jù)量始終超過額定閾值,導致 WNDVR-Storm 基本失效.與LEEDSP 相比,執(zhí)行ERDM 集群的能耗始終低于LEEDSP.這是由于LEEDSP 并未考慮內存與網(wǎng)絡帶寬等部件的能耗,且執(zhí)行LEEDSP 內資源調度算法的能耗高于執(zhí)行ERDM 內數(shù)據(jù)遷移算法的能耗.此外,隨著節(jié)點數(shù)的增加,集群內存與網(wǎng)絡帶寬的能耗比重會不斷增大,從而始終影響LEEDSP 的節(jié)能效果.為量化集群內數(shù)據(jù)的傳輸與處理時間與能耗的關系,需要集群在相同數(shù)據(jù)量下對ERDM 與Storm 默認調度策略進行對比,具體的實驗結果如圖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 默認調度策略的時間為300s.與Storm 默認調度策略相比,相同數(shù)據(jù)量下執(zhí)行ERDM 集群拓撲中數(shù)據(jù)的傳輸與處理時間提高了28%.因此可以確定:在相同條件下,集群數(shù)據(jù)傳輸與處理的時間每提高1%,則集群的能耗降低1%.綜上所述,相比于Storm 默認的調度策略,本文提出的ERDM 具有更好的節(jié)能效果.

5 總結與展望

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

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