Why architecture matters here
Lineage matters architecturally because it is simultaneously the fault-tolerance mechanism, the execution plan, and the performance model — three things that in other systems are separate. Because recovery is recomputation-from-lineage, the shape of your lineage directly determines how expensive a single machine failure is: a chain of narrow transformations recovers a lost partition by recomputing just that partition's ancestry on one executor, cheaply and locally; a wide dependency recovers a lost partition by potentially recomputing an entire shuffle, pulling data from many upstream partitions. The same graph that describes your computation describes your recovery cost, so understanding lineage is understanding both.
The load-bearing distinction is narrow vs wide dependencies, and it drives everything downstream. A narrow dependency means each parent partition contributes to at most one child partition — map, filter, flatMap, union. These can be pipelined: Spark fuses a whole chain of narrow transformations into a single task that streams a partition through all of them in memory, no network, no intermediate materialization. A wide dependency (also called a shuffle dependency) means a child partition depends on many parent partitions — groupByKey, reduceByKey, join, repartition — because rows must be redistributed across the cluster by key. A wide dependency forces a shuffle: parents write their output to local disk partitioned by the destination, and children fetch across the network. Shuffles are the stage boundaries, the expensive operations, and the points where recovery gets complicated.
This is why the most consequential thing you can know about a Spark job is where its shuffles are. Narrow-only pipelines are cheap to run and cheap to recover; each shuffle adds network cost, disk I/O, a synchronization barrier, and a recovery liability. A developer who reads their job as a lineage graph — 'these five transformations pipeline into one stage, then this join forces a shuffle into a second stage' — can predict performance, spot unnecessary shuffles, and reason about what a failure costs. A developer who treats Spark as a black box writes a job with six accidental shuffles and a lineage so deep that a single node failure triggers minutes of recomputation. The architecture rewards seeing the graph.
It is worth being precise about why recomputation is safe, because the entire model rests on one assumption that is easy to violate: transformations must be deterministic and side-effect-free. Lineage guarantees fault tolerance only because replaying the same recipe from the same durable input produces byte-identical output every time. The moment a transformation reads the wall clock, consults an unseeded random generator, or depends on external mutable state, recomputation of a lost partition yields different data than the original — and now a single machine failure silently corrupts your results rather than transparently healing them. This is why 'keep transformations pure' is not a style preference in Spark but a correctness contract with the fault-tolerance mechanism; the same property that makes lineage powerful makes impurity dangerous.
The architecture: every piece explained
Top row: how the DAG is built. A source RDD is created by reading from durable storage (HDFS, S3, a table) — its 'lineage' bottoms out at data that can be re-read, which is what makes recomputation possible at all. Each transformation adds a node. Narrow dependencies (map, filter, union) link child partitions to specific parent partitions one-to-one or few-to-one, so they carry no shuffle. Wide dependencies (groupByKey, reduceByKey, join) link each child partition to all parent partitions via a key-based redistribution. The shuffle boundary is where a wide dependency sits: the parent stage must fully complete and write its shuffle files before the child stage can read them — a hard synchronization barrier.
Middle row: how the DAG becomes execution. When an action fires, the DAGScheduler traverses the lineage backward from the result and cuts it into stages at every wide dependency: each stage is a maximal run of narrow transformations that can be pipelined into a single set of tasks. It submits stages in dependency order — a stage runs only after the stages producing its shuffle inputs finish. The TaskScheduler takes each stage's tasks (one per output partition) and assigns them to executors, preferring data locality. When an executor dies, a lost partition (both cached data it held and shuffle files it wrote) must be reconstructed, and here lineage earns its name: the DAGScheduler consults the graph to find the recompute path — for a narrow chain, just replay that partition's ancestry; for a lost shuffle output, resubmit the missing tasks of the parent stage.
Bottom rows: the two ways to change the recovery calculus. Cache / persist materializes an RDD's partitions in memory (or memory-and-disk) so that repeated actions don't recompute the lineage from scratch — the first action pays to compute it, subsequent ones read the cached partitions. But cache is not durable: if the executor holding a cached partition dies, that partition is gone and Spark recomputes it from lineage, so caching speeds up reuse without weakening fault tolerance. Checkpoint is the durable option: it writes an RDD to reliable storage (HDFS) and then truncates the lineage — the checkpointed RDD becomes a new source, its ancestry forgotten. This is how you stop a lineage from growing without bound in long iterative jobs. The ops strip lists the levers that matter operationally: cache eviction policy, where to place checkpoints, shuffle file management, and controlling lineage depth.
End-to-end flow
Walk a realistic job: read a day of clickstream logs, filter to purchase events, join them against a user dimension, aggregate revenue per segment, and save. Trace how lineage shapes execution and recovery.
Build: sc.textFile creates the source RDD from HDFS. .filter(isPurchase) and .map(parse) add two narrow nodes. The join against the user RDD adds a wide node — rows must be co-located by user key — and reduceByKey for the per-segment sum adds another wide node. Nothing has run: this is a lineage graph of six RDDs. Plan: the save action fires. The DAGScheduler walks backward and finds two shuffle boundaries, cutting the job into three stages: Stage 1 reads-filters-parses the logs (narrow, pipelined) and writes shuffle output partitioned by user key; Stage 2 similarly prepares the user dimension; Stage 3 reads both shuffles, performs the join, then the reduceByKey shuffle and the final write. Run: Stages 1 and 2 run in parallel (independent), each task streaming its partition through the whole narrow chain in memory. When they complete, their shuffle files sit on executor local disks. Stage 3's tasks fetch the relevant shuffle partitions across the network, join, aggregate, and save.
Now the failure, which is where lineage pays off. Midway through Stage 3, an executor crashes. It held: some Stage 3 tasks in progress (simply rescheduled elsewhere), and — importantly — the shuffle output files that Stage 1 had written on that machine. Those shuffle files are now lost, so the Stage 3 tasks that needed them cannot fetch their inputs. The DAGScheduler consults lineage: it does not re-run the whole job; it resubmits only the specific Stage 1 tasks whose shuffle outputs lived on the dead executor, recomputing those partitions from the durable HDFS source through the narrow filter-parse chain, re-writing just those shuffle files, and then re-running the blocked Stage 3 tasks. Recovery cost is proportional to what was actually lost, and because the source is durable and the transformations are deterministic, the recomputation is guaranteed to reproduce identical data.
Contrast two design choices on the same job. Had the developer cache()d the parsed-and-filtered RDD because a downstream iterative model reuses it ten times, the first action materializes it and the next nine skip Stages 1–2 entirely — but a lost cached partition still recomputes from lineage, so correctness is preserved and only speed is affected. Had this been an iterative algorithm that grows lineage every pass (each iteration deriving from the last), after fifty iterations the lineage would be fifty layers deep, a single failure would replay all fifty, and even planning would slow as the DAG bloated — the fix is a periodic checkpoint that writes the current RDD to HDFS and truncates the ancestry, capping both recovery cost and DAG size. Same lineage machinery, three very different operational outcomes depending on where you place cache and checkpoint.