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

（1.新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；2.中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300；3.廣東金融學(xué)院互聯(lián)網(wǎng)金融與信息工程學(xué)院，廣東 廣州 510521；4.新疆財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與信息學(xué)院，新疆 烏魯木齊 830012）

1 引言

近年來，隨著移動(dòng)互聯(lián)網(wǎng)、云計(jì)算和物聯(lián)網(wǎng)的高速發(fā)展，數(shù)據(jù)的產(chǎn)生與積累已達(dá)到前所未有的速度，并推動(dòng)著各行各業(yè)進(jìn)入大數(shù)據(jù)時(shí)代。大數(shù)據(jù)的相關(guān)研究已成為學(xué)術(shù)界與產(chǎn)業(yè)界共同探討的熱點(diǎn)話題，其主要的處理模式為批量處理、流式處理、交互處理和圖處理等[1-5]。隨著大數(shù)據(jù)的飛速發(fā)展，各種處理模式不斷產(chǎn)生，出現(xiàn)了高能耗、高污染的。因此如何有效解決由于新興技術(shù)帶來的高能耗，一直是廣大學(xué)者共同面對(duì)的問題。據(jù)美國(guó)斯坦福大學(xué)的調(diào)查發(fā)現(xiàn)，全球數(shù)據(jù)中心2010年的耗電量為2 355億kW?h，占據(jù)全球電力總消耗的1.3%，其中美國(guó)數(shù)據(jù)中心的耗電量占據(jù)全美國(guó)電力總消耗的2%[6]。我國(guó)數(shù)據(jù)中心的電力消耗同樣驚人，截至2011年底，我國(guó)數(shù)據(jù)中心的總量達(dá)到43萬個(gè)，數(shù)據(jù)中心的耗電量占據(jù)全國(guó)電力總消耗的1.5%，并且所占比例仍在逐年上升[7]。隨著大數(shù)據(jù)時(shí)代的到來，海量的能源被用于數(shù)據(jù)處理，但其能效不斷降低。因此如何有效提高能源的利用率，是解決大數(shù)據(jù)處理能耗問題的關(guān)鍵。

大數(shù)據(jù)的處理一般被分為實(shí)時(shí)處理與非實(shí)時(shí)處理，在IDC與希捷（Seagate）公司聯(lián)合發(fā)布的《數(shù)據(jù)時(shí)代2025》白皮書中指出，2025年全球數(shù)據(jù)總量將達(dá)到163 ZB，比2016年創(chuàng)造出的數(shù)據(jù)量提高了10倍。其中實(shí)時(shí)數(shù)據(jù)所占比例超過25%[8]。由此可見，實(shí)時(shí)大數(shù)據(jù)擁有廣泛的應(yīng)用前景，而在大數(shù)據(jù)的處理模式中，流式處理具有很高的實(shí)時(shí)性。流式處理作為新的可容錯(cuò)、高性能的分布式處理平臺(tái)，存在著高能耗的問題[9]，已經(jīng)給產(chǎn)業(yè)界帶來了巨大的能耗開銷。因此流式處理平臺(tái)的節(jié)能優(yōu)化是一個(gè)亟待解決的問題。

現(xiàn)有流式處理平臺(tái)以Apache Storm框架[10]為代表。Storm是一個(gè)開源、主從式架構(gòu)、橫向擴(kuò)展性良好且容錯(cuò)能力強(qiáng)的分布式實(shí)時(shí)處理平臺(tái)，其編程模型簡(jiǎn)單，支持包含Java在內(nèi)的多種編程語言，數(shù)據(jù)處理高效。相較于不開源的Puma[11]以及社區(qū)冷淡的S4[12]，Storm擁有更廣闊的發(fā)展前景；相較于目前主流的實(shí)時(shí)處理平臺(tái)Flink[13]與Spark Streaming[14]，Storm的數(shù)據(jù)處理實(shí)時(shí)性能效果更佳；相較于后起之秀Heron[15]，Storm更加簡(jiǎn)單且業(yè)界的認(rèn)可度與成熟度更高。目前Storm已經(jīng)廣泛運(yùn)用到銀行金融[16]、臨床醫(yī)療[17]、社交網(wǎng)絡(luò)[18]等行業(yè)進(jìn)行實(shí)時(shí)大數(shù)據(jù)分析，并廣泛運(yùn)用到機(jī)器學(xué)習(xí)算法、分布式遠(yuǎn)程調(diào)用等領(lǐng)域進(jìn)行理論研究[19]，被譽(yù)為“實(shí)時(shí)處理領(lǐng)域的Hadoop”。

在Storm集群中，一個(gè)流式作業(yè)（拓?fù)洌┩ㄟ^有向無環(huán)圖（DAG,directed acyclic graph）表示，且拓?fù)鋬?nèi)的數(shù)據(jù)通過輪詢（RR,round-robin）調(diào)度策略均勻分配到各個(gè)工作線程上，而一個(gè)工作進(jìn)程包含多個(gè)工作線程。Storm集群采用輪詢調(diào)度策略均勻分配數(shù)據(jù)需要符合8種流組模式，其中最重要的是隨機(jī)分組（shuffle grouping）。但是隨機(jī)分組存在兩大弊端，致使Storm集群產(chǎn)生額外資源與能源的浪費(fèi)。其一是數(shù)據(jù)流經(jīng)工作節(jié)點(diǎn)時(shí)，有些線程數(shù)據(jù)處理復(fù)雜度較低，隨機(jī)分組致使線程因計(jì)算資源過剩而產(chǎn)生浪費(fèi)；其二是未考慮節(jié)能的問題，對(duì)于數(shù)據(jù)處理復(fù)雜度較低的線程，并未對(duì)存在該線程的節(jié)點(diǎn)進(jìn)行節(jié)能處理，造成能源的浪費(fèi)。因此要解決因隨機(jī)分組而帶來的資源與能源的浪費(fèi)問題，需要綜合考慮集群的路徑、工作節(jié)點(diǎn)的計(jì)算資源、數(shù)據(jù)的匹配等各方面的因素，尋找最優(yōu)的數(shù)據(jù)分配策略，從而在保證性能的前提下實(shí)現(xiàn)節(jié)約資源與能源的目的。本文的主要貢獻(xiàn)如下。

1)通過分析Storm集群的拓?fù)浣Y(jié)構(gòu)，建立數(shù)據(jù)分配模型、路徑開銷模型與資源約束模型，進(jìn)一步提出最優(yōu)線程數(shù)據(jù)重組原則，為數(shù)據(jù)遷移合并模型的建立奠定了基礎(chǔ)。

2)根據(jù)資源約束模型、數(shù)據(jù)遷移合并模型和節(jié)點(diǎn)降壓原則，提出基于Storm平臺(tái)的數(shù)據(jù)遷移合并節(jié)能策略（DMM-Storm,energy-efficient strategy for data migration and merging in Storm），該策略包括資源約束算法、數(shù)據(jù)遷移合并算法和節(jié)點(diǎn)降壓算法。其中，資源約束算法驗(yàn)證工作節(jié)點(diǎn)是否允許數(shù)據(jù)遷移，數(shù)據(jù)遷移合并算法根據(jù)集群拓?fù)涞膶?shí)際情況，確定數(shù)據(jù)遷移的最優(yōu)方法，并為節(jié)點(diǎn)降壓算法提供了理論支撐。節(jié)點(diǎn)降壓算法根據(jù)數(shù)據(jù)遷移合并算法與節(jié)點(diǎn)降壓原則的特點(diǎn)，降低非關(guān)鍵路徑上工作節(jié)點(diǎn)的電壓以減少集群中的能耗損失。最后通過實(shí)驗(yàn)從多角度驗(yàn)證了算法的有效性。

2 相關(guān)工作

學(xué)術(shù)界與產(chǎn)業(yè)界針對(duì)現(xiàn)有大規(guī)模數(shù)據(jù)處理平臺(tái)節(jié)能方面的研究主要分為4類：批量數(shù)據(jù)處理平臺(tái)節(jié)能算法、流式數(shù)據(jù)處理平臺(tái)節(jié)能算法、圖數(shù)據(jù)處理平臺(tái)節(jié)能算法和交互數(shù)據(jù)處理平臺(tái)節(jié)能算法。其中批量數(shù)據(jù)處理平臺(tái)節(jié)能算法的核心思想主要是以Hadoop為代表進(jìn)行算法的優(yōu)化，通常對(duì)框架內(nèi)的磁盤區(qū)域進(jìn)行劃分，通過動(dòng)態(tài)組件失活（dynamic component deactivation），即在一段時(shí)間內(nèi)動(dòng)態(tài)關(guān)閉集群硬件的部分組件或?qū)Υ疟P部分區(qū)域進(jìn)行休眠達(dá)到節(jié)能的目的[20-22]；圖數(shù)據(jù)處理平臺(tái)節(jié)能算法的核心思想主要是以Pregel為代表進(jìn)行算法的優(yōu)化，通常對(duì)圖邊緣數(shù)據(jù)的重要性進(jìn)行判別，彈性調(diào)節(jié)集群的功耗達(dá)到節(jié)能的效果[23-25]；交互數(shù)據(jù)處理平臺(tái)節(jié)能算法的核心思想主要是以MapReduce為代表進(jìn)行算法的優(yōu)化，通常以優(yōu)化配置參數(shù)[26]、作業(yè)遷移調(diào)度[27]和任務(wù)完成后關(guān)閉對(duì)應(yīng)節(jié)點(diǎn)[28]等提高能源利用率達(dá)到節(jié)能的目的[29-31]。這3種方案在一定程度上解決了大數(shù)據(jù)處理平臺(tái)的能耗問題，但是對(duì)于實(shí)時(shí)性較高的數(shù)據(jù)處理模式存在著較大的局限性，無法直接作用于流式處理的平臺(tái)。針對(duì)流式大數(shù)據(jù)處理模式的高能耗問題，現(xiàn)有學(xué)者提出從硬件[32]、軟件[33]以及兩者結(jié)合[34]這3個(gè)方面進(jìn)行研究。

硬件的節(jié)能策略主要通過替換高能耗的電子元件[35]，以達(dá)到節(jié)能的效果。該方法節(jié)能效果顯著且操作簡(jiǎn)單，但其價(jià)格高昂，不適合部署于大規(guī)模的集群當(dāng)中。軟件的節(jié)能策略主要通過任務(wù)調(diào)度[36]、資源遷移[37]等方法以提高集群的性能，達(dá)到節(jié)能的目的，但由于節(jié)能效果不穩(wěn)定致使節(jié)能效果不佳。軟件與硬件結(jié)合的節(jié)能策略是現(xiàn)在研究的重點(diǎn)，主要通過在任務(wù)完成后動(dòng)態(tài)調(diào)節(jié)集群的電壓或電源，實(shí)現(xiàn)集群電壓或電源的縮放管理[38]，以達(dá)到節(jié)能的目的。Cordeschi等[39]針對(duì)流式大數(shù)據(jù)傳輸?shù)牟豢煽?、不穩(wěn)定以及實(shí)時(shí)數(shù)據(jù)量大等特性，在不影響響應(yīng)時(shí)間約束條件的前提下，計(jì)算了最小化網(wǎng)絡(luò)傳輸?shù)目偰芎?。Wang等[38]通過使用動(dòng)態(tài)電壓調(diào)控技術(shù)（DVFS,dynamic voltage frequency scaling）調(diào)節(jié)集群CPU的電壓以達(dá)到節(jié)能的目的。Panda等[40]通過引入上下文感知數(shù)據(jù)流執(zhí)行模型，提高了任務(wù)執(zhí)行的效率，從側(cè)面降低了集群的能耗。綜上所述，以上研究都是從流式處理自身特性的角度出發(fā)，建立合理的流式處理能耗模型。但針對(duì)Storm平臺(tái)的節(jié)能策略仍具有較高的研究?jī)r(jià)值。

Sun等[9]提出一種流式大數(shù)據(jù)處理環(huán)境下的實(shí)時(shí)資源調(diào)度節(jié)能策略（Re-Stream），該策略通過建立集群響應(yīng)時(shí)間、CPU占用率以及能耗之間的邏輯關(guān)系，并根據(jù)流式處理框架的基本性質(zhì)，對(duì)整個(gè)集群拓?fù)鋱?zhí)行的關(guān)鍵路徑進(jìn)行定義，綜合利用拓?fù)鋱?zhí)行關(guān)鍵路徑上性能感知的任務(wù)調(diào)度策略，以及拓?fù)鋱?zhí)行非關(guān)鍵路徑上能耗感知的任務(wù)整合策略，使任務(wù)響應(yīng)時(shí)間和集群能耗均降低到最低值。

Zong等[41]根據(jù)流式大數(shù)據(jù)處理的自身特性提出2種基于副本的調(diào)度節(jié)能算法——能量感知副本算法（EAD,energy-aware duplication）以及性能和能量均衡副本算法（PEBD,performance-energy balanced duplication），該節(jié)能算法的核心思想為集群拓?fù)洳粓?zhí)行任務(wù)調(diào)度時(shí)或數(shù)據(jù)處理完成后，立刻降低集群節(jié)點(diǎn)的電壓。該算法不僅保證了集群數(shù)據(jù)處理的快速執(zhí)行，同時(shí)滿足任務(wù)執(zhí)行完成后節(jié)約集群能耗的思想。

蒲勇霖等[42]針對(duì)Storm平臺(tái)在進(jìn)行數(shù)據(jù)處理時(shí)存在高能耗的問題，提出工作節(jié)點(diǎn)內(nèi)存電壓調(diào)控節(jié)能策略（WNDVR-Storm），該策略根據(jù)Storm集群實(shí)際的數(shù)據(jù)處理及傳輸情況，對(duì)集群工作節(jié)點(diǎn)數(shù)據(jù)處理能力進(jìn)行判別，并由集群數(shù)據(jù)流實(shí)際情況，通過對(duì)工作節(jié)點(diǎn)的內(nèi)存電壓進(jìn)行動(dòng)態(tài)調(diào)節(jié)，以達(dá)到節(jié)能的目的。該節(jié)能策略不僅有效降低了集群的能耗，而且在一定程度上對(duì)集群的負(fù)載均衡進(jìn)行了優(yōu)化。但是還存在以下兩點(diǎn)不足：1)對(duì)集群工作節(jié)點(diǎn)內(nèi)存電壓進(jìn)行動(dòng)態(tài)調(diào)節(jié)，實(shí)現(xiàn)難度較高且存在一定的偶然性；2)若集群規(guī)模較大且工作節(jié)點(diǎn)過多，節(jié)能算法可能失效。

本文與文獻(xiàn)[9,38-42]的不同之處主要體現(xiàn)在4個(gè)方面。首先，本文通過分析集群進(jìn)行數(shù)據(jù)遷移時(shí)，工作節(jié)點(diǎn)存在資源約束（CPU、網(wǎng)絡(luò)帶寬和內(nèi)存）的問題而構(gòu)建資源約束模型，防止集群由于數(shù)據(jù)遷移而造成資源溢出的問題。其次，本文根據(jù)最優(yōu)線程數(shù)據(jù)重組原則與節(jié)點(diǎn)降壓原則，完成集群的數(shù)據(jù)遷移與節(jié)點(diǎn)降壓，該過程不會(huì)影響集群的性能，并節(jié)約了集群的能耗。第三，本文不僅節(jié)約了集群的能耗，還通過數(shù)據(jù)遷移算法減少了節(jié)點(diǎn)之間的通信開銷。最后，本文選取Intel公司[10]發(fā)布在GitHub上的基準(zhǔn)測(cè)試而非自己定義的拓?fù)?，因此更具代表性?/p>

3 問題建模與分析

本節(jié)主要從Storm拓?fù)涞臄?shù)據(jù)分配模型、路徑與成本模型和資源約束模型出發(fā)，分析Storm集群在節(jié)能方面存在的局限性，由此提出非關(guān)鍵線程中的數(shù)據(jù)遷移合并與關(guān)鍵線程中的數(shù)據(jù)遷移合并這2種模型，為節(jié)能策略的設(shè)計(jì)與實(shí)現(xiàn)提供了理論依據(jù)。

3.1 數(shù)據(jù)分配模型

在Storm集群中，一個(gè)流式作業(yè)由一個(gè)拓?fù)洌╰opology）的有向無環(huán)圖構(gòu)成，其中數(shù)據(jù)源編程單元（spout）和數(shù)據(jù)處理編程單元（bolt）這2類組件（component）共同構(gòu)成了數(shù)據(jù)源的頂點(diǎn)，且各組件之間針對(duì)不同的流組模式發(fā)送和接收數(shù)據(jù)流，進(jìn)而構(gòu)成了有向無環(huán)圖的弧。為提高拓?fù)鋵?duì)數(shù)據(jù)流的并行運(yùn)算能力，令每個(gè)組件都可同時(shí)創(chuàng)造多個(gè)線程（executor）。提交拓?fù)渲?，?shù)據(jù)將分發(fā)到集群各工作節(jié)點(diǎn)中，并進(jìn)行數(shù)據(jù)的處理與傳輸。設(shè)集群工作節(jié)點(diǎn)集合為，線程集合為，將工作節(jié)點(diǎn)的數(shù)據(jù)均勻分配到集群的線程上，記工作節(jié)點(diǎn)分配給線程eji的數(shù)據(jù)為daj（i若線程的并行度為1，則該線程上的數(shù)據(jù)為daj），則集合DAn={daj1,daj2,…,dajn}表示工作節(jié)點(diǎn)分配到線程上的數(shù)據(jù)集合。圖1為在3個(gè)工作節(jié)點(diǎn)下，Storm集群使用輪詢調(diào)度策略后線程數(shù)據(jù)的分配情況。其中工作節(jié)點(diǎn)的集合為N={n1,n2,n3}，線程內(nèi)數(shù)據(jù)可表示為

圖1 線程數(shù)據(jù)分配

為了消除節(jié)點(diǎn)內(nèi)部進(jìn)程間通信開銷，圖1為每個(gè)工作節(jié)點(diǎn)僅分配一個(gè)進(jìn)程（worker），因此在拓?fù)鋱?zhí)行過程中只需考慮2類通信成本開銷，一類為線程數(shù)據(jù)dad1與daf1之間，節(jié)點(diǎn)內(nèi)部線程間的通信開銷；另一類為線程數(shù)據(jù)dad2與daf1之間，節(jié)點(diǎn)間通信開銷。無論工作節(jié)點(diǎn)如何分配數(shù)據(jù)，都滿足以上2種通信開銷。

此外，令線程ea與eb為線程{ec,ed1,ed2,ed3,ee}的父線程，若線程{ec,ed1,ed2,ed3}為父線程ea下的子線程，則線程{ec,ed1,ed2,ed3}內(nèi)的線程互為同源線程；若線程{ed1,ed2,ed3,ee}為父線程eb下的子線程，則線程{ed1,ed2,ed3,ee}內(nèi)的線程互為同源線程，以此類推，完成父線程與同源線程之間的對(duì)應(yīng)關(guān)系。

3.2 路徑開銷模型

令一條路徑p(eji,emn)為集合B(p(eji,emn))的子路徑，其中頂點(diǎn)eji與emn表示從eji開始到emn結(jié)束。對(duì)于?k，則bj,k∈p(eji,emn)，bk,i∈p(eji,emn)，由此對(duì)于?bj,i∈p(eji,emn)都成立。此外，對(duì)于?bk,l∈p(eji,emn)，如果k≠j，則?m與bm,k∈p(eji,emn)；如果i≠j，則?m與bl,m∈p(eji,emn)。

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

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

此外，在確保Storm集群性能不變的前提下，根據(jù)數(shù)據(jù)在拓?fù)潢P(guān)鍵路徑處理及傳輸時(shí)間，確定位于拓?fù)鋱?zhí)行關(guān)鍵路徑上的工作節(jié)點(diǎn)與位于拓?fù)鋱?zhí)行非關(guān)鍵路徑上的工作節(jié)點(diǎn)。將位于拓?fù)鋱?zhí)行關(guān)鍵路徑上的工作節(jié)點(diǎn)稱作關(guān)鍵節(jié)點(diǎn)，位于拓?fù)鋱?zhí)行非關(guān)鍵路徑上的工作節(jié)點(diǎn)稱作非關(guān)鍵節(jié)點(diǎn)，位于拓?fù)鋱?zhí)行關(guān)鍵路徑上的線程稱作關(guān)鍵線程，位于拓?fù)鋱?zhí)行非關(guān)鍵路徑上的線程稱作非關(guān)鍵線程。

以圖2為例，定義一條拓?fù)鋱?zhí)行關(guān)鍵路徑為ea→ed1→ef2→eh，則工作節(jié)點(diǎn)n3上的所有線程為非關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程，工作節(jié)點(diǎn)n1與n2上的線程分為2類：一類為關(guān)鍵節(jié)點(diǎn)上的關(guān)鍵線程，另一類為關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程。此外，線程ec與線程{ed1,ed2,ed3}互為同源線程，以此類推，完成非關(guān)鍵節(jié)點(diǎn)上非關(guān)鍵線程與關(guān)鍵節(jié)點(diǎn)上線程的對(duì)應(yīng)關(guān)系。

圖2 拓?fù)鋱?zhí)行關(guān)鍵路徑的數(shù)據(jù)傳輸及處理情況

3.3 資源約束模型

根據(jù)Storm集群進(jìn)行數(shù)據(jù)遷移的特點(diǎn)，令工作節(jié)點(diǎn)分配給線程的資源集合為且計(jì)算資源主要包括CPU、內(nèi)存及網(wǎng)絡(luò)帶寬3類資源的占用率。令工作節(jié)點(diǎn)內(nèi)3類資源占用的極限為。其中表示工作節(jié)點(diǎn)CPU資源占用的極限，表示工作節(jié)點(diǎn)內(nèi)存資源占用的極限，表示工作節(jié)點(diǎn)網(wǎng)絡(luò)帶寬資源占用的極限，原工作節(jié)點(diǎn)CPU資源占用為（單位為Hz），內(nèi)存資源占用為（單位為B），網(wǎng)絡(luò)帶寬資源占用為（單位為bit/s）。由于Storm集群環(huán)境中數(shù)據(jù)源源不斷產(chǎn)生，且拓?fù)湟坏┨峤粚⒊掷m(xù)運(yùn)行下去，因此為了保證集群的高效運(yùn)行，且工作節(jié)點(diǎn)的資源不會(huì)溢出，這3類資源需要滿足如下條件，即

為了滿足集群運(yùn)行的可靠性，集群工作節(jié)點(diǎn)不能滿負(fù)荷運(yùn)行，本文將符合CPU資源的正常計(jì)算稱為滿足CPU資源臨界原則，符合內(nèi)存資源的正常計(jì)算稱為滿足內(nèi)存資源臨界原則，符合網(wǎng)絡(luò)帶寬資源的正常傳輸稱為滿足網(wǎng)絡(luò)帶寬資源臨近原則。

當(dāng)線程準(zhǔn)備遷入數(shù)據(jù)時(shí)，該工作節(jié)點(diǎn)資源滿足CPU資源臨界原則、內(nèi)存資源臨界原則以及網(wǎng)絡(luò)帶寬資源臨近原則時(shí)，允許線程遷入數(shù)據(jù)。即數(shù)據(jù)遷入原則tr需要滿足如下條件

為了在保證拓?fù)涓咝?zhí)行的同時(shí)，提高資源的占用率，且在一定程度上優(yōu)化集群的負(fù)載分配，資源約束模型為后續(xù)數(shù)據(jù)重分配原則提供了理論依據(jù)。

3.4 拓?fù)浞顷P(guān)鍵線程中的數(shù)據(jù)遷移合并模型

根據(jù)3.3節(jié)資源約束模型，提出最優(yōu)線程數(shù)據(jù)重組原則；本節(jié)針對(duì)存在關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程，提出非關(guān)鍵線程中的數(shù)據(jù)遷移合并模型。此外，根據(jù)集群數(shù)據(jù)傳輸及處理總時(shí)間，確定了拓?fù)鋱?zhí)行非關(guān)鍵路徑工作節(jié)點(diǎn)電壓的最低值。

定義1最優(yōu)線程數(shù)據(jù)重組原則。根據(jù)3.1節(jié)可知，E′(C)∈E(C)且E′(C)={eji,emn,…,eyz}為同源線程集合。同源線程之間數(shù)據(jù)的遷移合并可通過父線程進(jìn)行數(shù)據(jù)的重分配，而非同源線程之間進(jìn)行數(shù)據(jù)的遷移合并可能會(huì)出現(xiàn)數(shù)據(jù)不匹配問題，因此線程之間數(shù)據(jù)的遷移合并需要選擇互為同源的線程。定義父線程eab傳入子線程eji與emn數(shù)據(jù)大小分別為daab,ji與daab,mn，執(zhí)行最優(yōu)線程數(shù)據(jù)重組原則后，父線程對(duì)子線程的數(shù)據(jù)分配出現(xiàn)改變，類似數(shù)據(jù)由線程emn遷入線程eji，且遷入的數(shù)據(jù)大小為

由3.3節(jié)可知，線程之間數(shù)據(jù)的遷移合并，被遷入數(shù)據(jù)的線程存在工作節(jié)點(diǎn)的資源約束問題，則為滿足資源約束條件，存在

根據(jù)最優(yōu)線程數(shù)據(jù)重組原則設(shè)計(jì)數(shù)據(jù)遷移合并模型，為非關(guān)鍵節(jié)點(diǎn)的降壓奠定了基礎(chǔ)。針對(duì)是否存在關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程，提出2種線程中的數(shù)據(jù)遷移合并模型，當(dāng)集群存在關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程時(shí)，集群實(shí)施拓?fù)浞顷P(guān)鍵線程中的數(shù)據(jù)遷移合并模型，且該模型不改變集群性能；當(dāng)集群不存在關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程時(shí)，集群實(shí)施拓?fù)潢P(guān)鍵線程中的數(shù)據(jù)遷移合并模型，且該模型對(duì)系統(tǒng)性能造成一定的影響需要進(jìn)行相應(yīng)的評(píng)估。

定義2節(jié)點(diǎn)降壓原則。為計(jì)算集群實(shí)施節(jié)能策略后非關(guān)鍵節(jié)點(diǎn)電壓的最低值，需要注意以下兩點(diǎn)：其一，確定非關(guān)鍵節(jié)點(diǎn)電壓的限制條件；其二，確定非關(guān)鍵節(jié)點(diǎn)電壓的改變量。

集群實(shí)施非關(guān)鍵線程中的數(shù)據(jù)遷移合并模型，需要令非關(guān)鍵節(jié)點(diǎn)的集合為其中模型以不改變Storm集群性能為前提，因此不能改變拓?fù)鋱?zhí)行關(guān)鍵路徑，由此可知模型的執(zhí)行存在一個(gè)限制條件，即數(shù)據(jù)傳輸及處理的總時(shí)間不會(huì)發(fā)生改變。根據(jù)3.3節(jié)可知，線程遷入數(shù)據(jù)存在制約條件，即線程eji遷入數(shù)據(jù)需要滿足tr。由于線程遷入數(shù)據(jù)為，關(guān)鍵路徑的時(shí)間t不發(fā)生改變，則非關(guān)鍵節(jié)點(diǎn)的電壓為，此時(shí)調(diào)節(jié)電壓保證關(guān)鍵路徑的時(shí)間不發(fā)生改變，獲得改變后的電壓為。由此存在一個(gè)函數(shù)關(guān)系

其中，φ表示數(shù)據(jù)遷移合并過程中資源的損耗率，且0<φ<1。電壓的改變過程符合貪心原則，未達(dá)到貪婪狀態(tài)則無法確定電壓調(diào)節(jié)的最低值，因此為計(jì)算電壓調(diào)節(jié)的改變量vc，引入梯度下降的方法

其中，ε表示電壓改變軌跡；表示關(guān)鍵路徑時(shí)間不發(fā)生改變；α表示訓(xùn)練率，且0<α<1。當(dāng)滿足上述條件時(shí)，非關(guān)鍵節(jié)點(diǎn)的電壓以vc為步長(zhǎng)逐漸降低，直至達(dá)到條件改變的臨界點(diǎn)，由此可得集群實(shí)施非關(guān)鍵線程中的數(shù)據(jù)遷移合并模型后，非關(guān)鍵節(jié)點(diǎn)電壓的最低值。由于電壓調(diào)節(jié)過程中集群關(guān)鍵路徑不發(fā)生改變，則集群數(shù)據(jù)傳輸與處理的總時(shí)間不發(fā)生改變，因此集群的性能不發(fā)生改變。

3.5 拓?fù)潢P(guān)鍵線程中的數(shù)據(jù)遷移合并模型

本節(jié)針對(duì)不存在關(guān)鍵節(jié)點(diǎn)上的非關(guān)鍵線程，提出關(guān)鍵線程中的數(shù)據(jù)遷移合并模型。通過定義能效比（EER,energy efficiency ratio），確定集群性能與能耗之間的關(guān)系，并根據(jù)能效比，確定拓?fù)鋱?zhí)行關(guān)鍵路徑工作節(jié)點(diǎn)電壓的最低值。

模型以不改變Storm集群的性能為前提，即不改變數(shù)據(jù)傳輸及處理的時(shí)間。關(guān)鍵線程中的數(shù)據(jù)遷移合并模型對(duì)集群數(shù)據(jù)的處理及傳輸造成一定的影響，因此需要對(duì)集群的性能與能耗進(jìn)行評(píng)估。

定義3能效比。通過3.2節(jié)可知，集群數(shù)據(jù)處理及傳輸?shù)目倳r(shí)間為t（單位為s），定義集群數(shù)據(jù)處理及傳輸?shù)目偰芎臑镋（單位為J），則建立能效比模型，即集群數(shù)據(jù)處理及傳輸總時(shí)間與總能耗乘積的倒數(shù)為能效比R（單位為（s?J）-1），即

其中，C表示能效比誤差常數(shù)，且0

定理1Storm集群在實(shí)際拓?fù)鋱?zhí)行過程中，數(shù)據(jù)處理及傳輸總時(shí)間與總能耗的能效比R為

證明通過定義3可知，集群數(shù)據(jù)處理及傳輸總時(shí)間與總能耗的比值如果將總時(shí)間劃分為n等份，t為[t0,t1,…,tn-1]，則有

化簡(jiǎn)式(18)得

因此，獲得

證畢。

為計(jì)算集群實(shí)施關(guān)鍵線程中的數(shù)據(jù)遷移合并模型后的總能耗，需要計(jì)算集群非關(guān)鍵節(jié)點(diǎn)電壓的最低值。根據(jù)定義2可知，存在2個(gè)制約條件，其中實(shí)施關(guān)鍵線程中的數(shù)據(jù)遷移合并模型后，系統(tǒng)的能效比與原系統(tǒng)能效比之間的關(guān)系為一個(gè)制約條件。已知集群非關(guān)鍵節(jié)點(diǎn)的集合為通過3.3節(jié)可知，線程遷入數(shù)據(jù)存在制約條件，則線程數(shù)據(jù)da遷入需要滿足tr。由于線程遷入數(shù)據(jù)，由定義3可知集群的能效比為R，調(diào)節(jié)此時(shí)非關(guān)鍵節(jié)點(diǎn)的電壓為。同理，可獲得函數(shù)為

集群實(shí)施關(guān)鍵線程中的數(shù)據(jù)遷移合并模型電壓的改變量vc′為

其中，R(vei,da,vei+1)表示集群的能效比。當(dāng)滿足上述條件時(shí)，非關(guān)鍵節(jié)點(diǎn)的電壓以vc′為步長(zhǎng)逐漸降低，直至達(dá)到條件改變的臨界點(diǎn)，由此可得集群實(shí)施關(guān)鍵線程中的數(shù)據(jù)遷移合并模型后非關(guān)鍵節(jié)點(diǎn)電壓的最低值。

4 數(shù)據(jù)遷移合并節(jié)能策略

本節(jié)主要介紹基于Storm平臺(tái)的數(shù)據(jù)遷移合并節(jié)能策略，該策略在不影響集群性能的前提下，根據(jù)非關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程上數(shù)據(jù)的遷移情況，對(duì)非關(guān)鍵節(jié)點(diǎn)的電壓進(jìn)行調(diào)節(jié)，以此達(dá)到節(jié)能的目的。節(jié)能策略主要分為以下5個(gè)步驟，其執(zhí)行流程如圖3所示。

步驟1通過監(jiān)控器獲得原系統(tǒng)拓?fù)鋱?zhí)行關(guān)鍵路徑的基本信息。

步驟2判斷是否存在關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程。

步驟3計(jì)算被遷入數(shù)據(jù)的線程是否滿足tr。

步驟4計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值。

步驟5根據(jù)不同的節(jié)能算法計(jì)算集群總能耗。

圖3 節(jié)能策略流程

4.1 資源約束算法

根據(jù)3.3節(jié)可知，線程被遷入數(shù)據(jù)首先應(yīng)該考慮工作節(jié)點(diǎn)是否會(huì)出現(xiàn)資源溢出現(xiàn)象，因此需要對(duì)工作節(jié)點(diǎn)的資源總量進(jìn)行評(píng)估。

當(dāng)關(guān)鍵節(jié)點(diǎn)的某類資源占用率達(dá)到極限時(shí)，將該節(jié)點(diǎn)設(shè)置為極限節(jié)點(diǎn)，表示不能再向該節(jié)點(diǎn)內(nèi)線程遷入數(shù)據(jù)，需要重新選擇關(guān)鍵節(jié)點(diǎn)，且被選節(jié)點(diǎn)必須滿足數(shù)據(jù)遷入3條原則。針對(duì)線程被遷入數(shù)據(jù)存在節(jié)點(diǎn)資源約束的問題，提出算法1，確定非關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程上的數(shù)據(jù)可以順利遷出。具體的算法過程如下所示。

算法1資源約束算法

算法1為工作節(jié)點(diǎn)的資源約束模型。當(dāng)工作節(jié)點(diǎn)滿足tr時(shí)，允許線程遷入數(shù)據(jù)。步驟1)和步驟2)表示判斷節(jié)點(diǎn)ni是否為極限節(jié)點(diǎn)，若為極限節(jié)點(diǎn)則該節(jié)點(diǎn)上線程不能被遷入數(shù)據(jù)，否則需要判斷工作節(jié)點(diǎn)數(shù)據(jù)遷入是否滿足3條原則；步驟5)～步驟7)表示判斷關(guān)鍵節(jié)點(diǎn)是否滿足CPU資源臨界原則；步驟8)～步驟10)表示在滿足CPU資源臨界原則后，判斷關(guān)鍵節(jié)點(diǎn)是否滿足內(nèi)存資源臨界原則；步驟11)～步驟13)表示在滿足之前的兩條原則后，判斷關(guān)鍵節(jié)點(diǎn)是否滿足網(wǎng)絡(luò)帶寬資源臨近原則。

Storm集群節(jié)能策略首先需要考慮算法的時(shí)間復(fù)雜度，原集群數(shù)據(jù)的處理及傳輸為輪詢調(diào)度算法，其時(shí)間復(fù)雜度為O(n)。首先，算法1需要判斷節(jié)點(diǎn)是否為極限節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(1)；其次，算法1的本質(zhì)為依次判斷數(shù)據(jù)遷入節(jié)點(diǎn)是否滿足3條原則，其時(shí)間復(fù)雜度為3O(1)；最后，由于需要循環(huán)查找滿足3條原則的關(guān)鍵節(jié)點(diǎn)，類似于輪詢調(diào)度算法，因此時(shí)間復(fù)雜度為O(n)。則算法1的時(shí)間復(fù)雜度T(A)為

4.2 數(shù)據(jù)遷移合并算法

根據(jù)3.4節(jié)可知，需要通過最優(yōu)線程數(shù)據(jù)重組原則判斷數(shù)據(jù)遷移是否對(duì)集群性能造成影響。

在滿足算法1的前提下，當(dāng)數(shù)據(jù)遷入線程時(shí)，首先需要判斷對(duì)Storm集群的性能是否構(gòu)成影響，因此線程的選擇非常重要。為盡可能減少對(duì)集群性能的影響，應(yīng)該考慮以下2個(gè)條件：1)由于非同源線程之間進(jìn)行數(shù)據(jù)的遷移合并可能會(huì)出現(xiàn)數(shù)據(jù)不匹配的問題，因此應(yīng)該選擇非關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程的同源線程；2)數(shù)據(jù)遷入線程首先需要考慮對(duì)集群性能的影響，因此應(yīng)盡可能查找關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程作為數(shù)據(jù)遷入的線程。針對(duì)數(shù)據(jù)遷入線程的選擇問題，提出算法2，確定線程數(shù)據(jù)遷移的最優(yōu)方法。此外，算法2根據(jù)是否存在關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程分為關(guān)鍵線程中的數(shù)據(jù)遷移合并算法（DMMCE,data migration and merging among critical executor）與非關(guān)鍵線程中的數(shù)據(jù)遷移合并算法（DMMNE,data migration and merging among non-critical executor），具體的算法過程如下所示。

算法2數(shù)據(jù)遷移合并算法

算法2選擇數(shù)據(jù)遷入的線程。根據(jù)最優(yōu)線程數(shù)據(jù)重組原則，選擇最優(yōu)遷入數(shù)據(jù)的線程。步驟1)判斷集群是否允許進(jìn)行數(shù)據(jù)遷移；步驟13)～步驟21)根據(jù)集群性能不變的前提下，完成數(shù)據(jù)遷移；步驟18)～步驟27)根據(jù)集群能效比的變化，完成數(shù)據(jù)遷移；步驟22)更新Zookeeper的配置文件，防止因拓?fù)渎窂桨l(fā)生改變而對(duì)集群數(shù)據(jù)傳輸與處理造成影響。

集群應(yīng)在限制時(shí)間開銷的前提下執(zhí)行數(shù)據(jù)遷移合并算法。首先，算法2判斷非關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程是否存在同源的關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程，其時(shí)間復(fù)雜度為O(1)；其次，若存在同源的關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程，則需要將數(shù)據(jù)遷移到該線程，若關(guān)鍵路徑發(fā)生改變，則循環(huán)查找下一個(gè)同源關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程，其時(shí)間復(fù)雜度為O(nT)′；最后，若不存在同源的關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程，則需要查找同源的關(guān)鍵節(jié)點(diǎn)關(guān)鍵線程，并將數(shù)據(jù)遷移到該線程，在集群能效比低于原集群后，則循環(huán)查找下一個(gè)同源關(guān)鍵節(jié)點(diǎn)關(guān)鍵線程，其時(shí)間復(fù)雜度為O(nR)′。則算法2的時(shí)間復(fù)雜度T(B)為

其中，T′表示拓?fù)鋱?zhí)行DMMNE算法后集群數(shù)據(jù)處理及傳輸總時(shí)間，R′表示拓?fù)鋱?zhí)行DMMCE算法后集群的能效比。

4.3 節(jié)點(diǎn)降壓算法

根據(jù)3.4節(jié)與3.5節(jié)可知，集群執(zhí)行節(jié)點(diǎn)降壓算法需要計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值，因此需要節(jié)點(diǎn)降壓原則。

在滿足算法1與算法2的前提下，為計(jì)算集群執(zhí)行節(jié)點(diǎn)降壓算法后非關(guān)鍵節(jié)點(diǎn)電壓的最低值，需要針對(duì)不同的節(jié)點(diǎn)降壓制約條件進(jìn)行分析。其制約條件主要分為以下兩點(diǎn)：1)在非關(guān)鍵節(jié)點(diǎn)降壓過程中，集群拓?fù)潢P(guān)鍵路徑不發(fā)生改變；2)需要針對(duì)不同的模型確定每次節(jié)點(diǎn)電壓的改變量。針對(duì)非關(guān)鍵節(jié)點(diǎn)的降壓原則，提出算法3。同理，算法3根據(jù)是否存在關(guān)鍵節(jié)點(diǎn)非關(guān)鍵線程分為關(guān)鍵線程中的數(shù)據(jù)遷移合并節(jié)能算法（EDMMCE,energy-efficient algorithm for data migration and merging among critical executor）與非關(guān)鍵線程中的數(shù)據(jù)遷移合并節(jié)能算法（EDMMNE,energy-efficient algorithm for data migration and merging among non-critical executor），具體的算法過程如下所示。

算法3節(jié)點(diǎn)降壓算法

算法3根據(jù)不同的節(jié)能算法分別對(duì)非關(guān)鍵節(jié)點(diǎn)進(jìn)行降壓調(diào)節(jié)，達(dá)到節(jié)能的目的。步驟2)～步驟8)針對(duì)集群拓?fù)鋱?zhí)行DMMNE算法后，并根據(jù)集群性能不變的前提下，計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值。步驟10)～步驟16)針對(duì)集群拓?fù)鋱?zhí)行DMMCE算法后，并根據(jù)集群能效比，計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值。

與算法1與算法2相同，集群執(zhí)行節(jié)點(diǎn)降壓算法同樣需要注意算法的時(shí)間復(fù)雜度。首先，算法3需要判斷集群拓?fù)涫欠駡?zhí)行DMMNE，其算法時(shí)間復(fù)雜度為O(1)；其次，根據(jù)集群拓?fù)鋽?shù)據(jù)處理及傳輸時(shí)間不變的前提下，計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值，其算法時(shí)間復(fù)雜度為O(1)+O(nT′)；最后，根據(jù)集群能效比，計(jì)算非關(guān)鍵節(jié)點(diǎn)電壓的最低值，其算法時(shí)間復(fù)雜度為O(1)+O(nR′)。則算法3的時(shí)間復(fù)雜度T(C)為

此外，根據(jù)算法評(píng)估可以看出，算法3包括這2個(gè)算法，即EDMMNE與EDMMCE。且必須在滿足算法1與算法2的前提下，集群拓?fù)洳拍軋?zhí)行這2個(gè)算法。因此集群拓?fù)鋱?zhí)行EDMMNE的時(shí)間復(fù)雜度為

集群拓?fù)鋱?zhí)行EDMMCE的時(shí)間復(fù)雜度為

4.4 能耗模型

Storm集群在執(zhí)行拓?fù)鋾r(shí)的能耗一般分為2類，分別為基礎(chǔ)能耗與動(dòng)態(tài)能耗，其中基礎(chǔ)能耗為物理機(jī)的待機(jī)能耗，一般來說，同一種類型物理機(jī)的基礎(chǔ)能耗是一個(gè)固定常量。動(dòng)態(tài)能耗表示集群執(zhí)行拓?fù)鋾r(shí)數(shù)據(jù)處理及傳輸?shù)哪芎?，一般根?jù)任務(wù)的不同，產(chǎn)生的能耗也不相同，因此動(dòng)態(tài)能耗是一個(gè)變量。定義在一段時(shí)間t內(nèi)基礎(chǔ)能耗為，動(dòng)態(tài)能耗為，則Storm集群在執(zhí)行拓?fù)鋾r(shí)的總能耗Et為

其中，Pdynamic表示集群在執(zhí)行拓?fù)鋾r(shí)的功耗，定義集群未執(zhí)行節(jié)能策略時(shí)的能耗為，執(zhí)行節(jié)能策略后的能耗為，則執(zhí)行節(jié)能策略后節(jié)約的能耗為

將式(30)代入式(29)，化簡(jiǎn)得到集群執(zhí)行DMM-Storm節(jié)約的能耗為

其中，P1表示集群執(zhí)行EDMMNE后集群的功耗，P2表示集群執(zhí)行EDMMCE 后集群的功耗，M表示集群數(shù)據(jù)量。根據(jù)式(30)可知，集群拓?fù)鋱?zhí)行2種算法后節(jié)約的能耗為

根據(jù)3.2節(jié)可知，集群數(shù)據(jù)處理及傳輸總時(shí)間等于集群路徑總開銷，因此將式(4)代入式(32)化簡(jiǎn)得

其中，式(33)中的相關(guān)參數(shù)與式(4)、式(32)相同，表示集群拓?fù)鋱?zhí)行2種算法后節(jié)約的總能耗。

5 實(shí)驗(yàn)與評(píng)價(jià)

本文實(shí)驗(yàn)的目的為驗(yàn)證數(shù)據(jù)遷移合并節(jié)能策略的有效性。其主要的評(píng)估指標(biāo)包括集群的吞吐量、CPU資源占用率、內(nèi)存資源占用率、能耗與能效比等，實(shí)驗(yàn)選取Intel公司發(fā)布在GitHub上的基準(zhǔn)測(cè)試[10]，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估和分析。

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

為驗(yàn)證DMM-Storm的有效性，實(shí)驗(yàn)需要將Storm集群部署在19臺(tái)普通PC機(jī)上，且每臺(tái)PC機(jī)的網(wǎng)卡統(tǒng)一為100 Mbit/s LAN，內(nèi)存統(tǒng)一為8 GB。根據(jù)不同節(jié)點(diǎn)的運(yùn)行狀況，具體硬件配置如表1所示。

表1 Storm集群配置

其中，控制臺(tái)節(jié)點(diǎn)UI、關(guān)聯(lián)節(jié)點(diǎn)Zookeeper1（Leader）與主控節(jié)點(diǎn)Nimbus運(yùn)行在同一臺(tái)物理機(jī)上。從節(jié)點(diǎn)Supervisor1～Supervisor16與關(guān)聯(lián)節(jié)點(diǎn)Zookeeper2、Zookeeper3（Follower）分別部署在18臺(tái)不同PC機(jī)上。此外，隨機(jī)從16臺(tái)包含工作節(jié)點(diǎn)的PC機(jī)上選定3臺(tái)進(jìn)行nmon測(cè)試監(jiān)控，記錄CPU占用率、網(wǎng)絡(luò)帶寬占用率及內(nèi)存占用率等信息。各節(jié)點(diǎn)軟件配置如表2所示。

表2 Storm集群軟件配置

為全面測(cè)試DMM-Storm在各類不同資源開銷下的有效性，實(shí)驗(yàn)選取4組基準(zhǔn)測(cè)試，分別是CPU敏感型（CPU-Sensitive）的WordCount、網(wǎng)絡(luò)帶寬敏感型（Network-Sensitive）的Sol、內(nèi)存敏感型（Memory-Sensitive）的RollingSort和Storm在真實(shí)場(chǎng)景下的應(yīng)用RollingCount。各基準(zhǔn)測(cè)試運(yùn)行時(shí)工作進(jìn)程數(shù)量與當(dāng)前所需的工作節(jié)點(diǎn)數(shù)量保持一致（即一個(gè)工作節(jié)點(diǎn)對(duì)應(yīng)一個(gè)工作進(jìn)程），具體的參數(shù)配置如表3所示。

表3 基準(zhǔn)測(cè)試參數(shù)配置

表3中，component.xxx_num表示該基準(zhǔn)測(cè)試組件并行度，SOL中的topology.level表示拓?fù)涞膶哟?，需要設(shè)置為大于或等于2的整數(shù)，這里設(shè)置為3，結(jié)合component.xxx_num的配置參數(shù)來看，表示一個(gè)spout組件運(yùn)行著60個(gè)實(shí)例，2個(gè)bolt組件運(yùn)行著120個(gè)實(shí)例。此外，4組基準(zhǔn)測(cè)試統(tǒng)一設(shè)置topology.works為16，表示各基準(zhǔn)測(cè)試運(yùn)行時(shí)一個(gè)工作節(jié)點(diǎn)內(nèi)僅分配一個(gè)工作進(jìn)程；統(tǒng)一設(shè)置topology.acker.executors為16，表示保證線程間數(shù)據(jù)流的可靠傳輸；為防止元組傳輸因超時(shí)而重傳，通過多次實(shí)驗(yàn)結(jié)果統(tǒng)一設(shè)置 topology.max.spout.pending為200；最后，統(tǒng)一設(shè)置每個(gè)message.size等于一個(gè)tuple的大小。

為驗(yàn)證DMM-Storm的效果，本文還與WNDVR-Storm[42]進(jìn)行了對(duì)比。該策略的核心思想為通過動(dòng)態(tài)調(diào)節(jié)工作節(jié)點(diǎn)內(nèi)存電壓實(shí)現(xiàn)節(jié)能的目的。該節(jié)能策略為流式處理節(jié)能策略的代表，且包括關(guān)鍵路徑節(jié)能（DVRCP,DRAM voltage regulation on critical path）與非關(guān)鍵路徑節(jié)能（DVRNP,DRAM voltage regulation on non-critical path）2個(gè)算法。表4列舉了WNDVR-Storm在基準(zhǔn)測(cè)試RollingCount上的配置參數(shù)。表4中的β與γ分別表示工作節(jié)點(diǎn)CPU使用率與數(shù)據(jù)傳輸量的閾值，表4內(nèi)的結(jié)果都是通過對(duì)RollingCount進(jìn)行采樣獲得。component.spout_num與component.bolt_num分別為60與120，topology.works與topology.acker.executors都是16，是為了與本文的策略保持一致，保證在同等條件下驗(yàn)證策略的有效性。

表4 WNDVR-Storm參數(shù)配置

5.2 執(zhí)行節(jié)能策略的電壓選擇

為便于觀測(cè)，以下測(cè)試均設(shè)置metrics.poll為5 000 ms，metrics.time為300 000 ms，即每組實(shí)驗(yàn)每5 s進(jìn)行一次采樣，時(shí)長(zhǎng)為5 min。

5.2.1 數(shù)據(jù)遷移測(cè)試

為了集群內(nèi)數(shù)據(jù)遷移能夠正常執(zhí)行，現(xiàn)對(duì)集群關(guān)鍵節(jié)點(diǎn)各類資源的占用率進(jìn)行測(cè)試，并統(tǒng)計(jì)集群執(zhí)行數(shù)據(jù)遷移合并算法后關(guān)鍵節(jié)點(diǎn)各類資源的占用率，具體的結(jié)果如圖4所示。

圖4為RollingCount下各類資源的占用率對(duì)比，同理可得，WordCount、Sol與RollingSort這3個(gè)基準(zhǔn)測(cè)各類資源的占用率對(duì)比。為觀察集群執(zhí)行數(shù)據(jù)遷移合并算法的具體效果，表5統(tǒng)計(jì)了各類資源占用情況的平均值。

圖4 集群執(zhí)行RollingCount后，各類資源的占用率對(duì)比

表5 集群執(zhí)行不同基準(zhǔn)測(cè)試各類資源的占用率

根據(jù)圖4與表5可知，集群執(zhí)行數(shù)據(jù)遷移合并算法后關(guān)鍵節(jié)點(diǎn)各類資源的占用率急劇上升，數(shù)據(jù)遷移合并算法效果明顯，且執(zhí)行DMMNE與DMMCE的資源占用基本相同。此外，由圖4可知，策略對(duì)集群3類資源的占用率的影響時(shí)長(zhǎng)在第45～65 s，共耗時(shí)約20 s，資源占用率急速上升，其原因?yàn)榧和負(fù)鋱?zhí)行數(shù)據(jù)遷移合并算法，數(shù)據(jù)遷移過程中，集群資源消耗巨大。65 s后集群資源占用率趨于穩(wěn)定，由此，非關(guān)鍵節(jié)點(diǎn)線程上的數(shù)據(jù)順利遷出，并可通過節(jié)點(diǎn)降壓原則降低非關(guān)鍵節(jié)點(diǎn)電壓，從而實(shí)現(xiàn)節(jié)能的效果。

5.2.2 節(jié)點(diǎn)降壓測(cè)試

根據(jù)3.4節(jié)可知，節(jié)點(diǎn)降壓原則存在2個(gè)制約條件，即非關(guān)鍵節(jié)點(diǎn)電壓的限制條件與非關(guān)鍵節(jié)點(diǎn)電壓的改變量，其中執(zhí)行EDMMNE算法，非關(guān)鍵節(jié)點(diǎn)電壓的限制條件為集群性能；執(zhí)行EDMMCE算法，非關(guān)鍵節(jié)點(diǎn)電壓的限制條件為集群能效比。集群性能可通過單位時(shí)間內(nèi)數(shù)據(jù)的傳輸及處理速率表示，集群能效比可通過單位時(shí)間內(nèi)的集群功耗表示。非關(guān)鍵節(jié)點(diǎn)電壓的改變量可通過式(15)與式(22)確定。則原集群5 min內(nèi)集群吞吐量以及功耗可通過圖5表示。

圖5 原集群吞吐量與功耗

由圖5可知，通過使用DVFS[38]技術(shù)，集群執(zhí)行EDMMNE，規(guī)定單位時(shí)間內(nèi)數(shù)據(jù)的傳輸與處理速率不發(fā)生改變，則可每次以vc為步長(zhǎng)降低非關(guān)鍵節(jié)點(diǎn)電壓；集群執(zhí)行EDMMCE，規(guī)定集群能效比不低于原集群，則可每次以vc′為步長(zhǎng)降低非關(guān)鍵節(jié)點(diǎn)電壓。圖6為RollingCount下，集群執(zhí)行2種算法非關(guān)鍵節(jié)點(diǎn)電壓的改變情況。

圖6 集群執(zhí)行RollingCount后，2種算法非關(guān)鍵節(jié)點(diǎn)電壓的改變情況

由圖6可知，集群執(zhí)行EDMMNE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.01 V，集群執(zhí)行EDMMCE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.03 V。同理可得，WordCount后，集群執(zhí)行EDMMNE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.06 V；集群執(zhí)行EDMMCE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.05 V。Sol后，集群執(zhí)行EDMMNE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.04 V；集群執(zhí)行EDMMCE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.05 V。RollingSort后，集群執(zhí)行EDMMNE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.03 V；集群執(zhí)行EDMMCE非關(guān)鍵節(jié)點(diǎn)電壓的最低值為1.02 V。

此外，該實(shí)驗(yàn)通過降低電壓帶來的集群拓?fù)鋽?shù)據(jù)處理及傳輸延遲的問題，但由于集群的關(guān)鍵路徑不發(fā)生改變，因此在這里不做過多的敘述說明。

5.3 數(shù)據(jù)遷移合并節(jié)能策略實(shí)驗(yàn)結(jié)果分析

本節(jié)首先討論在Storm默認(rèn)的調(diào)度策略與DMM-Storm下，分別對(duì)WordCount、Sol與RollingSort進(jìn)行功耗測(cè)試，具體實(shí)驗(yàn)結(jié)果如圖7所示。

由圖7可知，45 s前Storm默認(rèn)的調(diào)度策略與DMM-Storm的功耗基本相同，而45～65 s，共耗時(shí)約20 s，集群執(zhí)行DMM-Storm的功耗急劇上升，其原因?yàn)榧涸诖似陂g執(zhí)行數(shù)據(jù)遷移合并算法，集群資源占用率消耗巨大，因此集群功耗急劇上升。之后70～90 s，共耗時(shí)約25 s，集群執(zhí)行默認(rèn)的調(diào)度策略與DMM-Storm的功耗又逐漸接近，其原因?yàn)閳?zhí)行數(shù)據(jù)遷移合并算法并不改變集群的功耗。95～115 s，共耗時(shí)約20 s，集群執(zhí)行DMM-Storm的功耗緩慢降低，其原因?yàn)榧涸诖似陂g執(zhí)行節(jié)點(diǎn)降壓算法。120 s之后集群功耗趨于穩(wěn)定，集群執(zhí)行DMM-Storm的功耗明顯低于原系統(tǒng)。集群120 s后的功耗結(jié)果如表6所示。

表6 集群穩(wěn)定后的功耗統(tǒng)計(jì)

根據(jù)表6可知，集群執(zhí)行DMM-Storm的功耗遠(yuǎn)低于原集群功耗。此外由于不同的基準(zhǔn)測(cè)試集群的拓?fù)洳⒉幌嗤虼藶闄z測(cè)策略在真實(shí)環(huán)境下的節(jié)能效果，需要對(duì)RollingCount進(jìn)行測(cè)試。

RollingCount作為Storm平臺(tái)下的一個(gè)大數(shù)據(jù)經(jīng)典應(yīng)用程序，廣泛應(yīng)用到各類大數(shù)據(jù)需求的實(shí)時(shí)應(yīng)用場(chǎng)景。本實(shí)驗(yàn)采用RollingCount對(duì)集群真實(shí)環(huán)境中的功耗進(jìn)行統(tǒng)計(jì)，并計(jì)算其實(shí)際的能耗。此外，引入WNDVR-Storm與Storm默認(rèn)的調(diào)度策略以及DMM-Storm作對(duì)比，其中WNDVR-Storm的配置參數(shù)與表4相同。圖8為RollingCount在不同節(jié)能策略下的功耗及能耗對(duì)比。

圖7 3種基準(zhǔn)測(cè)試下集群的功耗情況

圖8 RollingCount下集群的功耗與能耗

根據(jù)圖8(a)可知，集群功耗隨著時(shí)間的上升不斷增加，其中Storm默認(rèn)的調(diào)度策略與WNDVR-Storm在50 s之后趨于穩(wěn)定，而DMM-Storm則在115 s后趨于穩(wěn)定，其原因?yàn)樵?0～115 s，共耗時(shí)75 s，集群執(zhí)行數(shù)據(jù)遷移合并算法與節(jié)點(diǎn)降壓算法。集群功耗趨于穩(wěn)定后，DMM-Storm與WNDVR-Storm的功耗都遠(yuǎn)低于Storm默認(rèn)的調(diào)度策略，執(zhí)行EDMMNE的平均功耗為915.76 W，執(zhí)行EDMMCE的平均功耗為922.81 W，執(zhí)行DVRNP的平均功耗為928.13 W，執(zhí)行DVRCP的平均功耗為851.43 W，Storm默認(rèn)的調(diào)度策略的平均功耗為1 054.58 W。此外雖然執(zhí)行WNDVR-Storm的平均功耗低于DMM-Storm，但是執(zhí)行WNDVR-Storm的功耗波動(dòng)較大，非常不穩(wěn)定，且策略實(shí)現(xiàn)較為困難，不適合在大規(guī)模集群范圍內(nèi)使用。根據(jù)圖8(a)計(jì)算集群能耗獲得圖8(b)，由圖8(b)可知，30 s之前集群的能耗相同，其原因?yàn)?個(gè)節(jié)能策略中的算法并未觸發(fā)。集群執(zhí)行DMM-Storm在190 s之前低于Storm默認(rèn)的調(diào)度策略，其原因?yàn)镈MM-Storm觸發(fā)了數(shù)據(jù)遷移合并算法與節(jié)點(diǎn)降壓算法致使集群能耗增加。此外根據(jù)圖8(b)可知，120 s之后DMM-Storm的功耗趨于穩(wěn)定，而WNDVR-Storm上升幅度不斷變化且逐漸變高，其原因?yàn)殡S著集群數(shù)據(jù)量的不斷增大，數(shù)據(jù)量始終超過額定閾值，導(dǎo)致WNDVR-Storm基本失效。集群執(zhí)行EDMMNE與EDMMCE分別與原集群能耗作對(duì)比，執(zhí)行EDMMNE將原系統(tǒng)的能耗降低了28.1%，執(zhí)行EDMMCE將原系統(tǒng)的能耗降低了27.6%。綜上所述，DMM-Storm取得了較為理想的節(jié)能效果。

5.4 實(shí)驗(yàn)規(guī)模局限性與有效性評(píng)估

由于缺少更多的物理節(jié)點(diǎn)，實(shí)驗(yàn)選擇通過虛擬機(jī)建立更多的虛擬節(jié)點(diǎn)對(duì)集群規(guī)模的局限性進(jìn)行評(píng)估，實(shí)驗(yàn)分別建立32、48、64、80個(gè)工作節(jié)點(diǎn)與原集群16個(gè)工作節(jié)點(diǎn)進(jìn)行對(duì)比，檢驗(yàn)大規(guī)模集群下節(jié)能策略的有效性，具體結(jié)果如圖9所示。

圖9 擴(kuò)大節(jié)點(diǎn)規(guī)模后2種算法的效果

由圖9可知，隨著節(jié)點(diǎn)數(shù)的增加，2種算法節(jié)能效果并未受到影響。由于隨著節(jié)點(diǎn)數(shù)總量的增加，非關(guān)鍵節(jié)點(diǎn)的數(shù)量也在不斷增加，2種算法都是降低非關(guān)鍵節(jié)點(diǎn)電壓而達(dá)到節(jié)能的效果，因此并不受集群規(guī)模的影響。但策略并未考慮集群規(guī)模對(duì)性能的影響，現(xiàn)根據(jù)節(jié)點(diǎn)數(shù)的增加計(jì)算集群性能，具體的實(shí)驗(yàn)結(jié)果如圖10所示。

由圖10可知，隨著集群規(guī)模的擴(kuò)大，執(zhí)行EDMMNE的性能基本不受影響，而執(zhí)行EDMMCE集群性能隨節(jié)點(diǎn)數(shù)的增加不斷下降，且集群性能的下降符合線性關(guān)系，因此，根據(jù)圖10可得出EDMMCE的理論函數(shù)為

由式(35)可知，執(zhí)行EDMMCE因節(jié)點(diǎn)數(shù)增加而對(duì)集群性能造成一定的影響，因此DMM-Storm存在一定的局限性。

圖10 擴(kuò)大節(jié)點(diǎn)規(guī)模后2種算法對(duì)集群性能的影響

流式大數(shù)據(jù)處理的節(jié)能策略首先應(yīng)該關(guān)注其對(duì)集群性能的影響，根據(jù)圖10可知，執(zhí)行EDMMNE對(duì)集群的性能基本不造成影響，在此不作考慮，而執(zhí)行EDMMCE對(duì)集群的性能造成一定的影響，需要對(duì)該模型進(jìn)行評(píng)估，在此引入能效比的概念，具體結(jié)果如圖11所示。

圖11 能效比

由圖11可知，執(zhí)行EDMMNE后的能效比與原集群的能效比基本相等，則執(zhí)行EDMMNE對(duì)集群的性能并不構(gòu)成影響，但由于式(17)內(nèi)的常數(shù)C存在誤差，且不同節(jié)點(diǎn)間的能耗不相等，因此測(cè)量結(jié)果并不相同。進(jìn)過反復(fù)實(shí)驗(yàn)測(cè)量，誤差常數(shù)C的取值范圍為[0.81,0.96]，則原集群平均能效比為0.0741(s?J)-1，執(zhí)行EDMMNE后的集群能效比為0.0781(s?J)-1。綜上所述，EDMMNE是完全可行的。

6 結(jié)束語

目前，大數(shù)據(jù)技術(shù)飛速發(fā)展，各種分布式平臺(tái)應(yīng)運(yùn)而生，其中流式大數(shù)據(jù)平臺(tái)因其強(qiáng)大的實(shí)時(shí)性深受學(xué)術(shù)界與產(chǎn)業(yè)界的關(guān)注，而Storm平臺(tái)作為最重要的流式大數(shù)據(jù)平臺(tái)之一，在業(yè)界具有強(qiáng)大的影響力。但是由于Storm平臺(tái)在最初設(shè)計(jì)時(shí)并未考慮能耗的問題，導(dǎo)致其在執(zhí)行任務(wù)時(shí)產(chǎn)生的高能耗問題亟待解決。針對(duì)這一問題，本文通過分析Storm平臺(tái)的基本框架，建立了數(shù)據(jù)分配、路徑開銷與資源約束3個(gè)基本模型，并在此基礎(chǔ)上提出了資源約束算法、數(shù)據(jù)遷移合并算法與節(jié)點(diǎn)降壓算法。此外，根據(jù)節(jié)點(diǎn)降壓算法，確定了非關(guān)鍵節(jié)點(diǎn)電壓的最小值，以此降低了非關(guān)鍵節(jié)點(diǎn)電壓，達(dá)到了節(jié)能的效果。最后通過4個(gè)基準(zhǔn)測(cè)試驗(yàn)證了策略的有效性。

下一步的研究工作主要包括以下三方面：1)提高Storm平臺(tái)的計(jì)算能力，增強(qiáng)其任務(wù)執(zhí)行的效率，做到提高性能的同時(shí)節(jié)約能耗，如利用圖形處理器（GPU,graphics processing unit）提高集群的計(jì)算能力；2)減少集群節(jié)點(diǎn)間的通信，增加集群線程間與進(jìn)程間的通信，通過減少其部分通信開銷，縮短任務(wù)的執(zhí)行時(shí)間，以達(dá)到節(jié)能的效果；3)減少部分電子元件的內(nèi)部時(shí)延，提高電子元件的高效性，進(jìn)而提升集群的整體性能，以至從側(cè)面降低集群能耗。