MapReduce: Simplified Data Processing on Large Clusters
📜 Abstract
MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program’s execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google’s clusters every day.
✨ Summary
The paper introduced a restricted map-and-reduce programming model together with a runtime that automated data partitioning, scheduling, fault recovery, communication, data locality, and load balancing across commodity clusters. Its design demonstrated that large-scale data processing could be made accessible through a comparatively simple programming interface while retaining resilience to worker failures and stragglers.
The model subsequently became the conceptual and practical foundation for Hadoop MapReduce, whose framework provides parallel processing of multi-terabyte datasets on commodity clusters, task re-execution, shuffle and sorting, partitioning, counters, and data-local scheduling. (hadoop.apache.org) MapReduce also influenced later distributed data-processing research: subsequent work formalized its computational power and limitations, developed algorithms specifically for MapReduce, and examined extensions for graph processing and other workloads. (research.google) Systems such as Spark addressed important limitations of disk-oriented MapReduce by offering a distributed in-memory execution model while retaining a functional, map/reduce-style programming approach. (research.google) The paper was published as part of OSDI ’04, held December 6–8, 2004, in San Francisco. (usenix.org)