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).

Recall

These cards are also in your review deck, scheduled with spaced repetition.