MapReduce workflow with example

MapReduce is a programming model and framework for processing large datasets in parallel on a cluster. It is the core processing engine of Hadoop: HDFS stores the data and MapReduce processes it, moving computation to where the data is. The programmer writes only two functions, map and reduce, and the framework handles splitting, scheduling, shuffling, and fault tolerance.

Workflow

 Input -> Split -> Map -> Shuffle & Sort -> Reduce -> Output
 (HDFS)  (blocks) (k,v)   (group by key)     (k,list)  (HDFS)

1. Input and splitting: input files in HDFS are divided into input splits (usually one block of 128 MB). A RecordReader turns each split into (key, value) pairs.
2. Map phase: one map task per split runs the user's map() on every record and emits intermediate (key, value) pairs: map(k1, v1) -> list(k2, v2). Map output is written to local disk, not HDFS.
3. Combiner (optional): a local mini-reducer that merges map output of the same node to cut network traffic.
4. Partition, shuffle and sort: a partitioner (default hash(key) mod number of reducers) decides the reducer for each key. Map output is copied over the network to reducers (shuffle), and sorted and grouped by key.
5. Reduce phase: reduce(k2, list(v2)) -> list(k3, v3) is called once per key to aggregate the values.
6. Output: reducers write results to HDFS, one file per reducer (part-r-00000 ...).

The master (JobTracker, or ResourceManager and ApplicationMaster in YARN) schedules tasks and re-executes failed tasks.

Example 1: Word count

Input:

 line1: "big data is big"
 line2: "data is useful"

• Map output: (big,1) (data,1) (is,1) (big,1) | (data,1) (is,1) (useful,1)
• After shuffle and sort: big -> [1,1]; data -> [1,1]; is -> [1,1]; useful -> [1]
• Reduce output: (big,2) (data,2) (is,2) (useful,1)

// Mapper
public void map(LongWritable key, Text value, Context ctx) {
  for (String w : value.toString().split("\\s+"))
    ctx.write(new Text(w), new IntWritable(1));
}
// Reducer
public void reduce(Text key, Iterable<IntWritable> vals, Context ctx) {
  int sum = 0;
  for (IntWritable v : vals) sum += v.get();
  ctx.write(key, new IntWritable(sum));
}

Example 2: Maximum temperature per year

Input records: (year, temperature).

map:    emit (year, temp)
reduce: for each year, return max of the temps list

Map: (1950,22) (1950,34) (1951,30) ... Reduce: (1950,34) (1951,30). Here the reducer can also be used as the combiner, since max is associative.

Why "heart" of Hadoop

It provides scalable, fault-tolerant batch processing, and higher-level tools such as Hive and Pig compile their queries into MapReduce jobs (or, in newer versions, Tez or Spark jobs on YARN).