基于Storm平臺的數據遷移合并節能策略

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

（1.新疆大學信息科學與工程學院，新疆 烏魯木齊 830046；2.中國民航大學計算機科學與技術學院，天津 300300；3.廣東金融學院互聯網金融與信息工程學院，廣東 廣州 510521；4.新疆財經大學統計與信息學院，新疆 烏魯木齊 830012）

1 引言

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

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

現有流式處理平臺以Apache Storm框架[10]為代表。Storm是一個開源、主從式架構、橫向擴展性良好且容錯能力強的分布式實時處理平臺，其編程模型簡單，支持包含Java在內的多種編程語言，數據處理高效。相較于不開源的Puma[11]以及社區冷淡的S4[12]，Storm擁有更廣闊的發展前景；相較于目前主流的實時處理平臺Flink[13]與Spark Streaming[14]，Storm的數據處理實時性能效果更佳；相較于后起之秀Heron[15]，Storm更加簡單且業界的認可度與成熟度更高。目前Storm已經廣泛運用到銀行金融[16]、臨床醫療[17]、社交網絡[18]等行業進行實時大數據分析，并廣泛運用到機器學習算法、分布式遠程調用等領域進行理論研究[19]，被譽為“實時處理領域的Hadoop”。

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

1)通過分析Storm集群的拓撲結構，建立數據分配模型、路徑開銷模型與資源約束模型，進一步提出最優線程數據重組原則，為數據遷移合并模型的建立奠定了基礎。

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

2 相關工作

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

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

Sun等[9]提出一種流式大數據處理環境下的實時資源調度節能策略（Re-Stream），該策略通過建立集群響應時間、CPU占用率以及能耗之間的邏輯關系，并根據流式處理框架的基本性質，對整個集群拓撲執行的關鍵路徑進行定義，綜合利用拓撲執行關鍵路徑上性能感知的任務調度策略，以及拓撲執行非關鍵路徑上能耗感知的任務整合策略，使任務響應時間和集群能耗均降低到最低值。

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

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

本文與文獻[9,38-42]的不同之處主要體現在4個方面。首先，本文通過分析集群進行數據遷移時，工作節點存在資源約束（CPU、網絡帶寬和內存）的問題而構建資源約束模型，防止集群由于數據遷移而造成資源溢出的問題。其次，本文根據最優線程數據重組原則與節點降壓原則，完成集群的數據遷移與節點降壓，該過程不會影響集群的性能，并節約了集群的能耗。第三，本文不僅節約了集群的能耗，還通過數據遷移算法減少了節點之間的通信開銷。最后，本文選取Intel公司[10]發布在GitHub上的基準測試而非自己定義的拓撲，因此更具代表性。

3 問題建模與分析

本節主要從Storm拓撲的數據分配模型、路徑與成本模型和資源約束模型出發，分析Storm集群在節能方面存在的局限性，由此提出非關鍵線程中的數據遷移合并與關鍵線程中的數據遷移合并這2種模型，為節能策略的設計與實現提供了理論依據。

3.1 數據分配模型

在Storm集群中，一個流式作業由一個拓撲（topology）的有向無環圖構成，其中數據源編程單元（spout）和數據處理編程單元（bolt）這2類組件（component）共同構成了數據源的頂點，且各組件之間針對不同的流組模式發送和接收數據流，進而構成了有向無環圖的弧。為提高拓撲對數據流的并行運算能力，令每個組件都可同時創造多個線程（executor）。提交拓撲之后，數據將分發到集群各工作節點中，并進行數據的處理與傳輸。設集群工作節點集合為，線程集合為，將工作節點的數據均勻分配到集群的線程上，記工作節點分配給線程eji的數據為daj（i若線程的并行度為1，則該線程上的數據為daj），則集合DAn={daj1,daj2,…,dajn}表示工作節點分配到線程上的數據集合。圖1為在3個工作節點下，Storm集群使用輪詢調度策略后線程數據的分配情況。其中工作節點的集合為N={n1,n2,n3}，線程內數據可表示為

圖1 線程數據分配

為了消除節點內部進程間通信開銷，圖1為每個工作節點僅分配一個進程（worker），因此在拓撲執行過程中只需考慮2類通信成本開銷，一類為線程數據dad1與daf1之間，節點內部線程間的通信開銷；另一類為線程數據dad2與daf1之間，節點間通信開銷。無論工作節點如何分配數據，都滿足以上2種通信開銷。

此外，令線程ea與eb為線程{ec,ed1,ed2,ed3,ee}的父線程，若線程{ec,ed1,ed2,ed3}為父線程ea下的子線程，則線程{ec,ed1,ed2,ed3}內的線程互為同源線程；若線程{ed1,ed2,ed3,ee}為父線程eb下的子線程，則線程{ed1,ed2,ed3,ee}內的線程互為同源線程，以此類推，完成父線程與同源線程之間的對應關系。

3.2 路徑開銷模型

令一條路徑p(eji,emn)為集合B(p(eji,emn))的子路徑，其中頂點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)。

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

令整個拓撲存在m條路徑，則拓撲執行關鍵路徑l(Gp)為

此外，在確保Storm集群性能不變的前提下，根據數據在拓撲關鍵路徑處理及傳輸時間，確定位于拓撲執行關鍵路徑上的工作節點與位于拓撲執行非關鍵路徑上的工作節點。將位于拓撲執行關鍵路徑上的工作節點稱作關鍵節點，位于拓撲執行非關鍵路徑上的工作節點稱作非關鍵節點，位于拓撲執行關鍵路徑上的線程稱作關鍵線程，位于拓撲執行非關鍵路徑上的線程稱作非關鍵線程。

以圖2為例，定義一條拓撲執行關鍵路徑為ea→ed1→ef2→eh，則工作節點n3上的所有線程為非關鍵節點上的非關鍵線程，工作節點n1與n2上的線程分為2類：一類為關鍵節點上的關鍵線程，另一類為關鍵節點上的非關鍵線程。此外，線程ec與線程{ed1,ed2,ed3}互為同源線程，以此類推，完成非關鍵節點上非關鍵線程與關鍵節點上線程的對應關系。

圖2 拓撲執行關鍵路徑的數據傳輸及處理情況

3.3 資源約束模型

根據Storm集群進行數據遷移的特點，令工作節點分配給線程的資源集合為且計算資源主要包括CPU、內存及網絡帶寬3類資源的占用率。令工作節點內3類資源占用的極限為。其中表示工作節點CPU資源占用的極限，表示工作節點內存資源占用的極限，表示工作節點網絡帶寬資源占用的極限，原工作節點CPU資源占用為（單位為Hz），內存資源占用為（單位為B），網絡帶寬資源占用為（單位為bit/s）。由于Storm集群環境中數據源源不斷產生，且拓撲一旦提交將持續運行下去，因此為了保證集群的高效運行，且工作節點的資源不會溢出，這3類資源需要滿足如下條件，即

為了滿足集群運行的可靠性，集群工作節點不能滿負荷運行，本文將符合CPU資源的正常計算稱為滿足CPU資源臨界原則，符合內存資源的正常計算稱為滿足內存資源臨界原則，符合網絡帶寬資源的正常傳輸稱為滿足網絡帶寬資源臨近原則。

當線程準備遷入數據時，該工作節點資源滿足CPU資源臨界原則、內存資源臨界原則以及網絡帶寬資源臨近原則時，允許線程遷入數據。即數據遷入原則tr需要滿足如下條件

為了在保證拓撲高效執行的同時，提高資源的占用率，且在一定程度上優化集群的負載分配，資源約束模型為后續數據重分配原則提供了理論依據。

3.4 拓撲非關鍵線程中的數據遷移合并模型

根據3.3節資源約束模型，提出最優線程數據重組原則；本節針對存在關鍵節點上的非關鍵線程，提出非關鍵線程中的數據遷移合并模型。此外，根據集群數據傳輸及處理總時間，確定了拓撲執行非關鍵路徑工作節點電壓的最低值。

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

由3.3節可知，線程之間數據的遷移合并，被遷入數據的線程存在工作節點的資源約束問題，則為滿足資源約束條件，存在

根據最優線程數據重組原則設計數據遷移合并模型，為非關鍵節點的降壓奠定了基礎。針對是否存在關鍵節點上的非關鍵線程，提出2種線程中的數據遷移合并模型，當集群存在關鍵節點上的非關鍵線程時，集群實施拓撲非關鍵線程中的數據遷移合并模型，且該模型不改變集群性能；當集群不存在關鍵節點上的非關鍵線程時，集群實施拓撲關鍵線程中的數據遷移合并模型，且該模型對系統性能造成一定的影響需要進行相應的評估。

定義2節點降壓原則。為計算集群實施節能策略后非關鍵節點電壓的最低值，需要注意以下兩點：其一，確定非關鍵節點電壓的限制條件；其二，確定非關鍵節點電壓的改變量。

集群實施非關鍵線程中的數據遷移合并模型，需要令非關鍵節點的集合為其中模型以不改變Storm集群性能為前提，因此不能改變拓撲執行關鍵路徑，由此可知模型的執行存在一個限制條件，即數據傳輸及處理的總時間不會發生改變。根據3.3節可知，線程遷入數據存在制約條件，即線程eji遷入數據需要滿足tr。由于線程遷入數據為，關鍵路徑的時間t不發生改變，則非關鍵節點的電壓為，此時調節電壓保證關鍵路徑的時間不發生改變，獲得改變后的電壓為。由此存在一個函數關系

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

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

3.5 拓撲關鍵線程中的數據遷移合并模型

本節針對不存在關鍵節點上的非關鍵線程，提出關鍵線程中的數據遷移合并模型。通過定義能效比（EER,energy efficiency ratio），確定集群性能與能耗之間的關系，并根據能效比，確定拓撲執行關鍵路徑工作節點電壓的最低值。

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

定義3能效比。通過3.2節可知，集群數據處理及傳輸的總時間為t（單位為s），定義集群數據處理及傳輸的總能耗為E（單位為J），則建立能效比模型，即集群數據處理及傳輸總時間與總能耗乘積的倒數為能效比R（單位為（s?J）-1），即

其中，C表示能效比誤差常數，且0

定理1Storm集群在實際拓撲執行過程中，數據處理及傳輸總時間與總能耗的能效比R為

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

化簡式(18)得

因此，獲得

證畢。

為計算集群實施關鍵線程中的數據遷移合并模型后的總能耗，需要計算集群非關鍵節點電壓的最低值。根據定義2可知，存在2個制約條件，其中實施關鍵線程中的數據遷移合并模型后，系統的能效比與原系統能效比之間的關系為一個制約條件。已知集群非關鍵節點的集合為通過3.3節可知，線程遷入數據存在制約條件，則線程數據da遷入需要滿足tr。由于線程遷入數據，由定義3可知集群的能效比為R，調節此時非關鍵節點的電壓為。同理，可獲得函數為

集群實施關鍵線程中的數據遷移合并模型電壓的改變量vc′為

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

4 數據遷移合并節能策略

本節主要介紹基于Storm平臺的數據遷移合并節能策略，該策略在不影響集群性能的前提下，根據非關鍵節點非關鍵線程上數據的遷移情況，對非關鍵節點的電壓進行調節，以此達到節能的目的。節能策略主要分為以下5個步驟，其執行流程如圖3所示。

步驟1通過監控器獲得原系統拓撲執行關鍵路徑的基本信息。

步驟2判斷是否存在關鍵節點非關鍵線程。

步驟3計算被遷入數據的線程是否滿足tr。

步驟4計算非關鍵節點電壓的最低值。

步驟5根據不同的節能算法計算集群總能耗。

圖3 節能策略流程

4.1 資源約束算法

根據3.3節可知，線程被遷入數據首先應該考慮工作節點是否會出現資源溢出現象，因此需要對工作節點的資源總量進行評估。

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

算法1資源約束算法

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

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

4.2 數據遷移合并算法

根據3.4節可知，需要通過最優線程數據重組原則判斷數據遷移是否對集群性能造成影響。

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

算法2數據遷移合并算法

算法2選擇數據遷入的線程。根據最優線程數據重組原則，選擇最優遷入數據的線程。步驟1)判斷集群是否允許進行數據遷移；步驟13)～步驟21)根據集群性能不變的前提下，完成數據遷移；步驟18)～步驟27)根據集群能效比的變化，完成數據遷移；步驟22)更新Zookeeper的配置文件，防止因拓撲路徑發生改變而對集群數據傳輸與處理造成影響。

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

其中，T′表示拓撲執行DMMNE算法后集群數據處理及傳輸總時間，R′表示拓撲執行DMMCE算法后集群的能效比。

4.3 節點降壓算法

根據3.4節與3.5節可知，集群執行節點降壓算法需要計算非關鍵節點電壓的最低值，因此需要節點降壓原則。

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

算法3節點降壓算法

算法3根據不同的節能算法分別對非關鍵節點進行降壓調節，達到節能的目的。步驟2)～步驟8)針對集群拓撲執行DMMNE算法后，并根據集群性能不變的前提下，計算非關鍵節點電壓的最低值。步驟10)～步驟16)針對集群拓撲執行DMMCE算法后，并根據集群能效比，計算非關鍵節點電壓的最低值。

與算法1與算法2相同，集群執行節點降壓算法同樣需要注意算法的時間復雜度。首先，算法3需要判斷集群拓撲是否執行DMMNE，其算法時間復雜度為O(1)；其次，根據集群拓撲數據處理及傳輸時間不變的前提下，計算非關鍵節點電壓的最低值，其算法時間復雜度為O(1)+O(nT′)；最后，根據集群能效比，計算非關鍵節點電壓的最低值，其算法時間復雜度為O(1)+O(nR′)。則算法3的時間復雜度T(C)為

此外，根據算法評估可以看出，算法3包括這2個算法，即EDMMNE與EDMMCE。且必須在滿足算法1與算法2的前提下，集群拓撲才能執行這2個算法。因此集群拓撲執行EDMMNE的時間復雜度為

集群拓撲執行EDMMCE的時間復雜度為

4.4 能耗模型

Storm集群在執行拓撲時的能耗一般分為2類，分別為基礎能耗與動態能耗，其中基礎能耗為物理機的待機能耗，一般來說，同一種類型物理機的基礎能耗是一個固定常量。動態能耗表示集群執行拓撲時數據處理及傳輸的能耗，一般根據任務的不同，產生的能耗也不相同，因此動態能耗是一個變量。定義在一段時間t內基礎能耗為，動態能耗為，則Storm集群在執行拓撲時的總能耗Et為

其中，Pdynamic表示集群在執行拓撲時的功耗，定義集群未執行節能策略時的能耗為，執行節能策略后的能耗為，則執行節能策略后節約的能耗為

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

其中，P1表示集群執行EDMMNE后集群的功耗，P2表示集群執行EDMMCE 后集群的功耗，M表示集群數據量。根據式(30)可知，集群拓撲執行2種算法后節約的能耗為

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

其中，式(33)中的相關參數與式(4)、式(32)相同，表示集群拓撲執行2種算法后節約的總能耗。

5 實驗與評價

本文實驗的目的為驗證數據遷移合并節能策略的有效性。其主要的評估指標包括集群的吞吐量、CPU資源占用率、內存資源占用率、能耗與能效比等，實驗選取Intel公司發布在GitHub上的基準測試[10]，最后對實驗結果進行評估和分析。

5.1 實驗環境

為驗證DMM-Storm的有效性，實驗需要將Storm集群部署在19臺普通PC機上，且每臺PC機的網卡統一為100 Mbit/s LAN，內存統一為8 GB。根據不同節點的運行狀況，具體硬件配置如表1所示。

表1 Storm集群配置

其中，控制臺節點UI、關聯節點Zookeeper1（Leader）與主控節點Nimbus運行在同一臺物理機上。從節點Supervisor1～Supervisor16與關聯節點Zookeeper2、Zookeeper3（Follower）分別部署在18臺不同PC機上。此外，隨機從16臺包含工作節點的PC機上選定3臺進行nmon測試監控，記錄CPU占用率、網絡帶寬占用率及內存占用率等信息。各節點軟件配置如表2所示。

表2 Storm集群軟件配置

為全面測試DMM-Storm在各類不同資源開銷下的有效性，實驗選取4組基準測試，分別是CPU敏感型（CPU-Sensitive）的WordCount、網絡帶寬敏感型（Network-Sensitive）的Sol、內存敏感型（Memory-Sensitive）的RollingSort和Storm在真實場景下的應用RollingCount。各基準測試運行時工作進程數量與當前所需的工作節點數量保持一致（即一個工作節點對應一個工作進程），具體的參數配置如表3所示。

表3 基準測試參數配置

表3中，component.xxx_num表示該基準測試組件并行度，SOL中的topology.level表示拓撲的層次，需要設置為大于或等于2的整數，這里設置為3，結合component.xxx_num的配置參數來看，表示一個spout組件運行著60個實例，2個bolt組件運行著120個實例。此外，4組基準測試統一設置topology.works為16，表示各基準測試運行時一個工作節點內僅分配一個工作進程；統一設置topology.acker.executors為16，表示保證線程間數據流的可靠傳輸；為防止元組傳輸因超時而重傳，通過多次實驗結果統一設置 topology.max.spout.pending為200；最后，統一設置每個message.size等于一個tuple的大小。

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

表4 WNDVR-Storm參數配置

5.2 執行節能策略的電壓選擇

為便于觀測，以下測試均設置metrics.poll為5 000 ms，metrics.time為300 000 ms，即每組實驗每5 s進行一次采樣，時長為5 min。

5.2.1 數據遷移測試

為了集群內數據遷移能夠正常執行，現對集群關鍵節點各類資源的占用率進行測試，并統計集群執行數據遷移合并算法后關鍵節點各類資源的占用率，具體的結果如圖4所示。

圖4為RollingCount下各類資源的占用率對比，同理可得，WordCount、Sol與RollingSort這3個基準測各類資源的占用率對比。為觀察集群執行數據遷移合并算法的具體效果，表5統計了各類資源占用情況的平均值。

圖4 集群執行RollingCount后，各類資源的占用率對比

表5 集群執行不同基準測試各類資源的占用率

根據圖4與表5可知，集群執行數據遷移合并算法后關鍵節點各類資源的占用率急劇上升，數據遷移合并算法效果明顯，且執行DMMNE與DMMCE的資源占用基本相同。此外，由圖4可知，策略對集群3類資源的占用率的影響時長在第45～65 s，共耗時約20 s，資源占用率急速上升，其原因為集群拓撲執行數據遷移合并算法，數據遷移過程中，集群資源消耗巨大。65 s后集群資源占用率趨于穩定，由此，非關鍵節點線程上的數據順利遷出，并可通過節點降壓原則降低非關鍵節點電壓，從而實現節能的效果。

5.2.2 節點降壓測試

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

圖5 原集群吞吐量與功耗

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

圖6 集群執行RollingCount后，2種算法非關鍵節點電壓的改變情況

由圖6可知，集群執行EDMMNE非關鍵節點電壓的最低值為1.01 V，集群執行EDMMCE非關鍵節點電壓的最低值為1.03 V。同理可得，WordCount后，集群執行EDMMNE非關鍵節點電壓的最低值為1.06 V；集群執行EDMMCE非關鍵節點電壓的最低值為1.05 V。Sol后，集群執行EDMMNE非關鍵節點電壓的最低值為1.04 V；集群執行EDMMCE非關鍵節點電壓的最低值為1.05 V。RollingSort后，集群執行EDMMNE非關鍵節點電壓的最低值為1.03 V；集群執行EDMMCE非關鍵節點電壓的最低值為1.02 V。

此外，該實驗通過降低電壓帶來的集群拓撲數據處理及傳輸延遲的問題，但由于集群的關鍵路徑不發生改變，因此在這里不做過多的敘述說明。

5.3 數據遷移合并節能策略實驗結果分析

本節首先討論在Storm默認的調度策略與DMM-Storm下，分別對WordCount、Sol與RollingSort進行功耗測試，具體實驗結果如圖7所示。

由圖7可知，45 s前Storm默認的調度策略與DMM-Storm的功耗基本相同，而45～65 s，共耗時約20 s，集群執行DMM-Storm的功耗急劇上升，其原因為集群在此期間執行數據遷移合并算法，集群資源占用率消耗巨大，因此集群功耗急劇上升。之后70～90 s，共耗時約25 s，集群執行默認的調度策略與DMM-Storm的功耗又逐漸接近，其原因為執行數據遷移合并算法并不改變集群的功耗。95～115 s，共耗時約20 s，集群執行DMM-Storm的功耗緩慢降低，其原因為集群在此期間執行節點降壓算法。120 s之后集群功耗趨于穩定，集群執行DMM-Storm的功耗明顯低于原系統。集群120 s后的功耗結果如表6所示。

表6 集群穩定后的功耗統計

根據表6可知，集群執行DMM-Storm的功耗遠低于原集群功耗。此外由于不同的基準測試集群的拓撲并不相同，因此為檢測策略在真實環境下的節能效果，需要對RollingCount進行測試。

RollingCount作為Storm平臺下的一個大數據經典應用程序，廣泛應用到各類大數據需求的實時應用場景。本實驗采用RollingCount對集群真實環境中的功耗進行統計，并計算其實際的能耗。此外，引入WNDVR-Storm與Storm默認的調度策略以及DMM-Storm作對比，其中WNDVR-Storm的配置參數與表4相同。圖8為RollingCount在不同節能策略下的功耗及能耗對比。

圖7 3種基準測試下集群的功耗情況

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

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

5.4 實驗規模局限性與有效性評估

由于缺少更多的物理節點，實驗選擇通過虛擬機建立更多的虛擬節點對集群規模的局限性進行評估，實驗分別建立32、48、64、80個工作節點與原集群16個工作節點進行對比，檢驗大規模集群下節能策略的有效性，具體結果如圖9所示。

圖9 擴大節點規模后2種算法的效果

由圖9可知，隨著節點數的增加，2種算法節能效果并未受到影響。由于隨著節點數總量的增加，非關鍵節點的數量也在不斷增加，2種算法都是降低非關鍵節點電壓而達到節能的效果，因此并不受集群規模的影響。但策略并未考慮集群規模對性能的影響，現根據節點數的增加計算集群性能，具體的實驗結果如圖10所示。

由圖10可知，隨著集群規模的擴大，執行EDMMNE的性能基本不受影響，而執行EDMMCE集群性能隨節點數的增加不斷下降，且集群性能的下降符合線性關系，因此，根據圖10可得出EDMMCE的理論函數為

由式(35)可知，執行EDMMCE因節點數增加而對集群性能造成一定的影響，因此DMM-Storm存在一定的局限性。

圖10 擴大節點規模后2種算法對集群性能的影響

流式大數據處理的節能策略首先應該關注其對集群性能的影響，根據圖10可知，執行EDMMNE對集群的性能基本不造成影響，在此不作考慮，而執行EDMMCE對集群的性能造成一定的影響，需要對該模型進行評估，在此引入能效比的概念，具體結果如圖11所示。

圖11 能效比

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

6 結束語

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

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