Chapter7-厦门大学-林子雨-大数据技术原理与应用-第七章-MapReduce

《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]厦门大学计算机科学系2015年新版林子雨厦门大学计算机科学系E-mail:[e-mail]主页：第七章MapReduce（PPT版本号：2015年6月第1.0版）《大数据技术原理与应用》温馨提示：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]提纲•7.1概述•7.2MapReduce工作流程•7.3实例分析：WordCount•7.4MapReduce的具体应用•7.5MapReduce编程实践欢迎访问《大数据技术原理与应用》教材官方网站：本PPT是如下教材的配套讲义：21世纪高等教育计算机规划教材《大数据技术原理与应用——概念、存储、处理、分析与应用》（2015年6月第1版）厦门大学林子雨编著，人民邮电出版社ISBN:978-7-115-39287-9《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.1概述•7.1.1分布式并行编程•7.1.2MapReduce模型简介•7.1.3Map和Reduce函数《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.1.1分布式并行编程•“摩尔定律”，大约每隔18个月性能翻一番•从2005年开始摩尔定律逐渐失效，人们开始借助于分布式并行编程来提高程序性能•分布式程序运行在大规模计算机集群上，集群中包括大量廉价服务器，可以并行执行大规模数据处理任务，从而获得海量的计算能力•谷歌公司最先提出了分布式并行编程模型MapReduce，HadoopMapReduce是它的开源实现《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.1.2MapReduce模型简介•MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数：Map和Reduce•在MapReduce中，一个存储在分布式文件系统中的大规模数据集，会被切分成许多独立的小数据块，这些小数据块可以被多个Map任务并行处理•MapReduce框架会为每个Map任务输入一个数据子集，Map任务生成的结果会继续作为Reduce任务的输入，最终由Reduce任务输出最后结果，并写入到分布式文件系统中•MapReduce设计的一个理念就是“计算向数据靠拢”，而不是“数据向计算靠拢”，因为，移动数据需要大量的网络传输开销•MapReduce框架采用了Master/Slave架构，包括一个Master和若干个Slave。Master上运行JobTracker，Slave上运行TaskTracker•Hadoop框架是用Java实现的，但是，MapReduce应用程序则不一定要用Java来写《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.1.3Map和Reduce函数函数输入输出说明Mapk1,v1List(k2,v2)1.将小数据集进一步解析成一批key,value对，输入Map函数中进行处理2.每一个输入的k1,v1会输出一批k2,v2。k2,v2是计算的中间结果Reducek2,List(v2)k3,v3输入的中间结果k2,List(v2)中的List(v2)表示是一批属于同一个k2的value表7-1Map和Reduce《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2MapReduce工作流程•7.2.1工作流程概述•7.2.2MapReduce各个执行阶段•7.2.3Shuffle过程详解《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2.1工作流程概述分片0map()分片2map()分片1map()分片3map()分片4map()reduce()reduce()reduce()输出0输出1输出2输入Map任务Reduce任务输出图7-1MapReduce工作流程《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2.2MapReduce各个执行阶段InputFormatSplitSplitSplitRRRRRRMapMapMapShuffleReduceOutputFormat输入key,value中间结果key,value文件文件写入到分布式文件系统（如HDFS）InputFormatSplitSplitSplitRRRRRRMapMapMapShuffleReduceOutputFormat文件文件从分布式文件系统中加载文件从分布式文件系统中加载文件节点1节点2写入到分布式文件系统（如HDFS）最终结果key,value最终结果key,value中间结果key,value输入key,valuekey,value-listkey,value-list图7-2MapReduce工作流程中的各个执行阶段《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2.3Shuffle过程详解输入缓存溢写（分区、排序、合并）数据被Reduce任务取走磁盘文件归并多个分区归并归并输出Reduce任务Map任务其他Map任务其他Reduce任务MapReduce图7-3Shuffle过程1.Shuffle过程简介《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2.3Shuffle过程详解2.Map端的Shuffle过程Map任务缓存12输入数据和执行Map任务写入缓存3溢写（分区、排序、合并）4文件归并图7-4Map端的Shuffle过程《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.2.3Shuffle过程详解3.Reduce端的Shuffle过程缓存Map任务Reduce任务磁盘磁盘文件归并其他Map任务“领取”数据归并数据把数据输入给Reduce任务123其他Reduce任务分区分区其他Reduce任务图7-5Reduce端的Shuffle过程《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3实例分析：WordCount•7.3.1WordCount程序任务•7.3.2WordCount设计思路•7.3.3MapReduce具体执行过程•7.3.4一个WordCount执行过程的实例《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.1WordCount程序任务表7-2WordCount程序任务程序WordCount输入一个包含大量单词的文本文件输出文件中每个单词及其出现次数（频数），并按照单词字母顺序排序，每个单词和其频数占一行，单词和频数之间有间隔表7-3一个WordCount的输入和输出实例输入输出HelloWorldHelloHadoopHelloMapReduceHadoop1Hello3MapReduce1World1《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.2WordCount设计思路•首先，需要检查WordCount程序任务是否可以采用MapReduce来实现•其次，确定MapReduce程序的设计思路•最后，确定MapReduce程序的执行过程《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.3MapReduce具体执行过程输出文件0输出文件1Worker分片0分片1分片2……分片MWorkerWorkerWorkerWorkerMaster用户程序(1)程序部署(1)程序部署(1)程序部署(2)分配Map任务(2)分配Reduce任务(4)本地写数据(5)远程读数据(3)读数据(6)写数据输入文件Map阶段中间文件(位于本地磁盘)Reduce阶段输出文件图7-6WordCount执行过程《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.4一个WordCount执行过程的实例Map输入1.“HelloWorldByeWorld”2.“HelloHadoopByeHadoop”3.“ByeHadoopHelloHadoop”Map输出Hello,1World,1Bye,1World,1Hello,1Hadoop,1Bye,1Hadoop,1Bye,1Hadoop,1Hello,1Hadoop,1MapMapMap图7-7Map过程示意图《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.4一个WordCount执行过程的实例Map输出的结果Hello,1World,1Bye,1World,1Hello,1Hadoop,1Bye,1Hadoop,1Bye,1Hadoop,1Hello,1Hadoop,1Map端Shuffle后的结果发送给Reduce任务Reduce任务的输出Bye,3Hadoop,4Hello,3World,2ShuffleHello,1World,1,1Bye,1Hello,1Hadoop,1,1Bye,1Bye,1Hadoop,1,1Hello,1ShuffleShuffleReduce图7-8用户没有定义Combiner时的Reduce过程示意图《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.3.4一个WordCount执行过程的实例Hello,1World,1Bye,1World,1Hello,1Hadoop,1Bye,1Hadoop,1Bye,1Hadoop,1Hello,1Hadoop,1Hello,1World,2Bye,1Hello,1Hadoop,2Bye,1Bye,1Hadoop,2Hello,1Map输出的结果Map端Shuffle过程中使用Combiner函数后的输出发送给Reduce任务Reduce的输出Bye,3Hadoop,4Hello,3World,2CombineCombineCombineReduce图7-9用户有定义Combiner时的Reduce过程示意图《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.4MapReduce的具体应用•MapReduce可以很好地应用于各种计算问题，这里以关系代数运算、分组与聚合运算、矩阵-向量乘法、矩阵乘法为例，介绍如何采用MapReduce计算模型来实现各种运算•7.4.1MapReduce在关系代数运算中的应用•7.4.2分组与聚合运算•7.4.3矩阵-向量乘法•7.4.4矩阵乘法《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]7.4.1MapReduce在关系代数运算中的应用•针对数据的很多运算可以很容易地采用数据库查询语言来表示，即使这些查询本身并不在数据库管理系统中执行•关系数据库中的关系(relation)可以看做是由一系列属性值组成的表，关系中的行称为元组(tuple)，属性的集合称为关系的模式•