The idea: an RDD is a recipe, not data

In Apache Spark an RDD (resilient distributed dataset) is a collection cut into partitions that live on different machines. But an RDD object in your program holds no records. It holds a recipe: which RDD it comes from and which function to apply. The chain of recipes back to the input file is the RDD's lineage. Spark computes real records only when the program asks for a result, and it can compute any partition again from its lineage if the copy is lost.

From code to tasks, left to right. Transformations in the driver program build a lineage graph of five RDDs: sales, pairs, big, totals, points. Nothing runs. An action, collect, hands the graph to the DAG scheduler, which cuts it at the shuffle into stage 0 and stage 1. Each stage becomes one task per partition, and the tasks run on executors E1 and E2.
Transformations only grow the graph in the driver; an action turns the graph into stages, and each stage into one task per partition.

The page runs a five-line program on a tiny file of sales, product,amount, stored in two HDFS blocks. There is one driver (your program) and two executors, E1 and E2, which run the tasks. Every RDD has 2 partitions; partition 0 is computed on E1 and partition 1 on E2.

RDDLine of the programPartition 0Partition 1
salessc.textFile("sales.csv", 2)tea,3 milk,5 tea,4jam,2 milk,6 tea,1
pairssales.map(parse)(tea,3) (milk,5) (tea,4)(jam,2) (milk,6) (tea,1)
bigpairs.filter(v >= 2)(tea,3) (milk,5) (tea,4)(jam,2) (milk,6)
totalsbig.reduceByKey(_ + _)(tea,7) (jam,2)(milk,11)
pointstotals.mapValues(_ * 10)(tea,70) (jam,20)(milk,110)

On the canvas a box is one partition. A white box that says (no data) is only a recipe. Orange means a task is computing it now, blue means it is cached in executor memory, green is a shuffle file on an executor's disk, and red was lost with its executor.

Transformations are lazy, actions run jobs

A transformation makes a new RDD from an old one. Calling it does no work: the driver only adds a node and its arrows to the lineage graph. In Demo 1 all five lines run and the counters still show 0 jobs, 0 tasks and 0 partitions computed. The file has not even been opened.

An action returns a value to the driver or writes output, so it needs real records. Each action starts one job. Being lazy lets Spark see the whole chain before it runs anything, so it can put several steps into one task and skip work that no action needs.

KindExamplesWhat the call does
Transformation, narrowmap, filter, flatMap, mapValues, unionadds an RDD to the lineage; returns at once
Transformation, widereduceByKey, groupByKey, join, repartition, sortByKeyadds an RDD and a shuffle to the lineage; returns at once
Actioncollect, count, take, reduce, saveAsTextFilestarts a job and waits for its result

Narrow and wide dependencies

A dependency is narrow when each partition of the parent is used by at most one partition of the child. map and filter are narrow: partition 1 of big needs only partition 1 of pairs. The work stays on one executor, and no record moves.

A dependency is wide when a child partition needs records from many parent partitions. reduceByKey must add up all amounts of tea, and tea is in both partitions of big. So Spark does a shuffle: every map-side task writes its records to a shuffle file on local disk, grouped by target partition (hash(key) mod 2), and every task on the other side fetches its share from each file. On the page the hash is the sum of the letter codes, so tea and jam go to partition 0 and milk goes to partition 1. reduceByKey also adds up equal keys before writing, so partition 0 writes (tea,7), not two tea records: 4 records cross the shuffle instead of 5. MapReduce shows this combine step, the partitioner and the sort in detail.

Two small graphs side by side. Left, narrow dependency, filter: partition 0 of pairs feeds only partition 0 of big, and partition 1 feeds only partition 1; the arrows are parallel and both steps run in one task per partition. Right, wide dependency, reduceByKey: both partitions of big feed both partitions of totals; the four arrows cross, the records pass through shuffle files, and a stage boundary is drawn through the crossing.
Parallel arrows can share a task; crossing arrows need a shuffle, and a shuffle ends the stage.

Stages and tasks

When an action is called, the driver's DAG scheduler walks the lineage backwards from the target RDD. It keeps going through narrow dependencies and cuts at every wide one. Each piece is a stage. A stage runs as one task per partition, and a task runs the whole narrow chain of its stage for its own partition, record after record, without storing the steps in between.

In Demo 2, points.collect() gives two stages. Stage 0 is a shuffle map stage: 2 tasks read their block, run sales → pairs → big and write shuffle files. Stage 1 is the result stage: 2 tasks read the shuffle, run totals → points and send their records to the driver. That is 4 tasks and 10 RDD partitions computed (5 RDDs × 2 partitions). Stage 1 cannot start before stage 0 has finished, because it needs every shuffle file. The stages form a graph with no cycles, and Spark runs them in an order where parents come first, the same idea as a topological sort.

In Demo 3 the program stops after big. big.collect() meets only narrow dependencies, so the job has one stage, 2 tasks and no shuffle at all.

A second action, and cache()

When a job ends, the partitions it computed are gone: they were only streams of records passing through the tasks. So a second action starts again from the lineage. In Demo 4, points.count() after points.collect() computes totals and points a second time. It does not rerun the first stage, but only because the shuffle files are still on the executors' disks; the Spark UI shows that stage as skipped.

cache() marks an RDD so that executors keep its partitions in memory when they are first computed (it is short for persist(MEMORY_ONLY)). It is lazy too: nothing is stored until an action runs. In Demo 5 the first job fills two blue blocks, and the second job finds both. It still runs 2 tasks, but they compute nothing.

Second action, points.count()Stage 2 (map)Stage 3 (result)RDD partitions computedCache hits
no cache (Demo 4)skipped2 tasks40
points.cache() (Demo 5)skipped2 tasks02
cache, then E2 is lost (Demo 6)1 task2 tasks51

Cache an RDD that is used by more than one action and is costly to compute. Caching everything wastes memory: when memory runs out, Spark drops old blocks and computes them again from lineage when needed.

A lost partition is recomputed from lineage

Spark does not copy RDD partitions to other machines to survive a crash. It keeps the lineage in the driver, which is small, and recomputes. In Demo 6 executor E2 dies after the first job. Two things die with it: the cached block points[1] and the shuffle file that map task 1 wrote. The block points[0] and the other shuffle file, on E1, are fine.

The next action needs points[1] again. The DAG scheduler follows its lineage back: points[1] needs totals[1], which needs both shuffle files, and one is missing. So the map stage runs again with 1 task, for partition 1 only: it reads block 1 from HDFS again (HDFS keeps replicas, see HDFS read and write) and rewrites the file. Then the result stage computes totals[1] and points[1], while partition 0 is a cache hit. Only 5 of the 10 RDD partitions are computed again, and the answer is the same, 3.

The lineage graph after executor E2 is lost, with two rows of partitions. Top row, E1: the shuffle file of map task 0 and the cached block points 0 are kept, marked with a tick; sales 0, pairs 0, big 0 and totals 0 are not needed. Bottom row, the new E2: sales 1, pairs 1, big 1, the shuffle file of map task 1, totals 1 and points 1 are all computed again, in orange. An arrow from the kept shuffle file on E1 also feeds totals 1. Caption inside: 5 of 10 partitions recomputed.
Only the path that leads to the lost block is rebuilt: 5 partitions and one shuffle file, not the whole job.

This works because transformations are deterministic and the input is still there. Recomputing is cheap when the lineage is short and narrow, and costly when it is long or crosses several shuffles.

See also MapReduce, where every job is one map stage and one reduce stage with output written to HDFS, and Range vs Hash Partitioning for how keys are assigned to partitions.

See also Stream Windows and Watermarks for Spark Structured Streaming's windows, withWatermark and late data on a stream instead of a fixed batch.

See also Lambda vs Kappa architecture, where a Spark batch job recomputes the batch view and a stream job keeps the realtime view.

What the page leaves out

Real jobs have hundreds of partitions and many executors, and a partition can run on any executor; the page pins partition 0 to E1 and partition 1 to E2. Inside a task Spark pipes one record at a time through the whole narrow chain; the page shows one RDD per step. The driver here learns about the lost executor at once; in practice a task often finds out through a failed shuffle fetch, and the stages are then resubmitted. An external shuffle service can keep shuffle files alive when an executor dies. Left out as well: other storage levels (MEMORY_AND_DISK), checkpoint(), which saves an RDD to HDFS and cuts its lineage, unpersist(), task retries and speculation, data locality, broadcast variables and accumulators, and the DataFrame API, whose Catalyst optimizer rewrites the plan before it becomes RDDs. Simplifications: the hash is the sum of the letter codes, and results are shown in partition order.

On the mind map

Open the Distributed Systems mind mapDistributedSystemsReplication: copies of data · what reads seeReplicationPartitioning: split data over nodesPartitioningTime and membership: order events, know who is aliveTime and membershipConsensus: agree on one value or logConsensusTransactions: one change across many servicesTransactionsMessaging: send events between systemsMessagingKafka internals: a replicated append-only logKafka internalsRedis internals: one thread, data in memoryRedis internalsKubernetes: reconcile desired stateKubernetesResilience and speed: stay up and fast under loadResilience and speedPartitioning vs shardingPartitioning vs shardingone server vs many; shard key mattersConsistent hashingConsistent hashingring: adding a node moves few keysBitTorrent and the DHTBitTorrent and the DHTEvery downloader also uploadsRange vs hash partitioningRange vs hash partitioningrange: fast scans; hash: no hot spotRebalancing partitionsRebalancing partitionsmod N vs fixed vs dynamic: keys movedRedis ClusterRedis Cluster16384 hash slots, MOVED and ASKMapReduceMapReducemap, shuffle by key, reduceSpark RDD lineageLazy recipe; shuffle cuts stagesMapReduce joinsMapReduce joinssort-merge, skew, broadcast and merge joinsS3 object storageS3 object storagedata plus parity shards rebuild a fileRendezvous hashingRendezvous hashinghighest hash score of key+node winsHDFS / GFS file layoutHDFS / GFS file layoutNamenode maps blocks; datanodes pipelineOpen the Distributed Systems mind mapDistributed Systemssplit data over nodesPartitioningPartitioning vs shardingPartitioning vs shardingone server vs many; shard key mattersConsistent hashingConsistent hashingring: adding a node moves few keysBitTorrent and the DHTBitTorrent and the DHTEvery downloader also uploadsRange vs hash partitioningRange vs hash partitioningrange: fast scans; hash: no hot spotRebalancing partitionsRebalancing partitionsmod N vs fixed vs dynamic: keys movedRedis ClusterRedis Cluster16384 hash slots, MOVED and ASKMapReduceMapReducemap, shuffle by key, reduceSpark RDD lineageLazy recipe; shuffle cuts stagesMapReduce joinsMapReduce joinssort-merge, skew, broadcast and merge joinsS3 object storageS3 object storagedata plus parity shards rebuild a fileRendezvous hashingRendezvous hashinghighest hash score of key+node winsHDFS / GFS file layoutHDFS / GFS file layoutNamenode maps blocks; datanodes pipeline
This page on the Distributed Systems mind map · 88 pages in 10 branches · open it to see the whole map and test yourself in recall mode.