Papers
MapReduce: Simplified Data Processing on Large Clusters
Jeffrey Dean, Sanjay Ghemawat · USENIX Symposium on Operating Systems Design and Implementation (OSDI) 2004, 2004
The problem: simple computations hidden under parallelization code
Dean and Ghemawat start from an everyday observation at Google: over about five years, they and other engineers had written hundreds of special-purpose programs to process large volumes of raw data, such as crawled documents and request logs, and to produce derived data, such as inverted indexes, representations of the web graph, and counts of pages per host. Conceptually, each computation was simple. The problem is that the data was so large that the execution had to be distributed across hundreds or thousands of machines to finish in a reasonable time. Dealing with how to parallelize, distribute the data, and handle failures ended up obscuring the original logic, which was buried in a lot of complex code. The authors' answer was to create an abstraction that lets you express the desired computation and hides the details of parallelization, fault tolerance, data distribution, and load balancing in a library. The inspiration comes from the map and reduce primitives of Lisp and other functional languages. The idea is that most computations apply a map operation to each logical record of the input, generating intermediate key/value pairs, and then a reduce operation to all the values that share the same key. With this model, re-execution becomes the main fault-tolerance mechanism.
The programming model: map, reduce, and the word count example
The user writes only two functions. Map takes an input key/value pair and produces a set of intermediate key/value pairs. The library then groups together all intermediate values that have the same intermediate key and hands them to the Reduce function, which merges those values into a possibly smaller set, usually zero or one output value per call. The values reach reduce through an iterator, which makes it possible to handle lists too large to fit in memory. In terms of types, map transforms (k1, v1) into a list of (k2, v2), and reduce transforms (k2, list of v2) into a list of v2. The classic example is counting the occurrences of each word in a large collection of documents: map walks through each document's contents and emits each word paired with the value 1, and reduce sums all the values emitted for a given word. The paper shows other simple uses that fit the same mold: distributed grep, URL access frequency counting, reverse web-link graph, term vector per host, inverted index, and distributed sort. Besides the two functions, the user fills in a specification object with input and output file names and optional parameters.
The execution: splits, master, intermediate files, and the role of GFS
The described implementation was built for Google's environment: large clusters of commodity PCs connected by Ethernet, with cheap IDE disks, where machine failures are frequent and files live in a proprietary distributed file system (GFS) that uses replication. The library splits the input into M pieces (splits), typically 16 to 64 MB, and starts many copies of the program on the cluster. One of them is the master, which assigns tasks to the others, the workers, picking idle workers for map or reduce tasks. A map worker reads its split, applies the user's function and keeps the intermediate pairs in memory, periodically writing them to local disk, partitioned into R regions by a partitioning function, by default something like hash(key) mod R. The master forwards the locations of this data to the reduce workers, which read it remotely via RPC from the map machines' disks and sort it by key, using external sorting if it does not fit in memory. Each reduce worker iterates over the sorted data, calls the user's function for each key and appends the result to an output file. The final result is R output files, one per reduce task. To save network bandwidth, the master tries to schedule map tasks on machines that already hold a replica of the input block, or near them.
Fault tolerance, stragglers, and backup tasks
The master periodically checks each worker. If a worker does not respond for a certain time, it is marked as failed. Map tasks it had already completed go back to the initial state and are re-executed, because their output was on the local disk of the machine that is now inaccessible. Completed reduce tasks do not need to be redone, because their output is already in the global file system. Tasks in progress on the failed worker also become eligible for scheduling again. In one reported case, network maintenance took down groups of 80 machines for several minutes, and the master simply re-executed the work and completed the operation. The semantics rely on atomic commits: each task writes to temporary files, and the reduce atomically renames its temporary file to the final one, so that, if map and reduce are deterministic, the result is the same as that of a sequential execution without failures. Because there is a single master, the described implementation aborts the computation if it fails, and the client can try again. Another problem is the straggler, a machine that takes a very long time to finish one of the last tasks. Near the end of the operation, the master launches backup executions of the remaining tasks, and whichever finishes first counts. The authors say this usually increases resource usage by at most a few percent. In the sort benchmark, turning this mechanism off increased the total time by 44%.
Refinements, measured results, and real use at Google
Beyond the core, the paper describes useful extensions. A combiner function does a partial merge of the data on each map machine before sending it over the network, which helps when there is a lot of key repetition, as in word counting. You can define your own partitioning function, for example so that all URLs from the same host end up in the same output file. Within each partition, pairs are processed in increasing key order. An optional mode lets you skip records that cause deterministic failures, and there is also local execution for debugging, status pages and counters. In the experiments, on a cluster of about 1800 machines, a grep over 10^10 records of 100 bytes finished in about 150 seconds, including about a minute of startup overhead. The sort of the same volume, about 1 TB, took 891 seconds, and with 200 worker processes deliberately killed it took 933 seconds, only 5% more. As for usage, the authors report that the first version of the library was written in February 2003 and that the number of MapReduce programs in Google's source code grew from zero to almost 900 by September 2004. In August 2004, a sample recorded 29,423 jobs, with an average time of 634 seconds. The uses cited include machine learning, clustering for Google News and Froogle, reports of popular queries and graph computations.
See the ideas at work
Practice the designs that use this paper in the System Design school.