MapReduce working with example

MapReduce is a programming model and framework for processing very large datasets in parallel on a cluster of commodity machines. The user writes two functions:

• map(key, value) -> list of (key2, value2)
• reduce(key2, list of values) -> result

The framework handles splitting of data, scheduling, communication, and fault tolerance.

Working mechanism

1. Input splitting: the input file stored in a distributed file system (GFS/HDFS) is divided into blocks (for example 64/128 MB).
2. Map phase: each split is given to a map task running (where possible) on the node holding the data. It reads records and emits intermediate key-value pairs.
3. Shuffle and sort: pairs are partitioned by key, moved across the network and sorted so that all values of the same key come together.
4. Reduce phase: a reduce task takes each key and its list of values and combines them into a final result.
5. Output: results are written back to the distributed file system.
6. Fault tolerance: a master (job tracker) monitors workers; if a worker fails, its task is re-run on another node.

 Input -> Split1 -> Map -+
          Split2 -> Map -+-> Shuffle/Sort -> Reduce -> Out1
          Split3 -> Map -+                  Reduce -> Out2

Example: word count

Input: "to be or not to be"

• Map output: (to,1) (be,1) (or,1) (not,1) (to,1) (be,1)
• Shuffle/sort: be -> [1,1]; not -> [1]; or -> [1]; to -> [1,1]
• Reduce (sum): (be,2) (not,1) (or,1) (to,2)

map(String line):
   for each word w in line: emit(w, 1)
reduce(String w, List counts):
   emit(w, sum(counts))

Advantages

Scales to thousands of machines, hides parallel programming complexity, tolerates failures and moves computation to data.