You can’t really understand Spark without understanding the thing it was built to replace. So before we get to Spark itself in lesson 3, we need to spend a lesson on MapReduce — the programming model that defined an entire decade of distributed data processing, and the system that, more than anything else, made it possible for a normal application programmer to do work across a thousand machines without becoming a distributed-systems expert first.
If you started doing data work after, say, 2018, you may have skipped MapReduce entirely, in the same way someone learning JavaScript today can mostly avoid jQuery. That’s fine, but it leaves a gap. Most of the vocabulary of distributed data — map, reduce, shuffle, partition, job, stage — comes directly out of MapReduce. Spark inherited the model wholesale and then optimised the parts that hurt the most. Knowing what MapReduce was, what it got right, and what it got catastrophically wrong tells you most of what you need to know about why Spark looks the way it looks.
The 2004 paper
The story starts in December 2004, at the Sixth USENIX Symposium on Operating Systems Design and Implementation, where two Google engineers named Jeffrey Dean and Sanjay Ghemawat presented a paper titled “MapReduce: Simplified Data Processing on Large Clusters.” It is one of the most-cited systems papers in computer science history, and if you’ve never read it, it’s worth an evening — it’s eleven pages, written in plain English, and deceptively simple.
The context is important. Google in 2003 was running an entire web crawl, a search index, an ad system, and a dozen other internal services across what was already a planet-scale fleet of cheap commodity servers. Their engineers were writing custom distributed programs all the time — to parse logs, to build inverted indices, to count things, to sort things, to deduplicate things. Every single one of those programs had to independently solve the same hard problems: how do you split the input across machines, how do you handle the inevitable failures, how do you coordinate the workers, how do you put the answer back together. Each program reinvented the same scaffolding, badly.
Dean and Ghemawat’s insight was that almost all of these programs, despite looking superficially different, fit the same basic shape. You take a big input, you transform each record into one or more intermediate records (the map step), you group all the intermediate records by some key (the shuffle step, which the paper barely names), and then you combine the records for each key into a final answer (the reduce step). If you could give programmers an API where they wrote only the map function and the reduce function, and the framework handled everything else — splitting, scheduling, shuffling, fault tolerance, retries — then a vast number of distributed programs would suddenly become trivial to write.
That is the entire idea. Map. Shuffle. Reduce.
The model in plain words
A MapReduce job has three logical phases.
The map phase runs in parallel across many workers. Each worker reads a chunk of the input — typically a block from the distributed filesystem — and runs a user-supplied map function over each record. The map function takes one input record and emits zero, one, or many (key, value) pairs. That’s it. No coordination with other workers, no shared state, no global variables. Each map task is embarrassingly parallel and completely isolated.
The shuffle phase is the part nobody thinks about until they’re debugging it at 2 AM. After all the map outputs are produced, the framework groups them by key. All (key, value) pairs with the same key, no matter which mapper produced them, get sent to the same reducer. This requires moving data across the network, which is the expensive part. In Google’s original implementation, mapper outputs are written to local disk, then pulled by reducers over the network. The shuffle is where most of a MapReduce job’s wall-clock time disappears.
The reduce phase also runs in parallel across many workers. Each reducer is responsible for a subset of the keys. For each key, it receives the entire list of values that any mapper emitted for that key, and runs a user-supplied reduce function over that list to produce the final output. Output is written back to the distributed filesystem.
That’s the whole model. Two functions, one shuffle, three phases, parallel everything. The framework decides how many mappers and reducers to run, where to run them, what to do when one of them dies, and how to put the final files together.
A worked example: word count
Every MapReduce tutorial since 2004 has used the same example — counting how often each word appears in a large corpus — because it captures the model perfectly with no extraneous detail. Let’s walk through it the same way.
Imagine the input is a directory full of text files in HDFS, totalling say 2 TB. You want, for each word that appears anywhere in the corpus, the number of times it appears across all files.
The pseudocode is genuinely about four lines, which is the whole point.
map(filename, line):
for word in line.split():
emit(word, 1)
reduce(word, counts):
emit(word, sum(counts))That’s it. The framework reads the input, hands every line of every file to a mapper, and the mapper emits (word, 1) for each word it sees. The framework shuffles all of those tuples so that all the (the, 1) pairs end up at the same reducer, all the (spark, 1) pairs end up at another reducer, and so on. Each reducer sees its assigned key plus an iterable of all the 1’s that were emitted for that key, sums them, and writes out the total.
If your corpus has 10 billion words and 1 million distinct words, MapReduce will happily run this on a thousand machines, recover from a few worker failures along the way, and give you back a single deduplicated table of word counts. The programmer wrote eight lines of pseudocode. The framework did the rest.
This is the breakthrough. Not the speed — early MapReduce was not fast in any absolute sense — but the abstraction. Distributed processing went from “write a custom RPC system, a custom partitioner, a custom retry layer, and pray” to “write a map function and a reduce function.” Suddenly, hundreds of Google engineers who had no business writing distributed systems code were writing distributed systems code, and it mostly worked.
Hadoop: turning the paper into open source
The Google paper described an internal Google system. The implementation was not released. But two engineers at Yahoo, Doug Cutting and Mike Cafarella, were already working on an open-source web crawler called Nutch, and they had been hitting exactly the same scaling problems Google had hit a few years earlier. They read the paper. They read the related Google File System paper from 2003. And in 2006, they extracted the relevant pieces of Nutch into a new project named after Cutting’s son’s stuffed elephant: Hadoop.
Hadoop was, in essence, an open-source clone of Google’s two foundational systems. The Hadoop Distributed File System (HDFS) was the GFS analogue: a way to store enormous files across many machines with replication for fault tolerance. Hadoop MapReduce was the MapReduce analogue: a Java framework for writing map and reduce functions and running them across a cluster.
The combination — HDFS for storage, MapReduce for compute — became the default open-source big data platform for roughly a decade. Cloudera, Hortonworks, MapR, and a dozen smaller distros built businesses on packaging and supporting it. By 2012 or so, every Fortune 500 company that had any pretence of being “data-driven” had a Hadoop cluster somewhere in a basement, often barely used, almost always operated by exactly one terrified consultant named Steve.
The Hadoop ecosystem grew enormous. Hive (SQL on top of MapReduce). Pig (a scripting language on top of MapReduce). HBase (a NoSQL database on top of HDFS). Oozie (a workflow scheduler for chaining MapReduce jobs). YARN (a resource manager for running multiple frameworks on the same cluster, introduced in Hadoop 2.0 in 2012). Most of these are still around in 2026 in some form, though usually in much-reduced roles. Hive in particular survives as a metadata layer — the Hive Metastore — long after almost nobody runs Hive queries via MapReduce anymore.
Why everyone moved on
By around 2014, the cracks in MapReduce were impossible to ignore. The model was elegant, but the original implementation had three properties that made it increasingly painful to actually use.
Everything is two stages. Map then reduce. That’s the whole API. Real-world data work almost never looks like exactly one map and one reduce. A typical pipeline is: read input, filter, parse, join with a lookup table, group, aggregate, sort, join again, write output. In MapReduce, every one of those operations becomes its own job, with its own map step, its own reduce step, and its own write to HDFS in between. A pipeline that should be a five-step query becomes a chain of seven separate MapReduce jobs orchestrated by Oozie, each one a self-contained Java program with a hundred lines of boilerplate.
Intermediate state hits disk between every job. This is the killer. The output of a MapReduce job is always written to HDFS, in triplicate (default replication factor of 3), and then the next job in the chain reads it back. If your pipeline has six stages, you have written your data to disk six times and read it back five times. On 2010-era spinning disks, with 2010-era network bandwidth, this was just how things worked, and people accepted it. By 2014, with SSDs and 10-gigabit networking, it was visibly absurd.
Iterative algorithms are catastrophically slow. Machine learning, graph algorithms, and anything else that runs the same logic over the same data many times — k-means clustering, PageRank, logistic regression — all do this. Each iteration is an entire MapReduce job, which means each iteration writes the entire dataset to HDFS and reads it back. A k-means clustering job that should take 30 seconds takes 30 minutes, almost all of which is disk I/O for data that hasn’t even changed between iterations. This was the specific pain point that motivated Spark.
There were other complaints — the Java API was verbose, the failure modes were obscure, the configuration files were endless XML, the JVM startup overhead made small jobs disproportionately slow — but the deepest problem was architectural. MapReduce was a model designed in 2003 around 2003-era hardware assumptions, and by 2014 those assumptions no longer held.
The fix, as you may already be guessing, was to build a system that kept intermediate state in memory between operations rather than writing it to disk every single time. To let a programmer chain together as many transformations as they liked into a single logical job, with the engine deciding how many physical stages were actually needed. To make iteration cheap by caching working sets in RAM. To stop pretending every computation was exactly one map plus one reduce.
That system was Spark, and it’s the subject of lesson 3.
For further reading: the original Dean–Ghemawat MapReduce paper is genuinely one of the most readable systems papers ever published, and it’s worth reading even if you’ll never write a MapReduce job in your life. The Apache Hadoop project documentation is still maintained, mostly for the parts (HDFS, YARN, the Metastore) that survived the transition. Both are useful background for the rest of this course, even though we won’t be writing any actual MapReduce code.