基于遗传算法的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-），男，北京工业大学计算机学院硕士研究生，研究方向为分布式计算。