mapreduce basics

**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.