Beyond MapReduce: Dataflow Engines

How Spark, Tez and Flink run a whole pipeline as one graph of operators instead of a chain of MapReduce jobs, how they recover from failure, and how to choose between them.

Overview

Why MapReduce was not enough

A real batch pipeline is rarely one map and one reduce. Cleaning logs, joining them with users, aggregating by day and ranking the results might take five MapReduce jobs chained together. Each job writes its full output to the replicated distributed file system, and the next job cannot start until the previous one has finished and read it all back.

That costs time three ways: every intermediate result is written and replicated even though it is thrown away soon after; a job waits for every task of the job before it; and a mapper that only reads a file and passes it on still has to run. Algorithms that loop over the same data, such as machine learning training or PageRank, pay this on every pass.

The dataflow idea

A dataflow engine takes the whole pipeline as one directed acyclic graph (a DAG): nodes are operators such as map, filter, join and aggregate; edges show how data flows between them. Because the engine sees the whole graph, it can plan it as a unit.

Unit of work — One map, one reduce per job — A graph of any operators
Between steps — Output written and replicated in the file system — Passed on directly; only shuffles regroup data (Spark writes shuffle data to local disk)
Sorting — Always between map and reduce — Only where an operator needs it
Next step starts — After the whole previous job ends — As soon as its input is ready, where the operator allows
Reused data — Read from disk every time — Can be kept in memory

Operators that work record by record (map, filter) are joined into one task and run back to back in memory. The graph only has to stop and redistribute data at a shuffle, where records must be regrouped by key, for example before a join or an aggregation.

Spark: stages, laziness and lineage

Spark's core abstraction, from the 2012 paper, is the RDD (Resilient Distributed Dataset): a partitioned, read-only collection built by applying transformations to other datasets. Spark's DataFrame and SQL APIs sit on top of the same engine.

Transformations are lazy: Spark only records them. When an action asks for a result (count, collect, write), Spark builds the graph and splits it into stages. A stage holds as many record-by-record steps as possible, pipelined together; stages end at shuffles.

The paper names the difference. A narrow dependency means each input partition feeds at most one output partition (map, filter), so the steps can be pipelined and a lost partition is cheap to rebuild. A wide dependency means one input partition feeds many output partitions (a join or group-by on data not already partitioned by the key), which needs a shuffle.

Recovering without writing everything down

MapReduce survives failures because every job's output is safely stored. Spark avoids storing most intermediate data, so it needs another way. Each dataset remembers its lineage, the steps that built it from stored input. If a machine dies, Spark recomputes only the lost partitions from their parents. Shuffle output is still written to local disk on the machines that produced it, so recovery rarely has to go back to the start.

Lost partition after narrow steps — Recompute just that partition from its parent
Lost partition after a shuffle — Refetch shuffle files, or rerun the tasks that wrote them
Very long lineage, such as many loop iterations — Checkpoint the dataset to reliable storage to cut the chain
Cached partition that did not fit in memory — With the default MEMORY_ONLY level, recompute it when needed

Recomputation only gives the right answer if the operators are deterministic. An operator that uses unseeded randomness or the current time can produce different data the second time, and downstream partitions built from the first run will no longer match.

Why it is faster for loops

A dataset can be cached with cache() or persist(), so a loop reads it from memory instead of disk on each pass. The Spark paper reported up to 20 times faster than Hadoop on iterative machine learning and graph jobs. For one pass over data much larger than memory, the gain is far smaller, because both engines are limited by reading input and shuffling.

Tez and Flink

Apache Tez is a framework on Hadoop YARN for running a DAG of tasks. Hive and Pig use it so that one query runs as one job instead of a chain of MapReduce jobs.

Apache Flink is built as a stream processor, and treats a batch as a bounded stream: a stream that happens to end. Its recovery depends on the mode.

Input — Unbounded or bounded — Bounded only
Data between operators — Pipelined, record by record — Blocking shuffle, results stored
Recovery — Restart all running tasks from the last checkpoint, replay input from there — Restart only the failed tasks (or their predecessors), from stored intermediate results
State — Kept in operators, snapshotted in checkpoints — Not needed across the whole run

Flink's docs say a program on bounded input gives the same final result in either mode, and recommend batch mode for bounded input because it is more efficient.

Streaming latency: Spark and Flink

The engines differ most on low-latency streaming.

Default model — Micro-batches: small batch jobs run one after another — Continuous, record by record
Latency in the docs — As low as 100 ms end to end, exactly-once — Not a single number; record at a time with no batch boundary
Lower-latency option — Continuous Processing: as low as 1 ms, at-least-once — Default
Event time and late data — Supported with watermarks — Supported with watermarks

Apache Beam is a separate layer: one programming model for batch and streaming pipelines that runs on several engines, called runners, including Flink, Spark and Google Cloud Dataflow. Support differs by runner, so check Beam's capability matrix before relying on a feature.

Joins without a shuffle

A shuffle is the most expensive step, so engines avoid it when they can. If one side of a join is small, a broadcast join copies it to every task and joins locally, with no shuffle of the large side. Spark SQL does this automatically for tables under spark.sql.autoBroadcastJoinThreshold, 10 MB by default, and since Spark 3.2.0 adaptive query execution is on by default: it can switch a sort-merge join to a broadcast join, merge small shuffle partitions and split skewed ones, using statistics from the running job.

What you will be able to do

Explain what a chain of MapReduce jobs wastes, and how a DAG engine avoids it.
Say where Spark cuts a job into stages, and why narrow and wide dependencies matter.
Explain lineage-based recovery and when to checkpoint.
Choose between Spark and Flink for a batch or streaming job, with reasons.

Key concepts

Dataflow engine: A system that runs a whole pipeline as one graph of operators, passing data between them directly instead of storing each step in a file system.
DAG: Directed acyclic graph. Here, operators are the nodes and data flows along the edges, with no loops.
Stage (Spark): A group of record-by-record steps pipelined together. Stages end where a shuffle is needed.
Narrow and wide dependency: Narrow: each input partition feeds at most one output partition, so no shuffle. Wide: one input partition feeds many output partitions, so a shuffle.
Lineage: The record of which transformations built a dataset. Spark uses it to recompute lost partitions instead of storing every intermediate result.
Lazy evaluation: Spark records transformations and runs nothing until an action asks for a result, which lets it plan the whole graph.
Bounded stream: Flink's view of a batch: a stream with an end. The same program can run on bounded or unbounded input.
Broadcast join: Copying a small table to every task so the large table can be joined in place, with no shuffle.
Micro-batch: Spark Structured Streaming's default: the stream is processed as a series of small batch jobs.

When to use it

Designing a batch pipeline (ETL, daily aggregates, training data preparation) and choosing the engine.
Choosing between Spark Structured Streaming and Flink for a streaming job, based on latency and delivery guarantees.
Explaining why an iterative algorithm runs far faster on Spark than on MapReduce.
Tuning a slow job: finding its shuffles, skewed keys and joins that could be broadcast.

Interview questions

When would you use Flink instead of Spark?
How does Spark recover from a failed machine without writing every intermediate result to disk?
A Spark job with a big join is slow. What do you look for?