Hadoop-Style MapReduce Shuffle

Hadoop-Style MapReduce Shuffle A data-flow diagram generated by Archify. 01 / Input Shards 02 / Map Tasks 03 / Map Output 04 / Shuffle + Reduce 05 / Output Dataset Shard m1 · HDFS file/object · 01 / Input Shards · input dataset Shard m1 HDFS file/object input dataset Shard m2 · HDFS file/object · 01 / Input Shards · input dataset Shard m2 HDFS file/object input dataset Shard m3 · HDFS file/object · 01 / Input Shards · input dataset Shard m3 HDFS file/object input dataset Map Task 1 · emits (key,value) · 02 / Map Tasks · one per shard Map Task 1 emits (key,value) one per shard Map Task 2 · emits (key,value) · 02 / Map Tasks · one per shard Map Task 2 emits (key,value) one per shard Map Task 3 · emits (key,value) · 02 / Map Tasks · one per shard Map Task 3 emits (key,value) one per shard m1 Sorted Runs · m1r1 m1r2 m1r3 · 03 / Map Output · local disk m1 Sorted Runs m1r1 m1r2 m1r3 local disk m2 Sorted Runs · m2r1 m2r2 m2r3 · 03 / Map Output · local disk m2 Sorted Runs m2r1 m2r2 m2r3 local disk m3 Sorted Runs · m3r1 m3r2 m3r3 · 03 / Map Output · local disk m3 Sorted Runs m3r1 m3r2 m3r3 local disk Reduce Task 1 · mergesort shares · 04 / Shuffle + Reduce · group by key Reduce Task 1 mergesort shares group by key Reduce Task 2 · mergesort shares · 04 / Shuffle + Reduce · group by key Reduce Task 2 mergesort shares group by key Reduce Task 3 · mergesort shares · 04 / Shuffle + Reduce · group by key Reduce Task 3 mergesort shares group by key Output r1 · sorted records · 05 / Output Dataset · output shard Output r1 sorted records output shard Output r2 · sorted records · 05 / Output Dataset · output shard Output r2 sorted records output shard Output r3 · sorted records · 05 / Output Dataset · output shard Output r3 sorted records output shard m1 records record by record m2 records record by record m3 records record by record key-value hash(key) routing key-value hash(key) routing key-value hash(key) routing m1r1 sorted run m1r2 shuffle copy m2r2 shuffle copy m3r2 shuffle copy m3r3 sorted run sorted file one file per task sorted file one file per task sorted file one file per task Legend primary data data store data flow