您好, 访客   登录/注册

大数据连接算法分析

来源:用户上传      作者: 李立现 屈晓平 高琴琴

  摘要:大数据主要有四个典型特征:海量、多样性、高速、易变。连接算法优化是大数据热点问题之一,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]。所以,深入研究并优化数据倾斜时的两表或者多表连接算法的效率是提高大数据处理的关键。
转载注明来源:https://www.xzbu.com/8/view-6854290.htm