大数据连接算法分析

李立现　屈晓平　高琴琴

摘要：大数据主要有四个典型特征：海量、多样性、高速、易变。连接算法优化是大数据热点问题之一，2010年以来，数据库顶级会议ICDE，Sigmod和VLDB每年都有专门的文章研究基于MapReduce的连接算法优化。依据连接条件主要可以分为等值连接法、数据倾斜时连接法和任意连接法，分析三种数据连接方法，介绍三种连接算法设计和优化方式，并针对基于BloomFilter等值连接设计和优化做了和二阶段法和三阶段法的实验分析。两表等值连接，数据量较大时，采用基于BloomFilter等值连接方式会在一定范围减少算法执行时间，提高数据连接效率。

关键词：云计算；大数据集；等值连接；任意连接

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）13-0219-02

Abstract： Big data mainly has four typical characteristics： mass， diversity， high speed， easy to change.Connection algorithm optimization is one of the big data issues， since 2010， the database top meeting ICDE Sigmod and VLDB every year have special article studies connection efficiency optimization algorithm based on graphs.According to the connecting conditions are equivalent connecting method， the data skew links and any link method， analyzes the three methods of data connection， introduce three kinds of connection algorithm design and optimization method， and based on BloomFilter contour connection design and optimization done and two stage method and experimental analysis of three phase method.Equal join two tables， large amount of data， based on BloomFilter equivalent connections will be reduced in a certain range algorithm execution time， improve the efficiency of data connection.

Key words： Cloud Computing； Big Data ； Equi-join； [θ]Join

根据参考材料[1]中统计显示全部企业的信息每天高达 2.2ZB存储量，其中大型企业平均每天可以产生10WTB的信息量，而中小企业平均每天可以产生 563TB 的数据量。大数据主要有四个典型特征：海量、多样性、高速、易变[1-5]。连接算法优化是大数据热点问题之一，2010年以来，数据库顶级会议ICDE，Sigmod和VLDB每年都有专门的文章研究基于MapReduce的连接算法效率优化[6-10]。研究基于MapReduce的连接算法并优化其效率是大数据在云平台下能够快速处理的关键。依据连接条件，目前主要连接算法主要体现在以下三个方面：等值连接算法的设计与优化，数据倾斜时的连接算法的设计与优化，任意连接算法的设计与优化[11-15]。

1 大数据集连接算法

近年来，大数据领域中最常用的一个并行框架是MapReduce，MapReduce为许多大型公司尤其是互联网公司处理业务需求，基于MapReduce设计的Hive是现在市场主流的分布式数据仓库[14]。程序设计人员在进行任务查询时，数据仓库Hive内部连接操作是最占时间的，因而数据连接算法的设计和优化就成为目前的热点和关键技术。

1.1等值连接算法

缺少索引支持的MapReduce并行计算框架，如果需要处理一个或多个数据集，就需要MapReduce在系统内全部加载相应的数据集中的数据，先是需要map函数处理，接者是使用网络发送给reduce端，并且相应的处理操作要在reduce端进行，最后在HDFS中存放最终结果[14]。比如在R连接S时，设定数据集R的大小为r，数据集S的大小为s，reduce端接全部收来自map发送的两个数据集，在网络传输shuffle阶段时间代价记为C（r + s），这里的C我们设定为一个整数。假设我们选取连接选择率（0.1）较小的R和S，可以获知在shuffle阶段只需要发送的数据量是0.1C（r + s），消减了原来网络传输量的9/10，尤其在集群环境 Hadoop中，同一时刻会处理很多数据，在有限的网络宽带资源下，不但可以提高算法的运行效率，而且在Hadoop系统中也可以提高整体的吞吐量，优化的等值连接算法对网络传输的优化是十分重要[15]。

1.2数据倾斜时的连接算法

在数据通常的分析处理中，常常会有某个值或者某些值出现的频率很高，远远高于其他数值出现频率，数据的这种现象我们称之为数据倾斜或者倾斜的数据，比如某个论坛上，发帖数目方面活跃用户要远远高于非活跃用户，或者数据丢失情况下，日志收集中常常使用空值（NULL），从而导致多次出现（NULL） [14]。在连接查询中两表或者多表会遵循哈希函数的规则，在同一节点上分配相同的数值，这样就会使得在的节点上倾斜数据要非常明显的数据增多，尤其在并行环境的运行条件下，reduce端的负载会因倾斜的数据而造成不均衡，形成“长板效应”，大部分reduce节点执行时间很短，一个或几个节点执行时间较长，导致整个MapReduce程序在较长的时间运行[16]。所以，深入研究并优化数据倾斜时的两表或者多表连接算法的效率是提高大数据处理的关键。

1.3任意连接算法

任意连接是数据库中一种关系运算方式，又可以称之为[θ]连接，关系运算符主要包括<、[≤、=、≥、>]等，等值连接只是其中特殊一种方式，现在相对等值连接，任意连接具有更普遍的意义[16]。以两个企业商品数据集句R（A，B）和S（B，C）为例，设定属性B是商品入库时间，A表示第一个企业的商品名字，C表示第二个企业商品名字，S.B>R.B为其对应的连接条件，数据仓库Hive在设定条件下不能有效的支持[θ]连接，由于reduce端接收的来自map阶段产生key-value键值对形式的数据时间，不能提前获得两个数据集中的准确的数据分布信息，如果其中一个数据集不是对全部节点广播，其他数据集遵循哈希分配在相应节点上，就会导致不易确定连接属性B在R和S中哪些是适合连接条件，之后必须在每个节点做出相应的连接判断，这样shuffle阶段必然加大网络传输量[14]。可见有效设计和实现在MapReduce环境下两表和多表连接算法是影响到大数据处理效率。

2 连接算法优化

2.1等值连接算法优化

在大数据处理分析中，较为突出的是多表和两表的等值连接，改善等值连接算法可以较大提高数据处理效率，所以可以引入BloomFilter优化等值连接算法[14]。第一步，利用MapReduce快速高效生成BlooomFilter；第二步，基于BloomFilter进行多表和两表的等值连接算法设计，获得各种算法在不同的数据集下的连接处理效率；第三步，进行对算法进行建模，任意数据集实验分析出选择一个最佳的等值连接方案。

2.2 数据倾斜时的等值连接算法优化

MapReduce环境中，在使用基于Hadoop默认分区方法，倾斜的数据集会造成reduce端的数据集合倾斜，处理数据数量随着各个reduce端发生改变，使得整个MapReduce程序降低了执行效率[14]。在实际使用中，经常出现倾斜的数据，所以要优化倾斜数据连接是十分必要的，第一步，利用Maxdiff直方图技术，获得属性B在R中倾斜元素的集合Rskew和数据集S中倾斜元素的集合Sskew；第二部，map函数将Rskew和Sskew中的数据随机发给reduce端，发送方式为key-value键值对形式；第三步，reduce函数接收，输出到HDFS中。

2.3多表[θ]连接算法优化

[θ]连接比等值连接更为普遍，具有丰富的语义，更适合一般化的查询需求。MapReduce平台上，[θ]连接算法不容易实现，因而优化多表的[θ]连接算法是提高大数据分析处理的关键[14]。第一步，定义R1连接R2连接…连接 Rn连接方案的连接图；第二步，连接策略：在数据集对应的查询连接图，确定划分，每个划分的每个子图都对应一个连接策略，第三步，函数estimatedCost给出基于MapReduce的多表任意连接效率最好方案。

3 基于BloomFilter的等值连接实验分析

第三节介绍了三种优化方法，这里就等值连接优化算法两表连接进行实验分析。第一步，基于 MapReduce 的 BloomFilter 建立算法，对连接属性进行预先过滤，筛除掉对最终结果没有影响的数据元素，消减后续阶段shuffle的网络传输量，提高数据连接效率，这里分别就基于BloomFilter的改进法，两阶段法和三阶段法[14]。假设R（A，B）和S（B，C）两个数据集每个都包含了两个属性，每个属性值是通过随机生成的1到1000000范围内的整数，并且R（A，B）和S（B，C）数据集数目相等。实验主要验证两个方面的改变，一是数据集R和S中数据数目的大小，二是数据集R和S的属性B的连接选择率，我们定义连接选择率如下：符合设定连接条件的属性的值在数据集中所占比例，比如选择率是0.1，表示有10%的数据集R或者S 中元组需要进行连接操作。

如图1所示的实验结果，数据数量在5千万以下时，Improved Repartition Join算法的效率要低于两阶段法和三阶段法，试验中优化算法在运行中创建BloomFilter并增加了MapReduce轮数，所以增加了时间消耗。当数据量逐步增大到5千万以上时间，优化算法可以利用BloomFilter过滤掉很多无用数据，减少shuffle阶段网络传输量和reduce阶段的处理时间，优化算法效率就大大高于标准算法。实验对比分析，连接属性选择率小于1%时，两阶段法的效率要比三阶段法差，是由于第三阶段和三阶段法的第二阶段不需要shuffle过程和reduce过程，仅仅包含map过程，从而较大消减算法运行时间。在逐步增加到一定数目的数据集时，三阶段法的第二阶段产生的数据集Si会增加很大，传输Si到全部的map中，会浪费很多时间，因而两阶段法的运行效率要高于三阶段法。

4 结束语

简单介绍了根据连接条件分类的三种方法： 等值连接法、数据倾斜时连接法和任意连接法，说明了这三种方法各自的特点，指出了各自所适用的数据范围，并且对比了两表和多表下三种连接算法。重点基于BloomFilter等值连接实验的进行详细分析。分别采用二阶段、三阶段和基于BloomFilter的两表等值连接进行实验。实验表明，两表等值连接，数据量较大时，采用基于BloomFilter等值连接方式会在一定范围减少算法执行时间，提高数据连接效率。

参考文献：

[1] http：//www.enet.com.cn/cio/zhuanti/2012/bigdata.

[2] Randal E. B. ， Randy H. K. ， Edward D. L. ， Big-Data Computing： Creating revolutionaryBreakth

roughs in commerce， science and society[R]. http：//www.cra.org/ccc/files/docs/iiiit/Big-Data.pdf.

[3] James M. ， Michael C. ， Brad B. ，Jacques B” Big data： The next frontier for innovation， compe-

tition， and productivity[R]， http：//www.mckinsey.com/Insights/MGI/Research/Technology-and-

Innovation/Big-data-The-next-frontier-for-innovation

[4] The digital universe in 2020： big data， bigger digital shadows， and biggest growth in the far

east[EB/OL]. http：//www.emc.com/collateral/analyst-reports/idc-the-digitaluniverse-in-2020.pdf.

[5] Ibrahim S， Hai J， et al. Handling Partitioning Skew in MapReduce using LEEN[J]. Peer-to-

PeerNetworking and Applications， 2013， 409-424.

[6] 王珊， 王会举， 覃雄派， 周烜， 架构大数据：挑战，现状与展望计算机学报，2011，34（10）：1741-1752.

[7] 丁琳琳， 信俊昌， 王国仁， 黄山.基于Map-Reduce的海量数据高效Skyline查询处理[J]. 计算机学报， 2011， 34（10）： 1785-1796.

[8] 李建江， 崔健， 王聃，等. MapReduce 并行编程模型研究综述[J]. 电子学报， 2012， 39（11）： 2635-2642.

[9] 弥艳金. MapReduce模型在Hadoop平台下实现作业调度算法的研究和改进[D]. 华南理工大学硕士论文， 2011.

[10] 李成华， 张新访， 金海，等.Map Reduce：新型的分布式并行计算编程模型[J]. 计算机工程与科学， 2011（03）.

[11] 张凯. 视频运动检测算法的研究和分析[J]. 辽宁工学院学报， 2007（1）.

[12] 李鑫. Hadoop框架的扩展和性能调[D]. 西安：西安建筑科技大学硕士论文， 2012（05）.

[13] 彭辅权， 金苍宏， 明晖. MapReduce中Shuffle优化勾重构[D]. 杭州： 浙江大学计算机学院， 2012.

[14] 张常淳. 基于MapReduce的大大数据算法的设计与优化[D]. 中国科学技术大学博士论文， 2014.

[15] 孙慧. 基于hadhoop框架的大数据集连接优化算法[D]. 南京邮电大学硕士论文， 2013.

[16] 郭骐恺. 基于MapReduce的连接方法研究[D]. 吉林大学硕士论文， 2014.