超大集群的简单数据处理

1、 Jeffrey Dean and Sanjay Ghemawat 制作人：郑雅洁制作人：郑雅洁 2015.10.31Jeff Dean，Google的软件架构天才。Google大型并发编程框架Map/Reduce作者。 在Google，公司最顶尖的编程高手Jeff Dean曾发明过一种先进的方法，该方法可以让一个程序员在几分钟内完成以前需要一个团队做几个月的项目。他还发明了一种神奇的计算机语言，可以让程序员同时在上万台机器上用最短的时间完成极为复杂的计算任务。 Jeff Dean于1999年加入Google，目前是Google系统架构小组的成员。他在Google主要负责开发Google的网页

2、抓取、索引、查询服务以及广告系统等，他对搜索质量实现了多次改进，并实现了Google分布式计算架构的多个部分。 在加入Google之前，他工作于 DEC/Compaq的Western实验室，主要从事软件分析工具、微处理器架构以及信息检索等方面的研究。他于1996年在华盛顿大学获得了博士学位，与Craig Chambers一起从事面向对象语言的编译器优化技术方面的研究。在毕业之前，他还在世界卫生组织的艾滋病全球规划署工作过。 What is Map Reduce？ Why do we need Map Reduce？ What is Map Reduce for？什么是Map Reduce？ M

3、apReduce是一个编程模型 概念“Map”和“Reduce”，是他们的主要思想。 微软著名的C+大师Herb Sutter曾经说过：“The Free Lunch Is Over！”。 随着摩尔定律的提前终结，免费的午餐终究还要回去。那个依靠硬件升级来提高程序性能的时代已经一去不复返了，面对这一改变，一次全新的软件开发革命就显得尤为重要。Map Reduce 应时而生！为什么需要为什么需要Map ReduceMap Reduce？ 在Google，MapReduce用在非常广泛的应用程序中，包括“分布grep，分布排序，web连接图反转，每台机器的词矢量，web访问日志分析，反向索引构建，

4、文档聚类,机器学习，基于统计的机器翻译.”值得注意的是，MapReduce实现以后，它被用来重新生成Google的整个索引，并取代老的ad hoc程序去更新索引。Map Reduce 的用途 简单理解，它主要是两个过程： map过程，负责把一个庞大的任务，细分成为一个小任务，然后分配到不同的服务器上运行。 reduce过程，则是负责把已经细分的任务的计算结果，重新合并成为想要的完整结果。Map Reduce 的编程模型Example:计算一个大的文档集合中每个单词出现的次数map(String key, String value):/ key: document name/ value: do

5、cument contentsfor each word w in value:EmitIntermediate(w, “1);比如我们有篇文档，内容是 “I am a programmer, you are also a programmer”。经过Map运算后输出的中间文件将会是：(I,1) ,(am,1) ,(a,1) ,(programmer,1) ,(you,1) ,(are,1) ,(also,1) ,(a,1),(programmer,1).Reduce操作的输入是单词和出现次数的序列。用上面的例子 (”I”, 1), (”am”, 1), (”programmer”, 1,1)

6、, (”are”, 1), (”a”, 1,1) 等。然后根据每个单词，算出总的出现次数。reduce(String key, Iterator values): / key: a word / values: a list of counts int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result);最后输出的最终结果就会是：(”I”, 1), (”a”, 2)Map Reduce 的实现 MapReduce模型可以有多种不同的实现方式。如何正确选择取决于具体的环境。 Google内部

7、广泛使用的运算环境的实现：1.x86架构、运行Linux操作系统、双处理器、2-4GB内存的机器。2.普通的网络硬件设备，每个机器的带宽为百兆或者千兆。3.集群中包含成百上千的机器。4.存储为廉价的内置IDE硬盘。5.用户提交工作（job）给调度系统。每个工作（job）都包含一系列的任务（task），调度系统将这些任务调度到集群中多台可用的机器上。Google MapReduce ArchitectureSingle Master nodeMany worker beesMany worker beesMapReduce OperationInitial data splitinto 64MB

8、 blocksComputed, resultslocally storedM sends datalocation to R workersFinal output writtenMaster informed ofresult locations storage location source file ：GFS Map ：local-storage Reduce ：GFS journal ：GFSGFS 也就是 google File System，google公司为了存储海量搜索数据而设计的专用文件系统。Master的数据结构它存储每一个Map和Reduce任务的状态，以及Worker

9、机器(非空闲任务的机器)的标识。 Master就像一个数据管道，中间文件存储区域的位置信息通过这个管道从Map传递到Reduce。 容错处理 必要性：MapReduce库的设计初衷是使用由成百上千的机器组成的集群来处理超大规模的数据，所以，这个库必须要能很好的处理机器故障。两种主要故障Worker FailureMaster Failure master周期性的ping每个worker。如果在一个约定的时间范围内没有收到worker返回的信息，master将把这worker标记为失效。重新执行该节点上正在执行或尚未执行的Map任务重新执行该节点上尚未完成的Reduce任务让master周期性的

10、将上面描述的数据结构写入磁盘，即检查点（checkpoint）。中止MapReduce运算，从检查点恢复。Task Granularity 任务粒度 在之前的执行概括中，我们把Map拆分成了M个片段、把Reduce拆分成R个片段。理想情况下，M和R应当比集群中worker的机器数量要多得多。在每台worker机器都执行大量的不同任务能够提高集群的动态的负载均衡能力，并且能够加快故障恢复的速度。 但是实际上，在我们的具体实现中对M和R的取值都有一定的客观限制，因为master必须执行O(M+R)次调度，并且在内存中保存O(M*R)个状态。 我们把R值设置为我们想使用的worker机器数量的倍数。

11、我们通常会用这样的比例来执行MapReduce：M=200000，R=5000，使用2000台worker机器。 Backup Tasks备用任务进程机制类似于木桶效应中的短板，影响一个MapReduce的总执行时间最通常的因素是“Straggler”。 由于其他任务占用资源 磁盘损坏解决办法：当一个MapReduce操作接近完成的时候，master调度多个backup tasks去完成尚未完成的任务。 谁先完成，就算谁的显著提高执行效率 Locality本地化策略Master调度策略向GFS询问获得输入文件blocks副本的位置信息 Map Tasks的输入数据通常按64MB的大小划分（GF

12、S的block大小） 尽量将一个Map任务调度在包含相关输入数据拷贝的机器上执行效果 大部分机器从本地读取输入文件，节省大量带宽Refinements技巧Partitioning Function分区函数MapReduce的使用者通常会指定Reduce任务和Reduce任务输出文件的数量（R）。我们在中间key上使用分区函数来对数据进行分区，之后再输入到后续任务执行进程。 一个缺省的分区函数是使用hash方法(比如，hash(key) mod R)进行分区。 扩展：使用“hash(Hostname(urlkey) mod R”作为分区函数就可以把所有来自同一个主机的URLs保存在同一个输出文件

13、中。Refinements技巧Ordering Guarantees顺序保证我们确保在给定的分区中，中间key/value pair数据的处理顺序是按照key值增量顺序处理的。 这样的顺序保证对每个分区生成一个有序的输出文件 这对于需要对输出文件按key值随机存取的应用非常有意义 对在排序输出的数据集也很有帮助 Refinements技巧 Combiner 函数在某些情况下，Map函数产生的中间key值的重复数据会占很大的比重，并且，用户自定义的Reduce函数满足结合律和交换律。我们允许用户指定一个可选的combiner函数，combiner函数首先在本地将这些记录进行一次合并，然后将合并的结果发送给Reducer。 Combiner函数在每台执行Map任务的机器上都会被执行一次 Combiner函数和Reduce函数之间唯一的区别是Reduce函数的输出被保存在最终的输出文件里，而Combiner函数的输出被写到中间文件里部分的合并中间结果可以显著的提