MapReduce: Simplified Data Processing on Large Clusters

The problem it addresses

Large data sets do not fit comfortably on a single machine, and spreading a computation over many machines forces the programmer to deal with a set of concerns that have nothing to do with the calculation itself: how to split the input, how to hand out pieces of work, how to move data between machines, and what to do when one of them stops responding. The paper's abstract describes a typical MapReduce computation as processing many terabytes of data on thousands of machines ^[1]. At that scale, this bookkeeping is no longer a detail; it is most of the work.

The programming model

MapReduce is defined as a programming model together with an associated implementation for processing and generating large data sets ^[1][2]. The model has two user-supplied functions. The map function processes a key/value pair and generates intermediate key/value pairs. The reduce function merges all the intermediate values associated with the same intermediate key ^[1]. Nothing else is the user's responsibility.

A small illustration: to count how often each word appears in a large collection of documents, the map function emits the pair (word, 1) for every word it encounters, and the reduce function adds up the ones it receives for each word. The reader writes those two short functions; the framework supplies the parallelism.

What the run-time system does

Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines ^[1]. The run-time system handles partitioning of the data, scheduling of the work, machine failures and inter-machine communication ^[1]. Because failures are absorbed by the system rather than by the application code, the same program is not rewritten when the cluster grows.

Evidence from Google's use

The abstract reports that hundreds of MapReduce programs had been implemented, and that upwards of one thousand MapReduce jobs were executed on Google's clusters every day ^[1]. These numbers carry much of the paper's argument: the model was not a proposal for future use but something already running as part of daily work.

Publication

Jeffrey Dean and Sanjay Ghemawat of Google published "MapReduce: Simplified Data Processing on Large Clusters" at OSDI '04, the Sixth Symposium on Operating System Design and Implementation, held in San Francisco in 2004, at pages 137-150 ^[1]. The USENIX proceedings list the same two authors, affiliated with Google, Inc., and the same page range ^[2].

Why it matters, and what followed

The lasting idea is the separation between what to compute and how to spread it out. A programmer describes only the per-record transformation and the per-key aggregation; partitioning, scheduling, failure handling and communication are pushed into the run-time system ^[1]. Work that previously required careful hand-built distributed code could therefore be expressed in two ordinary functions.

The name itself changed status. MapReduce originally referred to the proprietary Google technology and has since become a generic trademark, and a popular open-source implementation is part of Apache Hadoop ^[3]. That move from an internal Google system to a general label for a style of data processing is the clearest sign of how widely the model was taken up.