第4讲 MapReduce (1)

软件工程学院安俊秀•Google的云计算由分布式文件系统GoogleFileSystem(GFS)、大规模分布式数据库BigTable、程序设计模式MapReduce、分布式锁机制Chubby等几个相互独立又紧密结合的系统组成，如图所示Google云计算架构。2/204.1Google的云计算基础设施3/20Google的云计算基础设施10.2.2Hadoop的发展•Hadopp是由Apache基金会开发的、分布式系统基础架构，基于Java技术实现了类似Google云计算的开源项目。专注于海量数据存储、处理的分布式系统。4/20MapReduce概述•MapReduce是Google的一项重要技术，它是一个编程模型，用以进行大数据量的计算。•对于大数据量的计算，通常采用的处理手法就是并行计算。•MapReduce就是一种简化并行计算的编程模型，它让那些没有多少并行计算经验的开发人员也可以开发并行应用。•MapReduce的名字源于这个模型中的两项核心操作：Map和Reduce。10.2.4Map/Reduce（分布式计算）•MapReduce模式的思想是通过自动分割将要执行的问题(程序)、拆解成Map(映射)和Reduce(化简)的方式。•在自动分割后通过Map程序将数据映射成不相关的区块，分配(调度)给大量计算机处理达到分散运算的效果，再通过Reduce程序将结果汇整，输出开发者需要的结果。MapReduce处理流程•Map是把一组数据一对一的映射为另外的一组数据，其映射的规则由一个函数来指定，比如对[1,2,3,4]进行乘2的映射就变成了[2,4,6,8]。•Reduce是对一组数据进行归约，这个归约的规则由一个函数指定，比如对[1,2,3,4]进行求和的归约得到结果是10，而对它进行求积的归约结果是24。MapReduce概述MapReduce概述•Map操作是独立的对每个元素进行操作。换句话说，Map操作将产生一组全新的数据，而原来的数据保持不变。因此，它是高度并行的。•Reduce操作虽然不如Map操作并行性那么好，但是它总会得到一个相对简单的结果，大规模运算也相对独立，因此也是比较适合并行的。MapReduce概述•Map是一个分的过程，Reduce则对应着合，这一分一合便在不知不觉中完成了计算。•Reduce操作虽然不如Map操作并行性那么好，但是它总会得到一个相对简单的结果，大规模运算也相对独立，因此也是比较适合并行的。•在Map/Reduce框架中，每一次计算请求，被称为作业。在分布式计算Map/Reduce框架中，为了完成这个作业，它进行两步走的战略，首先是将其拆分成若干个Map任务，分配到不同的机器上去执行，每一个Map任务拿输入文件的一部分作为自己的输入，经过一些计算，生成某种格式的中间文件，这种格式，与最终所需的文件格式完全一致，但是仅仅包含一部分数据。因此，等到所有Map任务完成后，它会进入下一个步骤，用以合并这些中间文件获得最后的输出文件。此时，系统会生成若干个Reduce任务，同样也是分配到不同的机器去执行，它的目标，就是将若干个Map任务生成的中间文件为汇总到最后的输出文件中去。经过如上步骤，最终，作业完成，所需的目标文件生成。整个算法的关键，就在于增加了一个中间文件生成的流程，大大提高了灵活性，使其分布式扩展性得到了保证。Map/Reduce工作步骤一•Map程序从输入流中读取一组“记录”，然后对记录进行需要的过滤或者转换，然后输出一组记录(key,value)。当Map程序生成输出记录时，一个分割方法将记录划分为M个不相交的块并赋予一个键值。这个分割方法一般是一个hash函数，只要这个决定性的函数能够满足就行。当一个块被填充后，它将写入磁盘，Map程序结束的时候每个块都将输出M个文件。用户指定一个Map函数处理一个(key,value)对、从而产生中间的(key,value)对集。Map/Reduce工作步骤二•用户指定一个Reduce函数合并所有的具有相同中间key的中间value。以这种方式写的程序能自动的在大规模的普通机器上实现并行化。这个运行时系统关心这些细节:分割输入数据、在机群上的调度、机器的错误处理、管理机器之间必要的通信。Map/Reduce的适用条件•Map/Reduce并不是万能的，适用于Map/Reduce计算有一个先提条件是：待处理的数据集可以分解成许多小的数据集，而且每一个小数据集都可以完全并行地进行处理。•若不满足以上两条中的任意一条，则不适合使用Map/Reduce模式Map/Reduce在海量数据处理中的优势•I.Map/Reduce这个模型很简单，对于海量数据的处理必须做到简易性和快捷性，否则处理的时间就是漫长的等待。•II.Map/Reduce具有强大的并行处理能力，将一个庞大的数据分布到大规模的集群进行分布式处理，计算时间和处理时间明显要优于本地单一的数据处理。•III.Map/Reduce具有高容错能力和封装好的错误处理，这使得即便在集群中某一个节点出现错误，并不会对整个数据处理有太大的影响。•IV.Map/Reduce就是一个计算函数，对于迁移计算本身就比迁移数据更加快，更合理。Map/Reduce的缺陷•虽然Map/Reduce具有高容错性，对于集群中发生的错误，一般将错误节点中的数据集进行副本拷贝，然后再将副本重新放在另外一个节点中进行处理，但是进行这些处理之前，整个程序或者数据处理都要终止，需要重新进行再次处理。那么这样，不仅影响了程序运行时间，而且集群中节点如果出现大规模的错误，很可能会导致整个系统的崩溃。•当然即便是数据未发生错误，如果在节点中发生数据处理延迟，同样地，进行上述相同的处理，在进行出现延迟节点的数据集进行副本拷贝后，然后再将副本重新放在另外一个节点中进行处理。那么对于这些延迟，也一样会影响整个程序的运行时间，何况Map/Reduce同样有一个心跳处理，用于检测节点是否出现延迟和错误情况，而心跳反馈时间处理同样也是不容忽略的。Map/Reduce的缺陷•假设N个Map实例中的每个实例都将生成M个输出文件。每个输出文件都分发给不同的Reduce实例。这些文件都被写入本地硬盘以备Map实例使用。如果N是1000，M是500，那么在Map阶段将生成500000个本地文件。当Reduce阶段开始，500个Reduce实例必须读取1000个输入文件，必须使用类似FTP的协议将每个输入文件从各个Map实例运行的节点中获取过来。在100秒内所有Reduce实例将同时的运行起来，不可避免的会发生两个或者更多个Reduce实例企图并行的从同一个Map节点中获取输入文件，包括大量的磁盘搜索，当超过因子20时，将极大的降低磁盘的有效传输率。Map/Reduce的缺陷•Map/Recduce仅支持简单操作，对于复杂操作而言，Map/Recduce显得毫无还手之力。这里的简单操作是指简单的加、减、乘、除、数据统计和简单的查询操作等；对于复杂的查询，如多层嵌套的SQl语言，Map/Reduce都不能支持。