Definition
- Lineage – for every RDD, Spark records the directed acyclic graph (DAG) of transformations that produced it, storing the recipe as cheap metadata in the Driver.
- Targeted recomputation – when an executor fails and partitions are lost, the Driver replays the lineage of only the missing partitions rather than restarting the whole job.
- Correctness guarantee – RDDs are immutable and transformations are pure functions, so replaying the recipe on the same parent data produces exactly the same result.
- Checkpointing – for very long lineage chains, checkpointing writes an RDD to reliable storage and truncates the lineage so recovery is bounded.
Imagine the National Bank of India keeps, for every summary report, not a photocopy but the exact recipe: take the raw transaction box, filter Rajesh's slips, and total the amounts. If a clerk's desk catches fire and one summary page is destroyed, the manager does not redo the entire day's work and does not need a backup photocopy. He re-runs that one recipe on the original transaction box and reproduces exactly that one page. Because the recipe is written down and the raw box never changes, the rebuilt page is identical to the lost one.
Understanding the Concepts
What is lineage in Spark?
Lineage is the recorded chain of transformations that produced each RDD or DataFrame. Each RDD knows its parent RDDs and the transformation that derives it from them. This chain forms a directed acyclic graph (DAG) held as metadata in the Driver – it stores the recipe, not the data.
from pyspark.sql import SparkSession, functions as F
spark = SparkSession.builder.appName("LineageDemo").getOrCreate()
raw = spark.read.parquet("/lake/bronze/transactions")
filtered = raw.filter(F.col("amount") > 10000)
totals = filtered.groupBy("account_id").agg(F.sum("amount").alias("total"))
# The logical plan shows the full lineage
totals.explain(True)
== Analyzed Logical Plan ==
Aggregate [account_id], [account_id, sum(amount) AS total]
+- Filter (amount > 10000)
+- Relation[txn_id, account_id, amount, ...] parquet
This plan is the lineage. Spark can replay it from any point to rebuild any partition.
How does Spark detect a failure?
The Driver monitors every executor through heartbeats. When an executor stops sending heartbeats or a task on it fails, the Driver marks the executor as lost. Any partitions that executor held – including cached partitions – are marked as unavailable.
# If the executor holding partition 3 of 'totals' crashes,
# the Driver detects it and re-schedules only partition 3
totals.cache()
totals.count() # materializes the cache across executors
# Executor 2 crashes here – partition 3 is lost
# Spark re-derives partition 3 by replaying the lineage:
# read partition 3 of raw -> filter -> aggregate
The recomputation is invisible to the application. The next action that needs partition 3 simply takes longer while it is rebuilt.
Why is recomputation correct?
Recomputation produces the exact same result because of two guarantees: immutability and determinism.
# Immutability: raw never changes after creation
raw = spark.read.parquet("/lake/bronze/transactions")
# Determinism: filter is a pure function – same input, same output
filtered = raw.filter(F.col("amount") > 10000)
# Replaying the filter on the same raw partition always yields
# the same filtered partition, bit for bit
If the parent partition itself was also lost, the scheduler recurses further up the lineage until it reaches partitions that still exist or the base data in reliable storage, then recomputes forward.
How do narrow and wide dependencies affect recovery cost?
Narrow dependencies make recovery cheap because a lost child partition depends on just one parent partition. Wide dependencies are costlier because recovering a post-shuffle partition may require recomputing many parent partitions and re-running the shuffle.
# Narrow: recovering partition 3 of 'filtered' needs only
# partition 3 of 'raw' – one parent, one task
filtered = raw.filter(F.col("amount") > 10000)
# Wide: recovering partition 3 of 'totals' after the shuffle
# may need data from ALL parent partitions that contributed to it
totals = filtered.groupBy("account_id").agg(F.sum("amount"))
This is why checkpointing is especially important after expensive wide transformations – it caps the recomputation cost.
What is checkpointing and when do you use it?
Checkpointing writes an RDD or DataFrame to reliable storage (HDFS or S3) and truncates the lineage, so future recovery starts from the checkpoint instead of replaying the entire chain.
# Set the checkpoint directory
spark.sparkContext.setCheckpointDir("/lake/checkpoints")
# Iterative ML training builds very long lineage chains
from pyspark.ml.feature import VectorAssembler
features = VectorAssembler(
inputCols=["amount", "tx_count", "avg_balance"],
outputCol="features"
).transform(totals)
# Checkpoint after expensive preparation
features.checkpoint()
# Lineage is now truncated – recovery starts from this file
Without checkpointing, an iterative algorithm that appends transformations each iteration builds a lineage hundreds of steps deep, making recovery after a failure very expensive.
How is lineage different from data replication?
Hadoop HDFS replicates every block three times for fault tolerance, which is simple but triples storage cost. Spark's lineage stores only a lightweight recipe and recomputes on demand.
| Aspect | Replication (HDFS) | Lineage (Spark) |
|---|---|---|
| Storage cost | 3x the data | Only metadata |
| Recovery speed | Instant (read replica) | Recomputation time |
| Correctness | Bit-identical copy | Deterministic replay |
| Best for | Base storage layer | In-memory computation |
# Lineage metadata is tiny – just the transformation recipe
print(totals.explain(True)) # a few KB of plan text
# vs. replicating the full dataset three times on disk
Spark uses lineage for in-memory computation and relies on HDFS or S3 replication for the base data that sits at the root of the lineage.
Why is cache not a durability guarantee?
Caching is a performance optimization. A cached partition is the result of evaluating the lineage, stored in memory or on local disk for faster access. If it is lost, Spark transparently recomputes it from lineage.
totals.cache() # performance hint, not durability
totals.count() # materializes the cache
# If executor memory is tight, Spark can evict cached partitions
# under MEMORY_ONLY, dropped partitions are simply recomputed
# under MEMORY_AND_DISK, they spill to local disk first
To make data durable, you write it to reliable storage with df.write, not rely on cache.
What should a senior engineer know?
- Lineage-based fault tolerance means Spark jobs are resilient to individual executor failures without any application-level retry logic.
- The cost of recovery depends on the lineage depth and the ratio of narrow to wide dependencies.
- For streaming, structured streaming uses write-ahead logs and checkpoints that combine lineage truncation with offset tracking for exactly-once processing.
- In production, set checkpoint directories on reliable storage, checkpoint after expensive shuffles, and monitor executor failures in the Spark UI.
# Production pattern: checkpoint after an expensive shuffle join
enriched = txn.join(accounts, "account_id")
enriched.checkpoint() # truncates lineage, caps recovery cost
# Subsequent operations start from the checkpointed data
gold = enriched.groupBy("branch_code").agg(
F.sum("amount").alias("branch_total")
)
What are common interview follow-up questions?
- What happens if the Driver itself fails? The Driver is a single point of failure; the job must be restarted from scratch (or from the last external checkpoint in streaming).
- Does lineage work with external data sources? The root of the lineage is the reliable external source (HDFS, S3), so Spark can always re-read base data.
- How does lineage interact with accumulators and broadcast variables? Accumulators may double-count on recomputation; broadcast variables are re-sent to the replacement executor.
Visual Overview
Lineage-Based Recovery
──────────────────────
Reliable Storage (S3 / HDFS)
│
▼
┌──────────────────┐
│ raw (parquet) │ ← base data, always available
└────────┬─────────┘
│ filter(amount > 10000)
▼
┌──────────────────┐
│ filtered │ ← narrow: 1 parent per partition
└────────┬─────────┘
│ groupBy + sum (shuffle)
▼
┌──────────────────┐
│ totals │ ← wide: many parents per partition
└──────────────────┘
If partition 3 of 'totals' is lost:
┌───────────────────────────────────────┐
│ 1. Driver detects missing heartbeat │
│ 2. Looks up lineage of partition 3 │
│ 3. Recomputes: re-read → filter → │
│ shuffle → aggregate │
│ 4. Only partition 3, not the job │
└───────────────────────────────────────┘
Key Takeaway
Spark achieves fault tolerance through lineage, which is a fundamentally different approach from replicating data. For every RDD, Spark records the directed acyclic graph of transformations that produced it – the recipe for deriving each partition from its parents – and keeps this lineage as cheap metadata in the Driver. When an executor fails and its partitions are lost, the Driver does not restart the whole job; it consults the lineage of the lost partitions and recomputes only those by re-applying their transformations to their parent partitions.
This works correctly because RDDs are immutable and transformations are deterministic. Replaying the recipe on the same parent data produces exactly the same result. Narrow dependencies make recovery cheap because a lost child partition depends on just one parent, while wide dependencies are costlier because a post-shuffle partition may need data from many parents. For deeply iterative work where lineage chains grow very long, checkpointing materializes an RDD to reliable storage and truncates the lineage, bounding recovery cost.
At the National Bank of India this meant that a single executor dying during a long nightly aggregation caused only a small, localized recompute rather than an expensive full restart. We checkpointed after the most expensive shuffle join in our pipeline so that any failure downstream would replay from the checkpoint, not from the raw files. Caching was used for speed but never confused with durability – a lost cached partition was simply recomputed transparently.
Remember one sentence: Spark stores the recipe, not the copy, so when a partition is lost it replays the lineage to rebuild only that partition, making jobs resilient to executor failures without restarting the whole job.
---