在这个系列的前两篇中,介绍了基本的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
相关推荐
NULL 博文链接:https://mysun.iteye.com/blog/1748484
Map-Reduce-Join-Locate: a Data Processing Framework for
19、Join操作map side join 和 reduce side join 网址:...本文介绍mapreduce的join操作。 本文前提是hadoop可以正常使用。 本文分为3个部分介绍,即join的介绍、map side join和reduce side join。
thetaJoin 使用 Map-Reduce 编程框架实现 theta 连接的算法
【MapReduce篇06】MapReduce之MapJoin和ReduceJoin1
展示使用MR方式实现表连接的代码示例。利用HIVE PIG之类的高层工具也可以实现,本代码旨在展示手工连接的流程
Map side join 比 reducer side join 快。 但是只有当您执行映射端连接操作的表之一小到足以放入内存时,映射端连接才足够。 日期集信息 客户数据集:每行包含:CustID、Name、Age、CountryCode、Salary。 交易...
Map/Reduce framework seems to be specifically designed for group-by aggregation tasks rather than across-table op- erations; on the other hand, join operation in distributed database systems was never...
Map/Reduce是海量离线数据分析中广泛应用的并行编程模型.Hive数据仓库基于Map/Reduce实现了查询处理引擎,然而Map/Reduce框架在处理偏斜数据时会出现工作负载分布不均的问题.均衡计算模型(computation balanced model...
通过使用 python 执行一些本地 map reduce 任务来模拟算法 data/MapReduce.py -- 执行 mapreduce 的函数。 所有其他脚本都调用此方法来执行 map 和 reduce。 data/inverted_index.py -- 创建倒排索引。 给定一组...
The Joins query by using Hadoop and map reduce
3.5.1 Reduce-Side Join 64 3.5.2 Map-Side Join 66 3.5.3 Memory-Backed Join 67 3.6 Summary 4 Inverted Indexing for Text Retrieval 4.1 Web Crawling 4.2 Inverted Indexes 4.3 Inverted Indexing: Baseline ...
数据可以有许多来源,如Kafka, Flume, Twitter,ZeroMQ或传统TCP套接字,可以使用复杂算法对其处理实现高层次的功能,如map,reduce,join和window。最后,经处理的数据可被输出到文件系统,数据库,和实时仪表盘。事实...
jQuery 的核心功能都是通过这个函数实现的。 jQuery中的一切都构建于这个函数之上,或者说都是在以某种方式使用这个函数。这个函数最基本的用法就是向它传递一个表达式(通常由 CSS 选择器组成),然后根据这个...
9.3.3 MapJoin;9.3.4 Group By;9.3.5 Count(Distinct) 去重统计;9.3.6 笛卡尔积;9.3.7 行列过滤;9.3.8 动态分区调整;9.3.9 分桶;9.3.10 分区);9.4 数据倾斜(9.4.1 合理设置Map数;9.4.2 小文件进行合并;...
以及 TCP sockets,从数据源获取数据之后,可以使用诸如 map、reduce、join 和 window 等 高级函数进行复杂算法的处理。最后还可以将处理结果存储到文件系统,数据库和现场仪表盘。 在“One Stack rule them all”的...
FocusBigData :elephant:Hadoop分布存储框架 Hadoop篇 HDFS篇 HDFS客户端操作 --- 开发环境准备 HDFS客户端操作 --- 文件操作 HDFS客户端操作 --- IO流操作 ...MapReduce之MapJoin和ReduceJoin MapReduce之
文件汗有三个java类,两个测试文件txt ReduceClass.java MapClass.java TaggedRecordWritable.java customers.txt orders.txt 经过亲自测试,可以将两个文件中的信息以groupby的key关联起来,查出类似数据库的join.
这些章节探讨了诸如Task-Parallel库之类的主题,实现了诸如Fork / Join,分而治之和Map-Reduce之类的并行模式。 还讨论了声明式组合,异步操作中的高级抽象,代理程序编程模型以及消息传递语义。 然后,第13章和第...