MapReduce — a programming paradigm for processing massive datasets in parallel across distributed clusters, popularized by Google and Apache Hadoop.

Two Phases

1. Map: Apply a function to each input record independently → produce (key, value) pairs 2. Reduce: Group all values by key → combine them into final results

Example: Word Count

Input: "the cat sat on the mat"

Map: "the"→1, "cat"→1, "sat"→1, "on"→1, "the"→1, "mat"→1

Shuffle/Sort: Group by key
  "cat"→[1], "mat"→[1], "on"→[1], "sat"→[1], "the"→[1,1]

Reduce: Sum values per key
  "cat"→1, "mat"→1, "on"→1, "sat"→1, "the"→2

Why It Works

• Map phase is embarrassingly parallel (each record independent)
• Framework handles data distribution, fault tolerance, shuffling
• Programmer only writes Map and Reduce functions
• Scales linearly: 2x nodes → ~2x throughput

Implementations

• Apache Hadoop MapReduce (original, disk-based)
• Apache Spark (in-memory, 10-100x faster than Hadoop)
• Google Cloud Dataflow / AWS EMR

Limitations

• Not great for iterative algorithms (ML training) — each iteration requires full data pass
• Spark and newer frameworks address this with in-memory caching

MapReduce is the foundation of big data processing — understanding it is essential for distributed computing.