Narrow and Wide Dependencies

Narrow and wide dependencies describe how the partitions of one distributed dataset relate to the partitions of the dataset it was derived from. The distinction comes from the 2012 RDD paper by Zaharia and colleagues, which classifies dependencies into two types: “narrow dependencies, where each partition of the parent RDD is used by at most one partition of the child RDD, wide dependencies, where multiple child partitions may depend on it.” A map creates a narrow dependency; a join generally creates a wide one, unless the inputs are already partitioned by the join key.

Why the distinction decides how work runs

The paper gives two reasons. The first is execution: narrow dependencies “allow for pipelined execution on one cluster node,” so a filter after a map can be computed element by element without any data leaving the machine. Wide dependencies, by contrast, “require data from all parent partitions to be available and to be shuffled across the nodes using a MapReduce-like operation.”

That is exactly where an engine draws a stage boundary. Everything joined by narrow dependencies collapses into one pipeline; the first wide dependency forces a redistribution of rows, and a new stage begins after it. Counting the wide dependencies in a query is therefore the same as counting the shuffles it will perform.

The right-hand column is not a list of mistakes. Grouping and joining are the point of most analytical work; the aim is to do them once, on as little data as possible, rather than to avoid them.

The recovery consequence

The second reason the paper gives is failure recovery, and it is less widely known. With a narrow dependency, only the lost parent partitions need to be recomputed, and that can happen in parallel on other nodes. With wide dependencies in the lineage, “a single failed node might cause the loss of some partition from all the ancestors of an RDD, requiring a complete re-execution.”

This is why the paper suggests checkpointing for datasets with long lineage graphs containing wide dependencies, while noting that for datasets with narrow dependencies on data in stable storage, checkpointing “may never be worthwhile.” Recomputation is cheap when the work is local and expensive when it is not.

How these boundaries show up as stages and tasks, and what to do when one of them is slow, is worked through in How Spark Decides What to Run.

References: Matei Zaharia et al., Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, NSDI 2012.