基于遺傳算法的Spark中間結果數據遷移策略

梁毅 陳金棟 蘇超 畢臨風

摘要：Spark是大數據內存計算系統的典型代表，通過內存緩存數據加速迭代型、交互型大數據應用的運行。基于時間窗口的數據分析是一類典型的大數據迭代型應用。基于Spark平臺運行時間窗口數據分析應用，存在中間結果數據放置不均的問題，造成應用執行效率降低。針對上述問題，提出基于遺傳算法的Spark中間結果數據遷移策略，通過考慮中間結果數據遷移時機、遷移數據規模，并使用遺傳算法優化選取遷移數據放置位置，提高時間窗口應用執行效率。實驗結果表明，在既有Spark平臺中，采用該遷移策略可使時間窗口應用執行時間最大減少28.45%.平均減少21.59%。

關鍵詞：Spark;中間結果數據;數據遷移

DOI： 10. 11907/rjdk.191 383

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP301

文獻標識碼：A

文章編號：1672-7800（2020）004-0089-04

Spark Intermediate Result Data Migration Strategy Based on Genetic Algorithm

LIANG Yi. CHEN Jin-dong ， SU Chao ， BI Ling-f'eng

（Comp u.ter Academy ， Beijing University of Technology ， Beijing 100124 ， China ）Abstract：Spark is a ty pical representative of big data memory computing system. It accelerates the operation of iterative. interactiveand other big data applications through the memory-hased data cache. Data analysis based on time window is a typical big data itera-tive application.Data analysis application based on Spark platform 's runtime window has the problem of' uneven placement of intermedi-ate result data.which reduces the ef'f'iciency of application execution. To solve the above problems， this paper proposes Spark interme-diate results data migration strategy based on genetic algorithm. By considering the migration timing and data scale of intermediate re-sults data， and using genetic algorithm to optiruize the selection of the location of migrated data. the execution efficiency of time win-do，v application is improved. Experiments show that on the existing Spark platform ， by using the proposed intermediate results data mi-gration strategy ， it can reduce the maximum execution time of time window applications by 28.45% and the average by 21.59%.Key Words：Spark;intermediate data;data migration

O 引言

隨著物聯網技術的快速發展，如今已步人大數據時代[1-3]，通過各種途徑獲取數據的規模與速度急劇上升。因此，如何高效存儲、處理與分析海量物聯網數據成為大數據時代面臨的挑戰[4-5]。其中，Spark內存計算平臺在大數據處理領域得到了廣泛應用。[6-7]。

基于時間窗口的數據分析是物聯網中常見的數據分析應用[8-9]，其主要計算邏輯是對一段時序連續的采集數據，以固定/可變的滑動時間窗口對局部數據反復進行分析處理，并對局部數據產生的中間結果數據進行聚合，形成最終分析結果。基于時間窗口的數據分析是典型的迭代型計算，可充分利用Spark平臺內存計算的優勢，通過將運行過程中形成的中間結果數據緩存于任務執行器內存中，減少在最終分析結果計算中的數據讀取開銷，提升應用執行效率。然而，由于數據傾斜的原因，基于時間窗口的數據分析應用在多個任務執行器中形成的中間結果數據規模差異較大，導致部分任務執行器無法完整緩存相應的中間結果數據。另一方面，既有Spark平臺尚未提供任務執行器間的緩存數據遷移策略，無法完整緩存中間結果數據的任務執行器將不能緩存在內存中的數據存儲于本地磁盤，從而增加了最終分析結果計算階段的磁盤數據讀取開銷，降低了應用執行效率。

在數據存儲管理領域，相關研究成果主要從網絡拓撲結構[10-12]、應用間數據相關性角度進行數據遷移策略設計[13-17]。然而，將上述策略應用于Spark平臺未能考慮Spark任務執行器的數據緩存能力，以及數據遷移對當前計算任務執行的影響，難以形成高效的數據遷移方案。

針對上述問題，本文提出一種Spark中間結果數據遷移策略。該策略充分考慮Spark任務執行器的內存規模，以及基于時間窗口數據分析應用多輪迭代執行中形成的中間結果數據規模，定義數據遷移時機和遷移規模，并采用遺傳算法優化選取中間結果數據遷移目標位置。實驗結果表明，在Spark平臺中采用本文提出的數據遷移策略，可有效減少基于時間窗口的數據分析應用執行時間。

1 Spark簡介

Spark是大數據領域的新一代內存計算框架，同時提出一種抽象數據結構彈性分布式數據集（Resilient Distrib -uted Datasets.RDD）[18]，Spark架構如圖1所示。Spark采用主從（ Master/Slave）架構，其中每個Worker節點中有任務執行器Executor。Spark在基于時間窗口數據分析應用的多輪迭代執行過程中，將中間結果數據保存在任務執行器的Cache中，而各個任務執行器的緩存數據不能遷移，從而導致數據傾斜，降低了應用執行效率。

2 Spark中間結果數據遷移策略

2.1 中間結果數據遷移時機及遷移規模

在處理Spark時間窗口應用程序時，多輪迭代執行中不斷形成的中間結果數據使得各個任務執行器的剩余內存空間逐漸變小。當產生新的中間結果數據時，如果任務執行器的內存空間不足，則無法寫入新數據。因此本文定義中間結果數據遷移時機：在一個時間窗口處理過程中，當產生新的中間結果數據時，如果任務執行器的緩存空間不能緩存新的中間結果數據，則觸發中間結果數據遷移。

在確定中間結果數據遷移時機后，需要選取中間結果遷移對象。本策略選取的中間結果數據遷移對象是新產生的中間結果數據分區。將需要遷移的中間結果數據分區集合記為P，P中分區總數為pNurFi.exeNum為任務執行器個數，n為第i個任務執行器中需要遷移的數據塊總數，其中P如公式（1）所示。

2.2基于遺傳算法的中間結果數據遷移目標選取

遺傳算法（Genetic Algorithrn，GA）[19-20]是一種由白然生物進化過程發展而來的模擬生物遺傳過程搜索最優解方法，其主要特點是模擬生物遺傳過程中發生的染色體復制、交叉與變異等，從一個初始種群開始操作，首先進行隨機選擇，然后染色體交叉，最后染色體變異，產生一群比上一代種群更優秀的個體，使種群不斷進化到更好的區域，不斷迭代地繁衍進化，直到最終收斂為一群最適應環境的個體，從而得到最優解。

本文提出的策略有兩個主要目標：一是使每個任務執行器的數據放置均勻，即各任務執行器核的剩余內存空間方差VOF最小，二是遷移數據開銷moveCost最小。選取中間結果數據遷移位置問題可以形式化為：

Mini，nize（VOF）（ 2 ）

Minirn ize（moveCost ）（ 3 ）

滿足以下約束：

remain Memorvi>nex tlnpu tSizei（4）

其中，remainmemorv，表示第i個任務執行器exe，中剩余的緩存空間，nextlnputSize，表示在Spark時間窗口應用程序中，下一個時間窗口輸入時第i個任務執行器的輸入數據規模。

2.2.1 編碼與解碼

Spark中間結果數據遷移策略基于遺傳算法實現，首先需要進行編碼與解碼。本文中染色體串編碼規則如下：

假設需要遷移的中間結果數據分區集合為：

（5）

在公式（5）中，pNurriber為需要遷移的中間結果數據分區數量，mp為中間結果數據分區c其中，mp=pij表示需要遷移的分區為第i個任務執行器上第i個中間結果的數據分區。現有pNumber個需要遷移的中間結果數據分區，則pNurnber個中間結果數據分區通過串結構組成一個染色體，長度為pNurnber。串中每一位表示每個中間結果數據分區應遷移的任務執行器編號。

2.2.2種群初始化

本文設定種群規模M的值為100，染色體長度為pNumber，個體每一位數值隨機從[1，exeNum]中產生，按照編碼規則隨機生成100個染色體，完成種群初始化。2.2.3適應度函數

適應度函數即為本文優化目標，遺傳算法根據適應度進行種群選擇，并淘汰種群中適應度較低的個體。本策略優化目標為保證在數據遷移之后，每個任務執行器上緩存的中間結果數據量與其計算能力匹配，并且保證遷移數據傳輸開銷盡可能小。第一優化目標是保證遷移數據傳輸開銷，即：

Fl（X）= moveCost（6）

第二優化目標是每個任務執行器上緩存的中間結果數據量與其計算能力匹配，如公式（7）所示。

F，（X）= VOF（7）

每個染色體都會有兩個目標函數對應的適應度函數，根據適應度函數進行后續選擇。2.2.4選擇

本文采用參數C1、C2表示選擇F.（X）和F7（X）的概率，其中Cl+ C2=1，0

2.2.5 交叉與變異

本策略中染色體交叉采用線性重組法，該方法通過選取父代個體中的染色體片段進行交叉組合，形成新的子代個體，如公式（8）所示。

其中， 為父代個體染色體， 為父代個體經過交叉操作后產生的子代個體， 為染色體片段交叉因子，其取值范圍為（0，1）。

變異操作采用逆轉算子進行變異，逆轉算子選取個體碼串中兩個隨機選取的變異點，將兩個變異點中間的基因值逆序排列，得到變異后的個體。

2.2.6 收斂條件

遺傳算法需要預先設置迭代終止條件，本文設置進化100代為迭代次數，并且設置當連續50代種群都沒有產生更優解時，則終止迭代。

3性能評估

3.1 實驗環境及負載選擇

本文實驗環境由7臺物理節點組成，包括l臺主節點和6臺從節點，具體節點配置情況如表1所示。

本實驗選取常見的Spark時間窗口應用程序作為負載，包括移動平均法（avg）、分時段排序（sort）和時段詞頻統計（wc）。輸入數據采用真實數據集，并擴展為20G。任務執行器內存為8GB，時間窗口數量分別為5、10和15個，具體如表2所示。

3.2 實驗結果分析

實驗結果如圖2所示。從圖中可以看出，相比于既有Spark平臺，本文提出的Spark中間結果數據遷移策略在處理Spark時間窗口應用程序時.應用執行時間最大減少了28 .45%，平均減少了21.59%。造成上述實驗結果的原因是在處理Spark時間窗口應用程序時，多輪迭代執行中形成的中間結果數據規模在各個任務執行器中分布不均，使得Spark在執行應用程序時效率降低。本文提出的策略當檢測到任務執行器數據放置不均時，則使用遺傳算法遷移中間結果數據，使得各個任務執行器的中間結果數據分布均勻，從而縮短了應用執行時間。

4結語

本文面向Spark中基于時間窗口的數據分析應用，設計并實現了基于遺傳算法的Spark中間結果數據遷移策略。該策略通過統計Spark任務執行器內存規模及基于時間窗口數據分析應用多輪迭代執行中形成的中間結果數據規模，并考慮中間結果數據遷移開銷，在滿足每個任務執行器數據放置均衡的情況下，保證數據遷移開銷最小，從而實現時間窗口應用程序執行過程中的負載均衡。針對真實Spark時間窗口應用程序的實驗結果表明，與既有Spark平臺相比，本文提出的策略可使時間窗口應用執行時間最大減少28.45%，平均減少21.59%。

然而，本文提出的基于遺傳算法的Spark中間結果數據遷移策略主要以HDFS為文件系統，在實際生產環境中，也可能會使用HBase等系統作為數據源，因此應考慮不同數據源情況下的中間結果數據遷移策略。而且本文提出的遷移策略主要是考慮遷移開銷，后續研究T作可以考慮從其它維度進行遷移策略優化。

參考文獻：

[1] 孫其博，劉杰，黎彝，等，物聯網：概念、架構與關鍵技術研究綜述[J].北京郵電大學學報，2010. 33（3）：1-9.

[2]孟小峰，慈祥.大數據管理：概念、技術與挑戰[J].計算機研究與發展，2013 .50（1）：146-169

[3]張引，陳敏，廖小飛大數據應用的現狀與展望[J].計算機研究與發展，2013.50（ S2）：216-233.

[4]李國杰，程學旗大數據研究：未來科技及經濟社會發展的重大戰略領域——大數據的研究現狀與科學思考[J].中國科學院院刊，2012.27（6）：647-657

[5]程學旗，靳小龍，王元卓，等.大數據系統和分析技術綜述[J].軟件學報，2014.25（9）：1889-1908.

[6]ZAHARIA M， CHOWDHURY M，FRANKLIN M J，et al. Spark： clus-ter computing with working sets[J]. HotCloud. 2010. 10： 95.

[7]ISARD M，BUDIU M .YUAN Y， et al. Dryad： distrihuted data-parallelSvstems Review. 2007， 41（3）：59-72.

[8]BABCOCK B， DATAR M. MOTWANI R.Sampling from a moving window over streaming data[C].Proceedings of the thirteenth annualACM-SIAM symposium on Discrete algorithms. Societv for Industrialand Applied Mathematics， 2002： 633-634.

[9]ARASU A，MANKU G S.Approximate counts and quantiles orer slid-ing windows[Cl. Proceedings of the twentv-third ACM SIG-MOD-SIGACT-SICART symposium nn Principles of datahase svs-tems. ACM， 2004： 286-296.

[10] BERENBRIhrK P. BRINKMANN A. SCHEIDELER C. Design ofthe PRESTO multimedia storage network [C]. International Work-shop on Cnmrnunication and Data Management in Large Networks.1999 ： 2-12.

[II] LIAN Q， CHEN W， ZHANG Z. On the impact of replica placement to the reliability of distrihuted hrick str'rage system [C]. IEEE Inter- puter SocietY . 2005.

[12]XIN O， SCHWARZ T， MILLER E L. Availahility in glnbalpeer-to-peer storage systems [C]. Distributed Data and Structures6 . Proceedings in Informatics . 2004.

[13] LIU C， ZHL' X， WANC J， et al. SP-partitioner： a norel partitionmethod to handle intermediate data skew in spark streaming [J]. Fu -ture Generation Cnmputer Systems ， 2018 ， 86 ： 1054-1063.

[14]TANG Z. ZHANG X， LI K. et al. An intermediate data plac：ementalgorithm for load balancing in Spark computing environment [J] . Fu-ture Generation Cnmputer Systems ， 2016 ， 78 ： 287-301.

[15] 卞琛 .于炯 .英昌甜 ，等.并行計算框架 Spark的自適應緩存管理策略 [J].電子學報 . 2017，45（2） ： 278-284.

[16] ELAHEH C， ALI R. HAMID H S J. Load halanc：ing in join algo-rithrns for skewed data in MapReduce systems[J]. The Journal of Su-percomputing， 2018 ， 75（1） ： 228-254.

[17]TANG Z ， LV W， LI K. et al. An intermediate data paitition algorithmfor skew mitigation in spark computing en，'irnnment

[18]ZAHARIA M . CHOWDHURY M. DAS T， et al. Resilient distributeddatasets ： a fault-tnlerant ahstraction for in-memory cluster comput-ing [C]. Prriceedings of the 9th USENrIX C.onference on NetworkedSystems Design and Implementation ， USENIX Association ， 201 2.

[19]HOLLAND J. Adaptation in artificial systems [Ml. Ann Arhror. MI ：University of Michigan Press ， 1975 ： 21-24.

[20] FUSER A S. Simulation of genetic systems [J] . Journal of Theoretical Biology， 1962（2） ： 329-346.

收稿日期：2019-03-25

基金項目：國家自然科學基金項目（91646201，91546111）;國家重點研發計劃項目（2017YFC0803300）

作者簡介：梁毅（1975-），女，博士，北京工業大學計算機學院副教授、碩士生導師，研究方向為分布式計算;陳金棟（1993-），男，北京工

業大學計算機學院碩士研究生，研究方向為分布式計算;蘇超（1992-），男，北京工業大學計算機學院碩士研究生，研究方向

為分布式計算;畢臨風（1994-），男，北京工業大學計算機學院碩士研究生，研究方向為分布式計算。