System Design · Module 9

Batch and Stream Processing: The MapReduce to Spark/Flink Lineage

MapReduce turned "write a distributed program" into "fill in two functions," and paid for that simplicity with an execution model that reruns a full job stage from disk on every failure and between every iteration. Spark's Resilient Distributed Datasets keep the same restricted, deterministic-transformation contract but replace disk-durable stage boundaries with an in-memory lineage graph, which is why the same iterative workload that took minutes per pass under MapReduce runs in seconds under Spark. After this module you can read the map/reduce type signature, the RDD lineage graph, and a Spark benchmark table and know exactly which mechanism produced which number.

Course 35 min read 5 sources As of 2026-09-17 Prerequisite: Module 8
MapReduce execution overview: input splits, master-assigned map and reduce workers, and the shuffle between them One MapReduce job, six numbered steps Master (1) fork (1) fork input splits (16-64 MB) map worker map worker map worker (3) read local disk (4) local write (5) remote read (shuffle) reduce worker reduce worker output 0 output 1 (6) write Input files Map phase Intermediate Reduce phase Global FS output (2) master assigns idle workers to M map tasks and R reduce tasks Every arrow after step 4 crosses the network; steps 3-4 stay local when the master can schedule a map task on a machine that already holds its input split.
Figure 1. The seven numbered actions of one MapReduce execution, redrawn from the paper's own Figure 1: fork, assign, read, local write, shuffle (remote read), and write1. Everything in this module is a variation on this one shape — the question each later section answers is what happens to steps 3-6 when a machine dies mid-job, or when the same job has to run a hundred times in a row.

1. From ad hoc parallel code to a type contract

Before 2004, Google had already implemented hundreds of special-purpose programs to process the raw data crawling and logging produced: inverted indices, graph representations of the web's link structure, per-host summaries of the most frequent queries1. Each one was, in principle, a simple computation — count words, follow links, sum frequencies. In practice, each one also had to solve parallelization, distribution across hundreds or thousands of machines, load balancing, and failure handling from scratch, and that machinery obscured the simple computation underneath it1. Dean and Ghemawat's response was not a faster cluster or a smarter scheduler; it was a narrower interface. If the programmer would express the computation as two functions with a fixed type signature, the runtime could own parallelization, distribution, and fault tolerance completely, and the programmer would never see a socket, a thread, or a machine list1.

This module's job is to derive that interface and its two implementations well enough that Module 32 can cite the result rather than re-deriving it: MapReduce's execution model and its specific failure-recovery asymmetry (§§2-3), and Spark's Resilient Distributed Dataset (RDD) abstraction, which keeps MapReduce's restricted, deterministic-transformation contract but replaces MapReduce's disk-durable stage boundaries with a lineage graph that is cheap to recompute from (§§5-7). Module 8 covered the log-structured message broker that often feeds these jobs; this module starts one layer up, with the compute framework that reads from a distributed file system (Module 7's GFS/HDFS) or a log (Module 8's Kafka) and turns bounded input into bounded output.

1.1 The map/reduce type signature and word count

The interface has exactly two user-supplied functions, and the paper states their types precisely:

$$ \text{map}\ (k_1, v_1) \rightarrow \text{list}(k_2, v_2) $$ $$ \text{reduce}\ (k_2, \text{list}(v_2)) \rightarrow \text{list}(v_2) $$

Map takes one input key/value pair and produces a set of intermediate key/value pairs. The MapReduce library groups together all intermediate values associated with the same intermediate key and passes them to Reduce, which merges those values into a — typically smaller — set of output values1. Note the type discipline the paper is explicit about: the intermediate keys and values \(k_2, v_2\) are drawn from a domain that need not match the input domain \(k_1, v_1\), but the output domain matches the intermediate domain, because Reduce's output type is \(\text{list}(v_2)\), the same \(v_2\) it consumed1. Everything about MapReduce's execution model in §2 exists to implement exactly this grouping-by-intermediate-key step efficiently at cluster scale.

The canonical example, word counting, makes the two functions concrete: map emits (w, "1") for every word w in a document; reduce receives a key w and the list of all the "1"s emitted for it across every document, and sums them1. The paper's other worked examples — distributed grep (map emits a matching line, reduce is the identity function), reverse web-link graph (map emits (target, source) for every link, reduce concatenates the sources per target), and building an inverted index (map emits (word, docID), reduce sorts and emits (word, list(docID))) — are all the same shape: a per-record local transformation, followed by a grouping-and-merging step keyed on whatever the map phase decided mattered1. Nothing in this contract mentions machines, threads, or retries. That omission is the entire point, and §2 is about what the runtime has to do to honor it anyway.

2. Execution mechanics: splits, shuffle, locality

Figure 1 names the mechanism; this section derives why each step is shaped the way it is. The MapReduce library first splits the input files into M pieces, typically 16-64 MB each, a size the user can control1. One copy of the user's program becomes the master; the rest become workers that the master assigns to either a map task or a reduce task, picking idle workers as they become available1. A worker assigned a map task reads its input split, parses key/value pairs, and passes each pair to the user's Map function; the emitted intermediate pairs are buffered in memory, then periodically written to local disk, partitioned into R regions by a partitioning function — by default hash(key) mod R — and the locations of those regions are reported back to the master1.

This is the step that decides which reduce worker will eventually see which key: the partitioning function is the shuffle's routing table, computed independently by every map task, with the master only relaying the resulting file locations. When a reduce worker is notified of these locations, it uses RPCs to pull ("remote read") the buffered data for its partition from every map worker's local disk, sorts the combined intermediate data by key so that all occurrences of the same key are grouped together — using an external sort if the data doesn't fit in memory — and then invokes the user's Reduce function once per unique intermediate key, appending each result to a per-partition output file1. This is also why MapReduce gives you a free ordering guarantee: within a given partition, the paper states, intermediate key/value pairs are processed in increasing key order, which is a direct consequence of the sort step every reduce task performs and is exposed because it is useful for producing a sorted output file per partition1.

Two refinements matter for the arithmetic later in this module. First, the combiner function: when a reduce function is both commutative and associative — word counting again — the user can supply an optional combiner that runs on the map side and pre-aggregates values for a key before they cross the network, cutting the volume of the shuffle for any workload whose keys follow a skewed (for example Zipfian) distribution1. Second, locality: because the input lives on GFS, which stores several copies (typically 3) of each 64 MB block on different machines, the master takes chunk-location information into account and tries to schedule a map task on a machine that holds a replica of its input split, or failing that, on a machine on the same network switch1. The measured payoff is direct — on large MapReduce operations using a significant fraction of the workers in a cluster, most input data is read locally and consumes no network bandwidth at all1. This is the same locality-aware placement idea Module 7 introduced for GFS chunk placement, reused here on the compute side: the scheduler moves the computation to the data because moving 64 MB is expensive and moving a task descriptor is not.

2.1 Task granularity: why M and R must exceed the worker count

The paper's guidance on choosing M and R is not a rule of thumb; it is a memory-bounded design constraint you can compute directly. Ideally, M and R should be much larger than the number of worker machines, because giving each worker many small tasks improves dynamic load balancing and — crucially for §3 — speeds up recovery: if a worker fails, the many map tasks it had completed can be spread out across all the other idle workers rather than dumped onto one machine1.

The upper bound on M and R comes from the master's own memory footprint. The master must make \(O(M+R)\) scheduling decisions and keeps \(O(M \cdot R)\) state in memory — one in-memory record of task state (idle, in-progress, or completed) and worker identity per map task, and, per completed map task, the locations of the R intermediate file regions it produced1. The paper states the constant factor directly: the \(O(M \cdot R)\) piece of state costs approximately one byte per map-task/reduce-task pair1. Google's own production choice, stated in the same section, is \(M = 200{,}000\) and \(R = 5{,}000\), run on 2,000 worker machines1. Plugging those numbers in:

$$ M \cdot R = 200{,}000 \times 5{,}000 = 1 \times 10^{9} \text{ pairs} \approx 954\ \text{MiB of master state at 1 byte/pair} $$

Under one gigabyte, resident in a single master process's memory, for a job spanning 2,000 machines — a hundred map tasks and roughly two and a half reduce tasks per worker on average. That ratio (\(M/\text{workers} = 100\), \(R/\text{workers} \approx 2.5\)) is exactly the "much larger than the number of worker machines" guidance made concrete, and it is also why the practical upper bound on R is real: users are further constrained because each reduce task's output lands in its own separate file, so in practice the paper reports choosing M so each task is 16-64 MB of input (the same split size chosen for locality) and making R a small multiple of the expected worker count1. A single master architecture — the same simplifying choice Module 7 covered for GFS — only stays simple as long as its in-memory bookkeeping stays in the hundreds-of-megabytes range, not gigabytes; the \(M \cdot R\) arithmetic is the reason the paper's own recommended job sizes stay where they do.

3. Fault tolerance: the map/reduce recovery asymmetry

MapReduce runs on "hundreds or thousands of machines," so the library "must tolerate machine failures gracefully" as a baseline requirement, not an edge case1. The master pings every worker periodically; if a worker does not respond within a certain time, the master marks it failed1. What happens next is deliberately asymmetric between the two task types, and the asymmetry is the single most important fact this module carries forward to Spark's design in §5.

Any map task or reduce task that was in progress on the failed worker is reset to idle and becomes eligible for rescheduling on another machine — that part is symmetric. The asymmetry is about completed tasks. A completed map task is re-executed on a failure, because its output was written to the local disk of the now-unreachable machine and is therefore inaccessible1. A completed reduce task is not re-executed after a failure, because its output was written to the global file system (GFS), which survives the loss of any single machine through its own replication1. Put in one sentence: map output durability is borrowed from whichever machine happened to compute it; reduce output durability is borrowed from the file system underneath the whole cluster. Recomputing a map task is cheap because its input split is still sitting, replicated, in GFS; recomputing a reduce task would be needed only if GFS itself lost the data, which the file system's own replication is designed to prevent.

Worker A fails: its completed map tasks are re-executed on worker B; its completed reduce output is untouched Same failure, two different recovery costs Worker A unreachable local disk: map output (2 done) -- gone with the machine Master no heartbeat re-execute A's 2 completed + any in-progress map tasks Worker B re-runs the 2 map tasks reduce worker re-read reduce output (GFS) already written to the globally replicated file system -- not re-executed on A's failure
Figure 2. When worker A stops responding to the master's pings, every map task A had completed is re-run — because that output lived only on A's local disk — while any reduce task the cluster had already finished is left alone, because its output already sits in GFS1. Reduce workers that had not yet finished reading A's data simply redirect their remote reads to worker B once B completes A's re-executed map tasks1.

3.1 Backup tasks and the cost of not having them

A different failure mode does not involve any machine going down: a straggler, a machine that takes unusually long to finish one of the last few map or reduce tasks, for reasons ranging from a bad disk with degraded read throughput to resource contention with other jobs scheduled on the same box1. The paper reports one real instance where a bug disabling processor caches slowed affected machines' computations by over a factor of one hundred1. The general mitigation is backup execution: when a MapReduce operation is close to completion, the master schedules backup copies of whatever in-progress tasks remain; the task is marked complete whenever either the primary or the backup execution finishes first, and the mechanism is tuned to add no more than a few percent to the computational resources used1. RDDs will reuse this exact idea unmodified in §5 — it works because MapReduce's map and reduce operators are (almost always) deterministic functions of their input, so two executions of the same task produce equivalent output and racing them is safe1.

The paper measures the effect directly on its ~1 TB sort benchmark (1010 100-byte records, M=15,000, R=4,000, ~1,700 machines): a normal execution completes in 891 seconds1. With backup tasks disabled, the same job takes 1,283 seconds — a 44% increase in elapsed time — entirely due to a handful of straggling reduce tasks that don't finish until 300 seconds after everything else1. A separate experiment on the same benchmark intentionally killed 200 of 1,746 worker processes several minutes into the computation; the underlying cluster scheduler restarted new workers immediately, the master re-executed the lost map work, and the whole job finished in 933 seconds — only a 5% increase over the failure-free run1. Read those two numbers together: a straggler that never fails outright costs the job more (44%) than losing over 10% of the workforce outright and recovering from it (5%). This is direct evidence that partial slowness, not outright failure, is the more expensive-to-tolerate condition in this architecture — the reason the backup-task mechanism exists as a separate feature from ordinary worker-failure handling.

Master failure is handled differently again, and deliberately without the same machinery: the master could write periodic checkpoints of its data structures so a new master could resume from the last checkpoint, but because there is only one master, its failure is judged unlikely enough that the current implementation simply aborts the MapReduce job if the master fails, leaving the client to retry the whole operation1. This is the same single-master trade-off Module 3 and Module 7 already introduced for GFS: a single master vastly simplifies the design, and its low failure probability is treated as an acceptable cost of that simplicity rather than something worth building a second consensus-backed mechanism to survive.

Table 1. A representative slice of MapReduce jobs running inside Google in August 2004, from the paper's own production statistics1.
MetricValue
Number of jobs29,423
Average job completion time634 s
Machine-days used79,186
Input data read3,288 TB
Intermediate data produced758 TB
Output data written193 TB
Average worker machines per job157
Average worker deaths per job1.2
Average map tasks per job3,351
Average reduce tasks per job55
Unique map implementations395
Unique reduce implementations269
Unique map/reduce combinations426

Two numbers in Table 1 are worth holding onto for §4: 1.2 average worker deaths per job means that essentially every job of any size experiences at least one machine failure during its run — fault tolerance in this system is not a rare-event insurance policy, it is a per-job certainty being amortized — and 634 seconds of average job completion time is the per-job cost that iterative algorithms in §4 will end up paying on every single pass.

4. Where the model runs out of road: iteration and interactivity

Everything in §§2-3 optimizes a single pass over bounded input, and MapReduce is very good at exactly that: Table 1's 634-second average job and the 79,186 machine-days it consumed in one month were mostly single-pass jobs — build an index, sort a dataset, extract a report. The model starts to strain on two classes of workload the Spark paper calls out by name: iterative algorithms, which apply the same operation to the same dataset over and over until convergence (gradient descent for logistic regression, PageRank's repeated contribution-and-update step), and interactive data mining, where an analyst runs several different ad-hoc queries against the same subset of data in a session2.

Both classes share one property the map/reduce contract does not optimize for: data reuse across computations. In a stock MapReduce (or Hadoop) pipeline, the only way to share a dataset between two jobs is to write it to an external stable storage system — the distributed file system — and have the next job read it back2. For a genuinely one-shot job that is free: you were going to write the output somewhere durable anyway. For ten or a hundred iterations of the same gradient-descent step over the same points, it means paying full disk I/O, replication, and serialization cost on every single iteration to re-read data that has not changed since the last one2. Nothing about this is a bug in MapReduce's fault-tolerance design; the disk-durable stage boundary in Figure 1 is precisely what makes step 6 (reduce output landing in the global file system) survivable in §3. The cost is a direct, structural consequence of using job-to-job durability as the only mechanism for both fault tolerance and data sharing — the same mechanism is being asked to do two jobs, and paying the full cost of the first (durability against failure) on every use of the second (handing data to the next stage) even when no failure occurred.

Specialized systems had already patched around this for narrow cases by 2012 — Pregel keeps iterative graph state in memory for graph-specific computations, HaLoop offers an iterative MapReduce interface that loops a series of MapReduce steps — but both only support one specific computation pattern and share data implicitly within that pattern, rather than providing a general abstraction a programmer can use for arbitrary reuse, such as loading several datasets into memory once and running ad-hoc queries across them2. The gap this module's second half addresses is that general case: a data-sharing abstraction that keeps intermediate results in memory across operations, without giving up the fault tolerance MapReduce gets for free from re-execution and GFS durability.

5. Resilient Distributed Datasets: lineage instead of replication

Spark's answer is a data structure, not a new scheduler: a Resilient Distributed Dataset (RDD) is a read-only, partitioned collection of records that can only be created through deterministic operations, called transformations, on either data in stable storage or another RDD — examples include map, filter, and join2. An RDD does not need to be materialized at all times. Instead, it carries enough information about how it was derived from other datasets — its lineage — to compute its own partitions from data in stable storage whenever it needs to2. The paper states the consequence plainly: "in essence, a program cannot reference an RDD that it cannot reconstruct after a failure"2. If a partition of an RDD is lost, Spark does not restore it from a replica or replay a log — it re-derives it by re-running the recorded transformation chain on whichever ancestor partitions are still available2.

The worked example the paper builds around is log mining. An operator loads error lines out of terabytes of logs sitting in HDFS, then wants to run several interactive queries against just those error lines:

lines = spark.textFile("hdfs://...")
errors = lines.filter(_.startsWith("ERROR"))
errors.persist()

errors.count()
errors.filter(_.contains("MySQL")).count()
errors.filter(_.contains("HDFS"))
      .map(_.split('\t')(3))
      .collect()

The first line defines lines, an RDD backed by the HDFS file; the second derives errors by filtering it; the third calls persist(), which asks Spark to keep errors's partitions in memory once they are computed, so that every later query against errors reuses them instead of re-filtering lines from scratch2. Note that lines itself is deliberately not forced into RAM — the base log file might be far larger than the error subset, so keeping only the derived, smaller RDD resident is the actual point of choosing what to persist()2.

RDD lineage graph for the log-mining example, and recomputation of one lost partition of errors Lineage graph for the third query lines filter(startsWith("ERROR")) errors persist() filter(contains("HDFS")) HDFS errors map(split('\t')(3)) time fields One partition of errors is lost (node failure) lines: p3 re-filter errors: p3 (recomputed, not restored) Only partition p3 of errors is rebuilt. Partitions p1, p2, p4... are untouched and are not re-derived at all. No replica read, no log replay, no rollback of the whole program.
Figure 3. Lineage graph redrawn from the paper's own Figure 1 for its third console-log query2. Boxes are RDDs; arrows are the transformations Spark records but does not execute until an action forces it to. If one partition of the persisted errors RDD is lost, Spark rebuilds it by re-running the recorded filter on only the corresponding partition of lines — the rest of the dataset, and the rest of the pipeline, is untouched2.

5.1 Coarse-grained transformations: the restriction that makes lineage cheap

The design choice that makes this recovery cheap is a restriction, and the paper is explicit that it is a deliberate trade rather than an oversight. RDDs can only be written through coarse-grained transformations — the same operation applied to every element of a dataset — while a general distributed shared memory (DSM) system allows reads and writes to arbitrary individual memory locations2. This restricts RDDs to applications that perform bulk writes, but in exchange it allows for dramatically more efficient fault tolerance2. The paper's own Table 1 lays out the comparison point by point: RDD fault recovery is "fine-grained and low-overhead using lineage," where a DSM system "requires checkpoints and program rollback"; RDD reads can still be fine-grained (an application can treat an RDD as a large read-only lookup table) even though writes cannot2.

The reason coarse-grained writes are the enabling restriction, not an arbitrary one, is that logging one high-level operation ("filter all lines starting with ERROR") is orders of magnitude cheaper than logging or replicating the fine-grained mutations a general key-value store or DSM would need to survive failure on. A system like Piccolo, which exposes a shared, mutable, distributed hash table, must implement fault tolerance by checkpointing that table's contents or replicating individual updates across machines — both of which cost network bandwidth and storage proportional to the size of the data itself2. RDDs, being immutable and built only from bulk transformations, need only log the transformation, not the data:

Worked derivation: lineage graph size vs. replicating the data

The paper reports two concrete numbers from its own fault-recovery experiment (§6.3, detailed with real timings in §7): the lineage graphs for the RDDs in its examples were all under 10 KB in size, while the working sets they describe were on the order of 100 GB2. Contrast that with what a checkpoint-based recovery scheme would need to pay instead: to survive a node failure with the same recovery guarantee via checkpointing, the system would need to replicate the application's full working set across the network, which would either consume twice Spark's memory to hold two full in-RAM copies, or force the system to write the entire multi-gigabyte-to-terabyte working set to disk before it could call itself durable2. The ratio is not a small constant-factor win — it is metadata (kilobytes) standing in for data (gigabytes), a difference of five to seven orders of magnitude, and it is the reason a lost RDD partition is "recovered, often quite quickly, without requiring costly replication," as the paper's introduction puts it2.

This is also why RDDs explicitly do not try to be a general-purpose mutable store. The paper is direct about where the abstraction stops fitting: applications that make fine-grained asynchronous updates to shared state — a storage system for a web application, or an incremental web crawler — are a poor fit for RDDs, and the paper recommends traditional update-logging and checkpointing systems (databases, RAMCloud, Percolator, Piccolo) for exactly that class of problem instead2. RDDs are for batch analytics over bulk data, deliberately leaving asynchronous fine-grained mutation to specialized systems built for it.

5.2 Narrow vs wide dependencies and where recovery gets expensive

Not every lost partition is equally cheap to recompute, and the distinction is exactly which parent partitions a child partition depends on. The paper classifies dependencies between RDDs into two types. A narrow dependency is one where each partition of the parent RDD is used by at most one partition of the child RDD — map and filter are narrow, because each output partition is computed purely from the one input partition at the same index. A wide dependency is one where multiple child partitions may depend on the same parent partition — groupByKey is wide, and so is a join whose inputs are not already partitioned the same way2.

Narrow dependencies map one parent partition to one child partition; wide dependencies fan many parents into one child and force a stage boundary Narrow (map, filter) Wide (groupByKey, join without co-partitioning) parent partitions child partitions 1 parent partition -> 1 child partition recompute one lost partition in isolation parent partitions child partitions many parents -> each child (shuffle) losing one child needs all parent ancestors: a full re-execution A wide dependency is also where Spark's scheduler cuts a stage boundary and materializes intermediate data, much like MapReduce's shuffle2.
Figure 4. Narrow dependencies (map, filter, union) let Spark pipeline execution on one node and recompute a lost partition by touching only the one parent partition it needed. Wide dependencies (groupByKey, an un-co-partitioned join) require data from every parent partition to compute one child partition, so recovering after a node failure can require recomputing partitions from every ancestor RDD — closer to a full re-execution2.

The distinction earns its place in the interface for two separate reasons the paper states directly. First, narrow dependencies allow pipelined execution on one cluster node, which can compute all the parent partitions it needs without any data leaving the machine; wide dependencies, by contrast, require data from all parent partitions to be available and shuffled across the nodes in a MapReduce-like operation before the child can be computed at all2. Second — the recovery-cost point Figure 4 draws — recovery after a node failure is far more efficient with a narrow dependency, because only the lost parent partitions need to be recomputed, and they can be recomputed in parallel on different nodes; with a wide dependency, a single failed node can cause the loss of some partition from every one of an RDD's ancestors, which can require a complete re-execution of the lineage chain up to that point2. This same narrow/wide split is what determines Spark's job-stage boundaries at scheduling time: the scheduler builds pipelined stages out of chains of narrow-dependency transformations, and starts a new stage only where a wide dependency forces a shuffle or where an already-computed, persisted partition lets it short-circuit a parent RDD's computation entirely2.

6. Persistence, checkpointing, and when lineage isn't enough

Spark gives programmers three storage options for a persisted RDD: as deserialized Java objects in memory, which is fastest because the JVM can access each element natively; as serialized data in memory, which is more space-efficient at some CPU cost to deserialize; and on disk, for RDDs too large to keep resident but too costly to recompute on every use2. When a new RDD partition needs space and there isn't enough, Spark evicts a partition from the least-recently-accessed RDD, using an LRU policy at the RDD level, unless the new partition belongs to the same RDD as the one being considered for eviction, in which case the old partition is kept to avoid cycling partitions of the same RDD in and out of memory2. Users get a further override for their own memory-priority tuning via a persistence-priority flag2.

Lineage-based recovery can always reconstruct a lost RDD, but §5.2 already showed that "always possible" and "always cheap" are different claims once wide dependencies are involved. The paper is explicit that checkpointing — writing an RDD's data, not its lineage, out to stable storage — is useful specifically for RDDs with long lineage graphs containing wide dependencies, such as the ranks dataset in the PageRank example, where a node failure could force recomputation from every ancestor partition2. For RDDs built entirely from narrow dependencies on data already in stable storage — the points RDD in the logistic-regression example, or the static links RDD in PageRank — checkpointing may never be worth it: if a node fails, the lost partitions can be recomputed in parallel on other nodes at a fraction of the cost of replicating the whole RDD2.

Spark's checkpointing API at the time of the paper was manual: a REPLICATE flag passed to persist(), leaving the decision of which RDDs to checkpoint entirely to the programmer2. The paper flags automatic checkpoint-set selection as future work, noting that because the scheduler already knows each dataset's size and the time it originally took to compute, it should in principle be able to choose an optimal checkpoint set to minimize expected recovery time — but that optimization was not implemented in the system the paper measures2. One property makes checkpointing itself cheaper here than in a general DSM system: because RDDs are read-only, checkpointing can run in the background without requiring the application to pause or take a consistent distributed snapshot, since there is no concurrent mutation to a checkpointed RDD to race against2.

7. The measured case for Spark

The paper's headline claims are stated in its abstract and then backed with specific benchmarks: Spark is up to 20x faster than Hadoop for iterative applications, speeds up a real-world data analytics report by 40x, and can be used interactively to scan a 1 TB dataset with 5-7 second latency2. The benchmarks that produce the "20x" figure compare three systems on a 100-node EC2 cluster running 10 iterations over 100 GB of data: stock Hadoop 0.20.2; "HadoopBinMem," a variant that pre-converts the input to a low-overhead binary format and serves it from an in-memory HDFS instance, isolating the cost of text parsing from the cost of the Hadoop stack itself; and Spark2.

Hadoop vs Spark per-iteration time for logistic regression and k-means, 100-node cluster, 100 GB 120s 60s 0s 76 Hadoop 62 HadoopBM 3 Spark Logistic Regression — 25.3x / 20.7x faster 106 Hadoop 33 Spark K-Means — 3.2x faster Average time per iteration after the first (seconds)
Figure 5. Later-iteration time for logistic regression and k-means, 100-node cluster, 100 GB of data, redrawn from the paper's Figure 72. Logistic regression is I/O- and deserialization-bound, so avoiding repeated HDFS reads and object deserialization is worth 25.3x against Hadoop and 20.7x against the in-memory-binary HadoopBinMem variant2. K-means is compute-bound — most of its iteration time is spent on the clustering arithmetic itself, not I/O — so the same change in storage layer is worth only 3.2x, matching the paper's stated 1.9-3.2x range for k-means across cluster sizes2. The abstract's "up to 20x" is a conservative summary of the first number, not an average of both.

The paper's own explanation for why Spark beats even HadoopBinMem by a wide margin — despite HadoopBinMem already avoiding text parsing and serving data from RAM — is threefold: a minimum fixed overhead in the Hadoop software stack itself (measured at at least 25 seconds just for job setup, task startup, and cleanup on a no-op job); overhead in HDFS while serving data, including multiple in-memory copies and a checksum computed for every block served; and the cost of deserializing binary records into usable in-memory Java objects, which the paper measured at about 3 seconds on top of a 2-second HDFS-read overhead for 256 MB of input, comparable to the cost of the logistic-regression computation itself2. Spark avoids all three because RDD elements already sit in memory as native Java objects between operations; there is no HDFS layer, no checksum, and no deserialization step in the hot loop after the first read.

Three more results round out the case, and each isolates a different mechanism. On PageRank over a 54 GB Wikipedia dump (roughly 4 million articles, 10 iterations), in-memory storage alone gives Spark a 2.4x speedup over Hadoop at 30 machines; additionally controlling the partitioning of the RDDs so it stays consistent across iterations — hash-partitioning the static links RDD once so every join against the per-iteration ranks RDD needs no shuffle — improves that to 7.4x, and the result scales nearly linearly out to 60 machines2. On fault recovery, a 75-node, 10-iteration k-means run with a machine killed at the start of iteration 6 shows iteration times holding steady at about 58 seconds for iterations 1-5, jumping to 80 seconds for iteration 6 while Spark re-runs the lost tasks and reconstructs the affected RDD partitions via lineage, then returning to 58 seconds for the remaining iterations2 — a 22-second, one-time cost to lose and rebuild one node's share of the data, not a job-wide restart. And on interactive querying, scanning an entire 1 TB in-memory Wikipedia page-view-log dataset across 100 m2.4xlarge instances returns query results in 5-7 seconds, more than an order of magnitude faster than the 170 seconds the same query takes reading the same 1 TB file from disk2.

Table 2. MapReduce and Spark/RDD compared on the mechanisms this module derived12.
PropertyMapReduceSpark / RDD
Durability of intermediate outputMap output: local disk (ephemeral). Reduce output: GFS (replicated)Lineage graph (metadata, <10 KB typical); data optionally checkpointed
Fault-tolerance mechanismRe-execute the failed task from its inputRecompute only the lost partition from its lineage
Unit of recovery on node lossEvery map/reduce task that was on that nodeThe lost partitions only — whole ancestors only if a wide dependency is involved
Straggler mitigationBackup tasks near job completion1Backup tasks, same mechanism, reused directly2
Data reuse across jobs/queriesWrite to GFS/HDFS, re-read by the next jobpersist() keeps partitions resident in memory across actions
Programming restrictionTwo typed functions, map and reduceCoarse-grained transformations only (map, filter, join, ...); no fine-grained writes
Iterative workload, 100 GB, 100 nodes76 s/iteration (logistic regression)23 s/iteration (logistic regression)2
Best fitOne-shot batch jobs over data used onceIterative algorithms and interactive queries reusing the same data

8. Batch and stream processing after MapReduce: micro-batch vs continuous dataflow

Everything so far assumes bounded input: a fixed set of files sitting in GFS or HDFS, known in advance, that a job reads once from beginning to end. A general textbook framing of the alternative is useful here: batch processing takes a finite input and produces a finite output; stream processing treats its input as unbounded, a series of events that keeps arriving and is never "done"3. Module 8 covered the log (Kafka) that supplies unbounded input in practice; this section is about what a compute framework does with it, because the RDD paper itself already names the resulting fork.

The RDD paper's own related-work section calls out "batched stream processing" as an adjacent, not-yet-unified problem: systems were being proposed at the time that periodically update a result with new data — recomputing a report every 15 minutes by combining intermediate state from the previous window with newly arrived logs — performing bulk operations similar to Dryad but storing application state in distributed filesystems, where placing that intermediate state in RDDs instead would speed the processing up2. That description is, almost exactly, Spark Streaming: a stream is discretized into a sequence of small, bounded RDDs, each covering a short time window, and the exact same map/reduce-lineage machinery from §§5-7 runs on each one in turn. Spark's current production successor to that design, Structured Streaming, states its own execution model directly: "by default, Structured Streaming queries are processed using a micro-batch processing engine, which processes data streams as a series of small batch jobs," and reports end-to-end latencies as low as 100 milliseconds with exactly-once fault-tolerance guarantees, inherited from the same lineage-based recovery this module derived for batch RDDs4.

Flink starts from the opposite direction. A Flink program is a dataflow: sources read input, transformations are applied by calling methods that add operators to the graph, and sinks consume the resulting stream and forward it to files, sockets, or external systems5. Flink programs execute lazily — the data loading and transformations described in a program's code do not run when the code runs; instead, each operation is added to a dataflow graph, and the graph as a whole is triggered as one holistically planned, continuously running unit only when execution is explicitly requested5. There is no discretization step: a record that arrives is processed by the operator graph as it arrives, not batched up into a window first and handed to a scheduler that treats each window as an independent job. Spark itself offers a matching continuous-processing option — since Spark 2.3, an experimental Continuous Processing mode achieves end-to-end latencies as low as 1 millisecond, but only with at-least-once guarantees rather than the micro-batch engine's exactly-once4, which is the tell that record-at-a-time execution and the lineage-replay recovery this module spent §§5-7 deriving are not free to combine: give up the discrete, replayable batch boundary and you give up exactly-once for free, too.

Where experts disagree

Section 8 already surfaced the live fork: once a compute framework has to process unbounded input rather than the bounded input §§1-7 assumed, should it reuse the batch engine's job-and-scheduler machinery by discretizing the stream into small batches, or should it be built ground-up as a continuously running dataflow that processes one record at a time? This is not a resolved question with one side simply wrong — it is a genuine architectural fork that two widely deployed systems answer differently, and the answer changes what a downstream engineer gets for free and what they have to build themselves.

Discretize into micro-batches, reuse the batch engine

Apache Spark / Structured Streaming4, and implicitly the RDD paper's own related-work framing of "batched stream processing" as an extension of bulk operations rather than a separate execution model2

Treat a stream as a sequence of small, bounded RDDs (or DataFrames), one per short time window, and run the identical scheduling, lineage-tracking, and lazy-transformation machinery derived in §§5-7 on each one. Fault tolerance, exactly-once semantics, and the programming model are the same code path as batch Spark, not a second system with a second set of failure modes to learn.

  • One fault-tolerance and consistency story for both batch and streaming jobs on the same platform4
  • Exactly-once end-to-end by default, because each micro-batch is a replayable, lineage-tracked unit4
  • Reuses a mature scheduler and the same operational tooling as every other Spark job on the cluster
  • Latency is bounded below by the batch interval; the default micro-batch engine's floor is around 100 ms4
  • Spark's own lower-latency alternative (Continuous Processing, ~1 ms) trades away exactly-once for at-least-once, showing the discretization boundary is load-bearing for the stronger guarantee4

Build a continuous dataflow engine from the ground up

Apache Flink5

Represent the whole program as one dataflow graph of sources, operators, and sinks that runs continuously once triggered, with no discrete per-window job boundary at all5. Records are processed as they arrive rather than being collected into a window first, and the fault-tolerance mechanism (periodic distributed snapshots of operator state, not lineage replay of a bounded RDD) is designed around that continuity rather than adapted from a batch engine.

  • No batch-interval floor on latency — records are handled individually, not accumulated into a window first
  • One execution model for genuinely unbounded streams, without borrowing a job abstraction designed for bounded input
  • A different checkpointing and backpressure mechanism from the batch engine's lineage-and-re-execution story this module derived, so an operator moving between Spark-style batch and Flink-style streaming systems is learning a second failure model, not reusing the first
  • Cannot lean on the arithmetic in §5.1's derivation (kilobytes of lineage standing in for gigabytes of data) in the same direct way, because there is no discrete RDD boundary at which to draw a lineage graph
Assessment

Neither position is wrong; they are optimizing for different constraints, and the RDD paper's own text is the tell — it describes the micro-batch idea as a natural extension of the bulk-operation, lineage-based world it had just built, not as a concession2. Micro-batching wins whenever a pipeline already lives on Spark/RDD lineage (which, per Module 32, most training-data batch pipelines do) and a few hundred milliseconds of latency is acceptable: it is one system, one fault-tolerance model, and one operational surface for both the batch jobs this module derived and the streaming jobs built on top of them. A ground-up continuous dataflow engine wins when the workload's own latency budget is sub-100ms end to end, or when correctness depends on exactly-once state that spans arbitrarily many records rather than resetting at each micro-batch boundary — a case where a replayable, bounded unit of work is the wrong abstraction to begin with. What would settle it for a specific workload is not a benchmark of the engines in the abstract, but measuring where that workload's own latency requirement sits relative to the ~100ms micro-batch floor Spark's own documentation states as its default engine's achievable range4: above that floor, the reuse argument for micro-batching dominates; below it, the case for a purpose-built continuous engine does.

References

  1. paperDean, J., Ghemawat, S. MapReduce: Simplified Data Processing on Large Clusters. OSDI 2004. https://research.google.com/archive/mapreduce-osdi04.pdf. Accessed 2026-09-17. Used for: the map/reduce type contract (§2.2), execution overview and Figure 1 (§3.1), master data structures and task-granularity arithmetic (§3.2, §3.5), worker/master failure handling (§3.3), locality optimization (§3.4), combiner functions (§4.3), backup tasks/stragglers (§3.6, §5.4), and the August 2004 production statistics (Table 1).
  2. paperZaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauley, M., Franklin, M. J., Shenker, S., Stoica, I. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing. USENIX NSDI 2012. https://www.usenix.org/system/files/conference/nsdi12/nsdi12-final138.pdf. Accessed 2026-09-17. Used for: the RDD abstraction and lineage graph (§2.1, Fig.1), the RDD-vs-DSM comparison and Table 1 (§2.3), narrow vs wide dependencies (§4, Fig.4/5), persistence/LRU eviction and checkpointing (§5.3/§5.4), and all benchmark figures (§6, Figs.7-14).
  3. textbookKleppmann, M., Riccomini, C. Designing Data-Intensive Applications. 2nd ed., O'Reilly Media, 2026. https://www.oreilly.com/library/view/designing-data-intensive-applications/9781098119058/. Accessed 2026-09-17. Used for: the general bounded-input (batch) vs. unbounded-input (stream) framing (no specific chapter cited — the publisher's table-of-contents page returned HTTP 403 to automated fetch, and 2nd-edition chapter numbering relative to the well-known 1st-edition Batch Processing/Stream Processing chapters is unconfirmed).
  4. officialThe Apache Software Foundation. Structured Streaming Programming Guide. Apache Spark v3.5.6 docs. https://spark.apache.org/docs/3.5.6/structured-streaming-programming-guide.html. Accessed 2026-09-17. Used for: the default micro-batch processing engine and its ~100ms end-to-end latency with exactly-once guarantees, and the experimental Continuous Processing mode's ~1ms latency with at-least-once guarantees (Overview section).
  5. officialThe Apache Software Foundation. DataStream API — Anatomy of a Flink Program. Apache Flink 1.19 docs. https://nightlies.apache.org/flink/flink-docs-release-1.19/docs/dev/datastream/overview/. Accessed 2026-09-17. Used for: the dataflow-graph program model (sources, transformations, sinks) and lazy, continuously-executing dataflow graph semantics.