MapReduce data flow technique

Data flow in MapReduce describes how data moves from the input in HDFS, through map, shuffle/sort and reduce, to the final output. The input is split, processed in parallel, and the intermediate results are redistributed by key.

 HDFS input
   |
 [Split 1][Split 2][Split 3]
   |         |         |
 Mapper1   Mapper2   Mapper3     (local disk output)
   |         |         |
 Combiner  Combiner  Combiner    (optional)
   +---- Partition / Shuffle ----+
   |                             |
 sort+merge                  sort+merge
 Reducer1                    Reducer2
   |                             |
 part-r-00000               part-r-00001  (HDFS)

Steps

1. Input splits: the job's input is divided into fixed-size splits (about one HDFS block). One map task is created per split. The InputFormat and RecordReader convert records into (key, value) pairs.
2. Map: each mapper processes its split, ideally on the node that holds the block (data locality), and emits intermediate pairs. Output is buffered in memory (circular buffer), partitioned by reducer, sorted by key, and spilled to local disk. Spill files are merged into one partitioned, sorted file.
3. Combiner (optional): it runs on map output before it is sent, to reduce the volume (e.g. local sum).
4. Shuffle: each reducer fetches its partition from every mapper's output over the network (HTTP). Partitioning is hash(key) mod R, which ensures all values of one key go to the same reducer.
5. Sort/merge: the reducer merges the fetched pieces, sorting them by key and grouping values with the same key.
6. Reduce: reduce(key, values) is called once per key group.
7. Output: results are written by OutputFormat to HDFS, one file per reducer, and replicated.

Notes

• Intermediate data lives on local disks, not HDFS, to avoid replication cost.
• With zero reducers (map-only job), map output goes directly to HDFS.
• Failed tasks are re-run on another node using the same input split.

Small example (word count)

Two splits: "to be or" and "not to be".

• Mapper 1 emits (to,1) (be,1) (or,1); mapper 2 emits (not,1) (to,1) (be,1).
• Partitioner with two reducers sends to,be to one reducer and or,not to another (by hash).
• Reducer groups: be -> [1,1], to -> [1,1], or -> [1], not -> [1].
• Output: (be,2) (to,2) (or,1) (not,1).

Fault tolerance and locality in the flow

• The master schedules map tasks close to input blocks and re-runs failed map or reduce tasks.
• Completed map output on a failed node must be recomputed, because it is only on local disk.
• Reducers start copying map outputs as soon as maps complete, but the reduce function itself starts only after all maps finish.