MapReduce：大规模集群上的简化数据处理

要解决的问题

当数据量大到一台机器处理不了时，把计算摊到多台机器上，程序员就得处理一堆与计算本身无关的事情：输入怎么切分、任务怎么分配、机器之间数据怎么传、某台机器中途出故障怎么办。论文摘要把一次典型的 MapReduce 计算描述为在数千台机器上处理许多 TB 的数据^[1]。在这个量级上，这些「杂事」已经不是细节，而是主要负担。

编程模型

MapReduce 被定义为一种编程模型，以及配套的、用于处理和生成大规模数据集的实现^[1][2]。模型只有两个由用户提供的函数。map 函数处理一个键值对（key/value pair），生成若干中间键值对；reduce 函数把同一个中间键对应的所有中间值合并起来^[1]。除此之外都不归用户管。

一个常见的例子是统计一大批文档里每个词出现的次数：map 每看到一个词就输出（词, 1）这样一对，reduce 把同一个词收到的那些 1 加起来。用户写的是这两个很短的函数，并行由框架负责。

运行时系统做了什么

用这种函数式风格写成的程序会被自动并行化，并在由大量廉价机器（commodity machines）组成的大集群上执行^[1]。运行时系统（run-time system）负责数据划分、任务调度、机器故障处理和机器间通信^[1]。故障由系统兜住，而不是由应用代码兜住，因此同一份程序不必因为集群变大而重写。

谷歌内部的使用情况

摘要给出了两个数字：当时已有数百个 MapReduce 程序被实现出来，谷歌的集群上每天执行上千个 MapReduce 作业^[1]。论文的论证很大程度上建立在这组数字上——它描述的不是一个设想，而是已经在承担日常负载的东西。

发表情况

论文由谷歌的 Jeffrey Dean 和 Sanjay Ghemawat 撰写，发表在 2004 年于旧金山举行的第六届操作系统设计与实现研讨会（OSDI '04）上，收录于会议论文集第 137 至 150 页^[1]。USENIX 的会议论文集同样把作者列为谷歌公司的这两位，页码也相同^[2]。

为什么重要，以及后来的影响

留下来的核心想法，是把「算什么」和「怎么摊开算」分开。程序员只描述针对每条记录的处理和按 key 的汇总，数据划分、调度、故障处理和通信统统交给运行时系统^[1]。过去需要手工编写、小心维护的分布式代码，因此可以用两个普通的函数表达出来。

这个名称本身的地位也变了。MapReduce 最初指的是谷歌的专有技术，后来成为一个通用化的商标（generic trademark）；一个流行的开源实现是 Apache Hadoop 的一部分^[3]。从一个谷歌内部系统变成一类数据处理方式的通称，这是该模型被广泛采用的最清楚的迹象。