基于MapReduce的大数据在线聚集优化设计

李骏

(成都工业学院 教务处，四川 成都 611730)

大数据具备数据规模达到PB级别、数据组织形式多样、数据增长速率快、处理时间较为敏感等特征[1-3]. 伴随互联网应用的飞速发展，大数据量呈现几何式增长态势，在如此巨大的数据量中包含着具备极高价值度的信息资源，但是受到数据规模和内存等因素限制，即使在云计算模式下，大数据的分析处理也无法满足用户实时交互需求. 为此快速、精准挖掘大数据中潜在信息价值，对促进各大行业进步十分重要[4-5].

在线聚集具备快速、精准获取查询估计结果的特点受到了学者的广泛关注. 文献[6]提出基于多维分层采样的大数据在线聚集方法，解决了查询出现小分组或低选择率时产生的估计结果不准确问题；文献[7]提出了基于POI的大数据在线聚集方法，利用兴趣点为数据源，有效实现了数据的聚类.但这2种方法的大数据在线聚集执行时间并不具备显著优势.

MapReduce是一种编程模型，其中心思想是“Map(映射)”和“Reduce(归约)”，可用于大规模数据集的并行运算. 为此本文提出基于MapReduce的大数据在线聚集优化程序设计方法，进一步提升大数据在线聚集执行性能，更好地服务于大数据应用，为大数据查询处理的发展做出有益贡献.

1 基于MapReduce的大数据在线聚集优化程序设计

1.1 基于列存储的MapReduce大数据并行连接算法

通过分片聚集实现大数据的并行连接，并采用启发式的优化方法优化各节点的子连接，综合上述步骤实现了基于列存储的MapReduce大数据并行连接. 在查询计划执行的Map阶段使用分片聚集方法，使集群中所有机器的计算资源得到充分调用，促使大数据的并行连接得以有效实现[8]，完成大数据在线聚集. 基于列存储的MapReduce并行连接算法示意如图1所示.

图1 基于列存储的MapReduce并行连接算法示意Fig.1 Schematic diagram of MapReduce parallel connection algorithm based on column storage

在并行连接算法中，分片聚集方法的查询形式如下.

1)抽取：子连接结果是通过分别在集群之间的各机器上并行连接操作后得到，向分片聚集过程反馈子连接结果.

2)分片聚集：每个子连接结果通过逐步计算实现聚集. 使得数据量通过分片方法得以减少，计算能力得以提高. 并且分片聚集结果可以在多查询任务当中重复使用.

3)分布：为了使有相同查询字符串的结果能够分到同一个Map任务，依照查询语句的分组条件把之前的结果重新分到每个分组当中. 查询结果的分组实现也完成了GROUPBY字句要求.

4)全聚集：最终聚集结果中把每一个Map任务中具有相同查询字符串的查询结果进行合并计算. 例如,得到count(*)结果.

5)过滤：过滤掉HAVING字句中的分组条件. 如,count(*)>50. Reduce阶段不会输入低于50的计算.

6)排序：剩余结果按照ORDER BY字句的要求，通过hadoop排序算法和TeraSort算法并行排序.

图2 混合近似查询框架Fig.2 hybrid approximate query framework

7)合并：最终结果是通过融合全部分区排序结果，以及各Reducer实现合并处理获取.

8)输出.

大数据在线聚集并行连接过程中，采用启发式优化方法来优化各节点本地执行连接任务关系运算. 启发式优化的基本思想是：最具限制性的选择和连接操作最先完成[9-10]. 优化策略：优先执行选择操作；优先执行投影操作；优先采用同列谓词的下推控制元组数目缩减. 中间结果的规模因为同列表的rowid唯一又一致，被同表列连接的优先执行大大减少. 因此最优的计划是Map阶段产生的中间结果之和较少的计划[11-13].

1.2 大数据在线聚集动态切换机制

以增强上述并行连接过程中大数据在线聚集有效性以及稳定性，最大限度降低大数据在线聚集估计失效对度在线聚集执行性能的干扰为出发点，利用引入动态切换机制的混合近似查询框架，对传统在线聚集近似失效概率实施估计，完成2种近似查询模式切换的同时，缩减因估计失效降低导致的执行性能低下问题以及非必须全局扫描[14-16]. 其中在线聚集动态切换机制采用渐进式近似估计方法，通过完善各轮估计所需样本量，缩减动态切换误判率，实现在线聚集优化设计.

1.2.1 混合近似查询框架

混合近似查询框架主要包括3部分，分别为在线聚集执行模式、近似查询模式以及动态切换机制， 如图2所示.

1)在线聚集执行模式

假设来自于HDFS(Hadoop分布式文件系统)的一组随机样本为S，在线聚集执行模式利用近似估计方法，近似估计查询结果[17-19]. 如果结果符合用户对精度的要求则将结果直接输出至用户，如果结果不符合用户对精度的要求，那么需要增加样本量，构建全新样本集S′=S+ΔS，继续采用近似估计方法对其展开近似估计，直至查询结果符合用户精度要求，完成查询结果精度完善.

2)动态切换机制

混合近似查询框架的重点部分为动态切换机制，可以有效监控在线聚集执行模式中各项查询工作的执行进程并获取近似估计失效概率的预测结果，并以此为依据，将在线聚集执行模式动态切换至近似查询模式，解决估计失效问题以及非必要全局扫描.

1.2.2 基于渐进近似估计的动态切换机制

混合近似查询的执行性能会受动态切换的误判率影响，是因为bootstrap近似查询部分的执行开销高于在线聚集查询部分. 只有通过降低查询切换误判率才能提高混合近似查询的执行性能. 在线聚集近似估计的有效结果，通过估计失效概率pf达到最大值前获取估计结果是减少查询切换误判率的有效处理措施[23-25]，依据该种措施提出渐进式的近似估计方法，调整各轮样本量确保误判率最小. 似估计次数利用改进各轮近似估计样本需求量的增多，使得额外进行估计开销与在线聚集查询在同一时间解决.

渐进近似估计有以下几个步骤：先把近似估计周期用n个固定大小的样本量代表;将n分割成l个子区间，各子区间的样本量是ni；ni个样本需要在线聚集的第i轮近似估计采集，即ΔSi=ni. 划分方式见公式(1).

当前样本统计量的结果E(ΔSi)，会在第i轮近似估计中对采集到的ΔSi个样本实行统计获取. 在样本量扩大到ΔSi+1时计算E(ΔSi+1)统计量，与之前E(ΔSi)统计量结果合并完成当前样本的近似估计，使结果达到用户对样本近似估计精度的需求.

2 实验分析

搭建Hadoop环境，选取40台普通计算机构建测试集群，在集群上部署本文方法设计的基于MapReduce的大数据在线聚集优化程序，实现大数据在线聚集相关基本功能. 测试集群中节点CPU为4核，内存大小为4GB，硬盘大小为500 GB机械硬盘. 同时设置渐进近似估计参数n=1 000，l=3. 为验证本文方法设计优化程序的有效性，选取基于多维分层采样方法[6]、基于POI方法[7]作为本文方法对比方法，从不同角度验证本文方法优势.

2.1 数据量变化下的性能对比

为验证数据量大小对大数据在线聚集时间的影响，选择数据量大小分别为15 GB、150 GB、1.5 TB数据，统计3种方法的大数据聚集时间，在节点全部使用情况下，分别采用了不同的数据对3种方法各测试15次，算出平均值，3种方法大数据聚集时间对比结果见图3.

图3 大数据聚集时间对比Fig.3 Comparison of big data aggregation time

从图3 中可以看出，数据量的数值变化对3种方法聚集时间有明显影响. 随着数据量的增加，基于多维分层采样方法的执行时间不稳定，呈现大幅度增加趋势；基于POI方法的执行时间相对稳定；而随着数据量的增加本文方法的执行时间变化最平稳，且显著低于2种对比方法. 因此实验充分证明了本文方法在大数据聚集时间方面具备显著稳定性和性能优越性.

2.2 基本频繁查询性能对比

为验证3种方法的基本频繁查询性能，在用户查询任务集合中选取连接语句测试数据P1、简单聚集任务测试数据P2、复杂聚集任务测试数据P3和P4作为查询测试样本，设置查询次数为30次，频繁查询周期为5，统计节点数量为60个，数据量大小为150 GB条件下，3种方法的计算执行时间均值，结果如图4所示.

图4 3种方法基本频繁查询性能对比Fig.4 Performance comparison of three methods for basic frequent query

分析图4可知，本文方法的计算执行均值优势较为显著，尤其是在复杂聚集任务P3和P4条件下，本文方法相比基于多维分层采样方法的计算执行时间均值节省25.3%，相比基于POI方法节省48.3%. 实验结果充分体现了本文方法的基本频繁查询性能优势.

3 结论

本文从MapReduce并行连接和在线聚集动态切换机制2个角度对大数据在线聚集进行了优化设置，实现了大数据的快速在线聚集，提升了大数据在线聚集性能,并通过一系列实验验证了本文方法的性能优势.今后可以从简化构造方法入手，使本文方法更加完善，并且结合其他的理论方法，扩大研究对象的范围，以便更好地应对大数据时代，为促进各行业发展奠定基础.