Google云计算三大核心技术

Google云计算三大核心技术

Google三大核心技术之一: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库的用户用两个函数表达这个

Google云计算三大核心技术

计算:map和reduce.

用户自定义的map函数,接受一个输入对,然后产生一个中间key/value对集.MapReduce库把所有具有相同中间key I的中间value聚合在一起,然后把它们传递给reduce函数.

用户自定义的reduce函数,接受一个中间key I和相关的一个value集.它合并这些value,形成一个比较小的value集.一般的,每次reduce调用只产生0或1个输出value.通过一 个迭代器把中间value提供给用户自定义的reduce函数.这样可以使我们根据内存来控制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(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更多实例

Google云计算三大核心技术

这里有一些让人感兴趣的简单程序,可以容易的用MapReduce计算来表示.

分布式的Grep(UNIX工具程序, 可做文件内的字符串查找):如果输入行匹配给定的样式,map函数就输出这一行.reduce函数就是把中间数据复制到输出.

计算URL访问频率:map函数处理web页面请求的记录,输出(URL,1 …… 此处隐藏：20284字，全部文档内容请下载后查看。喜欢就下载吧 ……