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