基于Spark的大数据统计中等值连接问题的优化

刘容辰，周明强，皮兴杰，赵欣

（重庆大学计算机学院，重庆 400044）

基于Spark的大数据统计中等值连接问题的优化

刘容辰，周明强，皮兴杰，赵欣

（重庆大学计算机学院，重庆 400044）

伴随着互联网应用技术的飞速发展，导致传统的数据处理技术已经无法满足对大数据高效处理的要求。因此对现有的大数据的统计分析便急需相应的大数据技术的支持。为了解决实际Spark应用中的Join操作低效的问题，首先，提出一种高效的基于BloomFilter过滤再分区算法，通过该算法率先过滤掉绝大部分不符合条件的无效连接，然后针对过滤数据产生的倾斜问题进行再分区操作，以便能充分发挥各个工作节点的计算资源，达到在最大程序上优化Join过程的目的。

大数据；Spark；等值连接；BloomFilter；Shuffle

1 相关工作

近些年来，伴随着互联网应用技术的飞速发展，导致数据量巨大且种类繁多的数据给传统的数据处理技术带来了巨大的挑战，因此大数据便成为现在阶段最受到关注且有待解决的热门问题[1，4]。在传统数据库（如：Oracle、MySQL）中，Join操作是特别常见且耗时的操作[2]。如何优化这种等值连接操作便成为了大家的研究重点[3,5]。

文献[6]提出了一种大表等值连接的优化算法，其优化思想是利用Bit-Map压缩算法对大表的连接属性进行压缩处理，这种优化算法可以提前过滤掉一些不符合连接条件的记录，减少Shuffle阶段的数据量。但是这种优化算法在数据过滤阶段的误判率特别高，因此会误判很多不符合连接条件的数据，Shuffle阶段的数据量仍然会比较大，数据过滤效果并不明显。文献[7]的优化思路同样是在大表相连以前过滤掉一些不符合条件的记录，其过滤算法采用BloomFilter数据结构，因为BloomFilter结构相对于Bit-Map而言，它的数据过滤效果更好，但它的缺点是生成的位数组更大。文献[8]结合了BloomFilter的思想，提出一种高效的基于BloomFilter数据结构的大表等值连接优化算法，但是针对RDD过滤后产生的数据倾斜的问题却没有进一步的优化操作。

本文借鉴了传统数据库的统计查询方法以及基于Hadoop平台的统计思想，在数据统计过程中，优化了数据的等值连接过程，针对RDD进行预先数据过滤产生数据倾斜的问题，借鉴一致性的思想，进一步对过滤后RDD进行重分区操作，以便能充分发挥各个工作节点的计算资源，达到在最大程序上优化Join过程的目的，并通过实验验证了该算法的有效性。

2 Bloom Filter介绍

BloomFilter过滤器是一种具备极高的空间效率的数据结构，主要用于检索一个元素是否已经存在于某一个数据集合中[9]。如图1所示，x，y，z这三个哈希函数所对应数值均为1，都是符合条件的数据，而w则不是。

BloomFilter的优点是空间效率高和查询时间较短，其缺点则是会存在一定的误判率。对于具备n条记录的数据集，k个哈希函数，位数组大小为m，造成的误判率p如下：

图1 BloomFilter过滤示意图

本文将BloomFilter应用在Spark平台的Join操作中，以达到提前过滤掉不符合连接条件的数据的目的。

3 过滤再分区的大表等值连接算法介绍

3.1 过滤算法介绍

过滤算法主要可以分成两个部分。第一部分：对抽取的两张数据表的连接属性进行去重操作，然后对经过去重后操作后的连接属性进行BloomFilter压缩处理，从而得到过滤所需要的位数组数据。对两个位数组进行与运算便可得到最终的位数组（BF）。第二部分，使用最终生成的BF位数组对待Join的两张数据表进行过滤，提前过滤掉所有不满足连接条件的记录，当经过Judge运算之后，其返回false的元素将被提前过滤掉。Judge操作如下：首先针对每条记录数据的连接属性，使用生成的位数组的k个哈希函数，计算出k个Hash值，然后再对m取模运算，从而得到k个0～m-1的值，最后检查BF位数组中k个位置的值是否均为1，BF位数组中这个k个位置值若全为1，则返回true，反之则，返回false[4]。过滤算法整体步骤如图2所示。

图2 过滤算法整体示意图

在上述两个过程中，两个数据表一定要使用相同的Hash函数进行压缩处理。最后利用Broadcast操作将该位数组广播到集群的其他工作节点上，从而加速数据表的过滤阶段。

3.2 分区策略介绍

（1）首先，根据table_a_p，table_b_p的元组数量，从而计算连接并行度pd，pd=min（table_a_p.partionSize+ table_b_p.partionSize，w），其中partionSize表示分区数，w表示用于控制并行度的最大值。

（2）分别选取table_a_p，table_b_p的连接属性key，根据设定好的采样率ω进行对两者的并集采样，得到样本sampleKey。

（3）然后，计算sampleKey中key的Hash值，根据（1）计算的pd值，将Hash空间划分成为pd个区间，并且需要保证每个区间的样本大小相等。

（4）最后，将table_a_f，table_b_f按照步骤（3）中划分出区间，通过Hash分配到集群对应节点上。

对经过上述的过滤在分区操作后数据表执行普通的Join操作，再将处理过后的RDD转换成数据表，然后将相关业务sql进行HashJoin操作，最后，将生成结果保存到传统数据库（如：Oracle,MySQL）中。

3.3 过滤再分区算法分析

本文所提出的基于过滤再分区的大表等值连接算法——BF-P-Join（BloomFilter-Partitioner-Join）主要包含三个主要阶段及数据表过滤阶段、数据表再分区阶段和最后的HashJoin阶段。Spark处理等值连接的方法主要有两种：BroadcastJoin方式和HashJoin方式。本节将从代价开销和适用场景两个角度对比这几种处理方式优劣。

完成数据处理任务的开销主要在Shuffle阶段的网络通信开销和Join阶段的执行时间。代价分析中的符号描述如表1所示：

（1）HashJoin方式，对原数据表直接进行关联，在整个关联过程中的重分区操作会出现Shuffle操作，因此这种方式的网络通信的开销主要与数据表的数据量相关：

（2）BroadcastJoin方式，将其中一张关联表以广播的方式发送到集群的其他节点上，连接过程中无Shuf-fle操作，因此网络开销主要与广播表的数据量相关。通常选择数据量较小的数据表作为广播表，假设table_b是广播表，则它的网络开销如下：

BF-P-Join方式，其开销主要由两部分构成。第一个部分的开销主要在位数组生成阶段。第二部分是数据表执行HashJoin操作时Shuffle操作产生的数据量所产生的网络开销。总代价开销如下：

从整体上看，BF-P-Join方式虽然增加了分区阶段的时间开销，但在最后的运行阶段可以充分利用了集群中各节点的并行运算性能，从而缩短统计时间。

表1 代价分析符号描述

4 实验

将本文提出的基于过滤再分区的大表等值连接算法，与SparkSql默认的HashJoin算法以及文献[4]中提出的BF-Join算法进行对比实验，以验证该算法在Shuffle阶段的数据读写量及算法的整体运行时间要更加高效。本次实验选取了三组不同规模的数据集，如表2所示。

表2 数据集大小

为了使得实验结果更加可信，在实验过程中对每组实验重复执行一百次，并记录实验结果的平均值。实验结果如表3、表4和图3所示。

根据以上实验结果，可以看出，在Shuffle读和Shuffle写两个方面，BF-Join算法和BF-P-Join算法都要优于HashJoin算法。BF-P-Join算法需要因为进行过滤后再分区的阶段，该阶段同样也会产Shuffle操作，因此这两方面上不如BF-Join算法。从算法整体运行时间方面，可以看出BF-Join算法和BF-P-Join算法同样优于HashJoin算法。BF-P-Join算法因为出了一步分区操作，在数据量较小的情况下，集群的任务量较少，没有出现数据倾斜的现象，从而导致整体运行时间略慢于BF-Join算法。在数据量较大的情况下，可以看出上本文提出的BF-P-Join算法明显优于BF-Join算法。

表3 Shuffle写数据量对比

表4 Shuffle读数据量对比

图3 算法整体运行时间对比图

5 结语

本文针对大表的等值连接问题，提出了基于过滤再分区的BFP算法。该算法在大表等值连接过程中，首先采用BloomFilter结构过滤大部分不符合连接条件的数据。然后，通过自定义分区操作将剩余的计算任务平均分配到集群中的各计算节点上，以达到优化Join过程的目的。最后，通过对比实验验证了该算法的有效性。

参考文献：

[1]沈晓磊.基于“大数据”的重点人员管控系统的设计与实现[D].苏州大学，2014.

[2]马建光,姜巍.大数据的概念、特征及其应用[J].国防科技大学，2013,34（2）:10-17.

[3]王妍,柴剑平.大数据及相关技术解读[J].广播电视信息，2014（2）:18-21.

[4]张昕.大数据环境下电子商务的发展探析[J].中国科技信息，2014（23）:197-200.

[5]陶雪娇,胡晓峰,刘洋.大数据研究综述[J].系统仿真学报，2013（S1）:142-146.

[6]孙惠.基于Hadoop框架的大数据集连接优化算法[D].南京邮电大学,2013.

[7]Ramesh S,Papapertrou O.Optimizing Distributed Joinswith Bloom Filters[J].Lecture Notes in Computer Science,2008,5375:145-156.

[8]周思伟.Spark大表等值连接的优化及其在网络流量数据分析的应用研究[D].华南理工大学,2015.

[9]王凤君.P2P存储系统中副本管理策略的研究[D].北京邮电大学，2011.

Optim ization of the Equi-Join Problem Based on Big Data in Spark

LIU Rong-chen，ZHOU Ming-qiang，PIXing-jie，ZHAO Xin
（College of Computer Science,Chongqing University,Chongqing 400044）

With the rapid development of Internet application technology,leading to the traditional data processing technology has been unable to meet the requirements for the efficient processing of large data.So the existing large-scale statistical analysis of the big data will be in urgentneed of the support of the corresponding large data technology.In order to solve the problem of the joining operation inefficient in practical Spark application,firstly,proposes an efficientalgorithm of BloomFilter filter re-partitioning,uses the algorithm to filter outmost of the invalid connections that do notmeet the criteria.And then，re-partition the filtering data which is tilted,in order tomake full use of the computing resources various nodes to achieve themaximum process to optimize the purpose of the join process.

Big Data;Spark;Equi-Join;BloomFilter;Shuffle

1007-1423（2017）12-0003-04

10.3969/j.issn.1007-1423.2017.12.001

刘容辰（1992-），男，湖南怀化人，硕士，研究方向为复杂网络、数据挖掘

周明强（1977-），男，重庆人，博士学位，研究方向为复杂网络、数据挖掘

皮兴杰（1989-），男，湖北襄阳人，硕士，研究方向为复杂网络、数据挖掘

赵欣（1991-），男，甘肃天水人，硕士，研究方向为数据挖掘

2017-03-06

2017-04-20