Hadoop与MapReduce厦门大学数据库室课件.ppt

1、MapReduce编程简介报告人：蔡珉星厦大数据库实验室2014-07-12遇到的问题遇到的问题目录Hadoop与MapReduceMapReduce编程MapReduce执行MapReduce实例Part 1Hadoop与MapReduce-Hadoop简介：Hadoop是一个分布式系统基础架构，由Apache基金会所开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序，并且可以方便的利用集群来提供强大的运算和存储能力。Hadoop设计：Hadoop的框架最核心的设计：HDFS和MapReduce。HDFS为海量的数据提供了存储；MapReduce为存储的数据提供了计算。Hadoop

2、与MapReduce-Hadoop优点：可靠：数据冗余存储，能对失败的节点能重新分布处理；高效：并行处理，可伸缩，能处理PB级数据；成本低：依赖于廉价服务器；运行于Linux平台：Hadoop带有用Java语言编写的框架，适合于Linux；支持多种语言：支持C+，Python等语言。Hadoop与MapReduce的关系：04年Google发表论文介绍了MapReduce，MapReduce是一种编程模型，可用于大规模数据集。Nutch(开源网络搜索项目)使用了MapReduce，后来Nutch项目独立出来，成为Hadoop。Hadoop是一个分布式平台，其组成包括了MapReduce。Had

3、oop与MapReduce-Hadoop与MapReduceHadoop体系结构体系结构-Hadoop与MapReduceHDFS集群集群 一个HDFS集群是由一个NameNode和若干个DataNode组成的。其中NameNode作为主服务器，管理文件系统的命名空间和客户端对文件的访问操作；集群中的DataNode管理存储的数据Part 2MapReduce编程MapReduce编程MapReduce 分布式并行计算模型-MapReduce极大的简化了分布式并行开发，隐藏了复杂的分布式开发细节，而将运行于大规模集群上的并行计算过程高度地抽象到两个函数：Map(映射)和Reduce(规约)。M

4、apReduce编程MapReduce的编程思想 分而治之-大数据计算任务子任务子任务子任务子任务任务划分计算结果结果合并MapReduce编程MapReduce可解决哪些算法问题-MapReduce待处理的数据集可以分解成许多小的数据集,而且每一个小数据都可以完全并行地进行处理，因此不能解决不可分拆的计算任务，或者相互间有依赖关系任务，如Fibonacci函数:Fk+2=Fk+Fk+1 MapReduce可解决的基本算法：各种全局数据相关性小、能适当划分数据的计算任务，如分布式排序关系代数操作 如：选择，投影，求交集、并集，连接，成组，聚合矩阵向量相乘、矩阵相乘词频统计(word count

5、)文档倒排索引MapReduce编程MapReduce可解决哪些算法问题-可解决的复杂算法：Web搜索引擎 网页爬取、网页排序、搜索算法Web访问日志分析 分析和挖掘用户在Web上的行为数据/文本统计分析 如专利文献引用分析和统计图算法 并行化宽度优先搜索(最短路径问题)机器学习数据挖掘MapReduce编程MapReduce的设计思想 借鉴函数式编程-函数式设计语言Lisp：函数式程序设计(functional programming)语言Lisp是一种列表处理言(List processing)，是一种应用于人工智能处理的符号式语言Lisp定义了可对列表元素进行整体处理的各种操作 如:(a

6、dd#(1 3 3 4)#(6 3 2 1)将产生结果：#(7 6 5 5)Lisp中也提供了类似于Map和Reduce的操作 如:(map vector#+#(1 2 3 4 5)#(10 11 12 13 14)通过定义加法map运算将2个向量相加产生结果#(11 13 15 17 19)(reduce#+#(11 13 15 17 19)通过加法归并产生累加结果75MapReduce定义了Map和Reduce两个抽象的编程接口，由用户编程实现。Map:对一组数据元素进行某种重复式的处理Reduce:对Map的中间结果进行某种进一步的结果整理MapReduce编程Map端-map:(k1,

7、v1)list(k2,v2)输入：键值对(k1,v1)表示的数据处理：文档数据记录(如文本文件中的行，或数据表格中的行)将以“键值对”形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果list(k2,v2)输出键值对(k2,v2)表示的一组中间数据备注:list(k2,v2)表示有一个或多个键值对组成的列表MapReduce编程Reduce端-reduce:(k2,list(v2)list(k3,v3)输入：由map输出的一组键值对list(k2,v2)将被进行合并处理，同样主键下的不同数值合并会到一个list(v2)中，故reduce的输入为(k

8、2,list(v2)。处理：对传入的中间结果列表数据进行某种整理或进一步的处理，并产生最终的某种形式的结果输出list(k3,v3)。输出：最终输出结果list(k3,v3)。MapReduce编程基于Map和Reduce的并行计算模型-各个map函数对所划分的数据并行处理，从不同的输入数据产生不同的中间结果输出；各个reduce各自并行计算，各自负责处理不同的中间结果数据集合；进行reduce处理之前，须等到所有的map函数做完，并且在进入reduce前会对map的中间结果数据进行整理(Shuffle)，保证将map的结果发送给对应的reduce；最终汇总所有reduce的输出结果即可获得最

9、终结果。函数函数输入输入输出输出Map(k1,v1)List(k2,v2)Reduce(k2,List(v2)List(k3,v3)牢记：Part 3MapReduce执行-MapReduce执行MapReduce的体系结构的体系结构 MapReduce框架是由一个单独运行在主节点上的JobTracker 和运行在每个集群从节点上的TaskTracker共同组成的。主节点负责调度构成一个作业的所有任务，这些任务分布在不同的从节点上。主节点监控它们的执行情况，并且重新执行之前失败的任务；MapReduce执行Part 3MapReduce实例MapReduce实例单词统计 WordCount-问

10、题描述：统计文本中所出现单词的次数 解决思路：需符合Map、Reduce各自的输入、输出格式。Map端：输入为(k1,v1),以文本行号为k1，以行内容为v1 输出为list(k2,v2)，每有一个单词就输出一个(word,1)Reduce端：输入为(k2,list(v2)，将list(v2)中所有数字相加即可得到单词次数 输出为list(k3,v3)，即最终的结果：(单词,单词次数)MapReduce实例单词统计 WordCount-Map的执行MapReduce实例单词统计 WordCount Java版-Map函数MapReduce实例单词统计 WordCount-Reduce的执行Ma

11、pReduce实例单词统计 WordCount Java版-Reduce函数MapReduce实例单词统计 WordCount Python版-Mapper.py 文件MapReduce实例单词统计 WordCount Python版-Reducer.py 文件MapReduce实例最高气象温度-问题描述：Hadoop权威指南中的例子，给出气象站历年每天的数据，要提取出每年的最高气温。数据示例：0067011990999991950051507004.99999N9+00221+99999 解决思路：Map端：输入为(k1,v1):(行号，内容)输出为list(k2,v2):(年份，温度)，例

12、如(1950,22)Reduce端：输入为(k2,list(v2):如(1950,22,-11)，对list(v2)排序可得到高气温 输出为list(k3,v3)，即最终的结果：(年份,最高气温)MapReduce实例单词统计 WordCount Java版-Map函数MapReduce实例单词统计 WordCount Java版-Reduce函数MapReduce实例文档倒排索引算法-算法描述：Inverted Index(倒排索引)是目前几乎所有支持全文检索的搜索引擎都要依赖的一个数据结构。基于索引结构，给出一个词(term)，能取得含有这个term的文档列表(the list of do

13、cuments)。解决思路：还是从Map、Reduce的输入输出着手。MapReduce实例文档倒排索引算法-搜索：fish doc1,doc2red doc2,doc3red fish doc2doc1：one fish two fishdoc2：red fishblue fishdoc3：one red bird倒排索引：one:doc1,doc3fish:doc1,doc2two:doc1red:doc2,doc3blue:doc2bird:doc3Map：输入(文档名+行号,内容);输出list(单词,文档名)Reduce:输出(单词,list(文档名);输出list(单词,文档列表)

14、MapReduce实例文档倒排索引算法-Map端-MapReduce实例文档倒排索引算法 Reduce端-MapReduce实例MapReduce改进-Combiner-如单词统计问题，若有1亿个单词，那么就会传输1亿个键值对。合理的使用Combiner可以减少键值对的网络传输。减少数据网络传输也就意味着提升效率。Combiner发生在Map输出时，通常与Reduce有相同的实现。Combiner一般适用于求和，求最大/最小的实例中。map:(K1,V1)list(K2,V2)combine:(K2,list(V2)list(K3,V3)reduce:(K3,list(V3)list(K4,V4)Others其 他谷歌放弃MapReduce?微博吐槽：Google将自己弃用的技术分享给别人，让别人纠结于MapReduce的各种问题，然后Google就可以继续保持领先地位.但这其实也不阻碍我们学习MapReduce，MapReduce仍是主流，因为MapReduce是开源的，而Cloud DataFlow则是商业收费的。38遇到的问题遇到的问题Thanks.