Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 47 ยท MapReduce

The MapReduce Programming Model

Learn how MapReduce works: key/value pairs, the map, shuffle and reduce phases, data locality and why the model scales, with word count in plain Python.

MapReduce is a way of writing a program so that a cluster can run it in parallel on terabytes of data. You do not write threads, network code or failure handling. You write two small functions, a map function and a reduce function, and the framework splits the input, runs your functions on many machines, moves the data between them and reruns anything that fails.

It was published by Google in 2004 and became the first processing engine of Hadoop. Today Spark and SQL engines have largely taken over, but MapReduce is still the clearest way to understand how big data processing works. This lesson explains the model, and the next lessons dig into its machinery. It follows YARN: Resources and Scheduling, which runs the tasks.

A real MapReduce job needs a Hadoop cluster, so the Java and shell code in these lessons is read-only. The runnable examples are Python stand-ins: a tiny simulator written with ordinary functions that follows the same phases as the real framework.

Key/value pairs everywhere

MapReduce sees all data as key/value pairs. The input might be (line number, text of the line). The map function turns each input pair into zero or more intermediate pairs. The reduce function receives one key together with all the values for that key and writes the final pairs.

TEXT
map:    (k1, v1)        ->  list of (k2, v2)
reduce: (k2, [v2, ...]) ->  list of (k3, v3)

Your two functions only ever look at one record (map) or one key group (reduce). They share nothing and remember nothing between calls. That restriction is the secret: because the pieces do not depend on each other, they can run anywhere and in any order.

The three phases

Map, shuffle, reduce

Map Turn each record into key/value pairs.
Shuffle Group all values by key.
Reduce Combine each key's values.

You write map and reduce. The framework does the shuffle.

1 / 2

Take the classic example, counting words. Imagine the input is spread over two machines:

TEXT
Machine A: "the cat sat"      Machine B: "the dog sat down"
  1. Map. Each machine reads its lines and emits (word, 1) for every word. A produces (the,1) (cat,1) (sat,1). B produces (the,1) (dog,1) (sat,1) (down,1).
  2. Shuffle (and sort). The framework sends every pair with the same key to the same place and groups them: the -> [1,1], sat -> [1,1], cat -> [1], dog -> [1], down -> [1]. Keys arrive at each reducer in sorted order.
  3. Reduce. For each key, add the values: (the,2) (sat,2) (cat,1) (dog,1) (down,1).
flowchart LR
    I1["split 1"] --> M1["map"]
    I2["split 2"] --> M2["map"]
    M1 --> S{{"shuffle<br/>group by key"}}
    M2 --> S
    S --> R1["reduce<br/>keys a-m"]
    S --> R2["reduce<br/>keys n-z"]
    R1 --> O1["output part-0"]
    R2 --> O2["output part-1"]

Many maps feed the shuffle; each reducer gets whole key groups and writes one output file.

The shuffle is the expensive step: it moves data across the network and sorts it. It is also where the magic is, because it guarantees that one reduce call sees every value of its key, no matter which machine produced it. Inside the Shuffle and Sort opens that box.

Word count in plain Python

The stand-in below implements the three phases with ordinary Python. map_fn and reduce_fn look just like the functions you would write for Hadoop; run_job plays the role of the framework.

Python Word count: map, group, reduce

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the shape of the program: the job logic is two tiny functions, and run_job is generic. Swap the functions and the same engine finds the longest word, or counts requests per URL.

The model beyond counting

Many problems fit the same mould once you decide what the key is:

  • Total sales per country: map emits (country, amount), reduce sums.
  • Maximum temperature per year: map emits (year, temperature), reduce takes the max.
  • Which documents contain a word? map emits (word, doc_id), reduce collects a list.
  • Filtering: map emits only the records you want; there may be no reduce step at all (a map-only job).

The art of MapReduce is picking the key: it decides what is grouped together. MapReduce Design Patterns catalogues the common choices.

Python Same engine, different job: max temperature per year

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Data locality: move the code, not the data

Moving 1 TB across a network is slow; moving a 10 KB jar file is not. So Hadoop sends your map code to the machines that already hold the data. The input of a job is cut into input splits, normally one per HDFS block (128 MB). Each split becomes one map task, and YARN tries to start it on a node that stores a replica of that block (node-local), then on the same rack, then anywhere (see YARN: Resources and Scheduling).

Because each map task reads its own block straight from a local disk, the combined read speed grows with the number of nodes. 1,000 disks reading in parallel are about 1,000 times faster than one. The only large network traffic is the shuffle, and a trick called the combiner (next lessons) shrinks that.

Why the model scales

Why MapReduce scales

Independent tasks Maps never talk to each other.
Data locality Code goes to the data.
Safe to retry Tasks are deterministic.
Add nodes More machines, more speed.

Ten times the data and ten times the nodes take about the same time.

1 / 2
  • Independence. Map tasks do not communicate, and each reducer owns a disjoint set of keys, so adding machines adds speed almost linearly.
  • Fault tolerance by re-execution. A map or reduce function has no side effects, so if a machine dies the framework simply runs its task again elsewhere. You never write recovery code. Fault Tolerance, Tuning and Limits of MapReduce covers the details.
  • Simple mental model. The same two functions run unchanged on a laptop sample and on a 1,000-node cluster.

The price: every job reads from and writes to HDFS, and the shuffle writes to disk, so MapReduce is built for throughput, not latency. A tiny job still takes many seconds to start, and chains of jobs (such as iterative machine learning) are slow. That limit is why Spark replaced it for many workloads.

Simulating splits and parallel maps

One more stand-in shows the "scale" argument: the input is cut into splits, each split is mapped independently (as separate tasks could be), and the partial outputs are merged by the shuffle. The result is identical no matter how many splits you use.

Python The result does not depend on the number of splits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the reduce function receive?

    The shuffle groups all intermediate values by key, so each reduce call sees every value of one key.
  2. 2. Which step is done by the framework rather than by your code?

    You write map and reduce (and decide the key). The framework groups and sorts the intermediate pairs and moves them over the network.
  3. 3. What is data locality?

    Hadoop moves the small program to the big data, which avoids sending blocks across the network.
  4. 4. Why can a failed MapReduce task simply be run again?

    Deterministic, side-effect-free functions can be re-executed on another node without changing the final result.
  5. 5. What is MapReduce best suited for?

    It trades latency for throughput: starting a job is slow, but scanning terabytes in parallel is efficient.

Summary

  • MapReduce expresses a job as a map function and a reduce function over key/value pairs.
  • The framework splits input, runs map tasks in parallel, shuffles and sorts by key, then runs reduce tasks that each handle whole key groups.
  • Choosing the key decides what gets grouped; many problems fit the model, and a map-only job has no reduce.
  • Data locality sends code to the data: one map task per input split, preferably on a node holding the block.
  • It scales because tasks are independent and safe to re-run, but it favors throughput over latency.

Next: Inside the Shuffle and Sort.