MapReduce 是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一 个 Map 函数处理一个基于 key/value pair 的数据集合，输出中间的基于 key/value pair 的数据集合;然后再创建 一个 Reduce 函数用来合并所有的具有相同中间 key 值的中间 value 值。现实世界中有很多满足上述处理模型 的例子，本论文将详细描述这个模型。
MapReduce 架构的程序能够在大量的普通配置的计算机上实现并行化处理。这个系统在运行时只关心: 如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的错误处理，管理集群中计算机之间 必要的通信。采用 MapReduce 架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分 布式系统的丰富资源。
我们的 MapReduce 实现运行在规模可以灵活调整的由普通机器组成的集群上:一个典型的 MapReduce 计算往往由几千台机器组成、处理以 TB 计算的数据。程序员发现这个系统非常好用:已经实现了数以百计 的 MapReduce 程序，在 Google 的集群上，每天都有 1000 多个 MapReduce 程序在执行。
在过去的 5 年里，包括本文作者在内的 Google 的很多程序员，为了处理海量的原始数据，已经实现了数 以百计的、专用的计算方法。这些计算方法用来处理大量的原始数据，比如，文档抓取(类似网络爬虫的程 序)、Web 请求日志等等;也为了计算处理各种类型的衍生数据，比如倒排索引、Web 文档的图结构的各种表 示形势、每台主机上网络爬虫抓取的页面数量的汇总、每天被请求的最多的查询的集合等等。大多数这样的 数据处理运算在概念上很容易理解。然而由于输入的数据量巨大，因此要想在可接受的时间内完成运算，只 有将这些计算分布在成百上千的主机上。如何处理并行计算、如何分发数据、如何处理错误?所有这些问题 综合在一起，需要大量的代码处理，因此也使得原本简单的运算变得难以处理。
为了解决上述复杂的问题，我们设计一个新的抽象模型，使用这个抽象模型，我们只要表述我们想要执 行的简单运算即可，而不必关心并行计算、容错、数据分布、负载均衡等复杂的细节，这些问题都被封装在 了一个库里面。设计这个抽象模型的灵感来自 Lisp 和许多其他函数式语言的 Map 和 Reduce 的原语。我们意 识到我们大多数的运算都包含这样的操作:在输入数据的“逻辑”记录上应用 Map 操作得出一个中间 key/value pair 集合，然后在所有具有相同 key 值的 value 值上应用 Reduce 操作，从而达到合并中间的数据，得到一个想要的结果的目的。使用 MapReduce 模型，再结合用户实现的 Map 和 Reduce 函数，我们就可以非常容易的 实现大规模并行化计算;通过 MapReduce 模型自带的“再次执行”(re-execution)功能，也提供了初级的容灾实现方案。
这个工作(实现一个 MapReduce 框架模型)的主要贡献是通过简单的接口来实现自动的并行化和大规模
的分布式计算，通过使用 MapReduce 模型接口实现在大量普通的 PC 机上高性能计算。
第二部分描述基本的编程模型和一些使用案例。
第三部分描述了一个经过裁剪的、适合我们的基于集群的计算环境的 MapReduce 实现。
第四部分描述我们认为在 MapReduce 编程模型中一些实用的技巧。
第五部分对于各种不同的任务，测量我们 MapReduce 实现的性能。
第六部分揭示了在 Google 内部如何使用 MapReduce 作为基础重写我们的索引系统产品，包括其它一些 使用 MapReduce 的经验。
第七部分讨论相关的和未来的工作。
MapReduce 编程模型的原理是:利用一个输入 key/value pair 集合来产生一个输出的 key/value pair 集合。 MapReduce 库的用户用两个函数表达这个计算:Map 和 Reduce。
用户自定义的 Map 函数接受一个输入的 key/value pair 值，然后产生一个中间 key/value pair 值的集合。 MapReduce 库把所有具有相同中间 key 值 I 的中间 value 值集合在一起后传递给 reduce 函数。
用户自定义的 Reduce 函数接受一个中间 key 的值 I 和相关的一个 value 值的集合。Reduce 函数合并这些 value 值，形成一个较小的 value 值的集合。一般的，每次 Reduce 函数调用只产生 0 或 1 个输出 value 值。通 常我们通过一个迭代器把中间 value 值提供给 Reduce 函数，这样我们就可以处理无法全部放入内存中的大量 的 value 值的集合。
例子
例如，计算一个大的文档集合中每个单词出现的次数，下面是伪代码段:
`
map(String key, String value):
// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, “1′′);
reduce(String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));
1 |
|
map(k1,v1) ->list(k2,v2)
reduce(k2,list(v2)) ->list(v2)
1 | 比如，输入的 key 和 value 值与输出的 key 和 value 值在类型上推导的域不同。此外，中间 key 和 value 值与输出 key 和 value 值在类型上推导的域相同。 我们的 C++中使用字符串类型作为用户自定义函数的输入输出，用户在自己的代码中对字符串进行适当 的类型转换。 ### 更多的例子 这里还有一些有趣的简单例子，可以很容易的使用 MapReduce 模型来表示: 分布式的 Grep:Map 函数输出匹配某个模式的一行，Reduce 函数是一个恒等函数，即把中间数据复制到 输出。 计算 URL 访问频率:Map 函数处理日志中 web 页面请求的记录，然后输出(URL,1)。Reduce 函数把相同URL 的 value 值都累加起来，产生(URL,记录总数)结果。 倒转网络链接图:Map 函数在源页面(source)中搜索所有的链接目标(target)并输出为(target,source)。Reduce 函数把给定链接目标(target)的链接组合成一个列表，输出(target,list(source))。 |
Counter* uppercase;
uppercase = GetCounter(“uppercase”);
map(String name, String contents):
for each word w in contents:
if (IsCapitalized(w)):
uppercase->Increment();
EmitIntermediate(w, “1′′);
1 | 这些计数器的值周期性的从各个单独的 worker 机器上传递给 maste(r 附加在 ping 的应答包中传递)。master 把执行成功的 Map 和 Reduce 任务的计数器值进行累计，当 MapReduce 操作完成之后，返回给用户代码。 计数器当前的值也会显示在 master 的状态页面上，这样用户就可以看到当前计算的进度。当累加计数器 的值的时候，master 要检查重复运行的 Map 或者 Reduce 任务，避免重复累加(之前提到的备用任务和失效 后重新执行任务这两种情况会导致相同的任务被多次执行)。 有些计数器的值是由 MapReduce 库自动维持的，比如已经处理的输入的 key/value pair 的数量、输出的 key/value pair 的数量等等。 计数器机制对于 MapReduce 操作的完整性检查非常有用。比如，在某些 MapReduce 操作中，用户需要确 保输出的 key value pair 精确的等于输入的 key value pair，或者处理的 German 文档数量在处理的整个文档数 量中属于合理范围。 {% note info %} |