厦门大学-大数据技术原理与应用

大数据技术原理与应用 厦门大学计算机科学系 林子雨 厦门大学计算机科学系 2021 年新版林子雨林子雨厦门大学计算机科学系厦门大学计算机科学系主页：主页：第七章第七章 MapReduce PPT版本号：版本号：2021年年6月第月第1.0版版?大数据技术原理与应用大数据技术原理与应用?温馨提示：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字大数据技术原理与应用 厦门大学计算机科学系 林子雨 提纲7.1 概述概述7.2 MapReduce工作流程工作流程7.3 实例分析：实例分析：WordCount7.4 MapReduce的具体应用的具体应用7.5 MapReduce编程实践编程实践欢送访问?大数据技术原理与应用?教材官方网站：本PPT是如下教材的配套讲义：21世纪高等教育计算机规划教材?大数据技术原理与应用概念、存储、处理、分析与应用?2021年6月第1版厦门大学 林子雨 编著，人民邮电出版社ISBN:978-7-115-39287-9大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.1概述7.1.1分布式并行编程7.1.2MapReduce模型简介7.1.3Map和Reduce函数大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.1.1分布式并行编程“摩尔定律，大约每隔18个月性能翻一番从2005年开始摩尔定律逐渐失效，人们开始借助于分布式并行编程来提高程序性能 分布式程序运行在大规模计算机集群上，集群中包括大量廉价效劳器，可以并行执行大规模数据处理任务，从而获得海量的计算能力谷歌公司最先提出了分布式并行编程模型MapReduce，Hadoop MapReduce是它的开源实现 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.1.2MapReduce模型简介MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数：Map和Reduce在MapReduce中，一个存储在分布式文件系统中的大规模数据集，会被切分成许多独立的小数据块，这些小数据块可以被多个Map任务并行处理MapReduce框架会为每个Map任务输入一个数据子集，Map任务生成的结果会继续作为Reduce任务的输入，最终由Reduce任务输出最后结果，并写入到分布式文件系统中MapReduce设计的一个理念就是“计算向数据靠拢，而不是“数据向计算靠拢，因为，移动数据需要大量的网络传输开销MapReduce框架采用了Master/Slave架构，包括一个Master和假设干个Slave。Master上运行JobTracker，Slave上运行TaskTrackerHadoop框架是用Java实现的，但是，MapReduce应用程序那么不一定要用Java来写 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.1.3Map和Reduce函数函数函数输入入输出出说明明MapList()1.将小数据集进一步解析成一批对，输入Map函数中进行处理2.每一个输入的会输出一批。是计算的中间结果Reduce输入的中间结果中的List(v2)表示是一批属于同一个k2的value表7-1 Map和Reduce大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2MapReduce工作流程7.2.1工作流程概述7.2.2MapReduce各个执行阶段7.2.3Shuffle过程详解大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2.1工作流程概述图7-1 MapReduce工作流程大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2.2MapReduce各个执行阶段图7-2 MapReduce工作流程中的各个执行阶段大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2.3Shuffle过程详解图7-3 Shuffle过程 1.Shuffle过程简介过程简介大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2.3Shuffle过程详解2.Map端的端的Shuffle过程过程图7-4 Map端的Shuffle过程 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.2.3Shuffle过程详解3.Reduce端的端的Shuffle过程过程图7-5 Reduce端的Shuffle过程 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3实例分析：WordCount7.3.1WordCount程序任务7.3.2WordCount设计思路7.3.3MapReduce具体执行过程7.3.4一个WordCount执行过程的实例大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.1WordCount程序任务表7-2 WordCount程序任务程序WordCount输入一个包含大量单词的文本文件输出文件中每个单词及其出现次数（频数），并按照单词字母顺序排序，每个单词和其频数占一行，单词和频数之间有间隔表7-3 一个WordCount的输入和输出实例输入输出Hello WorldHello HadoopHello MapReduceHadoop 1Hello 3MapReduce 1World 1大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.2WordCount设计思路首先，需要检查WordCount程序任务是否可以采用MapReduce来实现其次，确定MapReduce程序的设计思路最后，确定MapReduce程序的执行过程大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.3MapReduce具体执行过程图7-6 WordCount执行过程 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.4一个WordCount执行过程的实例图7-7 Map过程示意图 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.4一个WordCount执行过程的实例图7-8 用户没有定义Combiner时的Reduce过程示意图 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.3.4一个WordCount执行过程的实例图7-9 用户有定义Combiner时的Reduce过程示意图 大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.4MapReduce的具体应用MapReduce可以很好地应用于各种计算问题，这里以关系代数运算、分组与聚合运算、矩阵-向量乘法、矩阵乘法为例，介绍如何采用MapReduce计算模型来实现各种运算7.4.1MapReduce在关系代数运算中的应用7.4.2分组与聚合运算7.4.3矩阵-向量乘法7.4.4矩阵乘法大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用针对数据的很多运算可以很容易地采用数据库查询语言来表示，即使这些查询本身并不在数据库管理系统中执行关系数据库中的关系(relation)可以看做是由一系列属性值组成的表，关系中的行称为元组(tuple)，属性的集合称为关系的模式下面介绍基于MapReduce模型的关系上的标准运算，包括选择、投影、并、交、差以及自然连接大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用对于关系的选择运算，只需要Map过程就能实现，对于关系R中的每个元组t，检测是否是满足条件的元组，如果满足条件，那么输出键值对，也就是说，键和值都是t。这时的Reduce函数就只是一个恒等式，对输入不做任何变换就直接输出1.关系的选择运算关系的选择运算大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用假设对关系R投影后的属性集为S，在Map函数中，对于R中的每个元组t，剔除t中不属于S的字段得到元组 ，输出键值对。对于Map任务产生的每个键，可能存在一个或多个键值对，因此，需要通过Reduce函数来剔除冗余，把属性值完全相同的元组合并起来得到 ,，剔除冗余后只输出一个。2.关系的投影运算关系的投影运算大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用对两个关系求并集时，Map任务将两个关系的元组转换成键值对，Reduce任务那么相当于一个剔除冗余数据的过程(合并到一个文件中)对两个关系求交集时，使用与求并集相同的Map过程，在Reduce过程中，如果键t有两个相同值与它关联，那么输出一个元组，如果与键关联的只有一个值，那么输出空值NULL对两个关系求差时，Map过程产生的键值对，不仅要记录元组的信息，还要记录该元组来自于哪个关系R或S，Reduce过程中按键值相同的t合并后，与键t相关联的值如果只有R说明该元组只属于R，不属于S，就输出元组，其他情况均输出空值3.关系的并、交、差运算关系的并、交、差运算大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用有关系R(A，B)和S(B,C)，将属性B的值分别作为它们的键和元组中其他属性值关联起来使用Map过程，把来自R的每个元组转换成一个键值对b,，其中的键就是属性B的值。注意，这里把关系R包含到值中，这样做使得我们可以在Reduce阶段，只把那些来自R的元组和来自S的元组进行匹配。类似地，使用Map过程，把来自S的每个元组，转换成一个键值对b,所有具有相同B值的元组被发送到同一个Reduce进程中，Reduce进程负责对这些元组进行合并。假设使用k个Reduce进程，这里选择一个哈希函数h，它可以把属性B的值映射到k个哈希桶，每个哈希值对应一个Reduce进程。每个Map进程把键是b 的键值对都发送到与哈希值h(b)对应的Reduce进程Reduce进程的输出那么是连接后的元组，输出被写到一个单独的输出文件中4.关系的自然连接关系的自然连接大数据技术原理与应用 厦门大学计算机科学系 林子雨 在关系代数运算中的应用以某工厂接到的订单与仓库货存为例，演示关系自然连接运算的MapReduce过程4.关系的自然连接关系的自然连接大数据技术原理与应用 厦门大学计算机科学系 林子雨 分组与聚合运算词频计算就是典型的分组聚合运算在Map过程中，选择关系的某一字段也可以是某些属性构成的属性表的值作为键，其他字段的值作为与键相关联的值。在Reduce过程中，对键值相同的键值对的值施加某种聚合运算，如SUM(求和)、COUNT(计数)、AVG(求平均值)、MIN和MAX(求最小最大值)等，输出那么为大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵-向量乘法假定一个n维向量V，其第j个元素记为 ，和一个 的矩阵M，其第i行第j列元素记为 ，矩阵M和向量V的乘积是一个n维向量X，其第i个元素 。矩阵M和向量V各自会在分布式文件系统比方HDFS中存成一个文件。假定我们可以获得矩阵元素的行列下标，例如从矩阵元素在文件中的位置来获得，或者从元素显式存储的三元组中来获得。大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵-向量乘法每个Map任务将整个向量V和矩阵M的一个文件块作为输入。对每个矩阵元素，Map任务会产生键值对。计算所得的n个求和项的键都相同，即都是i。Reduce任务将所有与给定键i关联的值相加即可得到 。大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵-向量乘法如果n的值过大，使向量V无法完全放入内存中，那么，在计算过程中就需要屡次将向量的一局部导入内存，这就会导致大量的磁盘访问一种替代方案是，将矩阵分割成多个宽度相等的垂直条，同时，将向量分割成同样数目的水平条，每个水平条的高度等于矩阵垂直条的宽度矩阵第i个垂直条只和第i个水平条相乘。因此，可以将矩阵的每个条存成一个文件，同样，将向量的每个条存成一个文件。矩阵某个条的一个文件块及对应的完整向量条输送到每个Map任务。然后，Map任务和Reduce任务可以按照前述过程进行大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵乘法矩阵M第i行第j列的元素记为 ，矩阵N中的第j行第k列的元素记为 ，矩阵 ，第i行第k列元素为 。把矩阵看作一个带有三个属性的关系：行下标、列下标和值。因此，矩阵M可以看作关系M(I,J,V)，元组为，矩阵N可以看作关系N(J,K,W)，元组为。矩阵乘法可以看作是一个自然连接运算再加上分组聚合运算。关系M和N根据公共属性J将每个元组连接得到元组，这个五字段元组代表了两个矩阵的元素对，对矩阵元素进行求积运算后可以得到四字段元组，然后可以进行分组聚合运算，其中，I、K是分组属性，的和是聚合结果。综上所述，矩阵乘法可以通过两个MapReduce运算的串联来实现。大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵乘法Map函数：对每个矩阵元素产生一个键值对j,，对每个矩阵元素产生一个键值对j,Reduce函数：对每个相同键j，输出所有满足形式 j,的元组。1.自然连接阶段自然连接阶段大数据技术原理与应用 厦门大学计算机科学系 林子雨 矩阵乘法Map函数：对自然连接阶段产生的键值对 j,.其中每个 是对应的 和 的乘积，Map任务会产生p个键值对,.,。Reduce函数：对每个键，计算与此键关联的所有值的和，结果记为,v，其中，v就是矩阵P的第i行第k列的值。2.分组聚合阶段分组聚合阶段大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5MapReduce编程实践7.5.1任务要求7.5.2编写Map处理逻辑7.5.3编写Reduce处理逻辑7.5.4 编写main方法7.5.5 编译打包代码以及运行程序大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.1 任务要求文件文件A的内容如下：的内容如下：China is my motherlandI love China文件文件B的内容如下：的内容如下：I am from China期望结果期望结果如如右侧所示右侧所示：I 2is 1China 3my 1love 1am 1from 1motherland 1大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.2 编写Map处理逻辑Map输入类型为期望的Map输出类型为Map输入类型最终确定为Map输出类型最终确定为大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.3 编写编写Reduce处理逻辑处理逻辑在Reduce处理数据之前，Map的结果首先通过Shuffle阶段进行整理Reduce阶段的任务：对输入数字序列进行求和Reduce的输入数据为大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.4 编写main方法public static void main(String args)throws Exception Configuration conf=new Configuration();/程序运行时参数 String otherArgs=new GenericOptionsParser(conf,args).getRemainingArgs();if(otherArgs.length!=2)System.err.println(Usage:wordcount );System.exit(2);Job job=new Job(conf,word count);/设置环境参数 job.setJarByClass(WordCount.class);/设置整个程序的类名 job.setMapperClass(MyMapper.class);/添加MyMapper类 job.setReducerClass(MyReducer.class);/添加MyReducer类 job.setOutputKeyClass(Text.class);/设置输出类型 job.setOutputValueClass(IntWritable.class);/设置输出类型 FileInputFormat.addInputPath(job,new Path(otherArgs0);/设置输入文件 FileOutputFormat.setOutputPath(job,new Path(otherArgs1);/设置输出文件 System.exit(job.waitForCompletion(true)?0:1);大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.5 编译打包代码以及运行程序包功能org.apache.hadoop.conf定义了系统参数的配置文件处理方法org.apache.hadoop.fs定义了抽象的文件系统APIorg.apache.hadoop.dfsHadoop分布式文件系统（HDFS）模块的实现org.apache.hadoop.mapredHadoop分布式计算框架MapReduce的实现，包括任务的分发调度等org.apache.hadoop.ipc网络服务端和客户端的工具，封装了网络异步I/O的基础模块org.apache.hadoop.io定义了通用的I/O API，用于针对于网络、数据库、文件等数据对象进行读写操作等大数据技术原理与应用 厦门大学计算机科学系 林子雨 7.5.5 编译打包代码以及运行程序实验步骤实验步骤：使用java编译程序，生成.class文件将.class文件打包为jar包运行jar包查看结果大数据技术原理与应用 厦门大学计算机科学系 林子雨 本章小结本章介绍了MapReduce编程模型的相关知识。MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数：Map和Reduce，并极大地方便了分布式编程工作，编程人员在不会分布式并行编程的情况下，也可以很容易将自己的程序运行在分布式系统上，完成海量数据集的计算MapReduce执行的全过程包括以下几个主要阶段：从分布式文件系统读入数据、执行Map任务输出中间结果、通过 Shuffle阶段把中间结果分区排序整理后发送给Reduce任务、执行Reduce任务得到最终结果并写入分布式文件系统。在这几个阶段中，Shuffle阶段非常关键，必须深刻理解这个阶段的详细执行过程MapReduce具有广泛的应用，比方关系代数运算、分组与聚合运算、矩阵-向量乘法、矩阵乘法等本章最后以一个单词统计程序为实例，详细演示了如何编写MapReduce程序代码以及如何运行程序大数据技术原理与应用 厦门大学计算机科学系 林子雨 主讲教师和助教单位：厦门大学计算机科学系个人网页：数据库实验室网站：主讲教师：林子雨主讲教师：林子雨单位：厦门大学计算机科学系数据库实验室2021级硕士研究生导师：林子雨助教：蔡珉星助教：蔡珉星欢送访问?大数据技术原理与应用概念、存储、处理、分析与应用?教材官方网站：大数据技术原理与应用 厦门大学计算机科学系 林子雨 Department of Computer Science,Xiamen University,June,2021