Part 4 of 6 · 2 min read
Sort and reduce
Think of the sort step as a librarian gathering every index card from every clerk. She arranges them alphabetically by label. All the cards for the same book end up next to each other, ready for one person to add them up.
In plain words: Between the map step and the reduce step, the framework sorts all the emitted key-value pairs by key. This sort is not something a programmer writes; it happens automatically, and it is the step that makes the rest of MapReduce work. Because the sort groups every pair with the same key next to each other, the reduce function can be called once per distinct key with an iterator over all the values for that key, without needing to hold the whole dataset in memory at once. The reducer combines those values into a final result for that key.
A worked example. After sorting, all the ("Database Systems", 1) pairs from every mapper land together. The reducer for the key "Database Systems" receives an iterator over every 1 emitted for that title and sums them, producing one output pair: ("Database Systems", 4213).
The key lines.
# A reducer, called once per distinct key, with an iterator over its values
def reduce(book_title, counts):
total = sum(counts)
emit(book_title, total)
Reduce function, shuffle
The reduce function is a callback invoked once per distinct key, given an iterator over every value emitted for that key across all mappers, and it combines those values into an output. The shuffle is the stage between map and reduce where the framework sorts and routes each key's pairs to the reducer responsible for that key, typically by hashing the key.
Example: the reducer above is called once for "Database Systems" with every 1 counted for that title already grouped together by the shuffle.