摘要

MapReduce是一种用来处理和生成大数据集的编程模型以及相关实现。用户选定一个map函数，该map函数的输入是一个键值对，输出是一系列中间键值对。然后用户选定一个reduce函数，该reduce函数用于处理具有相同键的所有中间键值对，并得到结果。实际生产中，有大量应用可以用此模型描述。

这种编程模型可以在集群上并行工作。运行时系统会自动分割输入数据、分发任务到各个机器、处理任务失败或者机器故障、管理必要的机器间通信。因此，即使没有分布式系统经验的程序员，也可以方便地利用分布式系统的资源。

现在每天有大量MapReduce模型的工程运行于谷歌集群，其具有高度的扩展性，一个典型的MapReduce计算可以利用集群处理TB级别的数据集。

1.介绍

过去数年，大量特殊目的的计算程序被设计出来，用于处理大量的原始数据集，比如爬虫结果、网络请求日志，来得到需要的衍生数据，比如倒排索引、web文档的图结构、某日查询最多的关键词。虽然这类计算在概念上非常直观，但是由于输入数据集非常庞大，因此需要将这些输入数据集切割、分发到多个机器上处理。但是除了原来本有的计算模型外，还需要编写大量复杂的代码去处理并行化计算、数据分发、故障处理等问题。

因此我们干脆设计一种新的抽象，将并行计算、容错、数据分发、负载均衡这些复杂技术细节隐藏起来，交给库去完成，我们只需要定义计算模型即可。这种抽象的灵感来自于Lisp等函数式编程语言中的Map和Reduce原语。我们意识到许多计算都需要对输入的每个记录应用一个"map"操作来得到中间一系列键值对，之后再对所有拥有相同键的值应用"reduce"操作，得到衍生数据集。因此如果一个编程模型，允许我们通过定义map操作和reduce操作，那我们就可以方便设计大量并行计算，并且我们可以使用重新执行作为主要的容错机制。

这次工作的主要贡献是提供一个简单而强大的接口，可以使用这个接口完成自动并行化和大规模分布式计算，并且该接口的实现在大型商用集群上性能卓然。

本文第二章给出基本编程模型以及一些栗子。第三章介绍为集群计算环境量身定做的MapReduce接口。第四章介绍一些对于编程模型的改进。第五章测试了我们的实现在不同任务