On this page

MapReduce & Apache Spark: Distributed Batch Processing

In December 2004, Jeffrey Dean and Sanjay Ghemawat presented "MapReduce: Simplified Data Processing on Large Clusters" at OSDI. Google was running hundreds of special-purpose programs that each processed terabytes of crawled documents and logs. Each one reinvented the same machinery: split the input, spread work across machines, handle the machines that died partway, collect the results. MapReduce took that machinery and hid it behind two functions a programmer could write in an afternoon.

Eight years later, Matei Zaharia and colleagues at UC Berkeley's AMPLab presented "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing" at NSDI 2012, where it won the best paper award. It described Spark, which kept MapReduce's central insight — recover from failure by recomputing, not by replicating — and fixed its biggest weakness: every job wrote everything to disk between steps, so iterative and interactive workloads were painfully slow.

Together these two papers explain almost every batch engine you'll meet: Hadoop, Spark, Flink's batch mode, Beam/Dataflow, Hive, Presto/Trino's execution model, and the engines inside modern lakehouses. This page goes through both, with worked examples, the papers' own numbers, and what changed after them.

Related pages

For practical batch pipeline patterns (partitioning, checkpointing, resource tuning) see Batch Processing. For streaming see Stream Processing. MapReduce read its input from GFS — see GFS & HDFS.


Part I — MapReduce

1. The Problem It Was Built to Solve

1.1 Google in 2003

Google's computations were conceptually simple: count word frequencies, build an inverted index, compute the graph of links between pages, summarise the number of pages crawled per host, find the most frequent queries in a day. The difficulty wasn't the logic. It was that the input was too large for one machine — terabytes then — so the work had to be spread across hundreds or thousands of machines, and at that scale some machines fail during almost every long job.

Every team wrote its own code for parallelisation, data distribution, load balancing and fault tolerance. That code was larger and buggier than the actual computation.

1.2 The constraints

The paper's environment shaped the design:

ConstraintDetail from the paperConsequence
Commodity machinesDual-processor x86 Linux boxes, 2–4 GB memory, cheap IDE disksFailures are normal; design for re-execution
Modest network100 Mb/s or 1 Gb/s per machine, much less bisection bandwidth per machineNetwork bandwidth is the scarce resource — move computation to data
StorageGFS on the same machines, files split into 64 MB blocks, typically 3 replicasInput blocks have known locations; the scheduler can use them
UsersEngineers with no distributed systems backgroundThe API must hide all distribution
WorkloadLarge batch jobs; latency of minutes to hours is fineOptimise throughput and robustness, not response time

1.3 The insight

Many computations follow the same shape: apply a function to every input record to produce intermediate key/value pairs, then group all values with the same key and combine them. This is a functional-programming idea (from Lisp's map and reduce), and its value is that both functions are pure — so the system may run them anywhere, as many times as it likes. Re-running a deterministic task is always safe. That one property makes fault tolerance, stragglers and load balancing easy problems.


2. The Programming Model

The user writes two functions:

The framework guarantees that all values with the same intermediate key reach the same reduce call. Everything else — where tasks run, how data moves, what happens on failure — is the framework's job.

2.1 Word count

The paper's own first example. Here is a small, runnable Python simulation of the model (single process, but the same structure):

from collections import defaultdict
from itertools import chain

def map_fn(doc_id, text):
    for word in text.lower().split():
        yield word, 1

def reduce_fn(word, counts):
    yield word, sum(counts)

def run_mapreduce(inputs, map_fn, reduce_fn, R=3):
    # Map phase: each input split is processed independently.
    partitions = [defaultdict(list) for _ in range(R)]
    for k1, v1 in inputs:
        for k2, v2 in map_fn(k1, v1):
            partitions[hash(k2) % R][k2].append(v2)   # partition function
    # Shuffle is implicit above. Reduce phase: each partition independently, keys sorted.
    return dict(chain.from_iterable(
        reduce_fn(k, vs) for part in partitions for k, vs in sorted(part.items())))

docs = [("d1", "the cat sat"), ("d2", "the cat ran"), ("d3", "a dog sat")]
result = run_mapreduce(docs, map_fn, reduce_fn)
assert result == {"the": 2, "cat": 2, "sat": 2, "ran": 1, "a": 1, "dog": 1}

2.2 More examples from the paper

The paper lists programs that fit naturally:

Taskmap emitsreduce does
Distributed grepthe line, if it matchesidentity
URL access frequency(URL, 1) per log linesum
Reverse web-link graph(target, source) for each linklist of sources per target
Term vector per host(hostname, term vector)add vectors, drop rare terms
Inverted index(word, document id)sorted list of document ids
Distributed sort(key, record)identity — relies on sorted partitions and a range partitioner

2.3 A join, worked through

Joins are where MapReduce stops being trivial. Suppose:

  • users(user_id, country) — 10 million rows
  • orders(order_id, user_id, amount) — 2 billion rows

We want total order amount per country.

Reduce-side (repartition) join. Tag each record with its source and use user_id as the key, so a user's row and all their orders meet in one reduce call:

def map_join(source, record):
    if source == "users":
        user_id, country = record
        yield user_id, ("U", country)
    else:
        order_id, user_id, amount = record
        yield user_id, ("O", amount)

def reduce_join(user_id, tagged):
    country, total = None, 0
    for tag, value in tagged:
        if tag == "U":
            country = value
        else:
            total += value
    if country is not None:
        yield country, total          # feeds a second job that sums per country

This needs a second MapReduce job to sum per country. Multi-step pipelines of jobs, each writing its output to GFS, are normal in MapReduce — and are exactly what Spark later made cheaper.

There are three problems to discuss in an interview:

  1. Every order moves across the network in the shuffle, though only the amount and country are needed.
  2. Skew. If one user has 50 million orders (a bot, a test account), one reducer gets them all and the job waits for it.
  3. Memory. reduce_join assumes it can buffer the tagged values; the "U" record may arrive last. The standard fix is a secondary sort so the user record sorts first within the key.

Map-side (broadcast) join. If users is small enough to fit in memory on each worker (10 million rows × ~20 bytes ≈ 200 MB is fine), give every map task a copy and look up country while mapping orders. No shuffle of orders by user is needed; each map task emits (country, amount), and a combiner pre-sums per country before the shuffle. Spark calls this a broadcast hash join, and optimisers pick it automatically when one side is small.


3. Execution

3.1 Architecture

flowchart TB
    U["User program<br/>(map, reduce, M, R)"] -->|"fork"| Ma["Master"]
    U -->|"fork"| W1
    U -->|"fork"| W2
    U -->|"fork"| W3

    subgraph GFSIn["Input in GFS — M splits of 16–64 MB"]
        S0["split 0"]
        S1["split 1"]
        S2["split 2"]
    end

    subgraph MapPhase["Map workers"]
        W1["worker 1<br/>map task 0"]
        W2["worker 2<br/>map task 1"]
        W3["worker 3<br/>map task 2"]
    end

    subgraph Local["Intermediate files on map workers' LOCAL disks<br/>R regions each"]
        L1["w1: r0 | r1"]
        L2["w2: r0 | r1"]
        L3["w3: r0 | r1"]
    end

    subgraph ReducePhase["Reduce workers"]
        R0["worker 4<br/>reduce task 0"]
        R1["worker 5<br/>reduce task 1"]
    end

    subgraph GFSOut["Output in GFS — R files"]
        O0["part-0"]
        O1["part-1"]
    end

    Ma -.->|"assign map"| W1
    Ma -.->|"assign reduce"| R0
    S0 --> W1
    S1 --> W2
    S2 --> W3
    W1 --> L1
    W2 --> L2
    W3 --> L3
    L1 -->|"remote read r0"| R0
    L2 -->|"remote read r0"| R0
    L3 -->|"remote read r0"| R0
    L1 -->|"remote read r1"| R1
    L2 -->|"remote read r1"| R1
    L3 -->|"remote read r1"| R1
    R0 --> O0
    R1 --> O1

3.2 The steps

The paper describes the execution in seven steps. In our words:

  1. The library splits the input into M pieces (typically 16–64 MB, matching GFS blocks) and starts many copies of the program. One copy is the master; the rest are workers.
  2. The master assigns M map tasks and R reduce tasks to idle workers.
  3. A map worker reads its split, parses records, calls map for each, and buffers output in memory.
  4. Periodically, buffered pairs are written to the worker's local disk, split into R regions by the partitioning function — by default hash(key) mod R. The worker reports the file locations to the master.
  5. When the master tells a reduce worker where its region is on each map worker, the reduce worker fetches the data by RPC from all the map workers' disks. Once it has all its data, it sorts by key (external sort if needed), so equal keys are adjacent.
  6. The reduce worker iterates over sorted keys, calls reduce for each key with its values, and appends output to a final file for its partition in GFS.
  7. When every task is done, the master wakes the user program.

The step from 4 to 5 — moving each map output region to the right reducer and sorting it — is the shuffle. It's the most expensive part of most jobs, and it's where almost all later engine optimisations focus.

3.3 The master's state

The master is simple. For every task it keeps a state (idle, in-progress, completed) and the worker running it. For every completed map task it keeps the locations and sizes of its R output regions, and it pushes these to reduce workers as they become available.

The paper notes the master makes scheduling decisions and keeps state — about one byte per map/reduce pair. A typical job had M = 200,000 and R = 5,000 on 2,000 workers. That sets a practical upper bound on how fine-grained tasks can be.

3.4 Partitioning and ordering

  • The partitioning function decides which reducer gets a key. The default hash(key) mod R balances well. Users can override it; the paper's example is hash(Hostname(url)) mod R, so all URLs from one host end up in the same output file.
  • Ordering guarantee: within one partition, keys are processed in increasing order. So each output file is sorted, which makes lookups by key cheap and makes distributed sort trivial with a range partitioner.

3.5 Combiners

In word count, a map task over a large document emits ("the", 1) thousands of times. All of them would be shuffled across the network. A combiner is a reduce-like function run on the map worker over its local output before writing it. For word count, the combiner is the same as the reducer: it turns 3,000 ("the", 1) records into one ("the", 3000).

A combiner is only correct if the reduce operation is associative and commutative (sum, max, count, set union). Average is not — you must combine (sum, count) pairs and divide at the end.

flowchart LR
    subgraph M1["Map task 1"]
        A1["the,1 ×3000<br/>cat,1 ×40"] --> C1["combiner"]
        C1 --> O1["the,3000<br/>cat,40"]
    end
    subgraph M2["Map task 2"]
        A2["the,1 ×2500<br/>dog,1 ×12"] --> C2["combiner"]
        C2 --> O2["the,2500<br/>dog,12"]
    end
    O1 -->|"shuffle: 2 records not 3040"| R["reducer for 'the'<br/>3000 + 2500 = 5500"]
    O2 -->|"shuffle: 2 records not 2512"| R

4. Fault Tolerance by Re-execution

4.1 Worker failure

The master pings every worker periodically. If a worker stops responding, it's marked failed, and:

  • Its in-progress map and reduce tasks are reset to idle and rescheduled.
  • Its completed map tasks are also re-executed, because their output lives on the failed machine's local disk, which is now unreachable.
  • Its completed reduce tasks are not re-executed, because their output is already in GFS, which is replicated.

When a map task is re-executed on another worker, every reduce worker is told, and any reducer that hasn't yet read that task's data reads it from the new location.

sequenceDiagram
    autonumber
    participant M as Master
    participant W2 as Worker 2 (map 1 done)
    participant W6 as Worker 6
    participant R0 as Reducer 0

    M->>W2: ping
    W2--xM: no reply
    Note over M: Mark W2 failed. Map 1 was completed,<br/>but its output is on W2's local disk
    M->>W6: run map task 1 again
    W6->>W6: read split 1 from GFS, run map, write R regions
    W6-->>M: map 1 complete, region locations
    M->>R0: map 1 region 0 is now on W6
    R0->>W6: fetch region 0

4.2 Why re-execution is enough: semantics

The paper states the guarantee precisely. When the user's map and reduce functions are deterministic functions of their input, the output of the distributed job is the same as a sequential, failure-free execution of the whole program would produce.

This is achieved with atomic commits of task output:

  • A map task writes its R outputs to temporary files and, when done, sends the file names to the master. If the master has already recorded a completed copy of that task, it ignores the duplicate.
  • A reduce task writes to a temporary file and, when done, atomically renames it to the final name. If two copies of the same reduce task finish, both renames target the same name. The file system's atomic rename guarantees the final file contains the output of exactly one execution.

Caveat from the paper: if map or reduce is non-deterministic, the guarantee is weaker. Each reduce output equals some sequential execution's output, but different reduce outputs may correspond to different executions of the non-deterministic map task. Side effects (writing to external systems from within map) are the user's problem; the framework doesn't make them atomic.

4.3 Master failure

The paper is blunt: the master could write periodic checkpoints and a new master could resume from one, but since there is only one master, its failure is unlikely, so the current implementation simply aborts the job if the master fails. The client can retry. This is a good example of an engineering trade-off: a single point of failure was accepted because it was rare and the cost was a job restart, not data loss.

4.4 Bad records

Some jobs crash deterministically on particular records — a bug in a third-party parsing library, say. MapReduce has an optional skip mode: each worker installs a signal handler that tells the master which record was being processed when the task crashed. If the master sees more than one failure on the same record, it tells the next re-execution to skip it. For large statistical jobs, losing a few records is better than never finishing.


5. Stragglers and Backup Tasks

A straggler is a machine that takes far longer than others to finish one of the last few tasks. The paper lists causes: a bad disk with frequent correctable errors slowing reads from 30 MB/s to 1 MB/s, other jobs competing for CPU or network on the same machine, or even a bug that disabled processor caches.

Since the job finishes only when the last task does, one straggler can double the job's time.

Backup tasks: when the job is close to finishing, the master schedules backup copies of the remaining in-progress tasks on other workers. Whichever copy finishes first wins; the other is discarded (safe because of the atomic-commit rules above). The paper says this increases total resource use by only a few percent but greatly reduces job time.

gantt
    title Last tasks of a job — with and without a backup task
    dateFormat X
    axisFormat %s
    section Without backup
    Normal tasks          :0, 300
    Straggler on slow disk :0, 900
    section With backup
    Normal tasks          :0, 300
    Straggler (killed)    :0, 420
    Backup copy           :300, 420

Measured result (§9): sort took 44% longer with backup tasks disabled.

This is called speculative execution in Hadoop and Spark. The same idea, in "hedged requests" form, is used to cut tail latency in online systems. It only works because tasks are idempotent.


6. Locality

Network bandwidth was the scarce resource. GFS stores each 64 MB block on (typically) three machines, and those machines are also MapReduce workers. The master uses block locations to schedule a map task on a machine that holds a replica of its input split. If none are free, it chooses a machine close to one, such as one on the same network switch.

The paper reports that with this, in large jobs on a significant fraction of the cluster, most input data is read locally and uses no network bandwidth. Only the shuffle and the replicated output writes cross the network.

This "move compute to data" principle was the core of the Hadoop ecosystem for a decade. Later, cloud networks became fast enough, and object storage (S3, GCS) took over from co-located HDFS, so modern engines generally separate compute from storage and rely on bandwidth and caching instead — a big change discussed in §15.


Part II — Apache Spark and RDDs

7. What MapReduce Couldn't Do Well

By 2010, MapReduce (through Hadoop) ran everywhere, and its limits were clear. The Spark paper focuses on two classes of workloads:

  1. Iterative algorithms — machine learning (logistic regression, k-means), graph algorithms (PageRank). Each iteration is a MapReduce job that reads its input from the distributed file system and writes its output back, with replication. A 10-iteration algorithm reads and writes the whole data set 10 times, even though the input data doesn't change.
  2. Interactive data mining — an analyst running many ad-hoc queries on the same data. Each query is a separate job that reads everything from disk, taking tens of seconds to minutes.

In both cases the problem was that MapReduce's only way to share data between computations is stable storage. Keeping data in memory across jobs would solve the speed problem — but how do you keep in-memory data fault-tolerant without replicating it (which costs the same network and memory you were trying to save)?

Existing in-memory systems (distributed shared memory, key-value caches like Piccolo) offered fine-grained updates to mutable state, so fault tolerance meant replicating data or logging every update — expensive for data-intensive workloads.

7.1 The RDD idea

The paper's answer: restrict the abstraction so fault tolerance is cheap.

A Resilient Distributed Dataset (RDD) is a read-only, partitioned collection of records that can only be created by deterministic operations (transformations) on data in stable storage or on other RDDs.

Because RDDs are immutable and created by coarse-grained transformations (the same function applied to many records), Spark doesn't need to replicate the data. It only needs to remember how each RDD was derived — its lineage. If a partition is lost, Spark recomputes just that partition from its parents.

This is MapReduce's re-execution idea, generalised from "re-run a task" to "re-run any part of a graph of transformations".

AspectRDDsDistributed shared memory
ReadsCoarse- or fine-grainedFine-grained
WritesCoarse-grained (transformations)Fine-grained
ConsistencyTrivial — immutableUp to the application or runtime
Fault recoveryLineage — recompute lost partitionsCheckpoints and rollback
StragglersBackup tasks possibleHard
Work placementAutomatic, by data localityUp to the application
Not enough RAMSpill to disk, degrade gracefullyPaging, poor performance

This table is our summary of the paper's comparison. The restriction to coarse-grained writes is what makes everything on the left possible. RDDs are a poor fit for workloads with fine-grained asynchronous updates to shared state, such as a web application's storage or an incremental web crawler — and the paper says so.


8. RDD Programming Model and Internals

8.1 Transformations and actions

  • Transformations create a new RDD from existing ones, and are lazy — nothing runs yet: map, filter, flatMap, sample, union, groupByKey, reduceByKey, join, cogroup, mapValues, sortByKey, partitionBy.
  • Actions return a value to the driver or write to storage, and trigger execution: count, collect, reduce, lookup, save.
  • Persistence: persist() / cache() asks Spark to keep the RDD after it's computed — in memory as deserialised objects, in memory serialised, or on disk.
  • Partitioning control: partitionBy(partitioner) lets you hash- or range-partition an RDD by key, so later joins on the same key don't need to shuffle.

The paper's log-mining example, adapted to PySpark (runnable against any text file):

from pyspark import SparkContext

sc = SparkContext("local[4]", "log-mining")

lines = sc.textFile("logs/*.log")                       # base RDD from storage
errors = lines.filter(lambda l: l.startswith("ERROR"))  # transformation (lazy)
errors.persist()                                        # keep in memory once computed

print(errors.count())                                   # action -> runs the job, caches errors
mysql = errors.filter(lambda l: "MySQL" in l)
print(mysql.count())                                    # reuses cached errors, no disk scan

# Third query: time field of HDFS-related errors (tab-separated, field 3)
times = (errors.filter(lambda l: "HDFS" in l)
               .map(lambda l: l.split("\t")[3])
               .collect())

Only errors is cached. If a node holding some errors partitions dies, Spark re-runs filter on just the corresponding lines partitions.

Word count in Spark:

counts = (sc.textFile("corpus/*.txt")
            .flatMap(lambda line: line.lower().split())
            .map(lambda w: (w, 1))
            .reduceByKey(lambda a, b: a + b))   # map-side combine is built in
counts.saveAsTextFile("out/wordcount")

8.2 How an RDD is represented

The paper defines RDDs through a small common interface. Every RDD provides:

OperationMeaning
partitions()The list of partition objects
dependencies()The list of parent RDDs and how this RDD depends on them
iterator(p, parentIters)Compute the elements of partition p from the parents' iterators
preferredLocations(p)Nodes where partition p can be accessed fastest (e.g. HDFS block locations)
partitioner()Whether the RDD is hash- or range-partitioned, if at all

With this interface, all transformations — even ones from other systems like Pregel-style graph processing — can be implemented in a few dozen lines each. The paper reports Spark itself was about 14,000 lines of Scala at the time.

8.3 Narrow and wide dependencies

The most important internal concept:

  • Narrow dependency: each partition of the parent is used by at most one partition of the child. Examples: map, filter, union, and join of two RDDs that are already co-partitioned.
  • Wide dependency: a parent partition may be used by many child partitions. Examples: groupByKey, reduceByKey, and join of RDDs that aren't co-partitioned. This needs a shuffle.
flowchart LR
    subgraph Narrow["Narrow — map, filter"]
        direction LR
        a1["A.p0"] --> b1["B.p0"]
        a2["A.p1"] --> b2["B.p1"]
        a3["A.p2"] --> b3["B.p2"]
    end
    subgraph Wide["Wide — groupByKey"]
        direction LR
        c1["C.p0"] --> d1["D.p0"]
        c1 --> d2["D.p1"]
        c2["C.p1"] --> d1
        c2 --> d2
        c3["C.p2"] --> d1
        c3 --> d2
    end

The distinction matters for two reasons:

  1. Pipelining. Narrow dependencies can be computed in one pass on one node, element by element — filter then map don't need a materialised intermediate. Wide ones require all parent partitions to be computed first and data to move across nodes.
  2. Recovery cost. A lost partition with narrow dependencies is rebuilt from one parent partition. A lost partition after a wide dependency might need every parent partition, possibly across the whole cluster. That's why Spark materialises shuffle output (§8.5) and why checkpointing matters for long lineage chains with wide dependencies.

8.4 The DAG scheduler: stages

When an action runs, Spark's scheduler looks at the lineage graph and builds a DAG of stages. Each stage contains as many pipelined narrow transformations as possible. Stage boundaries are at shuffles (wide dependencies) or at partitions already computed and cached, which can be skipped.

Example: join page visits with page names, then count per name.

visits = sc.textFile("visits").map(parse_visit)            # (url, user)
names  = sc.textFile("names").map(parse_name)              # (url, name)
joined = visits.join(names)                                # wide unless co-partitioned
by_name = joined.map(lambda kv: (kv[1][1], 1)).reduceByKey(lambda a, b: a + b)
by_name.collect()
flowchart LR
    subgraph S1["Stage 1"]
        V["textFile visits"] --> VM["map parse"]
    end
    subgraph S2["Stage 2"]
        N["textFile names"] --> NM["map parse"]
    end
    subgraph S3["Stage 3"]
        J["join"] --> M2["map to (name, 1)"]
    end
    subgraph S4["Stage 4"]
        RB["reduceByKey"] --> C["collect"]
    end
    VM -->|"shuffle by url"| J
    NM -->|"shuffle by url"| J
    M2 -->|"shuffle by name"| RB

Stages 1 and 2 have no dependency on each other and run in parallel. Within each stage, tasks — one per partition — run the pipelined functions together. If names had been pre-partitioned by url with the same partitioner as visits (using partitionBy and persist), the join would become a narrow dependency, and stage 2's shuffle would go away. The paper's PageRank evaluation shows exactly this gain (§9).

Tasks are placed by data locality using delay scheduling: a task waits briefly for a slot on a node holding its data (in memory or on disk) before accepting a non-local slot.

8.5 The shuffle and fault recovery

For wide dependencies, Spark (in the paper's version) materialises intermediate records on the nodes holding the parent partitions, much like MapReduce's map output on local disk. Reducers fetch them. This makes failure recovery simpler: if a reduce-side task fails, it can be re-run using the existing shuffle files.

On failure:

  • A failed task is re-run on another node, as long as its parent stage's outputs are still available.
  • If some stage outputs are lost (e.g., the node holding shuffle files died), the scheduler resubmits tasks in the parent stage to recompute just the missing partitions, in parallel across the cluster.
  • Scheduler (driver) failure was not tolerated in the paper's version. Replicating the lineage graph would be straightforward, but wasn't done.
sequenceDiagram
    autonumber
    participant D as Driver / DAG scheduler
    participant E1 as Executor 1
    participant E2 as Executor 2 (dies)
    participant E3 as Executor 3

    D->>E1: stage 3 task for partition 0
    E1->>E2: fetch shuffle block from stage 1, partition 4
    E2--xE1: connection refused
    E1-->>D: FetchFailed, stage 1 partition 4
    Note over D: Lineage says partition 4 of stage 1<br/>= map parse over visits block 4
    D->>E3: re-run stage 1 task for partition 4
    E3-->>D: done, shuffle output on E3
    D->>E1: retry stage 3 task for partition 0
    E1->>E3: fetch shuffle block

8.6 Memory management and checkpointing

The paper describes three storage options for persisted RDDs: deserialised Java objects in memory (fastest), serialised objects in memory (more compact, slower), and on disk. When memory runs out, Spark evicts partitions using LRU at the RDD level, while avoiding evicting partitions of the RDD currently being computed (that would cause thrashing).

Checkpointing to stable storage is offered for RDDs with long lineage graphs containing wide dependencies, such as PageRank after many iterations. Recomputing such a partition after failure could take a long time, so writing a checkpoint every few iterations bounds recovery time. For short lineages with narrow dependencies, checkpointing usually isn't worth it.


9. Performance Numbers From the Papers

9.1 MapReduce (OSDI 2004)

Test cluster: about 1,800 machines, each with two 2 GHz Intel Xeon processors with Hyper-Threading, 4 GB of memory, two 160 GB IDE disks and gigabit Ethernet, arranged in a two-level tree-shaped switched network.

ExperimentSetupResult
GrepScan 10¹⁰ 100-byte records (~1 TB) for a rare three-character pattern (92,337 matches). M = 15,000, R = 1Input scan rate peaked above 30 GB/s with 1,764 workers. Whole job about 150 s, including about a minute of startup overhead
Sort10¹⁰ 100-byte records (~1 TB), modelled on TeraSort. M = 15,000, R = 4,000, output 2-way replicated891 s. The best previously reported TeraSort result was 1,057 s
Sort, no backup tasksSame1,283 s — 44% longer; a few straggling reduce tasks held up the end
Sort, 200 workers killed200 of 1,746 worker processes killed a few minutes in933 s — only 5% longer than normal

Production use in August 2004 (the paper's Table 1): about 29,000 jobs in the month, average completion time of about 634 seconds, reading over 3,000 TB of input in total, using an average of 157 worker machines per job, with on average about 1.2 worker deaths per job. The paper also reports that rewriting Google's production indexing system on MapReduce cut one phase from about 3,800 lines of C++ to about 700.

9.2 Spark RDDs (NSDI 2012)

Experiments ran on Amazon EC2. The headline numbers from the paper's abstract and evaluation:

  • Iterative machine learning: up to 20× faster than Hadoop. The gap was largest for logistic regression (cheap computation per iteration, so I/O and deserialisation dominate Hadoop's time) and smaller for k-means (heavier computation per iteration). Spark's first iteration was also faster than Hadoop's, partly because of Hadoop's heartbeat-based task scheduling overhead.
  • PageRank on a 54 GB Wikipedia dump: in-memory storage alone gave about 2.4× speedup over Hadoop on 30 nodes; adding controlled partitioning (so the links and ranks RDDs were co-partitioned and joins didn't shuffle the links) raised it to about 7.4×.
  • A real-world analytics report: sped up by about 40×.
  • Interactive queries: a 1 TB data set scanned interactively with 5–7 second latency on 100 nodes, versus about 170 seconds for querying the same data on disk.
  • Fault recovery: when a node failed during a k-means run, only the failed iteration slowed down, as lost partitions were rebuilt in parallel from lineage; later iterations ran at normal speed.

9.3 Later benchmarks

In 2014 Databricks used Spark to sort 100 TB in 23 minutes on 206 EC2 machines, sharing the Daytona GraySort record (the previous record, set with Hadoop MapReduce, was 72 minutes on about 2,100 nodes). That run was dominated by shuffle engineering — a sort-based shuffle and a Netty-based network module — not by in-memory caching, which a one-pass sort can't use. It showed that Spark's advantage wasn't only memory.


10. Why Spark Was Faster — Honestly

"Spark is fast because it's in memory" is the common short answer, and it is only partly right. The real reasons, roughly in order of importance for typical jobs:

  1. No forced materialisation between steps. A multi-step MapReduce pipeline writes every intermediate result to replicated HDFS. Spark pipelines narrow transformations within a stage and only writes shuffle files (to local disk, unreplicated). For a 5-job pipeline, that removes most of the I/O.
  2. Caching for reuse. For iterative and interactive workloads, the working set is read from disk once. This is where 20× comes from.
  3. Lower task overhead. Hadoop 1.x started a JVM per task and scheduled through heartbeats every few seconds. Spark executors are long-lived and launch tasks in milliseconds, which makes fine-grained tasks practical.
  4. Controlled partitioning. Co-partitioned joins avoid shuffles entirely.
  5. A general DAG instead of map-then-reduce. No forcing every computation into a map stage plus a reduce stage, with identity mappers in between.

And where Spark isn't faster: a single-pass, I/O-bound scan with no reuse runs at disk or network speed in both systems.


11. DataFrames, Catalyst and Tungsten

RDDs exposed arbitrary functions (Python lambdas, Scala closures). The engine couldn't see inside them, so it couldn't optimise: it didn't know a filter could be pushed down, or that only two columns of a 50-column record were used.

Spark SQL (Armbrust et al., SIGMOD 2015) introduced DataFrames — distributed tables with a schema — and the Catalyst optimiser:

  • Queries (SQL or DataFrame API) become trees of logical operators.
  • Catalyst applies rule-based rewrites in phases: analysis (resolve names and types), logical optimisation (predicate pushdown, constant folding, projection pruning), physical planning (choose join algorithms using cost estimates, such as broadcast hash join when one side is small), and code generation (compiling expressions to JVM bytecode).
  • Data sources can accept pushed-down filters and column pruning, so a Parquet scan reads only the needed columns and row groups.
from pyspark.sql import SparkSession, functions as F

spark = SparkSession.builder.appName("orders").getOrCreate()
orders = spark.read.parquet("s3://lake/orders/")        # columnar, partitioned by date
users  = spark.read.parquet("s3://lake/users/")

result = (orders.where(F.col("order_date") >= "2026-10-01")   # pushed into the scan
                .join(F.broadcast(users), "user_id")          # broadcast hash join
                .groupBy("country")
                .agg(F.sum("amount").alias("revenue")))
result.explain()   # shows PartitionFilters, BroadcastHashJoin, HashAggregate

This is the same join from §2.3, now written declaratively. The optimiser picks the map-side join strategy that took careful hand-coding in MapReduce.

Project Tungsten (from 2015) changed the execution engine: compact binary row formats managed outside the JVM object model, cache-aware algorithms, and in Spark 2.0 whole-stage code generation, which fuses a stage's operators into one generated function to avoid virtual calls per row. Adaptive Query Execution (Spark 3.0) re-optimises at stage boundaries using real shuffle statistics: it coalesces small partitions, switches join strategies when a side turns out small, and splits skewed partitions — a direct fix for the reduce-side skew problem in §2.3.

For how these engines read lakehouse tables, see Query Engines and Table Formats.


12. Structured Streaming — a Pointer

Spark's first streaming system (D-Streams, SOSP 2013) treated a stream as a series of small RDD batches. Structured Streaming (Armbrust et al., SIGMOD 2018) replaced it with a cleaner model: a stream is an unbounded table, and you write the same DataFrame query you would for batch; Spark runs it incrementally. It supports event-time windows and watermarks, and gives end-to-end exactly-once results when sources are replayable (like Kafka) and sinks are idempotent or transactional. It runs as micro-batches by default, with a lower-latency continuous mode for some queries.

The streaming concepts are covered on their own pages: Stream Processing, Windowing, Watermarks, State Management and Exactly-Once Processing.


13. Guarantees — Precisely

PropertyMapReduceSpark (RDD model)
Output equivalenceEqual to a sequential, failure-free run, if map and reduce are deterministicSame, if transformations are deterministic; lineage recomputation must produce the same partition
Non-determinismEach reduce output matches some sequential run; different outputs may match different runsSame risk; recomputed partitions after failure may differ (e.g., sample without a fixed seed, zipWithIndex after an unordered shuffle)
Side effectsNot atomic. User's responsibilitySame — writes from inside foreach may happen more than once
Output commitAtomic rename per reduce taskOutput committers (task then job commit). Rename-based commit is not atomic on object stores; table formats like Delta and Iceberg solve this with transactional metadata
Driver / master failureJob abortedJob lost in the paper's design. Later: driver restart and checkpointing for streaming
Isolation between jobsNone — two jobs writing the same output path conflictNone at the RDD level; table formats add it

The non-determinism row bites in practice. If a pipeline uses a random split or a non-deterministic UDF before a shuffle and an executor dies, recomputation may produce different records for the lost partitions only. The rest of the job sees a mix of two executions. Spark later added detection for some of these cases (marking stages as "indeterminate" and rerunning all downstream tasks), but the general rule stays: make transformations deterministic, or checkpoint right after the non-deterministic step.


14. What They Got Right and Wrong

14.1 MapReduce

Right:

  • A narrow, functional API that hid distribution from non-experts — the reason Google ended up with hundreds of MapReduce programs within two years.
  • Fault tolerance through deterministic re-execution and atomic commit, rather than replication of intermediate data.
  • Backup tasks for stragglers.
  • Locality-aware scheduling for its era's networks.

Wrong or limiting:

  • Only two stages. Real pipelines became chains of jobs, each paying full HDFS write and read costs. Tools like FlumeJava (PLDI 2010) at Google and Pig and Hive in Hadoop were built to generate and optimise those chains.
  • No in-memory reuse, so iterative and interactive work was slow.
  • High per-job and per-task latency. Minutes of startup were fine for indexing, bad for analysts.
  • Opaque functions blocked optimisation — no predicate pushdown, no column pruning.
  • Single master — acceptable then, but Hadoop's equivalent (JobTracker) became a scalability and availability bottleneck, which led to YARN.

14.2 Spark

Right:

  • Lineage-based recovery for in-memory data — fault tolerance without replication.
  • A general DAG with narrow/wide dependency analysis, pipelining and stage-level scheduling.
  • One engine for batch, SQL, streaming, ML (MLlib) and graphs (GraphX).
  • Moving to declarative DataFrames so an optimiser could do the hard work.

Wrong or costly:

  • Memory management on the JVM was hard: garbage collection pauses and out-of-memory errors were the common Spark operations problem until Tungsten's off-heap formats.
  • Shuffle remained the bottleneck and the main source of failures (lost executors lose their shuffle files). External shuffle services, push-based shuffle (Magnet at LinkedIn, in Spark 3.2) and remote shuffle services were later added.
  • Python overhead — the RDD Python API serialised data between JVM and Python. Arrow-based pandas UDFs reduced it.
  • Micro-batch streaming gave higher latency than record-at-a-time engines like Flink.

15. MapReduce → Spark → Modern Engines

timeline
    title Batch processing engines
    2003 : GFS paper
    2004 : MapReduce paper at OSDI
    2006 : Hadoop (HDFS + MapReduce) at Yahoo
    2007 : Dryad — general DAGs (Microsoft)
    2009 : Hive — SQL compiled to MapReduce
    2010 : FlumeJava — optimised pipelines of MapReduces at Google : Spark open-sourced
    2012 : RDD paper at NSDI
    2013 : YARN separates scheduling from MapReduce
    2014 : Spark sorts 100 TB in 23 min
    2015 : Spark SQL, Catalyst : Dataflow model paper (Beam)
    2018 : Structured Streaming
    2020 : Spark 3.0 Adaptive Query Execution
    2022 : Photon, Velox — native vectorised engines

The main trends after Spark:

  1. Unified batch and streaming. Google's Dataflow model (VLDB 2015), Apache Beam and Flink treat batch as a bounded stream. Flink's pipelined, record-at-a-time execution suits low-latency streaming, with batch as a special case.
  2. Native, vectorised execution. JVM row-at-a-time execution was replaced in performance-critical paths by C++ engines processing columnar batches with SIMD: Databricks Photon (SIGMOD 2022), Meta's Velox, and Apache DataFusion in Rust. Projects like Gluten plug native engines into Spark's planner.
  3. Separation of compute and storage. HDFS's co-location gave way to object storage plus open table formats (Iceberg, Delta Lake, Hudi). Locality now means caching and fast networks, not scheduling on the node with the block. See Table Formats.
  4. MPP SQL engines (Presto/Trino, Impala, Dremel/BigQuery) run pipelined query plans across long-running workers, without materialising between stages, for interactive SQL.
  5. Single-node engines got very good. DuckDB and Polars process hundreds of gigabytes on one large machine. Many "big data" jobs are now small enough to skip distribution entirely — a lesson the Spark paper itself would agree with: use the simplest engine the data allows.
  6. General distributed computing for ML moved to systems like Ray, with actors and tasks, because ML training needs fine-grained, stateful computation — exactly the case the RDD paper said it was not designed for.

At Google itself, MapReduce was replaced internally by Flume (the successor of FlumeJava) and Cloud Dataflow during the early 2010s.


16. Lessons for System Design Interviews

  1. Deterministic, idempotent tasks make everything easier. Retries, speculative execution and recovery all rely on it. Say so whenever you design a pipeline.
  2. The shuffle is the cost. Reduce it: combiners and map-side aggregation, broadcast joins for small tables, co-partitioning, filtering and projecting early.
  3. Skew is the usual reason a job is slow. Mention salting hot keys, splitting skewed partitions (AQE), or a two-stage aggregation.
  4. Recompute vs replicate. Lineage is cheap when recomputation is cheap and narrow. For long, wide lineage, checkpoint. This trade-off appears everywhere — caches, materialised views, stream state.
  5. Stragglers dominate the tail. Backup tasks and hedged requests are the same idea.
  6. Know the data size. For tens of gigabytes, one machine with DuckDB or pandas may beat a cluster. Interviewers value this realism.
  7. Know the commit problem. Atomic rename on HDFS versus object stores; table formats give atomic commits and snapshot isolation for batch outputs.
  8. Batch vs stream. Batch reprocessing is simpler and more correct; streaming is lower latency. Many systems keep both, or use one engine for both with event-time semantics.

17. Interview Questions

1. Why are completed map tasks re-executed when their worker fails, but completed reduce tasks are not?

Map output lives on the map worker's local disk, so it's unreachable when the machine fails and reducers that haven't fetched it yet need it. Reduce output is written to GFS, which is replicated, so it survives the worker's failure.

2. How does MapReduce make sure that a backup task and the original don't both produce output?

Atomic commits. Map tasks write temporary files and report them to the master, which ignores completion messages for tasks already marked completed. Reduce tasks write to a temporary file and atomically rename it to the final name. Even if both copies rename, the file system ensures the final file holds exactly one execution's output. This is safe because tasks are deterministic.

3. When can you use a combiner? Give an example where using the reducer as a combiner is wrong.

When the reduce operation is associative and commutative, so partial results can be merged in any grouping — sum, count, max, set union. Average isn't: averaging averages gives the wrong answer for unequal group sizes. Instead combine (sum, count) pairs and divide in the final reducer.

4. Explain narrow vs wide dependencies and why the distinction matters.

Narrow: each parent partition feeds at most one child partition (map, filter, co-partitioned join). Wide: a parent partition feeds many child partitions (groupByKey, non-co-partitioned join), requiring a shuffle. Narrow dependencies can be pipelined in one task and recovered by recomputing a single parent partition; wide ones are stage boundaries and recovery may need many parent partitions, which is why shuffle output is materialised and long wide lineages are checkpointed.

5. How does Spark recover a lost cached partition without replication?

From lineage: the RDD records the transformations and parent partitions it came from. The scheduler re-runs those transformations for just the lost partition, on another node, reading from the parent (which may itself be cached, on disk as shuffle output, or in stable storage). Lost partitions are rebuilt in parallel across the cluster.

6. A Spark job joining a 5 TB fact table to a 50 MB dimension table is slow. What would you check?

Whether it uses a broadcast hash join (it should — 50 MB fits easily). Check the physical plan with explain. If it's a sort-merge join, raise the broadcast threshold or add a broadcast hint. Also check that filters and column pruning push into the Parquet scan, and look for skew in any remaining shuffle.

7. One reducer in your job takes 3 hours while the rest take 5 minutes. Diagnose and fix.

Probably key skew — one key (a null, a default, a bot user) has a huge share of records. Confirm with per-key counts. Fixes: filter or handle the hot key separately; salt it (append a random suffix, aggregate in two stages); for joins, broadcast the small side or split the skewed key and replicate the matching rows; in Spark 3, enable AQE skew-join handling. Speculative execution won't help: the backup copy has the same work.

8. Why did Spark beat Hadoop by 20× on logistic regression but much less on k-means?

Logistic regression does little computation per record per iteration, so Hadoop's time is dominated by reading and deserialising the input from HDFS every iteration — exactly what Spark's in-memory cache removes. K-means does more computation per record, so a bigger share of time is compute that both systems must do.

9. What goes wrong if a transformation before a shuffle is non-deterministic and an executor dies?

Recomputing the lost partitions may produce different records than the first run. Downstream tasks that already consumed the original output and tasks consuming the recomputed output see inconsistent data — duplicates or missing records. Fixes: make it deterministic (fixed seeds, stable ordering), checkpoint right after it, or rely on Spark's handling of indeterminate stages, which reruns all downstream tasks.

10. Design question — compute daily active users per country from 20 TB of daily event logs in object storage, with results by 6 a.m.

Store events in a columnar table format partitioned by date. Run a daily Spark (or similar) job reading only yesterday's partition and only user_id and country columns. Aggregate distinct users per country — exact with a two-stage distinct (group by country and user, then count), or approximate with HyperLogLog sketches if acceptable. Broadcast any small lookup tables, enable AQE for skew, write results atomically through the table format, and make the job idempotent by overwriting the date partition so retries are safe. Add data-quality checks and alert on late input.

11. MapReduce aborts the job when the master fails. Was that a reasonable design?

Yes for its context: one master versus thousands of workers makes master failure rare, jobs were batch with minutes-to-hours runtime, and the cost was a rerun, not data loss. Checkpointing the master would add complexity for little gain. It became a problem when Hadoop's JobTracker managed every job on a cluster — a shared, long-lived master — which is why YARN split scheduling into a resource manager plus one application master per job.


Further Reading

  • J. Dean, S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. OSDI 2004. — primary source for MapReduce numbers on this page.
  • M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, I. Stoica. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. NSDI 2012.
  • M. Armbrust et al. Spark SQL: Relational Data Processing in Spark. SIGMOD 2015.
  • M. Armbrust et al. Structured Streaming: A Declarative API for Real-Time Applications in Apache Spark. SIGMOD 2018.
  • C. Chambers et al. FlumeJava: Easy, Efficient Data-Parallel Pipelines. PLDI 2010.
  • T. Akidau et al. The Dataflow Model. VLDB 2015.
  • M. Isard et al. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. EuroSys 2007.
  • A. Behm et al. Photon: A Fast Query Engine for Lakehouse Systems. SIGMOD 2022.

Related Archon pages: Batch Processing · Idempotent Pipelines · Data Lineage · Query Engines · Table Formats · Stream Processing · GFS & HDFS · Bigtable & HBase