google论文3-mapreduce(上)

《google论文3-mapreduce(上)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、【google论文三】MapReduce:简化大集群上的数据处理(上)  2010-10-0215:20:03

2、  分类：搜索与分布式

3、  标签：reduce  task  mapreduce  函数  worker  

4、字号大中小 订阅转载请注明：http://duanple.blog.163.com/blog/static/709717672010923203501/ 作者phylips@bmy      摘要：MapReduce是一个编程模型以及用来处理和生成大数据集的一个相关实现。用户通过描述一个map函数，处理一组key/value对进而生成一组key/value对的中间结果

5、，然后描述一个reduce函数，将具有相同key的中间结果进行归并。正如论文所表明的，很多现实世界中的任务都可以用这个模型来表达。 以这种函数式风格写出来的程序在一个由普通机器组成的集群上自动的进行并行化和执行。由一个运行时系统来关注输入数据的划分细节，在机器集合上的程序执行调度，处理机器失败以及管理所需要的机器间的通信。这就允许那些没有并行分布式系统编程经验的程序员很容易的使用大型分布式系统的资源。 我们的MapReduce实现运行在一个有很多普通机器组成的集群上，而且具有高扩展性：一个典型的MapReduce计算将会在一个数千台机器的集群上处理很多T的数据。对于程序员来说，这个系统

6、很好用，目前已经有数百个MapReduce程序实现，在google的集群上每天有上千个MapReducejob在跑。 1.导引在过去的五年来，作者和google的其他工程师已经实现了数百了用于特殊目的在大量原始数据(比如爬虫爬的文档，web访问日志等等)上进行的运算。为了计算各种类型的衍生数据：比如倒排索引，网页文档的图结构的各种不同表示，每个host的网页数，给定的一天中最常查询集合。大部分这样的计算在概念上都是很直接的。然而由于输入数据通常是很庞大的，因此为了能在合理的时间内结束，计算就不得不分布在成百上千台机器上执行。如何并行化计算，分布数据，处理错误都会使得原本简单的计算需要大

7、量额外的代码去处理这些问题。 为了应对这种复杂性，我们设计了一种抽象，使得我们可以表达我们需要执行的这种简单的运算，而将并行化，容错，数据分布，负载平衡这样的细节封装在库里。我们的抽象源于Lisp以及其他函数式编程语言中的map-reduce原语。我们发现我们大部分的计算都是首先在输入的每条记录上执行一个map操作以产生一个key/value的中间结果集合，然后为了得到相应的派生数据，对那些具有相同key的值应用一个reduce操作。通过使用由用户描述的map和reduce操作组成的函数式模型，使得我们很容易的进行计算并行化，同时使用重新执行作为基本的容错机制。文章的主要贡献就是提供了

8、一个允许对大规模计算进行自动并行化以及数据分布的简单有力的接口。同时提供了一个可以在普通pc机组成的大集群上达到很高的性能针对该接口的实现。第2节描述了基本的编程模型并且给出了几个简单例子。第3节描述了一个面向我们的基于集群的计算环境的该接口的实现。第4节描述了该模型中我们认为很有用的几个概念。第5节对我们的实现通过几个task进行了测试。第6节介绍了MapReduce在google内部的使用，包括使用它重写我们的产品索引系统的一些经验。第7节讨论了相关的以及未来的工作。 2.编程模型计算有一个key/value输入对集合，产生一系列的输出key/value对。Mapreduce库的用

9、户通过两个函数：Map和Reduce来表达这个计算。 Map，由用户编写，有一个输入对，产生一集key/value对的中间结果。Mapreduce库将具有相同key(比如I)的那些中间值组织起来，然后将它们传给Reduce函数。 Reduce函数，也是由用户编写，接受一个中间值key(比如I)，以及对应于该key的value集合作为输入。它将这些value归并起来形成一个可能更小的value集合。通常每个Reduce调用产生0个或者1个输出值。中间值的value集合是通过一个迭代器来提供给用户的Reduce函数。这允许我们能处理那些太大以至于无法一次放入内存的value列表。 2.1例

10、子考虑在一个大文档集合中计算单词出现频率的问题。用户可以用类似如下伪代码的方式来编写代码。map(Stringkey,Stringvalue):      //key:documentname      //value:documentcontents     foreachwordwinvalue:      EmitIntermediate(w,"1"); reduce(Stringkey,Iteratorvalues):      //k