MapReduce: Divide and Conquer at Scale

A Worked Example: Top Songs Across 100B Plays

The 2004 Google MapReduce paper handed the industry a pattern that still runs ETL pipelines today. Walk through it on a Spotify-scale workload.

Input. A year of play logs: ~100 billion lines, each user_id, song_id, timestamp, duration_ms, scattered across 1,000 chunk files in HDFS.

Goal. The top 100 most-played songs of 2026.

The job has three phases, all distributed across the cluster.

Phase 1: Map

Each of 1,000 mapper workers reads one chunk file in parallel. For every line, the mapper emits a single key-value pair:

def map(line):
    user_id, song_id, ts, duration = parse(line)
    emit(song_id, 1)        # one play of this song

After Phase 1: ~100 billion key-value pairs sitting on the mappers' local disks.

Phase 2: Shuffle (the hidden core)

The framework hash-partitions every key-value pair by song_id. All (song_id=42, 1) pairs from any mapper end up on the same reducer (machine hash(42) % 100). This is the same hash-partitioning algorithm from Distributed Sort & Hash, now running automatically as part of the job.

Each reducer ends up with all the values for some subset of song IDs. Most of the wall clock goes here, because shuffle moves data across the network and writes it to disk.

Phase 3: Reduce

Each of 100 reducer workers gets a chunk of the song ID space and sums:

def reduce(song_id, list_of_ones):
    emit(song_id, sum(list_of_ones))

After Phase 3: ~50 million (song_id, count) pairs (one per song that was played at least once). A small follow-up sort gives the top 100.

Cost. ~10 minutes wall clock on 1,000 machines. The same job on a single beefy server: weeks.

Why MapReduce Won (2004–2014)

The model gave developers four things at once:

1. A simple programming surface. Two functions. No knowledge of how the cluster moves data, recovers from failures, or load-balances.

2. Built-in fault tolerance. When a worker dies mid-job, the framework restarts that worker's task on a different machine. Map and reduce are deterministic, so reruns produce the same answer.

3. Linear scaling. Doubling the cluster doubles throughput, up to thousands of machines.

4. Commodity hardware. Same calculus as GFS (5.1): a thousand cheap servers beats one supercomputer on price-per-throughput.

The trade-off is throughput-first, latency-last. The shuffle phase writes everything to disk. A 10-minute MR job feels glacial compared to a 100ms SQL query, but it processes 100,000× the data.

Where MapReduce Hit a Wall

By 2014 the industry had moved past pure MapReduce for two reasons:

• Iterative algorithms are slow. Machine learning needs many passes over the data; pure MR writes to disk between every pass, paying the IO cost every time.

• Interactive analytics need sub-minute response. A data scientist exploring a hypothesis cannot wait 10 minutes per query.

Both failure modes have the same root cause: the materialize-to-disk-between-stages design that made MR easy to recover from also made it slow whenever the same data was touched twice. The fix, covered next, is to keep intermediate data in RAM.

Next

Spark → Spark keeps the same hash-partitioning + worker model but holds intermediate data in memory and represents the pipeline as a chain of operators. Result: 100× speedup on iterative work, interactive analytics on terabyte-scale data.