Google三大核心技术之一

Google三大核心技术之一:MapReduce来源：CSDN作者：张凌云译发表于：2008-10-02Google的三大核心技术MapReduce、GFS和BigTable的论文之一，MapReduce的中文翻译版，译者是牛人，翻译质量很高，值得细读。MapReduce:超大机群上的简单数据处理摘要MapReduce是一个编程模型,和处理,产生大数据集的相关实现.用户指定一个map函数处理一个key/value对,从而产生中间的key/value对集.然后再指定一个reduce函数合并所有的具有相同中间key的中间value.下面将列举许多可以用这个模型来表示的现实世界的工作.以这种方式写的程序能自动的在大规模的普通机器上实现并行化.这个运行时系统关心这些细节:分割输入数据,在机群上的调度,机器的错误处理,管理机器之间必要的通信.这样就可以让那些没有并行分布式处理系统经验的程序员利用大量分布式系统的资源.我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的机群上,一个典型的MapReduce计算处理几千台机器上的以TB计算的数据.程序员发现这个系统非常好用:已经实现了数以百计的MapReduce程序,每天在Google的机群上都有1000多个MapReduce程序在执行.1.介绍在过去的5年里,作者和Google的许多人已经实现了数以百计的为专门目的而写的计算来处理大量的原始数据,比如,爬行的文档,Web请求日志,等等.为了计算各种类型的派生数据,比如,倒排索引,Web文档的图结构的各种表示,每个主机上爬行的页面数量的概要,每天被请求数量最多的集合,等等.很多这样的计算在概念上很容易理解.然而,输入的数据量很大,并且只有计算被分布在成百上千的机器上才能在可以接受的时间内完成.怎样并行计算,分发数据,处理错误,所有这些问题综合在一起,使得原本很简介的计算,因为要大量的复杂代码来处理这些问题,而变得让人难以处理.作为对这个复杂性的回应,我们设计一个新的抽象模型,它让我们表示我们将要执行的简单计算,而隐藏并行化,容错,数据分布,负载均衡的那些杂乱的细节,在一个库里.我们的抽象模型的灵感来自Lisp和许多其他函数语言的map和reduce的原始表示.我们认识到我们的许多计算都包含这样的操作:在我们输入数据的逻辑记录上应用map操作,来计算出一个中间key/value对集,在所有具有相同key的value上应用reduce操作,来适当的合并派生的数据.功能模型的使用,再结合用户指定的map和reduce操作,让我们可以非常容易的实现大规模并行化计算,和使用再次执行作为初级机制来实现容错.这个工作的主要贡献是通过简单有力的接口来实现自动的并行化和大规模分布式计算,结合这个接口的实现来在大量普通的PC机上实现高性能计算.第二部分描述基本的编程模型,并且给一些例子.第三部分描述符合我们的基于集群的计算环境的MapReduce的接口的实现.第四部分描述我们觉得编程模型中一些有用的技巧.第五部分对于各种不同的任务,测量我们实现的性能.第六部分探究在Google内部使用MapReduce作为基础来重写我们的索引系统产品.第七部分讨论相关的,和未来的工作.2.编程模型计算利用一个输入key/value对集,来产生一个输出key/value对集.MapReduce库的用户用两个函数表达这个计算:map和reduce.用户自定义的map函数,接受一个输入对,然后产生一个中间key/value对集.MapReduce库把所有具有相同中间keyI的中间value聚合在一起,然后把它们传递给reduce函数.用户自定义的reduce函数,接受一个中间keyI和相关的一个value集.它合并这些value,形成一个比较小的value集.一般的,每次reduce调用只产生0或1个输出value.通过一个迭代器把中间value提供给用户自定义的reduce函数.这样可以使我们根据内存来控制value列表的大小.2.1实例考虑这个问题:计算在一个大的文档集合中每个词出现的次数.用户将写和下面类似的伪代码:map(Stringkey,Stringvalue)://key:文档的名字//value:文档的内容foreachwordwinvalue:EmitIntermediate(w,1);reduce(Stringkey,Iteratorvalues)://key:一个词//values:一个计数列表intresult=0;foreachvinvalues:result+=ParseInt(v);Emit(AsString(resut));map函数产生每个词和这个词的出现次数(在这个简单的例子里就是1).reduce函数把产生的每一个特定的词的计数加在一起.另外,用户用输入输出文件的名字和可选的调节参数来填充一个mapreduce规范对象.用户然后调用MapReduce函数,并把规范对象传递给它.用户的代码和MapReduce库链接在一起(用C++实现).附录A包含这个实例的全部文本.2.2类型即使前面的伪代码写成了字符串输入和输出的term格式,但是概念上用户写的map和reduce函数有关联的类型:map(k1,v1)-list(k2,v2)reduce(k2,list(v2))-list(v2)例如,输入的key,value和输出的key,value的域不同.此外,中间key,value和输出key,values的域相同.我们的C++实现传递字符串来和用户自定义的函数交互,并把它留给用户的代码,来在字符串和适当的类型间进行转换.2.3更多实例这里有一些让人感兴趣的简单程序,可以容易的用MapReduce计算来表示.分布式的Grep(UNIX工具程序,可做文件内的字符串查找):如果输入行匹配给定的样式,map函数就输出这一行.reduce函数就是把中间数据复制到输出.计算URL访问频率:map函数处理web页面请求的记录,输出(URL,1).reduce函数把相同URL的value都加起来,产生一个(URL,记录总数)的对.倒转网络链接图:map函数为每个链接输出(目标,源)对,一个URL叫做目标,包含这个URL的页面叫做源.reduce函数根据给定的相关目标URLs连接所有的源URLs形成一个列表,产生(目标,源列表)对.每个主机的术语向量:一个术语向量用一个(词,频率)列表来概述出现在一个文档或一个文档集中的最重要的一些词.map函数为每一个输入文档产生一个(主机名,术语向量)对(主机名来自文档的URL).reduce函数接收给定主机的所有文档的术语向量.它把这些术语向量加在一起,丢弃低频的术语,然后产生一个最终的(主机名,术语向量)对.倒排索引:map函数分析每个文档,然后产生一个(词,文档号)对的序列.reduce函数接受一个给定词的所有对,排序相应的文档IDs,并且产生一个(词,文档ID列表)对.所有的输出对集形成一个简单的倒排索引.它可以简单的增加跟踪词位置的计算.分布式排序:map函数从每个记录提取key,并且产生一个(key,record)对.reduce函数不改变任何的对.这个计算依赖分割工具(在4.1描述)和排序属性(在4.2描述).3实现MapReduce接口可能有许多不同的实现.根据环境进行正确的选择.例如,一个实现对一个共享内存较小的机器是合适的,另外的适合一个大NUMA的多处理器的机器,而有的适合一个更大的网络机器的集合.这部分描述一个在Google广泛使用的计算环境的实现:用交换机连接的普通PC机的大机群.我们的环境是:1.Linux操作系统,双处理器,2-4GB内存的机器.2.普通的网络硬件,每个机器的带宽或者是百兆或者千兆,但是平均小于全部带宽的一半.3.因为一个机群包含成百上千的机器,所有机器会经常出现问题.4.存储用直接连到每个机器上的廉价IDE硬盘.一个从内部文件系统发展起来的分布式文件系统被用来管理存储在这些磁盘上的数据.文件系统用复制的方式在不可靠的硬件上来保证可靠性和有效性.5.用户提交工作给调度系统.每个工作包含一个任务集,每个工作被调度者映射到机群中一个可用的机器集上.3.1执行预览通过自动分割输入数据成一个有M个split的集,map调用被分布到多台机器上.输入的split能够在不同的机器上被并行处理.通过用分割函数分割中间key,来形成R个片(例如,hash(key)modR),reduce调用被分布到多台机器上.分割数量(R)和分割函数由用户来指定.图1显示了我们实现的MapReduce操作的全部流程.当用户的程序调用MapReduce的函数的时候,将发生下面的一系列动作(下面的数字和图1中的数字标签相对应):1.在用户程序里的MapReduce库首先分割输入文件成M个片,每个片的大小一般从16到64MB(用户可以通过可选的参数来控制).然后在机群中开始大量的拷贝程序.2.这些程序拷贝中的一个是master,其他的都是由master分配任务的worker.有M个map任务和R个reduce任务将被分配.管理者分配一个map任务或reduce任务给一个空闲的worker.3.一个被分配了map任务的worker读取相关输入split的内容.它从输入数据中分析出key/value对,然后把key/value对传递给用户自定义的map函数.由map函数产生的中间key/value对被缓存在内存中.4.缓存在内存中的key/value对被周期性的写入到本地磁盘上,通过分割函数把它们写入R个区域.在本地磁盘上的缓存对的位置被传送给master,master负责把这些位置传送给reduceworker.5.当一个reduceworker得到master的位置通知的时候,它使用远程过程调用来从mapworker的磁盘上读取缓存的数据.当reduceworker读取了所有的中间数据后,它通过排序使具有相同key的内容聚合在一起.因为许多不同的key映射到相同的reduce任务,所以排序是必须的.如果中间数据比内存还大,那么还需要一个外部排序.6.reduceworker迭代排过序的中间数据,对于遇到的每一个唯一的中间key,它把key和相关的中间value集传递给用户自定义的reduce函数.reduce函数的输出被添加到这个reduce分割的最终的输出文件中.7.当所有的map和reduce任务都完成了,管理者唤醒用户程序.在这个时候,在用户程序里的MapReduce调用返回到用户代码.在成功完成之后,mapreduce执行的输出存放在R个输出文件中(每一个reduce任务产生一个由用户指定名字的文件).一般,用户不需要合并这R个输出文件成一个文件--他们经常把这些文件当作一个输入传递给其他的MapReduce调用,或者在可以处理多个分割文件的分布式应用中使用他们.3.2master数据结构master保持一些数据结构.它为每一个map和reduce任务存储它们的状态(空闲,工作中,完成),和worker机器(非空闲任务的机器)的标识.master就像一个管道,通过它,中间文件区域的位置从map任务传递到reduce任务.因此,对于每个完成的map任务,master存储由map任务产生的R个中间文件区域的大小和位置.当map任务完成的时候,位置和大小的更新信息被接受.这些信息被逐步增加的传递给那些正在工作的reduce任务.3.3容错因为MapReduce库被设计用来使用成百上千的机器来帮助处理非常大规模的数据,所以这个库必须要能很好的处理机器故障.worker故障master周期性的ping每个worker.如果master在一个确定的时间段内没有收到worker返回的信息,那么它将把这个worker标记成失效.因为每一个由这个失效的worker完成的map任务被重新设置成它初始的空闲状态,所以它可以被安排给其他的worker.同样的,每一个在失败的worker上正在运行的map或