Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 47 ยท MapReduce

Inside the Shuffle and Sort

Open the black box between map and reduce: partitioning, spills, merging, sorting, combiners, choosing the reducer count and fighting skewed keys.

In the MapReduce programming model you wrote a mapper and a reducer, and the framework did everything in between. That "in between" is the shuffle and sort, and it is where most of a job's time goes. It moves data across the network, writes it to disk several times and sorts it. If you understand it, you can explain why one job takes ten minutes and another, almost identical, takes three hours.

This lesson follows one key-value pair from the moment a mapper emits it to the moment a reducer sees it. You will meet the partitioner, the spill files, the merge, the combiner, the choice of reducer count and the classic enemy of every cluster: skew.

The real shuffle runs inside Hadoop's Java code on many machines. It cannot run on this site. The commands and settings are read-only, and the runnable examples are Python stand-ins that reproduce the logic (partitioning, combining, grouping), not the real network transfer or disk format.

From mapper output to reducer input

The shuffle has two halves. The map side prepares output for the reducers, and the reduce side fetches and merges it.

The map side

Buffer Map output goes into a memory ring buffer.
Partition Each pair gets a reducer number.
Spill A full buffer is sorted and written to disk.
Merge Spill files become one sorted file.
1 / 2

Step by step:

  1. A mapper emits (key, value) pairs. They are serialized into an in-memory circular buffer (mapreduce.task.io.sort.mb, default 100 MB).
  2. For every pair, the partitioner decides which reducer will receive it.
  3. When the buffer is about 80% full (mapreduce.map.sort.spill.percent), a background thread spills it: it sorts the pairs by partition and then by key, runs the combiner if there is one, and writes a file to the mapper's local disk (not HDFS).
  4. When the mapper finishes, all spill files are merged into a single file that is sorted and indexed by partition.
  5. Each reducer fetches its slice from every mapper over HTTP, merges the sorted slices, and feeds the reduce function one key at a time with all of that key's values.

Notice the output of a mapper lives on local disk, not in HDFS. It is temporary, so replicating it would waste time. If the node dies before the reducers read it, the framework simply re-runs the map task (more in Fault Tolerance, Tuning and Limits).

flowchart LR
    M1["Mapper 1<br/>sorted, partitioned"] --> R0["Reducer 0"]
    M1 --> R1["Reducer 1"]
    M2["Mapper 2<br/>sorted, partitioned"] --> R0
    M2 --> R1
    M3["Mapper 3<br/>sorted, partitioned"] --> R0
    M3 --> R1

Every reducer pulls one slice from every mapper: 3 mappers and 2 reducers make 6 transfers.

The number of transfers is mappers x reducers, which is why a job with 10,000 maps and 5,000 reducers has 50 million small fetches. Large jobs are limited by this fan-in.

The partitioner

The partitioner is a tiny function: given a key and the number of reducers, return a number from 0 to reducers - 1. The default, HashPartitioner, is essentially this:

Java
public int getPartition(K key, V value, int numReduceTasks) {
    return (key.hashCode() & Integer.MAX_VALUE) % numReduceTasks;
}

Two things follow. First, all pairs with the same key go to the same reducer, which is exactly the guarantee reduce needs. Second, the split is balanced only if the keys are spread evenly. The partitioner balances distinct keys, not the amount of data behind them.

You can write your own partitioner, for example to send all keys starting with A to H to reducer 0 and the rest to reducer 1, giving globally sorted output across the output files (the technique behind total-order sort).

Here is a stand-in for the map side: two "mappers" emit word pairs, a partitioner assigns reducers, and we see what each reducer would receive. Python's built-in hash for strings is randomized per run, so the stand-in uses a CRC to stay deterministic.

Python A partitioned shuffle

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.

Run it and check two facts: every occurrence of the ends up at the same reducer, and the keys inside a reducer appear in sorted order. Sorted order is a feature: reduce functions can rely on it, and later lessons such as MapReduce Design Patterns use it for secondary sort.

The combiner: shrinking data before the network

Word count emits ("the", 1) for every occurrence. If a mapper sees the 50,000 times, it would send 50,000 tiny pairs. A combiner is a "mini reducer" that runs on the map side, on each spill and on the final merge, and collapses those into ("the", 50000).

For word count the combiner is the same function as the reducer. This works only because addition is associative and commutative: summing partial sums gives the same answer. A combiner is an optimization, so Hadoop may run it zero, one or several times. Your job must be correct either way.

Do not use a combiner for an operation that is not associative. An average is the classic trap: avg(avg(1, 2), 3) is 2.25, but avg(1, 2, 3) is 2. Instead, emit (sum, count) pairs and divide in the reducer.

Python How much does a combiner save?

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.

The combiner is one of the cheapest speedups in Hadoop. In a job with a handful of distinct keys, as here, it removes almost all shuffle traffic.

How many reducers?

Unlike mappers, whose count follows the input splits, you choose the number of reducers: job.setNumReduceTasks(n). It decides the number of output files (part-r-00000, part-r-00001, ...) and the parallelism of the reduce stage.

  • Too few: each reducer processes a huge slice, the job runs long, and one failure costs a lot of re-work.
  • Too many: you create many tiny output files (the small-files problem from NameNode HA, Federation and Operations), and each reducer pays startup and fetch overhead.
  • Zero reducers: a map-only job. Mapper output is written straight to HDFS with no shuffle at all. Filtering and format conversion jobs should always be map-only.

A common rule of thumb is a reducer count so each reducer handles roughly 1 GB or a few minutes of data, and slightly below the number of available reduce slots so reducers finish in one wave.

Skew: when one reducer does all the work

Hashing spreads keys evenly, not records. If 40% of your clicks belong to one user ID, whichever reducer receives that key does 40% of the work while the others sit idle. The job finishes only when the slowest reducer does, so you pay for all the machines and use one.

Typical causes are a null or empty key, a default value like "unknown", a celebrity user, or the word the. Remedies:

  • Combiner: shrinks hot keys before the shuffle (best when the operation allows it).
  • Filter or split off the hot key and handle it separately.
  • Salting: append a random suffix (user42#0 to user42#7) so one key becomes eight, aggregate partially, then strip the salt and aggregate again in a second job.
  • Custom partitioner: spread the known heavy keys over several reducers.
Python Skew and salting

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.

Salting trades an extra, cheap job for an even spread. The final answer is unchanged, which the last line confirms.

Tuning knobs (read-only)

XML
<property>
  <name>mapreduce.task.io.sort.mb</name>
  <value>256</value>   <!-- bigger buffer: fewer spills -->
</property>
<property>
  <name>mapreduce.map.output.compress</name>
  <value>true</value>  <!-- compress map output: less network, a bit more CPU -->
</property>
<property>
  <name>mapreduce.reduce.shuffle.parallelcopies</name>
  <value>10</value>    <!-- parallel fetch threads per reducer -->
</property>

Fewer spills mean fewer merge passes; compressing map output (with a fast codec such as Snappy or LZ4) usually pays off because the network is the scarce resource.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the default HashPartitioner guarantee?

    The partition number is derived from the key's hash, so equal keys always land on the same reducer. It does not balance record counts.
  2. 2. Where does intermediate map output live before reducers fetch it?

    Map output is temporary, so it is written to local disk. If the node is lost, the map task is simply re-run.
  3. 3. Why is a combiner NOT safe for computing an average directly?

    The operation must be associative and commutative. Emit (sum, count) from the mapper or combiner and divide in the reducer.
  4. 4. One reducer is still running after all others finished, and it processes a key that appears in 40% of the records. What is this called, and what helps?

    Hash partitioning balances keys, not data volume. Combiners, salting, or a custom partitioner spread the hot key's work.

Summary

  • The shuffle is: partition, sort and spill on the map side, then fetch, merge and group on the reduce side.
  • The partitioner maps each key to a reducer; equal keys always meet, and keys arrive sorted.
  • Map output lives on local disk, and each reducer fetches from every mapper.
  • A combiner is an optional map-side mini-reduce; it must be associative and commutative.
  • You choose the reducer count; zero reducers makes a map-only job.
  • Skew comes from uneven record counts per key; combiners, salting and custom partitioners fix it.

Next: MapReduce Design Patterns.