MapReduce to DAG Execution

MapReduce in one minute

1. Map — read split, emit (key, value) pairs in parallel
2. Shuffle — sort/group by key across the cluster (expensive network I/O)
3. Reduce — aggregate per key

Bottleneck: shuffle moves all data across the network. Everything since MapReduce optimizes what gets shuffled and when.

DAG execution engines

Spark, Flink batch, Tez, Beam — all compile a DAG of stages:

Concept	Meaning
Transformation	Lazy operation (map, filter, join) — builds DAG
Action	Triggers execution (count, write)
Stage	Group of tasks separated by shuffle boundaries
Task	Unit of work on one data partition

Narrow transformations (map, filter) — no shuffle, pipelined in one stage. Wide transformations (groupBy, join) — shuffle required, new stage.

Why Spark won

• In-memory caching between stages (vs MapReduce always to disk)
• Generality — same engine for SQL, ML, streaming
• Lazy optimization — Catalyst optimizer sees full DAG

MapReduce still matters conceptually — interviewers say "shuffle" and mean the same network pain.

Cluster roles (YARN/K8s)

Component	Role
Driver	Builds DAG, schedules tasks, collects metadata
Executor	Runs tasks, holds cached partitions
Cluster manager	Allocates containers/pods

Link to OS: executors are JVM processes with heap limits — OOM kills tasks.

Link to Databases

Reading Parquet from S3 is partition pruning at file level — the DAG engine skips directories. Storage layout (Topic in Databases) and compute partitioning (here) must align.

Interview answer template

"Word count is map → shuffle by word → reduce. The shuffle is O(data) network. I'd partition input by hash upfront if the downstream join key is known — co-locate early to skip a shuffle."