Notesbatch🌱 seedling

Dataflow Engine

Also: Dataflow · DAG Engine · RDD · Resilient Distributed Dataset · Lineage · Narrow and Wide Dependencies

A batch engine that runs a whole multi-step pipeline as one graph of operators, fusing steps, keeping intermediates in memory or on local disk, and recovering lost data by recomputing it from its lineage instead of replicating it.

Why it exists

Real pipelines chain many steps. As MapReduce jobs, each step writes its full output to the replicated file system before the next can start: wasted I/O for data nobody will ever read.

How it works

  • The job is a DAG of operators (map, filter, join, aggregate); the engine sees and optimises all of it.
  • Narrow dependencies (each input partition feeds at most one output partition) are pipelined into a single stage.
  • Wide dependencies need a Shuffle; stages are cut there, and shuffle output is kept on local disk.
  • Lineage: each dataset records which operator produced it from which parents, so a lost partition is recomputed, not restored from a replica.
  • Only the final output goes to durable, replicated storage.

Trade-offs

Gains Costs
no replicated intermediates; far less I/O recomputation after failure can be expensive for long chains
in-memory reuse for iterative jobs memory pressure and spilling to tune
optimiser can fuse, reorder and choose joins operators must be deterministic for recomputation to be correct

In practice

  • The RDD paper (2012) reported Spark up to 20× faster than Hadoop for iterative jobs.
  • In 2014 Spark sorted 100 TB in 23 minutes on 206 machines; tying the Daytona GraySort record; the previous Hadoop MapReduce record took 72 minutes on 2,100.
  • Google's FlumeJava fused one 207-stage MapReduce pipeline into a single stage, and evolved into Dataflow and Apache Beam.

Pitfalls

  • Very long lineages (iterative algorithms) make recovery replay a lot of work; checkpoint periodically.

Recall

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