Introduction to MapReduce

Introduction to MapReduce

MapReduce is a programming model for processing very large datasets in parallel. Developed at Google, it was designed for large-scale search and text processing over web data stored in systems such as Bigtable and the Google File System (GFS). The model is also useful for scientific and database workloads. Hadoop is an open-source implementation.

Parallel-computing background

The lecture reviews three parallel-system arrangements:

• Shared memory: Multiple processors access common memory.
• Shared disk: Independent servers share storage over a network.
• Shared nothing: Each server has its own processor and disk, and servers are connected by a network.

Parallelism can reduce execution time, but ideal speedup—where a job running on p processors takes one-pth as long—is uncommon. Efficiency may be reduced by:

• Synchronization among processors
• Communication overhead
• Uneven distribution of work
• Workloads with limited inherent parallelism

A computation is scalable when its efficiency remains stable as both the dataset and the number of processors grow together.

Example: Counting word frequencies

To illustrate how work can be divided, the lecture considers counting how often each word appears across a collection of documents.

Two strategies are discussed:

1. Divide the vocabulary among processors. Each processor counts a subset of the words, but must examine the documents to find them. As the number of processors grows, they may spend time reading data that does not contribute to their assigned counts, reducing efficiency.
2. Divide the documents among processors. Each processor counts all target words in its assigned portion of the documents, and the partial counts are combined afterward. This makes each processor’s document reads useful to the calculation and is more scalable as data and processor counts grow together.

The second strategy motivates MapReduce: process separate data partitions, then aggregate their partial results.

MapReduce model and workflow

MapReduce is a parallel-programming abstraction organized into map and reduce stages. A configurable number of mapper and reducer processes handle the work, coordinated by a master process.

1. Split the input: Each mapper processes a portion of the input data.
2. Map: A mapper transforms input key–value pairs into intermediate key–value pairs. For word counting, it emits words and their counts for its portion of the documents.
3. Write intermediate results: Each mapper creates an intermediate file for each reducer. Results are organized by key and stored locally, while the master tracks their locations.
4. Shuffle and fetch: The master tells reducers where to find the relevant mapper outputs, and reducers fetch those files.
5. Group and reduce: Each reducer groups records with the same key and applies the appropriate aggregation—for example, adding partial counts for each word.
6. Write final results: Reducers write the output to the distributed file system.

The map and reduce functions vary by problem. The central idea is to produce intermediate keyed results and combine the values associated with each key.

Fault tolerance

Because a MapReduce job may run across many processors and machines, it must handle failures. The lecture describes these mechanisms:

• Workers send periodic heartbeat messages to indicate that they are alive.
• If a worker appears to have stopped making progress, the master can duplicate or reassign its task.
• If a mapper fails, its assigned work is run again on another worker.
• If a reducer fails, unfinished work is reassigned. The lecture notes that completed work has already been written to the file system.

Performance and applications

MapReduce performance depends not only on the computation itself, but also on reading input, writing mapper output, transferring intermediate data, and writing final output. These stages add overhead beyond the ideal of simply dividing the work among processors.

Applications mentioned include:

• Document indexing for web search, where map tasks emit word–document records and reducers group records by word.
• Relational data operations, including SQL-style grouping and joins over large datasets.

MapReduce lets programmers express large computations as parallel map and reduce operations, while the framework coordinates data movement, aggregation, and recovery from failures.

Speakers and sources

• Speaker: One lecturer; no individual name is given in the subtitles.
• Organizations, systems, and references mentioned: Google, Bigtable, Google File System (GFS), Hadoop, Yahoo, Amazon EC2, and general parallel-computing and database literature.