Jeffrey Dean and Sanjay Ghemawat [email protected], [email protected]
Google, Inc.
OSDI '04: 6th Symposium on Operating Systems Design and Implementation — USENIX Association
MapReduce 是一种用于处理与生成大规模数据集的编程模型及其相关实现。用户指定一个 map 函数，用于处理 key/value 对并生成一组中间 key/value 对；以及一个 reduce 函数，用于合并与同一中间 key 关联的所有中间 value。如本文所示，许多现实任务都可以用该模型表达。
以这种函数式风格编写的程序会被自动并行化，并在由大量商用机构成的大规模集群上执行。运行时系统负责：对输入数据分区、在多台机器上调度程序执行、处理机器故障以及管理所需的机器间通信。这样，没有并行与分布式系统经验的程序员也能轻松利用大规模分布式系统的资源。
我们的 MapReduce 实现运行在由大量商用机构成的大规模集群上，并具有很好的可扩展性：典型的 MapReduce 计算会在数千台机器上处理数 TB 级数据。程序员认为该系统易于使用：已有数百个 MapReduce 程序被实现，每天在 Google 的集群上执行的 MapReduce 作业超过一千个。
在过去五年中，本文作者与 Google 的许多其他人实现了数百种专用计算，用于处理大量原始数据（如爬取的文档、Web 请求日志等），并生成各类派生数据（如倒排 index、Web 文档图结构的多种表示、按 host 爬取页面数汇总、某日最常见查询集合等）。这类计算在概念上大多很直接，但输入数据通常很大，计算不得不分布在数百或数千台机器上才能在合理时间内完成。如何并行化计算、如何分布数据、如何应对故障等问题交织在一起，用大量处理这些问题的复杂代码掩盖了原本简单的计算逻辑。
针对这种复杂性，我们设计了一种新的抽象：既能表达我们想要执行的简单计算，又把并行化、容错、数据分布与负载均衡等繁琐细节隐藏在库中。该抽象受到 Lisp 及许多其他函数式语言中 map 与 reduce 原语的启发。我们意识到，我们的大多数计算都对输入中的每条逻辑「record」施加一次 map 操作，得到一组中间 key/value 对，再对共享同一 key 的所有 value 施加一次 reduce 操作，以恰当方式合并派生数据。采用由用户指定 map 与 reduce 操作的函数式模型，使我们能轻松并行化大规模计算，并以重新执行作为容错的主要机制。
本工作的主要贡献是：一个简单而强大的接口，能够自动并行化与分布大规模计算；以及该接口的一种实现，在由大量商用 PC 构成的大规模集群上达到高性能。