MapReduce job execution flow in Hadoop - Step-by-Step Execution

Concept Flow - MapReduce job execution flow

Submit Job

↓

Split Input Data

↓

Map Tasks Start

↓

Map Tasks Produce (key,value)

↓

Shuffle and Sort

↓

Reduce Tasks Start

↓

Reduce Tasks Aggregate Results

↓

Write Output

↓

Job Complete

The flow starts with job submission, then input data is split and processed by map tasks. Map outputs are shuffled and sorted, then reduce tasks aggregate results and write output, ending the job.

Execution Sample

Hadoop

1. Submit job
2. Split input
3. Run map tasks
4. Shuffle and sort
5. Run reduce tasks
6. Write output

This sequence shows the main steps of a MapReduce job from start to finish.

Execution Table

Step	Action	Input	Output	Notes
1	Submit Job	User program	Job configuration	Job is sent to Hadoop cluster
2	Split Input Data	Large input file	Input splits	Data divided for parallel processing
3	Run Map Tasks	Input splits	(key,value) pairs	Map function processes each split
4	Shuffle and Sort	(key,value) pairs	Sorted (key, list(values))	Groups values by key across all maps
5	Run Reduce Tasks	Sorted (key, list(values))	Aggregated results	Reduce function processes grouped data
6	Write Output	Aggregated results	Output files	Results saved to distributed storage
7	Job Complete	Output files	Success status	Job finishes successfully

💡 Job completes after output is written and success status is returned

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
Input Data	Large file	Split into chunks	Chunks processed by map	Mapped pairs ready	Reduced results ready	Output files
Map Output	N/A	N/A	(key,value) pairs	Grouped by key	Aggregated results	Saved output
Reduce Output	N/A	N/A	N/A	N/A	Aggregated results	Saved output

Key Moments - 3 Insights

Why does the input data get split before mapping?

Splitting input allows parallel processing by multiple map tasks, speeding up the job as shown in execution_table step 2.

What happens during the shuffle and sort phase?

Shuffle and sort groups all map outputs by key so reduce tasks can process all values for each key together, as seen in step 4.

When is the job considered complete?

After reduce tasks write the output files and the job returns a success status, shown in steps 6 and 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the output after step 3 (Run Map Tasks)?

A Input splits

B Aggregated results

C (key,value) pairs

D Output files

💡 Hint

Check the 'Output' column for step 3 in the execution_table.

At which step does the job split the input data for parallel processing?

A Step 2

B Step 1

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column and find where input data is divided.

If the shuffle and sort phase was skipped, what would likely happen?

A Map tasks would fail to run

B Reduce tasks would receive unsorted data and might miss some keys

C Input data would not be split

D Output files would be written earlier

💡 Hint

Refer to the purpose of shuffle and sort in grouping keys before reduce tasks.

Concept Snapshot

MapReduce job flow:
1. Submit job
2. Split input data
3. Map tasks process splits
4. Shuffle and sort map outputs
5. Reduce tasks aggregate data
6. Write output files
Splitting enables parallelism; shuffle groups keys for reduce.

Full Transcript

A MapReduce job starts when a user submits it to the Hadoop cluster. The input data is split into smaller chunks so multiple map tasks can run in parallel. Each map task processes its input split and produces key-value pairs. These pairs are shuffled and sorted to group all values by their keys. Reduce tasks then process each key and its list of values to aggregate results. Finally, the reduce outputs are written to output files in distributed storage. The job completes successfully after writing output. This flow enables processing large data efficiently by dividing work and combining results.

Practice

1. What is the main role of the Map task in a MapReduce job?

easy

A. Process input data and create key-value pairs

B. Aggregate results from all nodes

C. Store the final output in HDFS

D. Schedule tasks on cluster nodes

Solution

1. Step 1: Understand the Map task function

   The Map task reads input data and transforms it into intermediate key-value pairs.

2. Step 2: Differentiate from Reduce task

   The Reduce task aggregates these key-value pairs, so it is not responsible for initial processing.

3. Final Answer:

   Process input data and create key-value pairs -> Option A

4. Quick Check:

   Map task = create key-value pairs [OK]

Hint: Map creates key-value pairs from input data [OK]

Common Mistakes:

• Confusing Map with Reduce task role
• Thinking Map stores final output
• Assuming Map schedules tasks

2. Which of the following is the correct sequence of steps in a MapReduce job execution?

easy

A. Map -> Shuffle -> Reduce

B. Shuffle -> Map -> Reduce

C. Reduce -> Map -> Shuffle

D. Reduce -> Shuffle -> Map

Solution

1. Step 1: Recall MapReduce execution order

   The job starts with Map tasks processing input, then Shuffle sorts and transfers data, followed by Reduce tasks aggregating results.

2. Step 2: Match sequence to options

   Only Map -> Shuffle -> Reduce correctly shows Map first, then Shuffle, then Reduce.

3. Final Answer:

   Map -> Shuffle -> Reduce -> Option A

4. Quick Check:

   Execution order = Map, Shuffle, Reduce [OK]

Hint: Remember: Map first, then Shuffle, then Reduce [OK]

Common Mistakes:

• Mixing up Shuffle and Map order
• Placing Reduce before Map
• Ignoring Shuffle step

3. Consider this simplified MapReduce code snippet:

map(String key, String value) {
  emit(value, 1);
}

reduce(String key, Iterator values) {
  int sum = 0;
  while (values.hasNext()) {
    sum += values.next();
  }
  emit(key, sum);
}

What will be the output for input: ["a", "apple"], ["b", "apple"], ["c", "banana"]?

medium

A. [('apple', 1), ('banana', 1)]

B. [('a', 1), ('b', 1), ('c', 1)]

C. [('apple', 2), ('banana', 1)]

D. [('apple', 3), ('banana', 1)]

Solution

1. Step 1: Analyze Map output

   Map emits (value, 1) pairs: ('apple',1), ('apple',1), ('banana',1).

2. Step 2: Analyze Reduce aggregation

   Reduce sums counts for each key: 'apple' = 1+1=2, 'banana' = 1.

3. Final Answer:

   [('apple', 2), ('banana', 1)] -> Option C

4. Quick Check:

   Count of 'apple' = 2, 'banana' = 1 [OK]

Hint: Map emits value with 1, Reduce sums counts by key [OK]

Common Mistakes:

• Counting keys instead of values
• Confusing input keys with values
• Adding counts incorrectly

4. Identify the error in this MapReduce job execution flow:

Map task reads input and emits key-value pairs.
Reduce task tries to read input directly from HDFS instead of shuffle output.
Reduce task aggregates values by key.

medium

A. Reduce task should emit key-value pairs before Map

B. Map task should aggregate values, not Reduce task

C. Map task should read from shuffle output

D. Reduce task should read from shuffle output, not directly from HDFS

Solution

1. Step 1: Understand Reduce input source

   Reduce tasks receive data from the shuffle phase, not directly from HDFS input files.

2. Step 2: Identify incorrect flow

   Reading directly from HDFS in Reduce breaks the flow and causes errors.

3. Final Answer:

   Reduce task should read from shuffle output, not directly from HDFS -> Option D

4. Quick Check:

   Reduce reads shuffle output [OK]

Hint: Reduce reads shuffle output, never direct HDFS input [OK]

Common Mistakes:

• Thinking Reduce reads input files
• Swapping Map and Reduce roles
• Ignoring shuffle phase

5. You want to optimize a MapReduce job that processes large logs by filtering out entries with empty user IDs before counting occurrences. Where should you apply this filter for best performance?

hard

A. In the Reduce task after aggregation

B. In the Map task before emitting key-value pairs

C. During the shuffle phase

D. After the job completes on the output files

Solution

1. Step 1: Understand filtering impact

   Filtering early reduces data volume, saving network and processing time.

2. Step 2: Apply filter in Map task

   Filtering in Map avoids sending unnecessary data to shuffle and Reduce phases.

3. Final Answer:

   In the Map task before emitting key-value pairs -> Option B

4. Quick Check:

   Filter early in Map for best performance [OK]

Hint: Filter data early in Map to reduce workload [OK]

Common Mistakes:

• Filtering only in Reduce wastes resources
• Trying to filter during shuffle (not possible)
• Filtering after job completion is too late