Map Tasks, Grouping by Key, and Reduce Tasks

2.3 Map Tasks, Grouping by Key, and Reduce Tasks

Recall first

For word count, what should the mapper emit for the word cat? Why must all cat values meet at one reducer?

First principles

MapReduce processes records as key-value pairs:

(k1, v1) --map--> (k2, v2) --group by k2--> (k2, [v2,...]) --reduce--> (k3, v3)

A mapper transforms each input pair into zero, one, or many intermediate pairs. The framework partitions and sorts intermediate output, then groups equal keys. A reducer receives one key and its iterable/list of values and emits a smaller result. Hadoop’s official tutorial describes maps, partitioning, grouping, shuffle/sort, and reducers (MapReduce Tutorial).

The programmer supplies the functions; the framework handles input splits, scheduling, transfer, grouping, and task monitoring. The model works best when records can be processed independently and each result can be expressed by a key-based aggregation.

Worked word-count trace

Input:

file1: cat dog cat
file2: dog bird

Map phase (one possible input split per file):

M1 -> (cat,1) (dog,1) (cat,1)
M2 -> (dog,1) (bird,1)

Partition/group phase: the framework ensures equal keys go to the same reducer:

bird -> [1]
cat  -> [1,1]
dog  -> [1,1]

Reduce phase: sum each list:

bird -> 1
cat  -> 2
dog  -> 2

The reducer does not need to know which mapper produced a value. That abstraction is the point of grouping.

Partitioning

With r reducers, a partitioner maps each intermediate key to one of r partitions; Hadoop’s default is hash-based. A key must go to one logical reducer so aggregation is complete. A skewed key can still overload one reducer.

Assumptions and trade-offs

• Map work should be independent or have controlled side effects.
• The reduce operation should tolerate values arriving through the framework’s grouped iterator; do not rely on accidental global ordering.
• The shuffle can dominate runtime because all mapper partitions may cross the network.
• More reducers can improve parallelism but add task and output-file overhead.
• Map-only jobs are valid when no grouping is needed.

Exercise — revealed answer

Exercise: To compute total sales per product from records (product, amount), choose mapper and reducer outputs.

Answer: Mapper emits (product, amount) unchanged (or parses a raw record into it). Grouping forms (product, [amounts]). Reducer sums each list and emits (product, total). If a product is absent, it produces no output unless the application supplies a default.

Exam lens

Always draw the four named stages: map → partition/group → reduce, with shuffle/sort between map and reduce. Explain that grouping is by intermediate key, not by input file or physical node.

Rapid revision checklist

• Define mapper and reducer.
• Write the pair flow (k1,v1) → (k2,v2) → (k2,[v2]) → (k3,v3).
• Explain why a partitioner is needed.
• Trace word count.
• State shuffle, skew, and reducer-count trade-offs.

Key takeaways

1. The key is the rendezvous point for related data.
2. MapReduce hides distributed movement and grouping, but shuffle cost and skew remain real.
3. A reducer aggregates one key’s values; it does not automatically see all records globally.

Sources

• Apache Hadoop MapReduce Tutorial.
• Google MapReduce paper.
• Mining of Massive Datasets.
• Syllabus-aligned supplement: the word-count trace follows the official Hadoop tutorial’s canonical example and adapts it for retrieval practice.