Beautiful Code

Chapter 23. Distributed Programming with MapReduce

Jeffrey Dean and Sanjay Ghemawat

This chapter describes the design and implementation of mapreduce, a programming system for large-scale data processing problems. MapReduce was developed as a way of simplifying the development of large-scale computations at Google. MapReduce programs are automatically parallelized and executed on a large cluster of commodity machines. The runtime 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 intermachine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.

A Motivating Example

Suppose that you have 20 billion documents, and you want to generate a count of how often each unique word occurs in the documents. With an average document size of 20 KB, just reading through the 400 terabytes of data on one machine will take roughly four months. Assuming we were willing to wait that long and that we had a machine with sufficient memory, the code would be relatively simple. Example 23-1 (all the examples in this chapter are pseudocode) shows a possible algorithm.

Example 23-1. Naïve, nonparallel word count program

map<string, int> word_count;
for each document d {
  for each word w in d {
    word_count[w]++;
  }
 }
... save word_count to persistent storage ...

One way of speeding ...