梁毅 陳金棟 蘇超 畢臨風

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

關鍵詞：Spark;中間結果數(shù)據(jù);數(shù)據(jù)遷移

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 引言

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

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

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

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

1 Spark簡介

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

2 Spark中間結果數(shù)據(jù)遷移策略

2.1 中間結果數(shù)據(jù)遷移時機及遷移規(guī)模

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

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

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

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

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

Mini，nize（VOF）（ 2 ）

Minirn ize（moveCost ）（ 3 ）

滿足以下約束：

remain Memorvi>nex tlnpu tSizei（4）

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

2.2.1 編碼與解碼

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

假設需要遷移的中間結果數(shù)據(jù)分區(qū)集合為：

（5）

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

2.2.2種群初始化

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

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

Fl（X）= moveCost（6）

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

F，（X）= VOF（7）

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

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

2.2.5 交叉與變異

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

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

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

2.2.6 收斂條件

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

3性能評估

3.1 實驗環(huán)境及負載選擇

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

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

3.2 實驗結果分析

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

4結語

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

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

參考文獻：

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

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

[3]張引，陳敏，廖小飛大數(shù)據(jù)應用的現(xiàn)狀與展望[J].計算機研究與發(fā)展，2013.50（ S2）：216-233.

[4]李國杰，程學旗大數(shù)據(jù)研究：未來科技及經(jīng)濟社會發(fā)展的重大戰(zhàn)略領域——大數(shù)據(jù)的研究現(xiàn)狀與科學思考[J].中國科學院院刊，2012.27（6）：647-657

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

[6]ZAHARIA M， CHOWDHURY M，F(xiàn)RANKLIN 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）;國家重點研發(fā)計劃項目（2017YFC0803300）

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

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

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