基于迭代MapReduce的混合云大数据分析

颜 烨，张学文，王立婧

(1.重庆大学城市科技学院 电气信息学院，重庆 402167；2.北华大学 机械工程学院，吉林 吉林 132021；3.重庆大学城市科技学院 人文学院，重庆 402167)

0 引 言

混合云服务模式兼具公有云模式计算资源充足以及私有云安全隐私性好的双重技术优点[1]。在混合云服务模式下运行诸如大数据分析等数据密集型业务，用户可灵活地选择涉及关键数据和敏感数据的应用程序运行于私有云平台上，而其它的应用程序则跨越公有云和私有云服务[2，3]。然而，跨平台数据迁移将会带来执行性能(如时间、物理开销)的下降。因此，研究混合云模式下诸如数据密集型业务的数据存储与迁移以及执行性能预测与分析具有重要意义。

文献[4]提出一种基于混合云的可扩展视频编码视频直播存储及调度机制，但文中未涉及大数据分析相关内容。文献[5]提出了混合云存储架构下的大数据迁移策略，但仅关注了大数据的存储机制与数据访问速度提升，对大数据分析与存储交互机制未做探讨。文献[6]设计了一种新型混合云平台以满足变电设备监测大数据分析的多样化实时需求，但未分析应用层数据分析与存储层实时交互耦合影响，且未考虑任务的时间成本。

MapReduce作为一种面向数据处理的编程框架[7]，在混合云框架下迭代MapReduce应用程序，可利用其输入数据不变的特点节省数据存储开销。然而，考虑到数据迁移操作的初始开销很高[8]，有必要提出一种有效的数据存储方案。此外，鉴于用户提交数据至混合云平台进行大数据分析时必须对运行经济成本与数据分析目标成本的权衡[9]，故在进行混合云平台上的大数据分析之前，必须对待处理的目标问题进行计算资源与计算时间的准确预测。

基于上述分析，提出一种混合云框架下基于迭代Map-Reduce 应用程序的大数据分析实现方法。主要创新点为：

(1)传统方案在每次迭代中都进行数据迁移操作，提出的方案在初次迭代过程中首先将输入不变量迁移到公有云中，虽然增加了初始迭代过程的物理开销，但在后续迭代计算过程中可有效节约数据迁移操作的时间，此外，无需对MapReduce框架或底层存储层进行修改，故而降低了技术难度；

(2)基于随机森林算法，提出了大数据分析性能预测方法，准确预测混合云平台上运行大数据分析过程中包括数据迁移与数据计算所需的时间。

1 混合云-大数据分析的难点

MapReduce应用程序中的数据存在高度的并发特性[10]。表现在：①大数据在映射阶段以并行方式转换为多个子数据集；②多个子数据集的处理结果在汇总(reduce)阶段以并行方式进行汇聚。因此，MapReduce应用程序要求在映射阶段大量并发地读取数据，而在汇总阶段则大量并发地写入数据，故要求底层数据存储层支持高度并发的I/O访问模式。

然而，混合云平台一般采用分布式文件系统(Hadoop distributed file system，HDFS)[11]进行数据存储，但直接使用与MapReduce无交互机制的传统分布式文件系统进行数据存储于读取将会产生大量的网络通信数据流量，不足以发挥分布式文件系统的技术优势。原因在于：①传统混合云设置中，数据初始存储在内部私有云中。因此，当外部公有云通过设置虚拟机运行应用程序时，首先需从私有云的虚拟机获取并写入数据；②私有云与公有云间的通信链路一般容量是有限的。因此，混合云服务模式下，外部虚拟机与内部虚拟机的通信比所有位于同一个云中的虚拟机间通信相比，其更易受到通信链路传输能力的制约。因此，在混合云平台上运行MapReduce的关键在于提高数据存储与读取的性能。

2 提出的混合云大数据分析实现方法

在混合云平台上运行MapReduce迭代程序时，有两个重要的环节：①数据存储与迁移；②性能预测评估。本节将数据存储迁移操作与大数据迭代分析算法步骤有机结合起来，提出一种混合云大数据分析实现方法，并提出了混合云平台下大数据迭代计算的性能预测通用方法。

2.1 数据存储策略设计

由于对于大数据分析这类需要重复迭代运行的应用程序而言，后续迭代过程中需要重复利用第一次迭代所需的大部分输入数据，这部分数据称为不变量。因此，外部公有云的虚拟机通过传输能力有限的通信链路重复读取来自内部虚拟机的输入数据会严重占用通信资源；而对于随迭代过程而改变的数据，外部虚拟机则需要不断的将数据通过通信链路写入内部虚拟机，在后续迭代过程中再通过通信链路读回数据。

此外，简单地将不变数据和迭代后新写入的数据直接存储在外部公有云的虚拟机中以提高访问速度并节约通信资源无法真正和MapReduce应用程序相匹配。这是由于MapReduce中任务调度机制优先调度内部虚拟机中的数据资源，这将导致外部虚拟机资源的利用率不足。此外，调度机制的首要目标是平衡虚拟机负载[12]，故上述数据存储方案与调度机制相冲突。

通过上述分析，在无需对MapReduce框架和底层存储层改进的基础上，提出一种基于HDFS机架感知[13]的新型数据存储方案。如图1所示，具体内容为，对于混合云的虚拟机配置，创建两个逻辑组分别用于部署内部私有云虚拟机和外部公有云虚拟机。当配置新的外部公有云虚拟机以提高内部私有云虚拟机计算能力时，通过机架感知的方式在外部公有云虚拟机上扩展HDFS部署。换言之，当非本地私有云虚拟机写入一个新的数据块时，实际上会同时创建本地副本和至少一个远程副本，从而实现弹性的数据存储。而非本地私有云虚拟机则可以根据实际问题需要简单的终止，由于在本地私有云虚拟机中已有数据副本，故无需将远程副本传输回本地。

图1 所提数据存储迁移策略

2.2 混合云框架下大数据分析应用性能预测方法

考虑到经济成本与时间成本，往往使用不同的云服务模式完成大数据分析。因此，混合云平台应当在用户提交数据与目标问题以确定所需的虚拟机配置之前，向用户给出预计的计算资源与计算时间。基于上述背景，提出如下性能预测方法。

2.2.1 问题假设

设初始阶段，MapReduce应用部署在N个内部私有云虚拟机上，且所有的初始不变数据均是分布存储的。当有M个外部公有云虚拟机扩展以支撑N个内部虚拟机进行大数据分析任务时，使用2.1节所提机架感知策略重新扩展部署MapReduce应用，并在生成的混合云平台上迭代基于MapReduce的大数据分析应用程序。为便于分析，设内部虚拟机与外部虚拟机的配置能力相同，且用户可以追溯应用程序的历史状态或有权限知晓如下MapReduce的性能指标：①映射(map)/汇总(reduce)任务的总数量，记为PM和PR；②执行map/reduce任务的物理槽位数量，记为kM和kR；③平均执行map,reduce和调度任务的时间，记为(AM,AR,AS)；④每次执行map,reduce和调度任务的平均调度数据量，记为(DM,DR,DS)。

此外，设大数据分析应用程序在运行时动态行为是可测的，即第一次迭代过程是先验已知的，而后续每次的map/reduce操作过程中的输入数据量、新生成数据量以及计算复杂度相互独立，互不影响。

2.2.2 内部虚拟机工作性能评价指标

在第i(i=1,…,I) 次map操作中，设数量为NumM_i的任务集合采用贪心分配[14]策略分配到kM_i个物理机上。这一过程中，首先需要启动任务调度操作，因此会引入额外时间，需要单独考虑其时间开销，记其执行时间为T1，其值与物理设备性能和软件系统工作机制有关，可以视为一个常量。而后续任务执行的执行时间的理论下限出现的情形为：速度最慢的任务最后被调度执行，而此前的NumR_i个任务已经执行完毕。故第i次map操作的理论最大执行时间为

(1)

进一步地，其最小执行延迟则出现在工作负载完全达到平衡，所有任务都以正常效率执行。因此，第i次map操作的理论最小执行时间为

(2)

由于MapReduce中reduce操作和map操作相互独立，但不需要再次进行任务调度操作，故类似于式(1)、式(2)，第i(i=2,3,…,J) 次reduce操作的最短执行时间与最长执行时间为

(3)

综上，对于第i次迭代过程而言，其执行完毕所需时延下界可通过下式估计得到

(4)

对于迭代次数为I的大数据分析应用，其总完成时间可通过下式估计得到

(5)

2.2.3 混合云模式下性能分析模型

混合云模式下，上述估计方法受到如下两方面因素的影响：①底层后台基于机架感知策略进行工作负载平衡时会占用额外物理开销，导致map、reduce和调度操作的执行速度被削弱；②当同时部署外部公有云虚拟机和内部私有云虚拟机时，二者间的调度操作将受到通信传输能力的限制。

为简化分析，我们首先忽略公有云与私有云虚拟机之间数据调度存在的通信能力受限问题，重点关注混合云模式下大数据分析应用执行过程中的时延预测问题，从两方面提出一种改进的执行时间预测方法。具体而言：

(1)引入一个衰减作用因子β以表征负载平衡过程中对MapReduce执行速度的影响,当负载平衡操作运行时，β>1，而负载平衡操作完成后，β=1；

(2)由于负载平衡期间引发的数据从内部虚拟机迁移到外部虚拟机，故更多的本地资源可提供给调度程序，等效于更多的外部资源可以执行映射操作。为便于分析，设只有本地私有云上的机架用于调度操作。此外，所有映射操作在开始迭代MapReduce时进行调度。从而第i次并发执行的map操作数量kM_i取决于迭代开始时负载平衡的进度；当负载平衡进度完成后，并发执行的映射操作占用的物理槽位分布于内部私有云虚拟机和外部公有云虚拟机上。从而混合云模式下，map操作的总完成时间的上界和下界分别为

(6)

2.2.4 基于随机森林算法的参数 (β,kM_i) 求解

随机森林算法中，采用分类回归树对每个数据集样本构建决策树。而每颗决策树采用随机分裂的方法进一步生成大量决策树，形成随机森林。所提算法的主要步骤为：

步骤1 根节点数据样本生成。对于Num个样本的数据集，有放回地选择num(≤Num) 个样本组成新的Bootstrap样本，并将其作为该决策树的根节点处的样本，每个样本对应的特征量为私有云虚拟机数量、外部公有云虚拟机数量、数据规模、map操作数量、reduce操作数量，共5个，特征构成的集合记作P0={p1,p2,p3,p4,p5}；

步骤2 决策树分裂操作。每个数据样本中的数量若小于某一阈值γ，则样本既作为根节点数据集也作为叶子节点不再进行分裂；否则，从上述5个特征量中随机选择η个特征量构成集合p′， 一般η经验值要大于总特征数量的 1/3，本文选取为2。对P′中的每个特征p′={p1,p2,p3,p4,p5}， 选择λ(λ=1,2,…,λmax) 个分裂点对p′在其允许范围内进行随机改变，例如对私有云虚拟机数量在其最小值与最大值间随机变化。进而计算出分裂后的参数 (β,kM_i)。 计算出Num个样本以不同特征量 {pj}(j=1,2,3,4,5) 和分裂点λk(k=1,2,…,λmax) 进行分裂的方差，若方差的最小值小于阈值σ， 则将本节点作为叶子节点不再分裂；反之，所选择最小方差对应的特征量以及分裂点取值作为分裂特征和分裂点作为最佳分裂点；

步骤3 重复上述步骤1和步骤2，构建具有一定数量的决策森林。

3 实验验证与结果分析

3.1 实验平台配置

为验证所提方法的可行性与优异性，搭建混合云测试平台，其中，内部私有云具有4个网络节点，配置4核Intel Xeon X3430 CPU，500 GB HDD和4 GB RAM，用于资源管理任务。外部公有云具有4个网络节点，配置2×8核Intel Xeon E5-2630v3 CPU，1 TB HDD和64 GB RAM。用于配置虚拟机。内部云与外部云均运行OpenStack云计算程序，运行QEMU/KVM应用程序以配置虚拟机，两个应用程序相互独立。OpenStack云计算程序将网络划分为3个相互独立的通信域：管理网络(即用于传输控制消息和管理流量)，内部网络(即用于传输使用内部私有云IP地址的虚拟机之间的流量)和外部网络(即用于传输内部私有云虚拟机与外部公有云间的流量)。内部私有云虚拟机和外部公有云虚拟机的任何通信都通过网络进行通信，且通信吞吐量为1 Gbps。

对于虚拟机配置，提出如下配置参数：每个虚拟机具有4个CPU，100 GB HDD和16 GB RAM，且每个计算节点都具有管理4个虚拟机的能力。如图2所示，对于内部私有云，每个云计算节点部署4个Hadoop 2.6.0的虚拟机，并指定其中一个虚拟机作为Hadoop主服务器，而其它虚拟机作为Hadoop从服务器；对于外部公有云，每个云计算节点配置1-3个部署了Hadoop的虚拟机。

图2 混合云部署示例

3.2 实验场景设计

基于前述分析，实验验证目标具体而言有两个：①验证2.1节所提数据存储策略的可行性；②验证第2节所提性能预测方法的准确性。故设计如下实验场景：

场景1:构建参数 (β,kM_i) 求解随机森林：通过构造样本数据得到参数 (β,kM_i) 的随机森林。

场景2:数据存储策略验证实验：通过改变内部私有云和外部公有云上部署的虚拟机数量，与场景1标准样本中的配置方案下统性能进行对比，以验证实验目标1。

(7)

然后，讨论理论预测结果与实际运行时延的对比结果以验证实验目标②。此外，为进一步说明所提方法的适用性，设置两组不同的大数据分析应用程序，即：K-means聚类分析和非结构化文本分析。

3.3 构建参数(β,kM_i)求解的随机森林

本次实验中，使用的输入数据量大小为20 GB，而每个映射处理器处理的数据量大小是随机变化的，等价于映射处理器的数量是随机变化的。因此，生成随机森林算法所使用的数据样本生成操作为：首先，在内部虚拟云中的3个虚拟机上部署HDFS，并写入运行TestDFSIO来生成数据块。在初始数据写入完毕后，部署在内部私有云虚拟机上的HDFS可进一步扩展部署至外部公有云虚拟机上；其次，在负载平衡阶段，令同时启动另一个TestDFSIO程序。

同时，令负载平衡阶段内部存储的每个数据块至少一个副本被移动到外部部署的虚拟机上。在实验运行期间，记录负载平衡阶段迁移到外部公有云上的数据数量，从而形成包含不同虚拟机配置方案以及对应算法性能的数据样本。进而应用2.2.4节所提步骤构建随机森林。

记具有N个部署在内部私有云上的虚拟机和M个部署在外部公有云上的虚拟机配置方案表示为N-on-M-off。其中，令M=0表示基准情况下的传统单一云存储方案，采用文献[15]提出的方案作为对比，而M>0则表示所提混合云存储方案。基准方案和混合配置方案下TestDFSIO实验被重复执行10次，并将这些结果进行参数β的计算。表1给出了表示部分配置方案下的数据传输时间与负载平衡时间的对应关系。其中，配置1：3-on-0-off (即为文献[15]所提单一云配置方案)；配置2：3-on-3-off；配置3：3-on-6-off；配置4：3-on-9-off；配置5：3-on-12-off。表2则示出了TestDFSIO的每个并发读取迭代的平均完成时间。

表1 不同虚拟机配置下的负载平衡过程

可以看出，混合云模式下，基于机架感知策略的数据迁移存储与负载平衡显著占用了物理开销，从而降低了并发读取吞吐量，负载平衡开销时间与单一云模式上升了40.5%以上。从表2还可以看出，所有混合云配置方案下的β值与单一云模式较为接近。

表2 TestDFSIO 每次迭代的平均完成时间

3.4 K-means聚类实验

本节通过在混合云平台上运行K-means聚类应用程序以验证所提方法的可行性。K-means基本原理为，将一组多维向量划分为k个集合，使得来自相同集合的所有向量之间的距离平方和及其平均值最小。一般使用迭代步骤进行K-means聚类求解，即每次迭代过程中都基于来自先前迭代的结果计算新均值，直到它们保持不变(或变化量小于预设阈值)。

本次实验中基于MapReduce框架实现K-means聚类分析，在每次迭代时仅生成少量的中间数据(即k个集合对应的均值)，但迭代过程之间则会有大量保持不变的输入数据。故K-means本质上是一种密集型映射操作。实验同样使用20 GB的输入数据，并进行10次迭代处理。

首先进行传统单个OpenStack云进行基准实验，其中部署Hadoop的虚拟机数量是可变的。图3(a)示出了随着虚拟机数量变化K-means完成时间的变化特性。可知，随着Hadoop部署规模的不断扩大，执行K-means的完成时间在不断下降，从而验证了虚拟机的扩展性对K-means性能具有明显的影响。图3同样示出了K-means实际运行时间和利用所提预测方法预测的时延上、下界间的位置关系。可见，基准实验下，实际运行时间总是在理论预测的上、下界之间，且上界值与实际运行值间的误差最多不超过7.8%，而下界值与实际运行值间的误差最多不超过5.9%。故所提性能预测方法能够较准确地估计K-means运行所需时间。

随后，进行混合云平台下的K-means实验。包括部署于内部私有云上的3个虚拟机和部署于外部公有云上数量可变的虚拟机。初始阶段，Hadoop仅部署在内部私有云上，并按照第2节所提数据存储方案扩展到外部公有云上。负载平衡策略与K-means程序同时启动运行。图3(b)所示混合云下K-means执行时间随部署虚拟机数量的变化趋势。与基准实验相比，负载平衡阶段所占用的物理开销对执行时间产生了负面影响，执行时间最多增加40%，但执行时间仍是随着扩展部署的虚拟机数量增加而下降。图4同样示出了采用所提性能预测方法推导的理论执行延时的上界与下界值和实际运行时间。可知，实际运行时间同样保持在理论推导的上界与下界之间，且下界误差最多为10%，而上界误差最多为7.9%。

图3 实际完成时间与理论预测时间

图4 K-means聚类每次迭代完成时间

图4为每次迭代过程的完成时间。对于3-on-0-off的基准情形，每次迭代的完成时间基本保持不变。而对于所提考虑数据存储的混合云方案(即3-on-M-off)情况，第一次迭代的完成时间将明显大于后续迭代操作的完成时间。这由于，第一次迭代时同时进行了数据迁移与负载平衡操作，从而后续迭代时可以重复使用不变输入量。而最终迭代完成时间表明，提出的方案较之于传统单一云方案降低至少51.4%以上。

3.5 迭代Grep文本分析实验

通过迭代Grep实验进一步说明所提方案的适用性。Grep是一种用于大型非结构化文本的流行分析工具，其由一组独立的Grep操作组成，通过查找与给定正则表达式匹配的所有字符串，并根据匹配的数量对它们进行排序。每次迭代过程中，输入数据保持不变，但正则表达式则随着每次迭代发生变化。如，为计算百度百科文章中某个术语出现的次数，并依据统计数量建立新的正则表达式以找到与另一个术语的相关性。由于正则表达式通常是确定的，故映射操作的输出十分简单，因此，Grep可以归类为典型的映射密集型MapReduce作业。

本次实验使用标准的Hadoop Grep应用程序。使用 20 GB 的百度百科文章作为输入数据，列举10个关键词对输入数据进行10次迭代，并同样采用文献[15]所提单一云存储方案作为所提混合云方案的对比实验。

图5(a)所示传统单个云平台下运行Grep应用程序的完成时间，即基准实验的完成时间。与上节类似，随着虚拟机数量的增加，完成时间逐渐下降。实际完成时间与理论预测时间的上界与下界之间的误差分别为19.54%和9.09%，但实际完成时间仍在理论预测的上下限范围之内。

进一步地，对于混合云模式下的Grep应用程序执行性能，同样在私有云上部署3个虚拟机，而外部公有云虚拟机的数量是可变的。图5(b)为Grep完成时间随虚拟机数量变化而变化趋势。同样地，随着外部公有云上部署的虚拟机数量的增加，Grep应用程序执行时间逐渐下降。而理论推导的执行时延上界与下界与实际执行时间之间的误差为6.86%和7.3%。

图5 实际完成时间与理论预测时间

类似地，图6为每次迭代完成时间。对于基准的传统单一云方案(即3-on-0-off)，每次迭代完成时间基本保持不变而混合云模式下(即3-on-M-off)，初始迭代完成时间由于数据迁移与负载平衡操作的同时进行，其时间长于后续迭代时间。而最终所提混合云运行方案的迭代完成时间则比单一云平台下的迭代完成时间缩短至少12.6%。

图6 Grep文本分析每次迭代完成时间

4 结束语

混合云平台由于兼具了私有云安全可靠和公有云计算能力强的优点，具有明显的技术经济优势。然而，在混合云框架下运行诸如大数据分析之类的密集型数据业务尚处于起步阶段，存在底层数据存储与高级应用程序不匹配、应用执行时间预测不准确的难点。针对上述问题，本文提出了在混合云上迭代MapReduce程序进行大数据分析的实现方法。实验结果表明，所提数据存储方法仅在大数据初次迭代时增加了物理开销，但有效提升了后续迭代过程中的执行速度，且所提预测方法能够准确预测迭代大数据计算任务的执行时间。因此，相较于传统的大数据存储与迁移方法，所提混合云框架运行大数据分析实现方法可以有效节约计算时间开销，具有更好的经济性与技术优势。

后续的研究中，将深入讨论私有云与公有云通信传输容量限制对迭代MapReduce应用程序执行性能的影响，从而进一步提高预测精度。