It is easy to talk about MapReduce as a thing that was replaced, which obscures the fact that almost every distributed engine in use today is a refinement of its core bargain rather than a repudiation of it. Understanding what that bargain was, and what it cost, is the only honest way to understand why the engines that followed are shaped as they are.

The bargain was this: you write two pure functions, and the system handles distribution, failure, retry and data movement. A map function transforms one record into zero or more key and value pairs. A reduce function receives all the values that share a key and produces an output. Between them sits a shuffle, which is the system's job rather than yours, and which moves every intermediate record to the machine responsible for its key.

What made this a genuine advance was not the programming model, which is restrictive and awkward for most real problems. It was the failure story. Because map and reduce are deterministic functions of their inputs, and because every intermediate result is written to durable storage, any task can be re run on any machine at any time and produce the same answer. A worker dying is not an incident, it is a retry. A machine being slow is handled by running a second copy of its task elsewhere and taking whichever finishes first.

The three phases, and what each one owns

A map phase reads input splits, typically one per block of the input files, and runs the map function over each record. The output is written to local disk, partitioned by the hash of the key, so that each map task produces one file per reducer. This is the first materialisation and it is unconditional.

The shuffle moves those partitioned files across the network. Each reducer fetches its partition from every map task, which means the number of transfers is the product of map tasks and reduce tasks. A job with ten thousand mappers and a thousand reducers performs ten million fetches, and this number, not the data volume, is frequently what makes a shuffle slow.

The reduce phase sorts the fetched data by key, groups it, applies the reduce function and writes the result to the distributed filesystem. That final write is the second unconditional materialisation, and it is replicated, which means every byte of output is written three times before the job is considered complete.

Why determinism was the whole design

Every property people liked about MapReduce follows from determinism plus materialisation, and it is worth tracing the chain carefully because the engines that came later had to preserve the conclusions while removing the premise.

Because tasks are deterministic, a failed task can be retried without coordinating with anything else. Because intermediate output is on disk, a retried reduce task can re fetch its inputs from map outputs that still exist, without re running the maps. Because output is written once at the end and then committed, a partially failed job leaves no half visible results. And because the scheduler can run speculative duplicates of slow tasks, a single slow machine costs a few percent rather than lengthening the job.

None of these properties is free, and they share a single price: everything is written down. The system's resilience is purchased with disk and network, paid on every job regardless of whether any failure occurs.

The combiner, and what it tells you

One optimisation in the original model is worth singling out because it previews everything the later engines did. A combiner is a reduce function run on the map side, over the output of a single map task, before the shuffle. If the reduce operation is associative and commutative, applying it early is safe, and it shrinks what has to cross the network by whatever factor the local aggregation achieves.

For a word count over a large document corpus, a combiner reduces each map task's output from one record per word occurrence to one record per distinct word in that split, which is frequently two orders of magnitude. The job's answer is identical and the shuffle is a hundredth of the size.

The point to take from this is that the single largest optimisation available in the model required the system to know something about the user's function, namely that it was associative. MapReduce had no way to know this, so it had to be declared, and most users did not declare it. A system that understood the operation rather than treating it as an opaque function could have applied the optimisation automatically, and that observation is most of the argument for the query planners that arrived later.

What it was genuinely bad at

The restriction to two phases is the complaint people remember, and it is real but secondary. Any computation can be expressed as a sequence of MapReduce jobs, so expressiveness is not actually the limit. The limit is what that sequence costs.

Consider a pipeline that joins two datasets, aggregates the result, joins against a third and aggregates again. That is four jobs. Each one reads its input from the distributed filesystem, writes its output back with replication, and the next one reads it again. The intermediate results, which nobody will ever look at and which exist for seconds, are written three times and read once. For a pipeline whose intermediate datasets are large, the cost of storing and moving data nobody wants exceeds the cost of the computation by a wide margin.

Iterative algorithms make this worse in a particular way. A machine learning algorithm that passes over the same dataset fifty times, updating a small model each pass, reads that dataset from durable storage fifty times, because there is no mechanism for keeping it in memory between jobs. The dataset is immutable and identical every time, and the system has no way to know that.

Interactive queries suffer from a different part of the same design. A query that returns a thousand rows from a billion still starts a job, allocates containers, reads splits and goes through the full lifecycle, with a startup cost measured in tens of seconds. For a batch job running for an hour that cost is noise. For an analyst asking a question it is the entire experience.

Where the time actually went

It is worth putting numbers on the complaint, because the shape of the breakdown explains which optimisations were worth pursuing.

On a typical multi job pipeline of the era, the map and reduce functions themselves, the actual user computation, accounted for a minority of wall clock time. The shuffle, including the sort and the fetches, was usually the largest single component. Writing and reading intermediate results to the distributed filesystem was the next largest, and job startup, container allocation and the gaps between jobs in a chain made up a surprising remainder, often ten to twenty percent on a pipeline of many short jobs.

That breakdown says the user's code is not the thing to optimise. It says the data movement is, and the places where data moves are precisely the places where the model forced a materialisation. An engine that could choose not to materialise, and could tell the difference between a stage boundary that genuinely redistributes data and one that merely separates two jobs somebody happened to write apart, had most of that time available to recover.

The three things the next generation had to keep

Any replacement had to preserve what made the original trustworthy, and it is worth stating those requirements precisely because they constrain every design that followed.

It had to keep the ability to recover from a lost worker without re running the whole job. It had to keep the ability to run duplicate copies of slow tasks safely, which requires determinism. And it had to keep the property that a job either produces its complete output or produces nothing visible.

The interesting part of the next twenty years is that all three were preserved while the unconditional materialisation that originally provided them was removed. That substitution is the subject of this lesson.