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