MapReduce

1The core idea#

Start with the problem, because it explains every design choice later.

The setup.

• You have a huge pile of data, far more than fits on one machine.
• You want to compute something over all of it: word counts across every scanned book, ad clicks per campaign, an inverted index for search.
• One box cannot hold the data, and even if it could, one CPU would grind for days.

Put a real number on it.

• 1 TB of logs, one machine reading at 100 MB/s off disk.
• That is 10,000 seconds just to read the data once, about 2.8 hours, before counting a single thing.
• Spread that read across 500 machines and each touches 2 GB, roughly 20 seconds of reading.
• Hours versus seconds. That gap is the entire reason this pattern exists.

The insight: these computations split into two phases.

• Map. Look at one small piece of input at a time and emit key-value pairs. The map function has no idea the rest of the data exists. Each record is independent, so you can run map on thousands of machines at once.
• Reduce. For each key, collect every value any mapper emitted for that key, and fold them into a final answer. Sum, count, max, whatever you need.

Word count, the classic example.

• Map takes a line of text and emits (word, 1) for every word.
• Reduce takes a word plus its list of 1s and adds them up.

map("the cat sat")   -> (the, 1), (cat, 1), (sat, 1)
map("the dog ran")   -> (the, 1), (dog, 1), (ran, 1)
reduce(the, [1, 1])  -> (the, 2)
reduce(cat, [1])     -> (cat, 1)

The magic is in the middle.

• Between map and reduce, the system groups every value by key and ships all values for one key to the same reducer.
• That step is the shuffle, where most of the real cost and real pain live.
• You never write shuffle code. You write two pure functions and the framework splits input, schedules tasks, moves data across the network, retries failures, and sorts.

2How it works#

Walk through what actually happens when you submit a job over 1 TB of input on a few hundred machines.

Input and map tasks.

• The input sits in a distributed file system (HDFS or S3), already chopped into 128 MB blocks.
• The framework creates one map task per block, so 1 TB divided by 128 MB is roughly 8,000 map tasks.
• A central coordinator assigns these tasks and tries hard to run each one on the machine that already holds that block.

Data locality is one of the biggest ideas here.

• Move the compute to the data, not the data to the compute.
• On the 1 TB job, locality is the difference between 1 TB of reads staying local versus 1 TB crossing a shared network link everyone else is fighting for.

The map side.

• Each map worker reads its block, runs your map function per record, and writes the emitted pairs to its own local disk.
• Before writing, it partitions the output by key, usually hash(key) % R where R is the number of reducers.
• So each mapper produces R little sorted files, one bucket per reducer.

The shuffle.

• Each reducer pulls its bucket from every single mapper.
• With 8,000 mappers and 100 reducers, that is 8,000 x 100, so 800,000 network fetches.
• The reducer merges the pieces, sorts them so equal keys sit together, runs your reduce once per key, and writes the result back to the distributed file system.

A few mechanics matter a lot in interviews.

The combiner.

• A single mapper reading 128 MB of English text might emit (the, 1) ten thousand times.
• A combiner is a mini-reduce that runs on the map side, so the mapper sends (the, 10000) instead: one record where there were ten thousand.
• It can cut shuffle traffic by orders of magnitude, often turning gigabytes of intermediate data into megabytes.
• The catch: it only works when your reduce is associative and commutative. Sum, yes. Average, no, not directly, because the average of averages is wrong.
• You can still compute an average with a combiner: emit (sum, count) pairs and divide at the end.

Barriers.

• Reduce cannot start finishing until every map task is done.
• A straggler mapper might still emit a value for a key a reducer cares about.
• This barrier between phases is why one slow machine can hold up the whole job.

Fault tolerance.

• Machines die mid-job constantly at scale. Picture 2,000 machines running six hours: even at a tiny per-machine failure rate, expect several deaths before the job ends.
• The coordinator pings workers. If one goes quiet, it reruns that task somewhere else.
• This works because map and reduce are pure functions with no side effects, so rerunning gives the same answer.
• Completed map output lives on local disk, so a dead map worker loses its output and the task reruns. Completed reduce output lives in the replicated file system, so it survives.

Speculative execution.

• Near the end, a handful of slow tasks (maybe on a machine with a dying disk) drag the whole job out.
• The framework launches duplicate copies of those stragglers on other machines and takes whichever finishes first.
• This routinely cuts total job time by 20 to 40 percent.

3Trade-offs#

MapReduce makes a deliberate bet, and the bet is what interviewers want you to reason about.

• It trades raw speed and expressiveness for simplicity and the ability to recover from constant failure on cheap hardware.
• That made sense in 2004 on commodity clusters. It makes less sense today when memory is cheap.

The biggest weakness is iterative work.

• Train a model or run PageRank and you need 30 passes over the data.
• Classic MapReduce writes the full dataset to disk and reads it back between every pass.
• On the 1 TB example that is 30 full round-trips through disk: 30 TB of reads and 30 TB of writes just in intermediate churn.
• This is why Spark ate MapReduce's lunch. Spark keeps intermediate data in memory and only spills when it must, so a 30-iteration job that took hours runs in minutes.

The second weakness is that two functions is a cramped programming model.

• A real pipeline is often ten stages: filter, join, aggregate, join again, sort.
• In raw MapReduce each stage is a separate job that writes to disk and gets read back, so a ten-stage pipeline means nine extra disk round-trips you did not ask for.
• People built Hive (SQL on top) and Pig to avoid writing this by hand, which tells you the raw API was too low level for daily use.

What it still gets right is the failure story.

• When a job runs six hours across 2,000 machines, something will break.
• The disk-backed, rerun-anything design means a dead machine costs you one task and a few minutes of rework, not the whole six-hour job.
• That durability is the thing you keep even when you move to newer engines.

4Where it is used#

Batch processing over huge, mostly-static datasets is the sweet spot. Think overnight jobs, not request-response.

Real cases where the pattern fits.

• Log and clickstream aggregation. Billions of events a day rolled up into per-user or per-campaign counts for the next morning's dashboards.
• Building search indexes. The original Google use case. Map over documents, emit (word, docID), reduce into posting lists.
• ETL. Clean and reshape raw dumps into tables a warehouse can query. A nightly job turning messy JSON into tidy Parquet is MapReduce in spirit even if you write it in Spark SQL.
• Large joins and dedup. Joining two 500 GB tables on a key, or deduplicating a firehose of records.

Where you should not reach for it.

• Anything latency-sensitive. If a user is waiting on the result, this is the wrong tool. It is minutes-to-hours, not milliseconds.
• Streaming data: want Flink or Kafka Streams.
• Interactive queries: want a columnar warehouse.
• Iterative ML: want Spark.

The honest state of things today.

• You almost never write Hadoop MapReduce directly. You write Spark or Beam or a SQL engine.
• Those borrow the map-shuffle-reduce skeleton under the hood, so the model is alive and well.
• The specific 2004 implementation is mostly legacy.

5Common pitfalls and gotchas#

Data skew is the number one killer.

• The whole system assumes keys spread evenly across reducers.
• Then one key (a null value, a celebrity user ID) has 40 percent of the records.
• You split work across 100 reducers hoping each handles about 1 percent, but one now carries 40 percent.
• That reducer runs an hour while the other 99 finish in two minutes. Job time is set by the slowest reducer.
• A roughly 40x machine fleet delivering about 2.5x speedup. You gained almost nothing from parallelism.
• Fixes: salt the hot key into key_0 through key_99 and aggregate the partials, or handle skewed keys in a separate pass.

Too many small files.

• A million 4 KB files instead of a few big blocks gives you a million map tasks, each with startup overhead, and the coordinator chokes on bookkeeping.
• The clean case: that same 4 GB as thirty-two 128 MB blocks is 32 map tasks, not a million.
• Fix: combine small files before processing.

Assuming the combiner always runs.

• The framework may run your combiner zero times, once, or many times, entirely at its discretion.
• If your combiner and reducer are not the same associative operation, you get silently wrong results.
• This is a nasty, non-reproducible bug: it passes on a small test input where the combiner never fired and fails in production where it fired twice.

Side effects in map or reduce.

• Someone writes to an external database inside the map function.
• A task gets speculatively duplicated or retried after a failure, and now that write happens twice.
• Keep these functions pure, or make external writes idempotent.

Forgetting the shuffle is the bottleneck.

• Beginners optimize their map and reduce code. The real cost is usually moving data across the network during shuffle.
• A combiner, better partitioning, or map-side joins buy you far more than micro-optimizing the functions.
• I would rather cut shuffle volume in half than shave 20 percent off a map function that was never the bottleneck.

6How it shows up in interviews#

MapReduce shows up two ways. Keep both in mind.

• Explicit: "design a system to count word frequencies across a billion documents."
• Hidden inside a bigger design: "how do you compute trending topics" or "build analytics for a URL shortener."
• Either way the interviewer wants to see that you reach for batch aggregation and understand the plumbing.

Here is the contrast that decides these conversations, weak answer versus strong answer, on the questions they actually ask.

"A machine dies halfway through. What happens?"

• Weak: "It retries the task." True but hand-wavy, and it does not show you know why retrying is safe.
• Strong: "Retry is safe because map and reduce are pure, so rerunning gives the same answer. Map output sits on the dead machine's local disk, so it is gone and that task reruns from the input block. Reduce output lives in replicated storage, so finished reduce work survives. Separately, for stragglers that are slow but not dead, speculative execution launches a duplicate and takes the winner." You split failure from slowness, which most people conflate.

"One reducer takes ten times longer than the rest. Why?" This is the skew question, the single best signal in the whole conversation.

• Weak: "Maybe that machine is slow," then waits.
• Strong: "That is data skew. One key, probably a null or a hot ID, owns a huge share of the records, so one reducer does most of the work while the fleet sits idle. I would salt that key into key_0 through key_99 to spread it across reducers, then do a second pass to combine the partials. Salting works because it breaks one overloaded reducer's load into many, then recombines." Naming the mechanism and why the fix works puts you clearly ahead.

"Would you actually use MapReduce for this today?"

• Weak: "Yes, MapReduce is the standard tool for big data." That signals you learned it from a 2010 blog post.
• Strong: "Honestly, no. I would use Spark or a SQL engine because they keep intermediate data in memory and skip the disk round-trips between stages, which matters a lot for anything iterative. But I would still credit the model: the map-shuffle-reduce shape and the failure handling carried straight into those newer engines, so understanding it is understanding them." You show history and current reality at once.

Anyone can describe two functions. The engineer who gets hired is the one who, unprompted, says what happens when a key is skewed and a machine dies at the same time.

Next, try the System Design Question walkthrough on building a large-scale analytics pipeline, where you decide between batch MapReduce-style jobs and a streaming engine for the same metrics.