MapReduce

Map shuffle reduce

Prerequisites

graph TD
  Prob[Probability basics] --> MR[MapReduce]
  Dist[Distributed systems overview] --> MR
  Batch[Batch data pipelines] --> MR

When to use

Offline batch jobs over terabytes (logs, crawls, ETL) where latency in hours is acceptable.
Embarrassingly parallel map plus shuffle/group-by-key reduce (word count, inverted index, PageRank iterations).
Commodity clusters where hardware failure and stragglers are expected — framework handles retry and backup tasks.

When not to use

Low-latency or per-record updates — use streaming (Flink, Kafka) or OLTP instead of batch MapReduce.
Tiny data that fits one machine — a single process or SQL is simpler.
Complex multi-pass joins without careful partitioning — consider Spark/Dask or a warehouse with a query optimizer.

Lab

On the interactive MapReduce lab, step through map → shuffle → reduce on the README word-count shards (keys A/B/C), enable a straggler on one mapper, and toggle backup tasks to compare map-phase wall time. Use Straggler + backup and Straggler stalls job presets, predict whether backup cuts map time by more than 2×, then reveal timings vs the cluster-failure formula (P(\text{no fail})=(1-p)^N).

Simple Fundamental Explanation

Imagine you want to count the number of times the word “the” appears in an entire physical library of 10,000 books.

Single-Threaded: You sit down, pick up the first book, and start reading and counting. It will take you 10 years.
The MapReduce Approach: You hire 1,000 people (the “Mappers”). You give each person 10 books and a notebook. They independently count the words in their assigned books and write down the totals. When they finish, they hand their notebooks to 10 other people (the “Reducers”). One Reducer’s only job is to take everyone’s count for the word “the” and add them all together.

MapReduce is a programming model and processing engine created by Google. It allows you to process petabytes of data across thousands of commodity computers. The genius of MapReduce isn’t just the splitting of work; it’s the probabilistic resiliency. It assumes that if you use 1,000 cheap computers, some of them will randomly die or freeze during the job. It handles these probabilistic hardware failures automatically so the programmer doesn’t have to.

Deep Dive: How It Works Under the Hood

A MapReduce job splits the input data into independent chunks (e.g., 64 MB blocks).

1. Map Phase

The Master node assigns Map tasks to Worker nodes. Each Map worker processes its chunk of data and emits intermediate key/value pairs. For word count: Map("Hello world hello") -> [("Hello", 1), ("world", 1), ("hello", 1)].

2. Shuffle and Sort Phase

The framework groups all values associated with the same intermediate key and sends them to the same Reducer worker. This requires massive network bandwidth (the “shuffle”).

3. Reduce Phase

The Master assigns Reduce tasks to Worker nodes. Each Reduce worker iterates over the grouped values for a specific key and aggregates them. Reduce("hello", [1, 1]) -> ("hello", 2).

Probabilistic Straggler Mitigation (Backup Tasks)

If you have 10,000 tasks, the probability that one machine has a failing hard drive and runs at 1% of normal speed is incredibly high. If you wait for that one “straggler” machine to finish, your entire job stalls. When a MapReduce operation is close to completion, the Master probabilistically schedules backup executions of the remaining in-progress tasks on idle machines. Whichever machine finishes first wins, and the other is killed. This simple trick reduces job completion time by 44%.

Visual Diagram

Input Data: [A, B, A, C] | [B, C, B, A] | [C, C, A, B]
(Split into 3 blocks)

--- MAP PHASE ---
Worker 1: (A,1), (B,1), (A,1), (C,1)
Worker 2: (B,1), (C,1), (B,1), (A,1)
Worker 3: [Worker Dies!] -> Master detects timeout -> Reassigns to Worker 4.
Worker 4: (C,1), (C,1), (A,1), (B,1)

--- SHUFFLE / GROUP ---
Key A sent to Reducer 1: (A, [1, 1, 1, 1])
Key B sent to Reducer 2: (B, [1, 1, 1, 1])
Key C sent to Reducer 3: (C, [1, 1, 1, 1])

--- REDUCE PHASE ---
Reducer 1: (A, 4)
Reducer 2: (B, 4)
Reducer 3: (C, 4)

Practical Example: Google Search Indexing

In the early 2000s, Google needed to crawl the entire web, extract the links, and build the reverse index that powers Google Search.

Doing this sequentially was impossible. Doing this with traditional databases resulted in massive deadlocks and race conditions. Google invented MapReduce to solve this exact problem.

Map: Read a web page. For every word on the page, emit (Word, URL).
Reduce: Receive a Word and a massive list of URLs. Sort them by PageRank, and emit (Word, [URL1, URL2, URL3]).

This allowed Google to index the internet every night using thousands of cheap, unreliable Linux machines.

The Mathematics: Equations and In-Depth Analysis

1. Probability of Hardware Failure

Why is MapReduce’s failure handling necessary? Let $p$ be the probability that a single commodity server fails in a given day (e.g., $p = 0.001$ , or 1 in 1000). If your job requires 1 server and takes 1 day, the probability of job success is $1 - 0.001 = 99.9%$ .

If your job requires $N = 5, 000$ servers, what is the probability that none of them fail?

P (No Failures) = (1 - p)^{N}

P (No Failures) = (0.999)^{5000} \approx 0.0067 (or 0.67%)

In a massive cluster, hardware failure is not an anomaly; it is a statistical certainty. A job will almost never finish without at least one machine dying. MapReduce treats hardware failure as a software engineering parameter rather than an IT emergency.

2. Straggler Probabilities (Tail Latency)

Let the execution time of a task follow an exponential distribution with rate $λ$ . If a job consists of $N$ parallel tasks, the total job completion time is the maximum of all $N$ variables. The expected value of the maximum of $N$ exponential variables grows logarithmically:

E [Max (T_{1}, \dots, T_{N})] \approx \frac{ln ( N )}{λ}

As $N$ grows, the tail latency (the time waiting for the slowest task) dominates the entire job. By launching redundant backup tasks (changing the math from finding the maximum to finding the minimum of the redundant pairs), MapReduce mathematically truncates the tail of the probability distribution, forcing the overall job completion time back toward the median.

Lab

Word-count MapReduce on three README shards (keys A/B/C): watch map workers emit counts, shuffle route keys to reducers, then reduce merge. Enable a straggler and backup task to see tail latency truncate (README § backup tasks).

Map tasks3 workers

Timelinestep 1 / 12

Straggler workerM3

Map

Shuffle

Reduce

ABAC

BCBA

CCAB

Straggler M3 at 12% speed

With 3 map tasks and M3 as a straggler (~12% speed), does turning on backup tasks shorten the map phase by more than 2× versus waiting for the straggler alone?

map · step 1/12 · Straggler M3 at 12% speed