Notesbatch🌱 seedling
Shuffle
Also: MapReduce Shuffle · Shuffle Phase · Exchange · Repartition · Push-Based Shuffle · Combiner
The distributed sort between map and reduce: every mapper partitions its output by key into one bucket per reducer, and every reducer fetches its bucket from every mapper, so all values for a key meet on one machine.
Why it exists
Grouping, aggregating and joining need all records with the same key together, but they were produced on different machines.
How it works
- Partition: each mapper splits its output into R buckets, usually by hash(key) mod R (Hash Partitioning).
- Sort and spill: in Hadoop and Spark, buckets are sorted by key and written to local disk, spilling and merging if they don't fit in memory (Google's original sorted on the reducer instead).
- Fetch: each reducer pulls its bucket from every mapper: M × R transfers.
- Merge: the reducer merges the sorted runs, then processes one key at a time.
- Combiner: a partial reduce on the map side (sum, count, max) shrinks what crosses the network.
Trade-offs
| Gains | Costs |
|---|---|
| any grouping or join across a cluster | all-to-all network traffic and disk I/O |
| scales past memory by sorting and spilling | M × R small blocks stress disks and connections |
| a natural recovery point (outputs on disk) | uneven keys concentrate work (Data Skew) |
In practice
- LinkedIn found its Spark shuffle blocks averaged tens of KB and about 15% of compute was wasted on shuffle latency; its push-based shuffle (Magnet, Spark 3.2) merges blocks per reducer and cut production job runtimes by nearly 30%.
- Apache Spark's adaptive execution coalesces small post-shuffle partitions using runtime sizes.
Pitfalls
- Too many partitions make tiny blocks and per-task overhead; too few make huge tasks that spill or run out of memory.
- Shuffling a big table to join with a small one: broadcast the small one instead (Join Strategies).
Connections
- Part of
- Batch Processing
- Builds on this
- Data SkewJoin Strategies
- In real systems
- Apache SparkHadoop
Recall
These cards are also in your review deck, scheduled with spaced repetition.