非均匀数据分布下的MapReduce连接查询算法优化
发布时间：2019-07-11 21:19
【摘要】：MapReduce分布式计算框架有助于提升大规模数据连接查询的效率,但当连接属性分布不均匀时,其简单的散列策略容易导致计算节点间负载不均衡,影响作业的整体性能。针对连接查询操作中的数据倾斜问题,研究了MapReduce框架下大规模数据连接查询操作的优化算法。首先对经典的改进重分区连接查询算法进行实验分析,研究了传统MapReduce计算框架下连接查询操作的执行流程,找出了基于MapReduce计算框架的连接查询算法在数据分布不均匀时的性能瓶颈;进而提出了组合分割平衡分区优化策略,设计并实现了基于组合分割平衡分区优化策略的改进型连接查询算法。实验结果表明,提出的优化策略在大规模数据的连接查询处理上很好地解决了数据倾斜带来的性能影响,具有好的时间性能和可扩展性。
文内图片：
图片说明： 耗，使得它被广泛地应用于大规模数据分析中。在Map阶段完成对连接属性的解析和标记，以HashPartition为核心完成Shuffle过程，在Reduce阶段完成连接操作。图1给出了IRJQ算法的计算框架和执行流程。IRJQ算法的运行过程主要分为Map、Shuffle和Reduce共3个阶段。其中Map阶段完成两表的连接属性的解析和标记操作，以及查询属性的解析；Shuffle阶段负责相同hash值分组从Map端到Reduce端的传递；Reduce阶段则将来自不同表的连接属性和查询值进行连接。Fig.1ComputationframeworkandimplementationprocessofIRJQalgorithm图1IRJQ算法的计算框架和执行流程755
文内图片：
图片说明： JournalofFrontiersofComputerScienceandTechnology计算机科学与探索2017,11(5)20亿、30亿、40亿、50亿、60亿、70亿和80亿，倾斜率分别取0.2、0.5和0.8。实验结果如图2所示。实验结果表明，ORDERS中的连接属性不均匀分布对IRJQ算法时间性能影响较大，随着ORDERS中的数据量及倾斜率增大，其时间性能大幅度下降。这主要是因为传统MapReduce框架为了保证所有的分区有相同数目的分组，以哈希分区策略完成对分组的划分。假设ORDERS共有m条记录，倾斜率为α，且倾斜分组数目为1；CUSTOMER共有n条记录，连接率为β；Reduce阶段共有k个分区。则每个分区的分组数目为n×βk，倾斜分组中的记录数目为m×α，非倾斜分组中的记录数目约为m×(1-α)n×β-1，倾斜分区中的记录数目约为m×α+m×(1-α)n×β-1×è÷n×βk-1，，非倾斜分区中的记录数目约为m×(1-α)n×β-1×n×βk，倾斜分区与非倾斜分区间的记录数目差约为m×α+m×(1-α)n×β-1×è÷nβk-1-m×(1-α)n×β-1×n×βk=m×(n×α×β-1)n×β-1。可以很清楚地看出，随着ORDERS中记录数目m或者倾斜率α的增加，倾斜分组的记录数目m×α变得越来越大，倾斜分组和非倾斜分组间的数据量差m×(n×α×β-1)n×β-1也会越来越大。当α→1或者m→∞时，limm→∞m×(n×α×β-1)n×β-1→∞，即ORDERS中数据分布严重不均匀或者数据量较大会导致多个分区间的数据量相差巨大，造成Reduce阶段负载严重不均衡，最终影响整个作业的时间性能。4.2基于改进型MapReduce连接查询算法IRJQ算法在数据分布均匀的情况下拥有较好的时间性能和稳定性，然而?
【作者单位】： 桂林电子科技大学广西可信软件重点实验室;桂林电子科技大学广西云计算与大数据协同创新中心;桂林电子科技大学广西自动检测技术与仪器重点实验室;
【基金】：国家自然科学基金Nos.U1501252,61363005,61462017 广西自然科学基金Nos.2014GXNSFAA118353,2014GXNSFAA118390,2014GXNSFDA118036 广西高等学校高水平创新团队及卓越学者计划 广西云计算与大数据协同创新中心基金项目 广西物联网技术与产业化推进协同创新中心资助项目~~
【分类号】：TP311.13
文内图片：
图片说明： 耗，使得它被广泛地应用于大规模数据分析中。在Map阶段完成对连接属性的解析和标记，以HashPartition为核心完成Shuffle过程，在Reduce阶段完成连接操作。图1给出了IRJQ算法的计算框架和执行流程。IRJQ算法的运行过程主要分为Map、Shuffle和Reduce共3个阶段。其中Map阶段完成两表的连接属性的解析和标记操作，以及查询属性的解析；Shuffle阶段负责相同hash值分组从Map端到Reduce端的传递；Reduce阶段则将来自不同表的连接属性和查询值进行连接。Fig.1ComputationframeworkandimplementationprocessofIRJQalgorithm图1IRJQ算法的计算框架和执行流程755
文内图片：
图片说明： JournalofFrontiersofComputerScienceandTechnology计算机科学与探索2017,11(5)20亿、30亿、40亿、50亿、60亿、70亿和80亿，倾斜率分别取0.2、0.5和0.8。实验结果如图2所示。实验结果表明，ORDERS中的连接属性不均匀分布对IRJQ算法时间性能影响较大，随着ORDERS中的数据量及倾斜率增大，其时间性能大幅度下降。这主要是因为传统MapReduce框架为了保证所有的分区有相同数目的分组，以哈希分区策略完成对分组的划分。假设ORDERS共有m条记录，倾斜率为α，且倾斜分组数目为1；CUSTOMER共有n条记录，连接率为β；Reduce阶段共有k个分区。则每个分区的分组数目为n×βk，倾斜分组中的记录数目为m×α，非倾斜分组中的记录数目约为m×(1-α)n×β-1，倾斜分区中的记录数目约为m×α+m×(1-α)n×β-1×è÷n×βk-1，，非倾斜分区中的记录数目约为m×(1-α)n×β-1×n×βk，倾斜分区与非倾斜分区间的记录数目差约为m×α+m×(1-α)n×β-1×è÷nβk-1-m×(1-α)n×β-1×n×βk=m×(n×α×β-1)n×β-1。可以很清楚地看出，随着ORDERS中记录数目m或者倾斜率α的增加，倾斜分组的记录数目m×α变得越来越大，倾斜分组和非倾斜分组间的数据量差m×(n×α×β-1)n×β-1也会越来越大。当α→1或者m→∞时，limm→∞m×(n×α×β-1)n×β-1→∞，即ORDERS中数据分布严重不均匀或者数据量较大会导致多个分区间的数据量相差巨大，造成Reduce阶段负载严重不均衡，最终影响整个作业的时间性能。4.2基于改进型MapReduce连接查询算法IRJQ算法在数据分布均匀的情况下拥有较好的时间性能和稳定性，然而?
【作者单位】： 桂林电子科技大学广西可信软件重点实验室;桂林电子科技大学广西云计算与大数据协同创新中心;桂林电子科技大学广西自动检测技术与仪器重点实验室;
【基金】：国家自然科学基金Nos.U1501252,61363005,61462017 广西自然科学基金Nos.2014GXNSFAA118353,2014GXNSFAA118390,2014GXNSFDA118036 广西高等学校高水平创新团队及卓越学者计划 广西云计算与大数据协同创新中心基金项目 广西物联网技术与产业化推进协同创新中心资助项目~~
【分类号】：TP311.13
【相似文献】
相关期刊论文 前10条
1 徐帆;汇总型多表连接查询的一种优化方法[J];计算机工程与设计;2002年10期
2 张雷;唐桂芬;苏冉冉;;基于通用空间连接图的适应性多元空间连接查询[J];计算机光盘软件与应用;2013年13期
3 彭建平,王变琴;再探多连接查询优化方法[J];中山大学学报(自然科学版);2001年02期
4 刘宇,孙莉,田永青;并行空间连接查询处理[J];上海交通大学学报;2002年04期
5 王果,徐仁佐;结合哈希过滤的一种改进多连接查询优化算法[J];计算机工程;2004年07期
6 陈恕胜;刘卫东;;基于图的适应性多连接查询优化算法[J];计算机工程;2009年10期
7 郭聪莉;朱莉;李向;;基于蚁群算法的多连接查询优化方法[J];计算机工程;2009年10期
8 王
本文编号：2513492
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2513492.html
