基于MapReduce 的数据倾斜连接算法 - 计算机科学.PDF

第 43 卷第9 期 计算机科学 Vo1. 43 No.9 2016 年 9 月 Computer Science Sep 2016 基于 MapReduce 的数据倾斜连接算法 梁俊杰何利民 (湖北大学计算机与信息工程学院 武汉 430062) 摘 要 连接操作是大规模数据集在数据分析应用中最常用的操作，针对 MapReduce 自身不能有效地处理数据倾斜 情况下的连接操作，提出了基于MapReduce 的频次分类连接算法。根据数据在连接数据集中出现的频率将整个数据 集分为 3 类，对倾斜数据利用分区算法和广播算法实现数据重分布，以消除数据倾斜的影响;对非倾斜数据采用 Hash 算法实现数据重分布。重分布后的数据在羊节点内即可完成数据连接操作，避免了 MapReduce 框架下连接操作的垮 节点传输代价;同时有效地均衡了 MapReduce 各节点的任务负载，ρ、而提高了数据倾斜状态下连接操作的效率。通 过与传统连接算法的对比，证明了所才是算法的有效性和实用性。 关键词 数据倾斜，MapReduce，连接算法，负载均衡 中图法分类号 TP31 1. 1 文献标识码 A 001 10. 11896/j. issn. 1002-137)立 2016.9.005 Join Algorithm in Skewed Datasets ßased on MapReduce LIANG ]un-jie HE Li-min (School of Computer Science and Information Engineering ,Hubei University ,Wuhan 430062 ,China) Abstract ]oin operation is the most common operation in data analysis applications with large -scale datasets ,and 鸟也p Reduce can not support join operation perfectly in handling data skew problem. MapReduce frequecncy classified join al gorithm was proposed ,and datasets were classified into three categories according to the appeared data frequency. Data redistribution applying partitioning algorithm and broadcast algorithms eliminate the impact of skewed data And data redistribution is realized by using hash algorithm for the non-skew data. ]oin operation can be completed in a single node ,avoiding the cost of communications across the nodes under the MapReduce for the redistributed data ,and balan cing the workload of each node effectively ,thereby improves the efficiency of join operations in skewed data. The effec- ti