MapReduce

MapReduce lets you process a huge data set by writing two functions. The framework handles the rest: splitting the input, moving data across machines, and retrying work that fails. Google published the model in 2004, and it made large-scale batch jobs routine.

The big idea

Think of sorting a pile of mail. A sorter reads each letter and writes the recipient on it. Then all letters for one recipient go into the same bin. Finally a clerk counts each bin. The first step is the map, the middle is the shuffle, and the last is the reduce.

The picture breaks down at the shuffle. In a real cluster the bins are machines, and moving the letters means sending data across the network. That movement is usually the expensive part.

Walking through it

Word count is the classic example. This program runs as written and shows its output.

from collections import defaultdict

def map_fn(line):
    for word in line.lower().split():
        yield word, 1

def reduce_fn(word, counts):
    return word, sum(counts)

splits = ["the cat", "the dog the"]

groups = defaultdict(list)                 # shuffle: group all values by key
for split in splits:
    for word, one in map_fn(split):        # map: emit (word, 1) for each word
        groups[word].append(one)

results = [reduce_fn(word, counts)         # reduce: combine each key's values
           for word, counts in sorted(groups.items())]
print(results)

Output:

[('cat', 1), ('dog', 1), ('the', 3)]

Three ideas made MapReduce work at scale:

• Move the computation to the data. Schedule map tasks on machines that already hold their input.
• Re-run failed tasks. Each task is a deterministic function of immutable input, so a slow or failed one can run again elsewhere. The paper launched backup copies of the last slow tasks, which cut one sort job's time by 44%.
• Combiners. Pre-add counts on the map side, so (the, 2) crosses the network instead of two (the, 1) pairs.

Its weakness was that every job wrote its full output to disk. A real pipeline chains many jobs, so iterative work spent most of its time on disk I/O. Spark fixed that.

Common mistakes

• Assuming reduce runs where map ran. The shuffle moves data between machines, so keys must be grouped across the network.
• Writing map or reduce with side effects. A task that writes to an external system twice on a retry causes duplicates.
• Ignoring skew. If one key has most of the values, one reducer does most of the work.

Check yourself

1. Why does map output get partitioned and sorted by key? So all values for one key reach the same reducer, which can then combine them.
2. Why can the framework just rerun a failed task? Tasks are deterministic functions of immutable input, so a rerun produces the same output.

Key takeaways

• MapReduce has three steps: map, shuffle, and reduce.
• The shuffle groups values by key, and it is where data crosses the network.
• Fault tolerance comes from rerunning deterministic tasks.
• Combiners shrink the shuffle by combining values early.

Further learning

Next, see how Spark keeps data in memory and why shuffles still decide the cost, in Spark and shuffles.

The original paper is short and still worth reading.