基于MapReduce的等值连接中数据倾斜问题研究.docVIP

基于MapReduce的等值连接中数据倾斜问题研究 　　摘要：针对MapReduce计算框架下实现数据表等值连接时不能很好地处理数据倾斜的问题，详细分析了数据倾斜带来的任务负载不均匀问题和解决思路，结合两表之间传统连接算法和广播连接算法思想，提出将倾斜数据和非倾斜数据区别对待的分区连接算法。实验结果表明，提出的算法很好地解决了数据倾斜问题下任务负载均衡问题，有效提高了两表之间等值连接查询效率。 　　关键词：数据倾斜；连接；MapReduce；分区 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）32-0226-03 　　Research on Data Skew in Equal-join based on MapReduce 　　CHU Long-xian 　　（Computer School， Pingdingshan University， Pingdingshan 467000， China） 　　Abstract： Aiming at the problem that data skew can’t be handled well when data table is joined by MapReduce， this paper analyzes the problem of task load unevenness and solution in detail. Combining the traditional join algorithm between two tables and broadcast join algorithm， we propose a partitioning algorithm that treats skewed and non-skewed data differently. The experimental results show that the proposed algorithm solves the problem of task load balancing under data skewing and improves the query efficiency of equal-join between two tables. 　　Key words： Data skew； join；MapReduce；partition 　　1 引言 　　计算机网络技术的不断发展和社会信息化建设的不断加强促使数据规模的快速增长，PB级大小的数据管理在很多行业成为常态。随着大数据的出现，数据处理必然需要分布式计算。MapReduce是Hadoop平台的并行计算框架，可以实现对存储在HDFS（Hadoop Distributed File System）中的大数据进行分布式处理，提高大数据处理效率[1，2]。在网络应用中，有哪些信誉好的足球投注网站和数据库查询领域离不开连接操作[3]，所以研究MapReduce下数据连接算法的优化有着重要意义。 　　MapReduce提供了数据连接并行处理的基本算法，但是在同一个数据集中经常出现某些数值大量出现，导致数据分布不平均问题，利用现有算法将导致节点负载不均衡[4，5]。本文以两个数据表连接为目标，研究数据倾斜情况下大数据连接操作的算法优化问题，提出分区连接算法，提高连接执行效率。 　　2 相关工作 　　2.1 MapReduce 　　MapReduce是基于Hadoop平台的并行计算框架，使用map和reduce函数实现数据的分布式处理，map函数对分片数据执行读取、分区、排序和合并后提交到reduce执行[6]。在执行任务过程中，由master节点负责系统控制和任务分配等工作，slave节点执行具体任务。MapReduce工作流程如图1所示。 　　 　　图1 MapReduce工作流程 　　2.2 连接查询 　　根据连接运算执行的时机，Hadoop下两表连接主要有分为map端连接和reduce端连接两种[7]。 　　map端连接适用于参与连接的其中一个表大小可以缓存到内存中，广播连接是常见的一种算法实现，主要通过将小表广播到所有map节点，然后与每个节点中存储的另一个表的数据块进行连接，将结果写入HDFS中。 　　reduce端连接可以是标准Hash连接也可以是先通过半连接预处理数据后连接。Hash连接主要在map函数将标记有数据来源的元组按照连接属性进行Hash划分，完成shuffle后，相同连接属性的两个表数据会划分到同一个reduce中，在reduce端完成连接操作。 　　半连接应用于大表和小表连接的场景，通过小表中的连接属性对大表参与连接的数据进行预处理过滤，以此减少参与