Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 47 ยท MapReduce

MapReduce Design Patterns

Learn the reusable MapReduce patterns: filtering, summarization, inverted index, map-side and reduce-side joins, top-N and secondary sort, each in a runnable simulator.

Almost every MapReduce job you will ever write is a variation on a handful of patterns. Once you recognize them, a new problem like "find the ten most active users" or "join orders with customers" stops being a puzzle and becomes "which pattern is this?". Each pattern is just a particular choice of what the mapper emits as the key and what the reducer does with a group.

This lesson builds a tiny in-memory MapReduce simulator and then implements six patterns on top of it: filtering, summarization, inverted index, joins, top-N and secondary sort. The runtime is the one from The MapReduce Programming Model and Inside the Shuffle and Sort.

Real Hadoop jobs are written in Java or run through Hadoop Streaming and cannot run on this site. The simulator below is a stand-in that executes map, shuffle (group by key, sorted) and reduce in one Python process. The patterns themselves transfer unchanged.

Six patterns, one skeleton

Filtering Map only, keep what matches.
Summarizing Key by group, aggregate values.
Inverted index Key by word, list the documents.
Join Key by join column, merge two inputs.
1 / 2

The simulator

All the examples below share one helper. run_job takes the input records, a mapper that yields pairs, an optional reducer and an optional combiner. Keys are sorted before the reducer sees them, like the real shuffle.

Python
def run_job(records, mapper, reducer=None, combiner=None):
    ...

You will see the full helper in the first TryIt and repeated (shortened) in later ones so each example stays runnable on its own.

Pattern 1: filtering

Filtering keeps only the records that match a condition. It needs no reducer: the job is map-only, so no shuffle happens and output is written directly. Use it for grep, sampling, removing bad rows and extracting a subset.

Pattern 2: summarization

Summarization groups records and computes counts, sums, minimums, maximums or averages. The mapper emits (group, value), the reducer aggregates. This is word count in different clothes. A combiner usually helps.

Python Filtering and summarization

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.

Pattern 3: inverted index

A search engine needs to answer "which documents contain this word?" quickly. The inverted index flips the data: instead of document -> words, it stores word -> documents. The mapper emits (word, doc_id); the reducer collects the distinct, sorted document IDs.

Python Inverted index

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.

You will turn this into a full search index in Project: Search Index over Documents.

Pattern 4: joins

Joining two datasets by a key is the most common "hard" pattern. Hadoop gives you two strategies.

Reduce-side join

Both inputs go through the mappers. Each mapper tags its records with the source (C for customers, O for orders) and emits the join column as the key. All records with the same key meet in one reducer, which combines them. It works for any sizes, but it shuffles both datasets across the network.

Map-side join (replicated join)

If one side is small enough to fit in memory (a lookup table of customers), ship a copy to every mapper (the distributed cache) and join while mapping. There is no shuffle and no reducer, so it is much faster. The rule: use a map-side join whenever one input is small.

Python Reduce-side and map-side joins

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.

Note order 104 refers to customer 4, who is missing: the inner join drops it, while the map-side version shows how a left join keeps it.

Pattern 5: top-N

"The ten biggest sales" sounds like a global sort, but you do not need one. Each mapper keeps only its local top N in a small heap and emits it at the end. A single reducer then merges those short lists (at most mappers x N records) and keeps the global top N. Because the combined data is tiny, one reducer is enough.

Pattern 6: secondary sort

Reducer input is sorted by key, but the values for one key arrive in no particular order. If you need them ordered (for example the events of one user by timestamp), you use secondary sort: put the sort field into a composite key (user, timestamp), then tell Hadoop to

  1. partition by user only, so all of a user's events go to the same reducer,
  2. sort by the full (user, timestamp), and
  3. group by user only, so one reduce call sees the whole user, already in time order.

In Java you do this with a custom Partitioner, a SortComparator and a GroupingComparator. The next TryIt shows both patterns.

Python Top-N and secondary sort

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.

Choosing a pattern

Question Pattern Needs shuffle?
Keep rows matching a rule Filtering No
Count, total or average per group Summarization Yes (combiner helps)
Which documents contain each word Inverted index Yes
Combine two large datasets Reduce-side join Yes, both
Combine a large and a small dataset Map-side join No
Largest or smallest N Top-N Tiny
Ordered values within a key Secondary sort Yes

Later technologies hide these patterns behind SQL: a GROUP BY is summarization, a JOIN chooses between the two join strategies (Hive Performance), and ORDER BY ... LIMIT is top-N.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which pattern needs no reducer and no shuffle?

    Filtering is a map-only job: each record is kept or dropped independently, and output is written directly.
  2. 2. When should you prefer a map-side join?

    The small table is copied to every mapper through the distributed cache, so the large table never has to be shuffled.
  3. 3. In a reduce-side join, why do mappers tag each record with its source?

    After the shuffle, records from both inputs are mixed in one group. The tag tells the reducer how to combine them.
  4. 4. How does top-N avoid a global sort?

    The global top N is always contained in the union of the local top N lists, so only a tiny amount of data is shuffled.
  5. 5. What do you change to get values sorted inside one reduce group?

    That is secondary sort: partition and group by the natural key, sort by the full composite key.

Summary

  • Every job is a choice of map output key and reduce logic.
  • Filtering is map-only; summarization is group and aggregate, usually with a combiner.
  • An inverted index maps each word to the sorted list of documents containing it.
  • Reduce-side joins work for any size but shuffle both inputs; map-side joins skip the shuffle when one side is small.
  • Top-N keeps local lists in mappers and merges them in one reducer.
  • Secondary sort uses composite keys with a custom partitioner and grouping.

Next: Writing a MapReduce Job in Java.