CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 4 of 7 · 4 min read

MapReduce

The same pattern as the Unix pipeline, spread over many machines.

Think of counting votes from a thousand ballot boxes. Teams at each box write the candidate's name on slips and put the slips into piles by candidate. Then one person per candidate counts the pile. The first step can happen at every box at once, and the second at every pile at once.

DDIA presents MapReduce as a Unix pipeline spread across machines. A single MapReduce job is like a single Unix process: it takes inputs and produces outputs, leaves its input unchanged, and has no other side effects. Instead of standard input and output, it reads and writes files in a distributed file system, such as HDFS (Hadoop Distributed File System). HDFS keeps each file block on several machines to survive failures, and a central server called the NameNode knows which machine holds which block.

The four steps of a job, using the log example, are:

  1. Read the input files and break them into records. Each line is a record.
  2. Map: call the mapper function on every record. It extracts a key and a value. For page counting, the key is the page and the value is empty. The mapper keeps no state between records.
  3. Sort and shuffle: group all pairs by key, so that all pairs with the same key reach the same place.
  4. Reduce: call the reducer once per key with all its values. It produces the output, such as the count.

Mapper

A mapper is the function in a MapReduce job that is called once for each input record and emits any number of key and value pairs.

Example: for the log line "GET /a", the mapper emits the pair (key "/a", value 1).

Reducer

A reducer is the function that receives one key and all the values collected for it, and produces output records.

Example: for the key "/a" with values 1, 1, 1, the reducer outputs "/a 3".

Shuffle

The shuffle is the step that sends each mapper's output to the right reducer, using a hash of the key, and sorts it so equal keys are together.

Example: all pairs with the key "/a" go to reducer 2, wherever the mappers ran.

The book explains how the work is split. Each input file block is a partition (Level 4) handled by one map task, ideally on a machine that already holds a copy of that block, so that data does not travel over the network. This is called putting the computation near the data. The number of reducers is chosen by the person who writes the job. A hash of the key picks the reducer, so that all pairs with the same key meet. Each mapper sorts its output into one file per reducer on its own disk. The reducers then fetch their files from all mappers and merge them, which keeps the sort order. "Shuffle" is a confusing name, says the book, because there is nothing random in it.

A worked example. Two mappers, two reducers, counting pages. Reducer choice is "keys starting before /b go to R1, others to R2" (made up).

Stage Machine Content
Input block 1 Mapper 1 /a, /b, /a
Input block 2 Mapper 2 /c, /a, /b
Map output Mapper 1 (/a,1) (/b,1) (/a,1)
Map output Mapper 2 (/c,1) (/a,1) (/b,1)
After shuffle Reducer 1 /a: 1, 1, 1
After shuffle Reducer 2 /b: 1, 1 and /c: 1
Reduce output Reducer 1 /a 3
Reduce output Reducer 2 /b 2, /c 1

A single job cannot do everything. The most popular pages need a second sort, so a second job reads the first job's output. Jobs are chained into workflows, in Hadoop simply by agreeing on a directory name. Chained jobs are less like a Unix pipe and more like a series of commands that write temporary files. The output of a job counts as valid only if it finishes successfully, so a failed job's partial output is thrown away.

Fault tolerance. If a task fails, the framework runs it again on another machine on the same input. This is safe because the input is immutable and failed output is discarded. The DDIA book says that the result looks as though nothing went wrong, which is the exactly-once effect from page 2.

Read it as

Map prepares the data by putting it in a form suitable for sorting. Reduce processes the sorted data.

Check yourself:

  • In the example above, why do all pairs for "/a" meet at one reducer?
  • Why is it safe to rerun a failed map task?