基于遺傳算法的Spark中間結(jié)果數(shù)據(jù)遷移策略

梁毅 陳金棟 蘇超 畢臨風(fēng)

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

關(guān)鍵詞：Spark;中間結(jié)果數(shù)據(jù);數(shù)據(jù)遷移

DOI： 10. 11907/rjdk.191 383

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP301

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

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

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

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

1 Spark簡介

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

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

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

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

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

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

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

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

Mini，nize（VOF）（ 2 ）

Minirn ize（moveCost ）（ 3 ）

滿足以下約束：

remain Memorvi>nex tlnpu tSizei（4）

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

2.2.1 編碼與解碼

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

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

（5）

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

2.2.2種群初始化

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

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

Fl（X）= moveCost（6）

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

F，（X）= VOF（7）

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

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

2.2.5 交叉與變異

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

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

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

2.2.6 收斂條件

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

3性能評估

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

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

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

3.2 實驗結(jié)果分析

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

4結(jié)語

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

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

參考文獻(xiàn)：

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

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

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

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

[5]程學(xué)旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報，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的自適應(yīng)緩存管理策略 [J].電子學(xué)報 . 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

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

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

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

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