10-605 · map, partition, shuffle, merge

Shuffle-Sort In Map-Reduce

A map step is embarrassingly parallel — each worker rewrites its own keys and never talks to anyone. The moment those keys have to be grouped so that each worker sees everything in a group, data may need to be moved between workers. That move is the shuffle, and it is the expensive part of MapReduce. Here it is in slow motion, over k workers, with one round of the wondrous-numbers map — n ↦ n/2 if even else 3n+1, emitting nothing once a key falls into the final 4 → 2 → 1 → 4 ... cycle.

Shuffle sort