`
lt200819
  • 浏览: 187580 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

通过Map-Reduce实现Join系列之三

 
阅读更多

在这个系列的前两篇中,介绍了基本的Join算法以及在Hadoop环境中,如何利用Map-Reduce过程来完成Join。而前面的介绍都是基于两个集合的Join,本文将会介绍利用Map-Reduce来完成2个以上文件的Join的相关算法(Multi-way join algorithms)。基本的思路与第二篇文章中介绍的Map-Reduce Join类似,根据将这个算法扩展到多个文件的方式,可以分为两种,一种是使用一个Map-Reduce任务完成所有文件的Join,另外一个中使用多个任务来完成多个文件的Join。 
1.使用单个Map-Reduce任务完成Join 
这种算法可以看作是第二篇中提到的基于一个完整的Map-Reduce来完成Join的算法的扩展。比如,有n个数据文件需要Join,他们分别是T1(A1,B),T2(A2,B),T3(A3,B),....,Tn(An,B),需要在B列上进行Join。

  • Map阶段

Map阶段从每个文件读取数据,然后根据一定的规则为不同来源的数据打上标记,然后以B列的值为Key,将数据写出到中间文件中。

  • Reduce阶段

所有在B列上具有相同值的来自不同文件的记录会被同一个Reducer进行处理。在第二篇的介绍中,对于两个文件的join,Reducer在调用reduce方法之前,会对同一个key下面的数据进行排序,保证来自于一个文件的所有数据会优先与另外一个文件的数据,对于多个文件的Join,这一点也同样需要得到保证。通过自定义Reducer端的分组和排序方式,可以达到这样的效果。recude方法将同一个key下来自于前n-1个文件的数据全部读到内存缓存起来,当读第n个文件的数据时,开始进行执行join操作,并将结果写出到结果文件中。 
这种算法的优点在于可以通过一个Map-Reduce任务完成所有数据文件的join,同时,产生的零时文件也是最少的,比较节省HDFS的磁盘空间。但是这个算法存在一个最大的劣势,Reducer阶段需要缓存大量的数据,当需要进行Join的数据文件个数比较多时,很容易产生内存的不足的情况。虽然可以将缓存的数据进行切分,放入磁盘,但是这样做会带来性能上的损失,同时也增加了算法的复杂度。 
2.使用多个Map-Reduce任务完成Join 
除了上面说的将多个文件的Join放到一个Map-Reduce任务中去完成之外,我们还可以将多个文件的Join切分成多个不同的Map-Reduce任务去执行。例如, 有n个数据文件需要Join,他们分别是T1(A1,B),T2(A2,B),T3(A3,B),....,Tn(An,B),需要在B列上进行Join。我们可以将T1和T2进行Join,然后将其结果与T3进行Join,以此类推,最终完成n个数据文件的Join操作。 
这种Join方式适用于任何大小任何数据量的文件之间的Join,而且相比于第一种方式,单个Map-Reduce任务需要处理的数据量小了很多。但是,由于需要实用多个Map-Reduce任务来完成Join,这种方式会产生很多的中间文件,占用HDFS的磁盘空间,同时对整个Hadoop集群带来的压力也比第一种方式要高很多。

  • 多任务Join的优化

简单的每次Join两个数据文件的方式其实是非常低效的,不仅消耗存储资源,对计算资源的消耗也非常巨大,下面有集中方式可以来优化多Map-Reduce任务的Join。 
首先,可以对每个任务产生的中间文件进行压缩处理,这样可以大大减小中间数据对存储的 消耗,同时也可以减小对网络贷款的消耗,因为要传输给Mapper或者Reducer的数据量减小了。 
第二,可以通过优化数据文件的Join顺序来提高效率。这种优化主要通过衡量两个数据文件Join之后可能产生的数据量来决定各个数据文件的Join顺序。Join之后产生的数据量最小的两个文件将被有限进行Join,以此类推。现在考虑如下的两个数据集合: 
 
这两个文件Join之后的结果如下: 
 
数据的记录数可以通过下面的公式得到: 
 
其中,T(K)表示数据文件T中,Join条件用到的列上,具有K值的记录条数。 
在上面给出的例子中,通过计算,我们可以得到这两个数据集合Join之后,将会产生的记录数是: 
1 x 1 + 2 x 1 + 1 x 2 = 5 
只要我们能够找出每个数据文件中包含的key的数量,已经每个key下面对应的记录的条数,我们可以很容易的决定各个数据文件之间的Join顺序。这个计算我们可以放到一个数据的预处理过程中,然后将预处理的结果存到HDFS上的一个指定文件中,当执行多文件Join时,首先读取这个文件,然后根据文件内容逐个两两Join不同的数据文件。 
第三,在知道了不同文件Join之后所产生的数据量之后,我们可以在一个Map-Reduce任务中尽量多地Join几个数据文件,而不是每次只Join两个数据文件,这样做也可以起到一定的节省存储和计算资源的效果。

转自:http://mysun.iteye.com/blog/1748483

分享到:
评论

相关推荐

    【MapReduce篇06】MapReduce之MapJoin和ReduceJoin1

    今天,我们将讲解 MapReduce 之 MapJoin 和 ReduceJoin 两种 Join 操作的实现原理和应用场景。 MapJoin 概述 MapJoin 是一种特殊的 Join 操作,通过在 Map 阶段对数据进行 Join 操作,减少了 Reduce 阶段的数据...

    19、Join操作map side join 和 reduce side join

    本文主要探讨了两种 MapReduce 中的 Join 实现:Map Side Join 和 Reduce Side Join。 一、Join 的概念 Join 操作在数据库中是非常常见的,它用于将来自两个或更多表的数据根据某些共享字段(即键)关联起来。在 ...

    Map-Reduce-Join-Locate: a Data Processing Framework for

    Map-Reduce-Join-Locate: a Data Processing Framework for

    hadoop Join代码(map join 和reduce join)

    本文将深入探讨Map JOIN和Reduce JOIN两种在Hadoop中实现JOIN的方法,并通过代码示例来阐述它们的工作原理。 1. Map JOIN: Map JOIN在Hadoop中主要应用于小表与大表的连接。小表的数据可以完全加载到内存中,而大...

    Mongo-Commands:MongoDB命令速查表。 包含map-reduce,aggregate等

    在MongoDB中,map-reduce用于执行复杂的分析任务,通过将数据分发到多个节点并进行并行处理来提升性能。 **Map阶段**: 在这个阶段,开发者定义一个JavaScript函数(map函数),它遍历集合中的每个文档,并为每个...

    在Hadoop Map-Reduce中实施联接

    3. **Reduce-Side Join**:这是最常见的Join策略,适合于两个或更多大小相近的数据集。在Map阶段,每个数据集独立处理,生成各自的中间键值对。在Reduce阶段,相同的键会被发送到同一个Reducer,从而完成Join操作。...

    thetaJoin:使用 Map-Reduce 编程框架实现 theta 连接的算法

    在MapReduce环境中实现Theta连接,通常分为三个主要步骤:Map、Shuffle和Reduce。 1. **Map阶段**:在这个阶段,我们对输入的数据进行预处理。对于每个表,我们分别读取其记录并生成键值对。键通常是连接字段,值则...

    Hive-Summit-2011-join.zip_hive

    3. **Map-side Join**:为了解决大规模数据集的Join问题,Hive引入了Map-side Join。这种方法适用于小表与大表的连接,小表可以被完全加载到内存中,从而避免了在Reduce阶段的昂贵数据交换。 4. **Bucketing与...

    pig-0.9.2.tar.gz下载

    Pig Latin编写的脚本最终会被转化为一系列的Map-Reduce作业,这是通过Pig的编译器实现的。Pig的这种特性使得开发者可以专注于业务逻辑,而不必关心底层的分布式计算细节。在Pig-0.9.2版本中,对Map-Reduce的优化和...

    大数据课程设计-Hadoop-MapReduce实现sql的统计、groupby和join-全部源码

    3) 内连接(Inner Join)和左连接(Left Join)可以通过一次MapReduce作业实现,Map阶段将JOIN键和对应数据发送到同一Reducer,Reduce阶段根据JOIN条件进行匹配。 在提供的"mapreduce-sql"压缩包文件中,很可能包含...

    Map_Reduce_Hadoop:实施map-reduce程序来执行等值连接

    在大数据处理领域,...总之,通过理解Hadoop MapReduce的工作原理和Java编程接口,我们可以有效地实现等值连接操作,处理大规模数据集的联合任务。这不仅有助于提升数据处理效率,还为大数据分析提供了强大的工具。

    javamap源码-MR-JOIN-JAVACODES:地图减少连接的Java源代码

    本资源"javamap源码-MR-JOIN-JAVACODES"似乎是一个关于Map在MapReduce框架下的Java实现,特别是针对数据连接操作的优化。MapReduce是一种分布式计算模型,由Google提出,常用于大数据处理。 在MapReduce中,Map阶段...

    Hive Summit 2011-join

    3. AutoMap Join(自动Map Join) Hive还提供了一种自动识别并执行Map Join的机制,称为AutoMap Join。它能够自动决定何时将普通的join操作转换为Map Join。这在很大程度上减轻了用户的负担,不需要手动指定join...

    基于 MapReduce 快速 kNN Join 方法1

    为了解决这个问题,我们引入了 map-reduce 框架来运行 kNN join 并提出了两种新的方法:基于 map-reduce 的分布式网格概略化 kNN join(DSGMP-J)和基于 map-reduce 的 voronoi diagram 下 kNN join(VDMP-J)。...

    hadoop_join.jar.zip_hadoop_hadoop query_reduce

    本文将深入探讨如何使用Hadoop和MapReduce进行高效的Join查询,并解析如何通过`hadoop_join.jar`这个工具来实现这一过程。 Hadoop是Apache软件基金会开发的一个开源分布式计算框架,它的核心组件包括HDFS(Hadoop ...

    hadoop_join_aggregate:在hadoop中加入和聚合mapreduce算法

    Map side join 比 reducer side join 快。 但是只有当您执行映射端连接操作的表之一小到足以放入内存时,映射端连接才足够。 日期集信息 客户数据集:每行包含:CustID、Name、Age、CountryCode、Salary。 交易...

    Mapside-Join

    Mapside Join是大数据处理领域中的一种优化策略,主要用于Hadoop MapReduce框架,旨在提高大规模数据集的JOIN操作效率。...通过Java编程,我们可以实现高效、可靠的Mapside Join,为海量数据处理提供强大的支持。

Global site tag (gtag.js) - Google Analytics