MapReduce:Simplified Data Processing on large Clusters－翻译版（上）

• 概括

MapReduce既是一种编程模型，也是用来处理和生成大数据集的一种实现。用户指定的map函数操作key/value对以生成中间形式的key/value对；指定的reduce函数把具有相同中间形式key的value合并在一起。许多现实中的任务都可以用这种模型进行表述，在这篇文章中，将看到这方面的任务。
以MapReduce方式进行编写的程序可以自动并行化，运行在大规模集群系统上。运行系统替用户处理输入数据的分割，程序在一系列机器上的调度执行，故障处理，机器间的通讯。这样使得无并行和分布式经验的程序员利用此系统很容易的采用系统资源。
我们的MapReduce实现系统运行在用商用PC搭建的大规模集群系统上。它具有很好的可扩展性，比如可以对数TB的数据在成千上万机器上进行计算。程序员发现系统的可用性很好。在Google，已经有成百上千的基于MapReduce的应用程序。每一天，将有超过1千左右的MapReduce作业运行在Google的集群上。

• 简单介绍

在过去的5年中，本文作者和其余在Google的开发者实现了用来处理大量原始数据（比如被抓取的文档，Web请求日志，等等）的各种特殊目的计算。比如反向索引，web文档图形结构的表示，基于每台主机被抓取页面数量的统计，在指定一天中最经常使用的查询，等等。大部分计算从原理上讲是很简单的。但是随着输入数据的加大，这些计算不得不分发在成百上千台计算机上进行计算，以便计算任务在一个可接受的时间限度内完成。这时本来很简单的应用程序不得不处理并行计算，分发数据，处理故障等问题而导致其变得晦涩难懂。
为了应付这种复杂性，我们设计了一种新的抽象。它可以使得用户表达自己的简单计算，而把并行化，容错，数据分发和负载平衡的细节全部隐藏在库中。此抽象的 灵感来自于Lisp和其它函数语言中的map和reduce操作。我们意识到大部分的计算都包括：对输入中的逻辑“记录”进行map操作，以获得一系列的 中间形式的key/value对；对共享同一key的中间值进行reduce操作，以并其合并。用户提供map和reduce操作，然后运用此函数模型， 可以使得我们非常容易进行大规模的并行计算，通过重新执行的方式来达到容错的目的。
这项工作最主要的贡献是提供了一个简单且强大的接口，通过这个接口实现，使得大规模计算得到自动并行与分布，在大规模集群系统上达到高性能。
第2节描述了基本的编程模型，另外给出了Google内部的一些实例；第3节描述了为集群系统量身定制的MapReduce接口实现；第4节阐述了一些对 现存编程接口模型十分有用的改进；第5节提供了基于各种任务，现有实现的性能测试；第6节说明了MapReduce在Google内部的使用，阐述了利用 它对现有索引系统进行重写所获得的一些经验；第7节讨论了相关及将来工作。

• 编程模型

计算是把一系列key/value对当作输入，产生一系列key/value对。使用MapReduce库的用户用Map和Reduce表示计算过程。
用户提供的Map获得输入对，产生一系列的中间形式的key/value对。MapReduce库把中间形式key值为I的所有value集中在一起，然后把它们传给Reduce函数。
用户提供的Reduce函数，接受中间形式key值I和与它关联的一系列value，然后把这些值合并产生一个可能相对较小的value集合。一般来说，每个调用产生0个或1个输出值。中间形式的value是通过迭代器的形式提供给reduce函数。这样使得我们可以处理那些太大而不能一次性载入内存的value。

1. 样例

考虑一个在大量文档中统计每个单词出现次数的问题。用户将会用如下类似的伪代码进行描述。
map(String key,String value):
//key: document name
//value:document contents
for each word w in value:
EmitIntermediate(w,"1");

reduce(String eky,Iterator values):
//key: a word
//values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));

map函数产生一个单词和它出现次数的值（在这个样例中是1）。reduce函数对每个特定单词累加其出现次数。
此外，用户代码提供输入与输出文件名，各种可选的可调整的参数以满足mapreduce specification对象需要。接着把对象传递给MapReduce函数，进行调用。此时，用户代码链接用C++实现的MapReduce库。附录A包含这个样例的完整程序。


2. 类型

尽管前面的伪代码输入输出类型都是字符串，但从理论上说，map和reduce函数在类型处理上具有一定关联性。
map (k1,v1) -> list(k2,v2)
reduce (k2,list(v2)) ->list(v2)
如：输入key/value与输出key/value是处在不同的域，中间的key/value与输出key/value是处在同一域。
我们的C++实现都是把字符串作为函数的输入输出。这就需要用户代码在字符串与其它类型之间进行正确的转换。


3. 更多实例

具体包括：分布grep，URL访问频率统计，web连接图反转，每台机器的词矢量，反向索引，分布排序。

参考：(1) 什么是MapReduce? Google的分布运算开发工具!