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:
| Constraint | Detail from the paper | Consequence |
|---|---|---|
| Commodity machines | Dual-processor x86 Linux boxes, 2–4 GB memory, cheap IDE disks | Failures are normal; design for re-execution |
| Modest network | 100 Mb/s or 1 Gb/s per machine, much less bisection bandwidth per machine | Network bandwidth is the scarce resource — move computation to data |
| Storage | GFS on the same machines, files split into 64 MB blocks, typically 3 replicas | Input blocks have known locations; the scheduler can use them |
| Users | Engineers with no distributed systems background | The API must hide all distribution |
| Workload | Large batch jobs; latency of minutes to hours is fine | Optimise 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:
| Task | map emits | reduce does |
|---|---|---|
| Distributed grep | the line, if it matches | identity |
| URL access frequency | (URL, 1) per log line | sum |
| Reverse web-link graph | (target, source) for each link | list 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 rowsorders(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:
- Every order moves across the network in the shuffle, though only the amount and country are needed.
- Skew. If one user has 50 million orders (a bot, a test account), one reducer gets them all and the job waits for it.
- Memory.
reduce_joinassumes 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:
- 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.
- The master assigns M map tasks and R reduce tasks to idle workers.
- A map worker reads its split, parses records, calls
mapfor each, and buffers output in memory. - 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. - 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.
- The reduce worker iterates over sorted keys, calls
reducefor each key with its values, and appends output to a final file for its partition in GFS. - 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 Rbalances well. Users can override it; the paper's example ishash(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:
- 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.
- 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".
| Aspect | RDDs | Distributed shared memory |
|---|---|---|
| Reads | Coarse- or fine-grained | Fine-grained |
| Writes | Coarse-grained (transformations) | Fine-grained |
| Consistency | Trivial — immutable | Up to the application or runtime |
| Fault recovery | Lineage — recompute lost partitions | Checkpoints and rollback |
| Stragglers | Backup tasks possible | Hard |
| Work placement | Automatic, by data locality | Up to the application |
| Not enough RAM | Spill to disk, degrade gracefully | Paging, 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:
| Operation | Meaning |
|---|---|
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, andjoinof two RDDs that are already co-partitioned. - Wide dependency: a parent partition may be used by many child partitions. Examples:
groupByKey,reduceByKey, andjoinof 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:
- Pipelining. Narrow dependencies can be computed in one pass on one node, element by element —
filterthenmapdon't need a materialised intermediate. Wide ones require all parent partitions to be computed first and data to move across nodes. - 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.
| Experiment | Setup | Result |
|---|---|---|
| Grep | Scan 10¹⁰ 100-byte records (~1 TB) for a rare three-character pattern (92,337 matches). M = 15,000, R = 1 | Input scan rate peaked above 30 GB/s with 1,764 workers. Whole job about 150 s, including about a minute of startup overhead |
| Sort | 10¹⁰ 100-byte records (~1 TB), modelled on TeraSort. M = 15,000, R = 4,000, output 2-way replicated | 891 s. The best previously reported TeraSort result was 1,057 s |
| Sort, no backup tasks | Same | 1,283 s — 44% longer; a few straggling reduce tasks held up the end |
| Sort, 200 workers killed | 200 of 1,746 worker processes killed a few minutes in | 933 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:
- 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.
- Caching for reuse. For iterative and interactive workloads, the working set is read from disk once. This is where 20× comes from.
- 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.
- Controlled partitioning. Co-partitioned joins avoid shuffles entirely.
- 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
| Property | MapReduce | Spark (RDD model) |
|---|---|---|
| Output equivalence | Equal to a sequential, failure-free run, if map and reduce are deterministic | Same, if transformations are deterministic; lineage recomputation must produce the same partition |
| Non-determinism | Each reduce output matches some sequential run; different outputs may match different runs | Same risk; recomputed partitions after failure may differ (e.g., sample without a fixed seed, zipWithIndex after an unordered shuffle) |
| Side effects | Not atomic. User's responsibility | Same — writes from inside foreach may happen more than once |
| Output commit | Atomic rename per reduce task | Output 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 failure | Job aborted | Job lost in the paper's design. Later: driver restart and checkpointing for streaming |
| Isolation between jobs | None — two jobs writing the same output path conflict | None 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:
- 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.
- 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.
- 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.
- MPP SQL engines (Presto/Trino, Impala, Dremel/BigQuery) run pipelined query plans across long-running workers, without materialising between stages, for interactive SQL.
- 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.
- 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
- Deterministic, idempotent tasks make everything easier. Retries, speculative execution and recovery all rely on it. Say so whenever you design a pipeline.
- The shuffle is the cost. Reduce it: combiners and map-side aggregation, broadcast joins for small tables, co-partitioning, filtering and projecting early.
- Skew is the usual reason a job is slow. Mention salting hot keys, splitting skewed partitions (AQE), or a two-stage aggregation.
- 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.
- Stragglers dominate the tail. Backup tasks and hedged requests are the same idea.
- Know the data size. For tens of gigabytes, one machine with DuckDB or pandas may beat a cluster. Interviewers value this realism.
- Know the commit problem. Atomic rename on HDFS versus object stores; table formats give atomic commits and snapshot isolation for batch outputs.
- 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