《MapReduce编程简介(PPT-38).ppt》由会员分享，可在线阅读，更多相关《MapReduce编程简介(PPT-38).ppt（38页珍藏版）》请在三一办公上搜索。
1、MapReduce编程简介,报告人：蔡珉星厦大数据库实验室2014-07-12,遇到的问题,目录,Hadoop与MapReduceMapReduce编程MapReduce执行MapReduce实例,Part 1,Hadoop与MapReduce,-,Hadoop简介：Hadoop是一个分布式系统基础架构，由Apache基金会所开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序，并且可以方便的利用集群来提供强大的运算和存储能力。Hadoop设计：Hadoop的框架最核心的设计：HDFS和MapReduce。HDFS为海量的数据提供了存储；MapReduce为存储的数据提供了计算。,Ha
2、doop与MapReduce,-,Hadoop优点：可靠：数据冗余存储，能对失败的节点能重新分布处理；高效：并行处理，可伸缩，能处理PB级数据；成本低：依赖于廉价服务器；运行于Linux平台：Hadoop带有用Java语言编写的框架，适合于Linux；支持多种语言：支持C+，Python等语言。Hadoop与MapReduce的关系：04年Google发表论文介绍了MapReduce，MapReduce是一种编程模型，可用于大规模数据集。Nutch(开源网络搜索项目)使用了MapReduce，后来Nutch项目独立出来，成为Hadoop。Hadoop是一个分布式平台，其组成包括了MapRedu
3、ce。,Hadoop与MapReduce,-,Hadoop与MapReduce,Hadoop体系结构,-,Hadoop与MapReduce,HDFS集群,一个HDFS集群是由一个NameNode和若干个DataNode组成的。其中NameNode作为主服务器，管理文件系统的命名空间和客户端对文件的访问操作；集群中的DataNode管理存储的数据,Part 2,MapReduce编程,MapReduce编程,MapReduce 分布式并行计算模型,-,MapReduce极大的简化了分布式并行开发，隐藏了复杂的分布式开发细节，而将运行于大规模集群上的并行计算过程高度地抽象到两个函数：Map(映射)
4、和Reduce(规约)。,MapReduce编程,MapReduce的编程思想 分而治之,-,MapReduce编程,MapReduce可解决哪些算法问题,-,MapReduce待处理的数据集可以分解成许多小的数据集,而且每一个小数据都可以完全并行地进行处理，因此不能解决不可分拆的计算任务，或者相互间有依赖关系任务，如Fibonacci函数:Fk+2=Fk+Fk+1 MapReduce可解决的基本算法：各种全局数据相关性小、能适当划分数据的计算任务，如分布式排序关系代数操作 如：选择，投影，求交集、并集，连接，成组，聚合矩阵向量相乘、矩阵相乘词频统计(word count)文档倒排索引,Map
5、Reduce编程,MapReduce可解决哪些算法问题,-,可解决的复杂算法：Web搜索引擎 网页爬取、网页排序、搜索算法Web访问日志分析 分析和挖掘用户在Web上的行为数据/文本统计分析 如专利文献引用分析和统计图算法 并行化宽度优先搜索(最短路径问题)机器学习数据挖掘,MapReduce编程,MapReduce的设计思想 借鉴函数式编程,-,函数式设计语言Lisp：函数式程序设计(functional programming)语言Lisp是一种列表处理言(List processing)，是一种应用于人工智能处理的符号式语言Lisp定义了可对列表元素进行整体处理的各种操作 如:(add#
6、(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的
8、输入为(k2,list(v2)。处理：对传入的中间结果列表数据进行某种整理或进一步的处理，并产生最终的某种形式的结果输出list(k3,v3)。输出：最终输出结果list(k3,v3)。,MapReduce编程,基于Map和Reduce的并行计算模型,-,各个map函数对所划分的数据并行处理，从不同的输入数据产生不同的中间结果输出；各个reduce各自并行计算，各自负责处理不同的中间结果数据集合；进行reduce处理之前，须等到所有的map函数做完，并且在进入reduce前会对map的中间结果数据进行整理(Shuffle)，保证将map的结果发送给对应的reduce；最终汇总所有reduce的
9、输出结果即可获得最终结果。,牢记：,Part 3,MapReduce执行,-,MapReduce执行,MapReduce的体系结构,MapReduce框架是由一个单独运行在主节点上的JobTracker 和运行在每个集群从节点上的TaskTracker共同组成的。主节点负责调度构成一个作业的所有任务，这些任务分布在不同的从节点上。主节点监控它们的执行情况，并且重新执行之前失败的任务；,MapReduce执行,Part 3,MapReduce实例,MapReduce实例,单词统计 WordCount,-,问题描述：统计文本中所出现单词的次数解决思路：需符合Map、Reduce各自的输入、输出格式
10、。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的执行,MapReduce实例,单词统计 WordCount Java版,-,
11、Reduce函数,MapReduce实例,单词统计 WordCount Python版,-,Mapper.py 文件,MapReduce实例,单词统计 WordCount Python版,-,Reducer.py 文件,MapReduce实例,最高气象温度,-,问题描述：Hadoop权威指南中的例子，给出气象站历年每天的数据，要提取出每年的最高气温。数据示例：0067011990999991950051507004.99999N9+00221+99999解决思路：Map端：输入为(k1,v1):(行号，内容)输出为list(k2,v2):(年份，温度)，例如(1950,22)Reduce端：输
12、入为(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 documents
13、)。解决思路：还是从Map、Reduce的输入输出着手。,MapReduce实例,文档倒排索引算法,-,搜索：fish doc1,doc2red doc2,doc3red fish doc2,doc1：one fish two fish,doc2：red fishblue fish,doc3：one red bird,倒排索引：one:doc1,doc3fish:doc1,doc2two:doc1red:doc2,doc3blue:doc2bird:doc3,Map：输入(文档名+行号,内容);输出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.,
