From MapReduce to Spark

"MapReduce and I agreed on the answer every time. We just disagreed about how many times we should drive to the disk to find it."

An Iterative Job That Read the Same Data Ninety Times

In Chapter 6 we built the MapReduce model from first principles: split the input across machines, apply a map to each record, shuffle records by key, and apply a reduce to each group. That model is one of the most consequential ideas in distributed computing, and the discipline it teaches (think in terms of partitioned data, key-based shuffles, and idempotent re-execution) carries directly into everything that follows. But by the end of that chapter, in Section 6.9, one limitation had become impossible to ignore, and it is the limitation that brought Spark into existence. Every MapReduce stage reads its input from disk and writes its output back to disk before the next stage may begin. For a single pass over the data, that cost is paid once and amortized away. For the workloads AI actually runs, it is paid again and again.

Those workloads are iterative. Training a model by gradient descent revisits the same dataset every epoch. PageRank multiplies the same graph by the same vector until it converges, often a hundred times. k-means reassigns the same points to centroids round after round. A feature pipeline cleans, joins, aggregates, and encodes the same records through a dozen sequential stages. Under MapReduce, each of those rounds is a separate job that re-reads the entire working set from disk, performs a little computation, and writes the result back out for the next round to re-read. The useful work is dwarfed by the bookkeeping. Spark was designed to delete that bookkeeping, and Figure 7.1.1 shows the contrast that motivated it.

1. The Disk Round-Trip That MapReduce Could Not Avoid Beginner

The disk round-trip in MapReduce is not an implementation accident; it is load-bearing. Writing every intermediate result to a replicated distributed file system is exactly what makes the model fault tolerant. If a worker dies mid-job, the scheduler re-runs that worker's task on another machine, and the inputs it needs are sitting safely on disk where the previous stage left them. Reliability and the disk round-trip are, in the original design, the same decision. The cost of that decision is invisible for a single pass over the data and crippling for anything that loops.

Put a number on it. Reading a large partition from a distributed file system runs in the tens to hundreds of megabytes per second per stream; the actual transformation applied to those bytes, a multiply-add or a comparison, runs orders of magnitude faster. For a one-pass aggregation, the read happens once and disappears into the noise. For an iterative algorithm that runs the same data through one hundred rounds, the same bytes are read from disk one hundred times, and the job spends the overwhelming majority of its wall-clock moving data it already had, not computing anything new. The Chapter 3 performance models make this precise: when the per-iteration data-movement cost dominates the per-iteration compute, total time scales with the number of iterations times the cost of re-reading, and adding machines does not help, because each machine still re-reads its own partition every round.

2. Spark's Three Moves: Memory, DAG, and Lineage Beginner

Spark keeps almost everything MapReduce got right. Data is still partitioned across machines, work is still expressed as transformations applied independently to each partition, key-based shuffles still move records between machines, and failed work is still re-executed rather than mourned. What changes is three connected design moves, and they are worth naming separately because each later section of this chapter develops one of them.

The first move is to keep working sets in memory across stages. Spark's core abstraction, the resilient distributed dataset, is a partitioned collection that can be held in cluster memory and reused by many operations without ever touching disk between them. The second move is to express the whole pipeline, not one stage at a time, as a directed acyclic graph of transformations. Because Spark sees the entire graph before it runs anything, it can fuse adjacent operations, avoid materializing intermediates, and schedule the work as one optimized plan rather than a chain of independent jobs. The third move is to recover from failure through lineage. Instead of relying on replicated on-disk copies, Spark records the sequence of transformations that produced each partition; if a partition is lost, it is recomputed from its inputs by replaying that recorded recipe. Reliability survives, but the disk round-trip that paid for it does not.

These three are one idea seen from three sides. Holding data in memory is only safe if you can recover it after a crash, which is what lineage provides; lineage is only cheap to record if the computation is a graph of deterministic transformations, which is what the DAG provides; and the DAG is only worth optimizing if its intermediate results can live in memory, which is what the resilient distributed dataset provides. The next three sections of this chapter take them in turn: resilient distributed datasets in Section 7.2, the DataFrame and SQL layer built on top of them in Section 7.3, and lazy DAG execution in Section 7.4.

3. Modeling the Speedup From First Principles Intermediate

The argument so far is qualitative; let us make it quantitative with a cost model and a runnable demonstration. Consider an iterative job of $T$ iterations over a fixed working set. Let $r_{\text{disk}}$ be the time to load that working set from disk, $r_{\text{mem}}$ the time to touch it when it already lives in memory, and $c$ the useful compute per iteration. Both engines pay one cold read $r_{\text{disk}}$ to bring the data in the first time. After that, the MapReduce-style job pays $r_{\text{disk}}$ again at every subsequent iteration, while the Spark-style job pays only $r_{\text{mem}}$. The two total times are

Because $r_{\text{disk}} \gg r_{\text{mem}}$, the speedup grows with the number of iterations and with how much the disk read dominates the compute. The script below models exactly this, running a small real per-iteration loop so the timings are concrete rather than asserted, and reports the modeled wall-clock for each engine, their ratio, and the fraction of time each one wastes outside of useful compute.

import time

# Model an iterative job over a fixed working set. Each iteration does the same
# fixed amount of CPU "compute"; the only difference is where the working set lives
# at the START of each iteration.
#
#   MapReduce style: every stage materializes its output to disk, so the NEXT
#   iteration must re-read the whole working set back from disk.
#   Spark style:     the working set is cached in memory after the first read,
#   so every later iteration skips the disk read entirely.

N_ROWS = 2_000_000          # rows in the working set
ITERS = 10                  # iterations of an iterative algorithm (PageRank, k-means, GD)
DISK_READ_S_PER_ITER = 0.90 # cost to re-load the working set from disk, one iteration
MEM_READ_S_PER_ITER = 0.03  # cost to touch the same set already resident in memory
COMPUTE_S_PER_ITER = 0.20   # the actual useful work per iteration (identical for both)

def run(reload_cost):
    # Simulate one iterative job; return modeled wall-clock seconds.
    total = 0.0
    workset = [i & 0xFF for i in range(N_ROWS)]   # the working set, built once (first read)
    first = True
    for _ in range(ITERS):
        if first:
            total += DISK_READ_S_PER_ITER          # both pay one initial cold read
            first = False
        else:
            total += reload_cost                   # MapReduce re-reads; Spark hits memory
        s = 0
        for v in workset[:50_000]:                 # a small real loop so timing is non-trivial
            s += v
        total += COMPUTE_S_PER_ITER                # the same per-iteration useful work
    return total

mapreduce_s = run(DISK_READ_S_PER_ITER)   # re-materialize to disk every round
spark_s = run(MEM_READ_S_PER_ITER)        # cache once, stay in memory

print(f"iterations                : {ITERS}")
print(f"working set rows          : {N_ROWS:,}")
print(f"MapReduce (disk each iter): {mapreduce_s:6.2f} modeled seconds")
print(f"Spark (cached in memory)  : {spark_s:6.2f} modeled seconds")
print(f"speedup                   : {mapreduce_s / spark_s:5.2f}x")

iterations                : 10
working set rows          : 2,000,000
MapReduce (disk each iter):  11.00 modeled seconds
Spark (cached in memory)  :   3.17 modeled seconds
speedup                   :  3.47x

The numbers are modeled, not measured on a cluster, but the structure is exactly right: the only difference between the two runs is whether the working set is re-read from disk each iteration or kept in memory, and that single difference produces the speedup. Notice what did not change. Both engines perform identical per-iteration compute and reach the identical answer; Spark is not approximating anything, just as the data-parallel gradient in Section 1.1 was exact. The win is entirely in the data movement that surrounds the compute, which is why this section sits at the head of a chapter about a faster engine and not a different one.

4. The Payoff for AI: Iteration and One Unified Engine Intermediate

Two consequences of these design moves matter most for the AI practitioner. The first is speed on exactly the workloads AI runs. Iterative optimization, graph algorithms such as PageRank, and multi-stage feature engineering all reuse the same working set many times, and all of them see the order-of-magnitude improvement that Output 7.1.1 sketches in miniature. A feature pipeline that joins, aggregates, and encodes a dataset through a dozen stages no longer writes and re-reads the data a dozen times; it streams through the whole graph with intermediates held in memory. The classical distributed machine learning of Chapter 12 is built directly on this capability.

The second consequence is unification. Because resilient distributed datasets and the DAG executor are general, Spark grew a family of libraries that share one engine and one data abstraction: SQL and DataFrames for structured queries, structured streaming for unbounded data, MLlib for machine learning, and GraphX for graphs. A practitioner can read raw logs with Spark SQL, engineer features with DataFrame operations, train a model with MLlib, and stream fresh data through the same cluster, without stitching together four separate systems with four separate data formats. That unified engine is the reason Spark became the default substrate for data preparation in machine learning, and it is why streaming gets its own treatment in Chapter 9 rather than living as an afterthought.

# Illustrative PySpark; needs a JVM + Spark runtime, not run in this section.
from pyspark.sql import SparkSession

spark = SparkSession.builder.appName("iterative").getOrCreate()
points = spark.read.parquet("s3://bucket/working_set")  # read from disk ONCE
points.cache()                                          # keep it resident in memory

centroids = init_centroids(points)
for _ in range(100):                                    # 100 iterations of k-means
    # every pass reads `points` from MEMORY, not disk, because of cache()
    centroids = (points
                 .withColumn("c", nearest(points, centroids))
                 .groupBy("c").mean()
                 .collect())

5. What This Chapter Builds Beginner

The rest of Chapter 7 turns the three design moves of Section 2 into working knowledge, in the order the ideas depend on one another. Table 7.1.1 is the map. Resilient distributed datasets come first because everything else is built on them; DataFrames and Spark SQL add a structured, optimizable layer on top; lazy evaluation explains why Spark waits until an action before running anything and how the DAG is planned; transformations and actions, partitioning and caching, and joins and shuffles are the day-to-day vocabulary of writing efficient Spark; and the chapter closes with PySpark for AI workloads and the performance tuning that turns a correct job into a fast one.

One caution sets the honest scope. Keeping the working set in memory wins only when it fits, or mostly fits, in cluster memory and is reused enough times to amortize the first read. A genuinely single-pass job over data far larger than memory gains little from Spark's central trick, and Spark spills to disk gracefully when the data does not fit, which costs back some of the advantage. The skill, as always in this book, is matching the tool to the workload: Spark earns its keep on iterative and multi-stage pipelines, which is most of what AI data preparation consists of, and the partitioning and caching choices of Section 7.6 are where you tell it which working sets are worth keeping resident.

We now have the thesis of the chapter (keep the working set in memory, plan the whole pipeline as a graph, recover by lineage rather than re-reading) and a cost model that shows why it matters for the iterative workloads AI runs. The next section makes the abstraction concrete by building the resilient distributed dataset itself: what it is, how its partitions and lineage work, and why it can sit in memory and still survive a worker's death. That construction begins in Section 7.2.