Questions: MapReduce and Batch Data Processing

Question 1

In MapReduce word count, map emits (word, 1) for every word in its input split. What does a single reduce call receive?

• A. One line of the original text
• B. One word and the list of all the 1s emitted for that word, from every mapper
• C. All words that start with the same letter
• D. The final total for every word in the corpus

Answer: (B)

The shuffle groups intermediate pairs by key across all map outputs. Each reduce call gets one key, here a word, and an iterator over all its values. For word count, reduce sums the 1s and emits (word, total).

Question 2

In the design described by Dean and Ghemawat, a worker machine fails after finishing several map tasks and before all reducers have read their output. What does the master do?

• A. Nothing, because completed tasks are never re-run
• B. It re-executes those completed map tasks on other workers, because their output was stored on the failed machine's local disk
• C. It restarts the entire job from the beginning
• D. It asks the reducers to skip the missing data

Answer: (B)

Map output is written to the mapper's local disk, so it is lost when that machine fails. The master reschedules those map tasks elsewhere. Completed reduce tasks need not be re-run, because their output is in the global distributed file system. Re-execution is safe because map and reduce are expected to be deterministic functions of their input.

Question 3

MapReduce is especially efficient for iterative algorithms that read the same dataset dozens of times.

• T. True
• F. False

Answer: False

Each MapReduce job reads its input from distributed storage and writes its results back, so an algorithm with 30 iterations pays for 30 full rounds of disk input and output. In-memory dataflow systems such as Apache Spark were designed largely to speed up this kind of workload.

Question 4

What is a combiner in MapReduce, and why does it help a job such as word count?

Model answer: A combiner is an optional function that runs on each mapper's output before the shuffle and partially merges values with the same key, for example adding up the counts for each word locally. It shrinks the amount of data sent across the network to reducers. It is valid when the reduce operation is associative and commutative, as addition is.

Without a combiner, a mapper that sees the word 'the' 10,000 times sends 10,000 pairs. With a combiner, it sends one pair carrying 10,000.