mapreduce学习报告

MapReduce学习汇报2MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce起源：Google搜索每一次搜索200+CPU200TB以上数据1010CPU周期0.1秒内响应5¢广告收入From:~bryant/presentations/DISC-FCRC07.ppt3MapReuce汇报合肥工业大学过程优化与智能决策实验室计算问题简单，但求解困难待处理数据量巨大（PB级），只有分布在成百上千个节点上并行计算才能在可接受的时间内完成如何进行并行分布式计算？如何分发待处理数据？如何处理分布式计算中的错误？简单的问题，计算并不简单！4MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce：大规模数据处理处理海量数据（1TB）上百/上千CPU实现并行处理简单地实现以上目的From:分而治之DivideandConquerGoogleMapReduce架构设计师JeffreyDean5MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce示例：单词计数案例：单词记数问题(WordCount)给定一个巨大的文本（如1TB），如何计算单词出现的数目？6MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce示例：单词计数使用MapReduce求解该问题Step1:自动对文本进行分割7MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce示例：单词计数使用MapReduce求解该问题Step2:在分割之后的每一对key,value进行用户定义的Map进行处理，再生成新的key,value对8MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce示例：单词计数使用MapReduce求解该问题Step3:对输出的结果集归拢、排序(系统自动完成）9MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce示例：单词计数使用MapReduce求解该问题Step4:通过Reduce操作生成最后结果10MapReuce汇报合肥工业大学过程优化与智能决策实验室一、术语对照中文Hadoop术语Google术语相关解释作业JobJob用户的每一个计算请求，就称为一个作业。作业服务器JobTrackerMaster用户提交作业的服务器，同时，它还负责各个作业任务的分配，管理所有的任务服务器。任务服务器TaskTrackerWorker任劳任怨的工蜂，负责执行具体的任务。任务TaskTask每一个作业，都需要拆分开了，交由多个服务器来完成，拆分出来的执行单位，就称为任务。备份任务SpeculativeTaskBackupTask每一个任务，都有可能执行失败或者缓慢，为了降低为此付出的代价，系统会未雨绸缪的实现在另外的任务服务器上执行同样一个任务，这就是备份任务。11MapReuce汇报合肥工业大学过程优化与智能决策实验室二、MapReduce的简化理解MapReduce：增加了分布式支持的计算函数.用户只要写好Map()和Reduce()函数,由客户端调用,即可实现分布式计算.函数式编程概念的优点函数是函数式编程的基本单位，函数几乎被用于一切，包括最简单的计算，甚至变量都由计算取代。函数值唯一地由其参数值所确定纯函数式的程序没有变量和副作用变量是不能更改的，所有变量只能被赋值一次不必考虑函数调用顺序函数式程序无需任何修改即可并行执行。不用担心死锁和临界区12MapReuce汇报合肥工业大学过程优化与智能决策实验室MapReduce特性MapReduce程序是设计用来并行计算大规模海量数据的，这需要把工作流分划到大量的机器上去，如果组件(component)之间可以任意的共享数据，那这个模型就无法扩展到大规模集群上去（数百或数千个节点），用来保持节点间数据的同步而产生的通信开销会使得系统在大规模集群上变得不可靠和效率低下所有在MapReduce上的数据元素都是不可变的，这就意味着它们不能够被更新。如果在一个mapping任务中你改变了一个输入键值对，它并不会反馈到输入文件；节点间的通信只在产生新的输出键值对((key,value)pairs)时发生，Hadoop系统会把这些输出传到下一个执行阶段。13MapReuce汇报合肥工业大学过程优化与智能决策实验室三、MR编程模型mapping和reducing函数接收数值（键，值）对mapper可能把一个输入map为0个，1个或100个输出reducer可能计算超过一个的输入列表并生成一个或多个不同的输出14MapReuce汇报合肥工业大学过程优化与智能决策实验室用户只需要实现两个函数接口：map(in_key,in_value)-(out_key,intermediate_valuelist)reduce(out_key,intermediate_valuelist)-out_valuelist输入的key和value的类型和输出的类型可以是不同的15MapReuce汇报合肥工业大学过程优化与智能决策实验室map将数据源中的记录（文本中的行、数据库中条目等）作为map函数中的key*value对例如（filename,line）map()将生成一个或多个中间结果，以及与input相对应的一个outputkey16MapReuce汇报合肥工业大学过程优化与智能决策实验室reducemap操作结束后，所有与某指定outkey相对应的中间结果组合为一个列表（list）。reduce()函数将这些中间结果组合为一个或多个对应于同一outputkey的finalvalue每一个outputkey通常只有一个finalvaluereduce()个数可以为0个或多个17MapReuce汇报合肥工业大学过程优化与智能决策实验室Datastore1Datastorenmap(key1,values...)(key2,values...)(key3,values...)map(key1,values...)(key2,values...)(key3,values...)Inputkey*valuepairsInputkey*valuepairs==Barrier==:Aggregatesintermediatevaluesbyoutputkeyreducereducereducekey1,intermediatevalueskey2,intermediatevalueskey3,intermediatevaluesfinalkey1valuesfinalkey2valuesfinalkey3values...18MapReuce汇报合肥工业大学过程优化与智能决策实验室三、MR执行流程（from:Google三大论文）19MapReuce汇报合肥工业大学过程优化与智能决策实验室后面内容以Hadoop为例阐述20MapReuce汇报合肥工业大学过程优化与智能决策实验室四、MapReduce总体架构MapReduce架构图图片来源：汇报合肥工业大学过程优化与智能决策实验室五、MapReduce的角色客户端(JobClient)通过RPC将Job以及配置参数打包成Jar文件存储到HDFS,并将路径提交到JobTracker;通过返回的JobStatus对象获得执行过程的统计数据来监控并打印到用户控制台。作业服务器(JobTracker)作业服务器是负责管理运行在此框架下所有作业的，它也是为各个作业分配任务的核心。应该把它部署在单独的机器上，简化了负责的同步流程。任务服务器(TaskTracker)每一个作业被拆分成很多的任务，包括Map任务和Reduce任务等，任务是具体执行的基本单元，它们都需要分配到合适任务服务器上去执行，任务服务器一边执行一边向作业服务器汇报各个任务的状态，以此来帮助作业服务器了解作业执行的整体情况，分配新的任务等等。分布式文件系统(Distributedfilesystem)用于存储上述实体运行时共享的job文件（如中间结果文件）。22MapReuce汇报合肥工业大学过程优化与智能决策实验室JobClient\JobTraker\TaskTracker关系图23MapReuce汇报合肥工业大学过程优化与智能决策实验室六、MR详细流程图24MapReuce汇报合肥工业大学过程优化与智能决策实验室InputPhaseMapPhaseSortPhaseCombinePhasePartitionPhaseReducePhaseOutputPhase25MapReuce汇报合肥工业大学过程优化与智能决策实验室Job任务调度26MapReuce汇报合肥工业大学过程优化与智能决策实验室七、MR流程分析27MapReuce汇报合肥工业大学过程优化与智能决策实验室关于ShuffleShuffle过程是MapReduce的核心，也被称为奇迹发生的地方Shuffle描述着数据从maptask输出到reducetask输入的这段过程。28MapReuce汇报合肥工业大学过程优化与智能决策实验室维基百科关于MapReduce过程描述AnotherwaytolookatMapReduceisasa5-stepparallelanddistributedcomputation:(1)PreparetheMap()input–theMapReducesystemdesignatesMapprocessors,assignstheK1inputkeyvalueeachprocessorwouldworkon,andprovidesthatprocessorwithalltheinputdataassociatedwiththatkeyvalue.(2)Runtheuser-providedMap()code–Map()isrunexactlyonceforeachK1keyvalue,generatingoutputorganizedbykeyvaluesK2.(3)ShuffletheMapoutputtotheReduceprocessors–theMapReducesystemdesignatesReduceprocessors,assignstheK2keyvalueeachprocessorwouldworkon,andprovidesthatprocessorwithalltheMap-generateddataassociatedwiththatkeyvalue.(4)Runtheuser-providedReduce()code–Reduce()isrunexactlyonceforeachK2keyvalueproducedbytheMapstep.(5)Producethefinaloutput–theMapReducesystemcollectsalltheReduceoutput,andsortsitbyK2toproducethefinaloutcome.29MapReuce汇报合肥工业大学过程优化与智能决策实验室MAP端假设有8个maptask和3个reducetask30MapReuce汇报合肥工业大学过程优化与智能决策实验室MAP端Input在maptask执行时，它的输入数据来源于HDFS的block，当然在MapReduce概念中，maptask只读取split。Split