Before anything else, the course disambiguates a word that gets used for two different things. Here is the original definition, from Dean and Ghemawat at Google:
“MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.”— Dean J., Ghemawat S. (Google)
And then the distinction that matters for the rest of the course: Hadoop MapReduce is an open-source implementation of the MapReduce programming model. Two different objects share one name.
This chapter is about the model: what you can express, what a combiner is allowed to do, why a partitioner exists. Chapter 5 is about the implementation: how Hadoop and YARN actually schedule the tasks, move the bytes, and recover from a dead machine. Keep them apart in your head — at the exam, “how does MapReduce work” and “how does Hadoop run a MapReduce job” are two different questions with two different answers.
MapReduce aims to support analytical jobs over large datasets. The shape of such a job is always the same four beats:
Two of those four beats are yours to write. The names come straight from functional programming:
| Function | What it does |
|---|---|
| MAP | Apply a function f to every element in a list |
| REDUCE | Iteratively apply a function g to aggregate elements |
The deck makes the lineage explicit by putting the imperative and the functional style side by side. In the imperative version you manage the loop, the index and the accumulator yourself; in the functional version you hand a function to a combinator and let it manage them:
a = 0
b = a + 1
### Map example to obtain [4,4,3]
names = ['Mary', 'Isla', 'Sam']
name_lengths = []
for i in range(len(names)):
name_lengths[i] = len(names[i])
### Reduce example to obtain 3
sentences = [
'Mary read a story to Sam and Isla.',
'Isla cuddled Sam.', 'Sam chortled.' ]
sam_count = 0
for sentence in sentences:
sam_count += sentence.count('Sam')a = 0
b = increment(a)
def increment(a):
return a + 1;
### Map example to obtain [4,4,3]
names = ['Mary', 'Isla', 'Sam']
name_lengths = map(len, names)
### Reduce example to obtain 3
sentences = [
'Mary read a story to Sam and Isla.',
'Isla cuddled Sam.', 'Sam chortled.' ]
sam_count = reduce(
lambda a, x: a + x.count('Sam'),
sentences, 0
)The difference looks cosmetic on three names. It is not. In the imperative version the order of the iterations is part of the program: name_lengths[i] is written at step i, and sam_count is a variable that every iteration mutates. In the functional version nothing is shared and nothing is ordered — len is applied to each name in complete isolation from the others. That isolation is the entire reason the model can be distributed: if applying f to element 1 cannot possibly affect applying f to element 2, the two applications can happen on two machines a rack apart.
MapReduce did not invent map and reduce, it industrialised them. The functional style forbids exactly the things that make parallelism hard — shared mutable state and implicit ordering — so a runtime that only accepts map and reduce can parallelise anything it is given, without understanding what it computes.
The deck grounds the whole paradigm in one running example. A travel agency offers hotel rooms on Trivago, competing with other agencies to offer the best value for money. The numbers add up quickly:
A handful of rows from that log:
| Hotel | City | Country | Date | TTT | LOS | GS | Market | Price | Markup | CMP | Impr. | Clicks | Book. |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| The Majestic | Rome | Italy | 22/09/24 | 4 | 2 | 1 | EU | 150 | 5 | 155 | 23 | 10 | 2 |
| Augustian | Rome | Italy | 22/09/24 | 4 | 2 | 1 | EU | 160 | 10 | 140 | 16 | 5 | 0 |
| Cosmopolitan | Milan | Italy | 19/12/24 | 10 | 1 | 2 | NA | 120 | 20 | 110 | 42 | 11 | 0 |
| The Empire | NYC | USA | 31/12/24 | 30 | 5 | 3 | AS | 130 | 2 | 125 | 8 | 1 | 1 |
| Presidential | Paris | France | 28/10/24 | 1 | 1 | 2 | EU | 150 | 3 | 140 | 4 | 2 | 1 |
| Royal Orchid | London | UK | 06/01/25 | 45 | 7 | 4 | EU | 100 | −5 | 100 | 15 | 10 | 1 |
Legend: TTT = time to travel (in number of days); LOS = length of stay (in number of days); GS = group size; CMP = cheapest market price.
The questions the business wants answered are ordinary analytical questions:
Every one of them is a GROUP BY you could write in SQL in twenty seconds. And then comes the sentence that turns a database exercise into this course:
How do we calculate them, considering that the data is distributed over multiple nodes in the cluster? The arithmetic is trivial. The problem is that no single machine has all the rows, and moving all the rows to one machine defeats the purpose of having a cluster.
Take the first query: how much revenue (markup × bookings) is made in each country? The deck walks it in three moves.
Each map task reads the records that happen to live on its node and throws away everything the query does not need, keeping a (Country, Revenue) pair per record. Nothing moves across the network yet; each task works only on the block already sitting on its disk. Three map tasks might produce:
MAP 1 MAP 2 MAP 3
Italy 5 Italy 12 France 8
Italy 10 Spain 8 Italy 15
Italy 20 France 10 Belgium 10
USA 2 UK 6 UK 11
France 3 Italy 9 Spain 6
UK -5 Spain 7 Italy 13And then the deck asks the right question: what then? Every node holds a partial answer for Italy. No node holds the answer for Italy.
Shuffling is a global operation to redistribute data, on the basis of how it is meant to be aggregated. After it, all the Italy pairs sit on one machine, all the France pairs on another, and so on. It is the only phase in which large volumes cross the network, and it is therefore the phase every optimisation in the next chapters attacks.
The deck immediately refines the name: it is actually Shuffle & Sort, as sorting is locally done to enable the later aggregation. Sorting is not decoration. If the values arriving at a reducer are ordered by key, the reducer can stream through them and close out each key the moment the key changes, holding one group in memory rather than all of them.
REDUCER 1 REDUCER 2 REDUCER 3
Italy 5 France 3 Belgium 10
Italy 10 France 10 Spain 7
Italy 20 France 8 Spain 10
Italy 12 UK -5 Spain 6
Italy 9 UK 6 USA 2
Italy 15 UK 11
Italy 13Now each reduce task performs an ordinary local aggregation, because everything it needs is finally in one place:
| Country | Total revenue |
|---|---|
| Italy | 84 |
| France | 21 |
| UK | 12 |
| Belgium | 10 |
| Spain | 23 |
| USA | 2 |
If you check the arithmetic by hand, verify against the shuffle & sort panel above, which is the one consistent with the totals (Italy 5+10+20+12+9+15+13 = 84; France 3+10+8 = 21; UK −5+6+11 = 12; Spain 7+10+6 = 23). The map-side panel in the original figure lists one Spain value differently; the discrepancy is in the drawing, not in the paradigm.
Two functions, and a very clear division of labour.
The map operation defines what must be extracted from the data, in the form of key-value pairs. Two properties follow:
The reduce operation defines how the values corresponding to the same keys must be aggregated/combined. And it comes with a hard requirement:
The programmer defines the map and the reduce functions. The execution framework handles everything else. This is the compromise from Chapter 1 made concrete: you say what, the runtime does how — scheduling, data movement, sorting, failure recovery.
Notice where the cost hides. The programmer writes the key, and the framework then has to physically relocate every record so that equal keys meet. Choosing the key is choosing the network traffic. That is why the same query can be fast or ruinous depending on a decision that looks like naming.
1) Input is divided into fixed-size splits. Smaller splits mean faster processing and better load balancing, but increased management overhead. And the sizing rule that ties this chapter back to the previous one: the optimal split size equals the DFS block size. Chapter 3 explained why from the storage side; here is the processing side of the same coin — if a split matched two blocks, half the input of every task would have to be fetched from another machine.
2) A map task is created for each split. The task runs the user-defined map function for each record in the split.
3) The key-value pairs returned by map tasks are sorted and stored on the local disk. Note local: map output is intermediate output, and storing it in HDFS with replication would be, in the words of the deck, “overkill”. If a map task dies, its output is simply recomputed. The output is sorted by key and subdivided into partitions — one for each reducer.
4) Map outputs are sent to the nodes where the reduce tasks are running. Four details to remember:
The slides use a consistent convention worth internalising, and reproduced in Plate 4.1: dotted boxes are nodes, light arrows are intra-node data transfers, heavy arrows are inter-node data transfers. When you read any MapReduce figure, find the heavy arrows first: they are the cost.
Two facts from this section are asked constantly. Why is map output written to local disk and not to HDFS? Because it is intermediate: replicating it would be overkill, and it can be recomputed by re-running the map task. Why is the optimal split size the DFS block size? Because it is the largest split that a single node can read entirely from its own disk, which is what makes data locality possible.
Two examples, deliberately almost identical, that teach the single most important design lesson in the model: what you choose as the key determines what the job computes.
Problem: counting the number of occurrences for each word in a collection of documents. Input: a repository of documents; each document is a value in the input pairs.
| Phase | What happens |
|---|---|
| Map | Read a document and emit a sequence of key-value pairs. Keys are the words found in the documents; values are equal to 1:(w1, 1), (w2, 1), (w1, 1), ... , (wn, 1) |
| Shuffle & Sort | Group by key and generate pairs of the form:(w1, [1, 1, ... , 1]) , ... , (wn, [1, 1, ... , 1]) |
| Reduce | Add up all the values for a given key and emit a pair of the form (w, m) |
| Output | w is a word that appears at least once among all the input documents; m is the total number of occurrences of w among all those documents |
Three tiny documents, three map tasks. Step through the phases and watch where the pairs go — and notice that after the shuffle, no machine needs to see anything but its own keys.
Problem: counting how many words of certain lengths exist in a collection of documents. Same input, same three phases — one different line in the mapper:
| Phase | What happens |
|---|---|
| Map | Read a document and emit key-value pairs where the key is the length of a word and the value is the word itself:(i, w1), ... , (j, wn) |
| Shuffle & Sort | Group by key:(1, [w1, ... , wk]) , ... , (n, [wr, ... , ws]) |
| Reduce | Count the number of words in the list and emit (l, m) |
| Output | l is a length; m is the total number of words of length l in the input documents |
Compare the two mappers. Word Count emits (word, 1); Word Length Count emits (length, word). The framework, the shuffle, the reduce skeleton are all unchanged — and yet one job counts vocabulary and the other measures style. Designing a MapReduce job is choosing the key. Everything else follows.
The two jobs also have very different shuffle profiles. Word Count has as many keys as there are distinct words — hundreds of thousands — spread over all reducers. Word Length Count has perhaps twenty keys, so at most twenty reducers can ever do work, and the values are whole words rather than the integer 1. A key with tiny cardinality is a bottleneck by construction; keep it in mind when you meet skew in section 9.
Combining means pre-aggregating data on the Map side. When the reduce function is associative and commutative, we can push some of what the reducers do to the map tasks: in this case we also apply a Combiner to the map function.
Two clarifications the deck insists on:
The combiner function must be associative and commutative:
Associativity: f( f(a,b), c ) = f( a, f(b,c) )
Commutativity: f(a,b) = f(b,a)Those are not decorative conditions. A combiner changes both the grouping of the arguments (some values get folded early, on the map side) and their order (values arrive at the reducer in a different sequence). If your function is sensitive to either, the combiner silently changes the answer. The deck demonstrates both failures.
Take concatenation of alphabetically-ordered values, so f(a,b) ≠ f(b,a). Four map tasks emit, for key 3, the values z, a, u, h.
| Intermediate for key 3 | Reducer 3 output | |
|---|---|---|
| With combiner | the task holding z and a combines them locally into az, so the reducer receives az, u, h | azhu |
| Without combiner | the reducer receives z, a, u, h | ahuz |
Two different answers from the same input. The pre-folded az can no longer be broken apart, so a can never sort before h at the end.
Take the average, where f( f(a,b), c ) ≠ f( a, f(b,c) ). For key c the map tasks emit 3, 9, 2, 8, with 3 and 9 on the same task.
| Intermediate for key c | Reducer 3 output | |
|---|---|---|
| With combiner | 3 and 9 are averaged locally to 6, so the reducer receives 2, 6, 8 | 5.33 |
| Without combiner | the reducer receives 2, 3, 8, 9 | 5.5 |
The average of averages is not the average. The combined value 6 arrives without its weight: the reducer cannot know it stands for two measurements rather than one.
Pick an aggregation function and check it against the two properties, with the exact numbers from the slides.
Expect to be handed a function and asked whether a combiner may be used. Test it against both properties separately, and be ready to show the failure with a two-line counter-example — that is what the slides do with azhu vs ahuz and 5.33 vs 5.5. And know the standard workaround for the average: emit (sum, count) pairs instead of raw values. Summing pairs component-wise is associative and commutative, and the division is performed once at the very end.
Partitioning map output means assigning to each key-value pair the ID of the reducer that will manage that key. It is the bookkeeping that makes the shuffle possible: before anything moves, every pair already knows its destination.
| Side | What determines the split |
|---|---|
| Maps | Partitioning depends on the input splits: one map task per input split. |
| Reducers | Data is shuffled according to a partitioning function, which decides for each key which reducer it goes to. The number of reducers is tuneable — based on the number of nodes and available resources, or defined by the user. The keyspace of the intermediate key-value pairs is evenly distributed over the reducers with a hash function. |
Type a key and change the number of reduce tasks. The hash is a simple deterministic function of the characters — the point is that the same key always lands in the same partition, and that different keys happily share one.
The simplest partitioner assigns approximately the same number of keys to each reducer. But — and this is the crucial observation — a partitioner only considers the key and ignores the number of values.
An imbalance in the amount of data associated with each key is relatively common in many text processing applications. The slides state the law behind it: in texts, the frequency of any word is inversely proportional to its rank in the frequency table. The most frequent word will occur approximately twice as often as the second most frequent word, three times as often as the third most frequent word, and so on.
The partitioning can be controlled by a user-defined partitioning function. However, the deck is pragmatic about it: the default partitioner normally works well. Write your own when you have measured a problem, not before.
Hadoop used to create only one, global Reduce task by default — an obvious bottleneck for a large job. So how many should there be? The deck offers two defensible answers and refuses to declare a winner.
| Strategy | Argument for | Argument against |
|---|---|---|
| One task per CPU many keys per task |
The obvious mapping of work onto hardware | Different tasks may take significantly different times, usually because of the non-uniform distribution of values within keys (skewness). A random distribution of keys within tasks may mitigate potential problems. |
| Many tasks per CPU fewer keys per task |
Better capable of mitigating skewness problems: time-consuming tasks occupy a CPU fully, while many quicker tasks run sequentially in the same CPU | There is overhead associated with each task |
The second strategy is worth understanding properly, because the reasoning recurs everywhere in this course. If you have many small tasks and one of them turns out to be huge, the scheduler simply keeps feeding the other CPUs with the remaining small tasks while the big one grinds away. With one task per CPU, every other CPU finishes and then waits. Over-decomposition buys you elasticity — at the price of per-task overhead.
Choosing the number of reducers for a job is more of an art than a science. The rule of thumb the deck gives is the useful takeaway: a task should run for about 5 minutes and produce at least one DFS block’s worth of output. Below that, you are paying more in scheduling than you gain in parallelism; well above it, a single failure or a single straggler costs too much.
Everything in this chapter collapses into four signatures. Two you must write; two you usually write.
map (k1, v1) → list(k2, v2)
reduce (k2, list(v2)) → list(k3, v3)All values with the same key are reduced together. And usually, programmers also specify:
combine (k2, list(v2)) → list(k3, v3)
partition (k2, number_of_partitions) → partition_for_k2| Function | Role |
|---|---|
| combine | Mini-reducers that run after the map phase; used as an optimization to reduce network traffic |
| partition | Divides up the key space for parallel reduce operations |
Look at the type of combine: it has exactly the signature of reduce. That is not a coincidence, it is the formal statement of section 8 — a combiner is a reducer you are allowed to run early, and it is legal precisely when running it early cannot change the result.
Four small functions, and then: the execution framework handles everything else. Splitting the input, launching tasks near their data, sorting, moving partitions across the network, restarting whatever died, and writing the output back to the DFS. Chapter 5 opens that box.
Before the patterns, a warning the deck states plainly: MapReduce is a paradigm, not a tool. You must fit your solution into the framework of map and reduce, and in some situations that might be challenging — translating machine learning and data mining algorithms to the MapReduce paradigm is not trivial. Sometimes you need multiple map/reduce stages: chains of maps and reduces (section 13, and all of Chapter 9).
Four patterns cover a surprising share of real jobs.
Goal: find lines/files/tuples with a particular characteristic. Examples: retrieve web logs for requests to a certain domain (or from a certain IP); retrieve a sample of the dataset; find the 10 customers with the highest reputation, given that the reputation is already stored in the data.
map (key, record) → if (criteria is met) then emit(key, record)
reduce (key, record) → if (criteria is met) then emit(key, record)
— reduce may even be omittedFiltering is the one pattern with no aggregation at all: there is nothing to bring together, so there is nothing to shuffle. A map-only job is the cheapest thing this framework can run.
Goal: compute the maximum/sum/average/... over a set of values. Examples: count the number of requests to each subdomain of *.csr.unibo.it; find the most popular domain; build an inverted index of words in documents.
map (key, record) → foreach group_criteria in record :
emit (group_criteria, value)
reduce (group_criteria, values) → emit (group_criteria, agg(values))A combiner may be used to perform a pre-aggregation — subject, of course, to section 8.
Goal: combine different inputs on some shared values. Example: given a list of professors (with the courses they teach) and a list of students (with the courses they follow), find all triples <professor, course, student> where the course is in common.
map (key, record) → if (dataset1)
then emit (sharedKey, (flag1, record) )
else emit (sharedKey, (flag2, record) )
reduce (sharedKey, records) → for r1 in records with flag1 :
for r2 in records with flag2 :
emit (someKey, <r1, sharedKey, r2> )The trick is the flag. Both datasets are poured into the same shuffle under the same key, and each record carries a tag saying which side it came from; the reducer then does the nested loop. Worked through with the example from the slides:
Prof(Name, Course) = {(Enrico, BigData), (Matteo, BigData)}
Stud(Name, Course) = {(Mario, BigData), (Lucia, DataMining)}
Prof JOIN Stud ON (Prof.Course = Stud.Course)
MAP: {(BigData, (Prof, Enrico)), (BigData, (Prof, Matteo)),
(BigData, (Stud, Mario)), (DataMining, (Stud, Lucia))}
SHUFFLE AND SORT: {(BigData, [(Prof, Enrico), (Prof, Matteo), (Stud, Mario)]),
(DataMining, [(Stud, Lucia)])}
REDUCE: {(k1, (Enrico, BigData, Mario)), (k2, (Matteo, BigData, Mario))}Notice what happened to DataMining: it arrives at a reducer with a student and no professor, the nested loop runs zero times, and nothing is emitted. The inner join falls out of the pattern for free.
Goal: sort input. Example: return all the domains indexed by Google and the number of pages in each, ordered by the number of pages.
Here the deck makes a subtle and very examinable point: the programming model (map, then reduce) does not support sorting per se — but the implementations do, because the shuffle stage performs grouping and ordering. You get sorting as a side effect of the machinery, not as a feature of the model.
map (sortKey, record) → emit (sortKey, record)
reduce (sortKey, records) → emit (sortKey, records[1]), ...The Map and the Reduce do nothing. With 1 reducer, we get sorted output. With many reducers, we get partly sorted output — each partition is internally sorted, but the partitions are not ordered relative to each other — unless you use the TotalOrderPartitioner, which assigns key ranges rather than hash values to reducers.
“Can MapReduce sort?” deserves a precise answer: the model cannot, the implementation can, because shuffle & sort already orders keys locally. State the consequence too: one reducer gives a globally sorted result but no parallelism; many reducers give parallelism but only partial ordering, unless the partitioner is range-based (TotalOrderPartitioner).
As map-reduce calculations get more complex, it is useful to break them down into stages:
And the economic argument for doing so: early stages of map-reduce operations often represent the heaviest amount of data access, so building and saving them once as a basis for many downstream uses saves a lot of work. The first stage is the one that touches the raw terabytes; every later stage works on something far smaller.
Read the two keys and the design becomes obvious. Stage one groups by month, year, product because that is the finest grain we will need. Stage two drops the year from the key and moves it into the value, so that the 2010 and the 2011 totals for the same month and product finally meet at the same reducer, where they can be divided.
Chaining stages is how you compare two things that live in different records. A reducer can only combine values that share a key, so if you need x and y together, some stage must emit them under the same key. Moving a field out of the key and into the value is the standard move, and it is worth recognising: you will do it again in Chapter 9 when parallelising genuinely awkward algorithms.
The course runs an exercise that is worth more than any diagram. The setup:
The tasks were prescribed, MapReduce-style:
| Task | Instructions |
|---|---|
| First task (on a given block) |
Convert USD to EUR (10 USD make 9 EUR) · Calculate partial totals by category in 2025 · Write partial totals in separate messages |
| Second task | Collect partial totals (of a given category) · Calculate the total |
That first task is a mapper with a combiner: transform each record, pre-aggregate locally, emit one message per category. The second is a reducer: collect everything for one key and sum. Then the five human clusters ran, and here is what they produced:
| Category | Ground truth | Cluster 1 (by the window) | Cluster 2 | Cluster 3 | Cluster 4 | Cluster 5 (by the entrance) |
|---|---|---|---|---|---|---|
| Books | 52.5 | 49 | 48.25 | 64.5 | 55.5 | 52.5 |
| Clothing | 80.5 | 57 | 80 | 77.5 | 95.5 | 80.5 |
| Technology | 75 | 77 | 75 | 85 | 100 | 75 |
One cluster out of five got all three numbers right. The deck congratulates Cluster 5 and closes with the line: to everyone else — this is why we use machines for this kind of job.
The interesting result is not that one group succeeded; it is how the other four failed, because each failure mode has a counterpart the framework must engineer away:
Every guarantee in this chapter looks like bureaucracy until you watch twenty intelligent people fail to add three columns without it.
If asked what the execution framework actually provides, do not answer “parallelism”. Answer correctness under parallelism: deterministic partitioning, the guarantee that all values of a key meet on one machine, sorted delivery, and automatic re-execution of whatever failed. Parallelism is easy; parallelism that returns the same number as a single machine would is the product.
“MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.” The ambiguity is that the name covers two different things: the programming model, and an implementation of it. Hadoop MapReduce is an open-source implementation of the MapReduce programming model — the model tells you what you can express, the implementation tells you how the tasks are actually scheduled and run.
Map: each task reads the records local to its node and extracts (Country, Revenue) pairs — no network traffic. Shuffle & Sort: a global operation that redistributes data on the basis of how it is meant to be aggregated, so that all values of one key land on one machine; sorting is done locally to enable the later aggregation. Reduce: each task performs an ordinary local aggregation over the keys it received (Italy 84, France 21, UK 12, Belgium 10, Spain 23, USA 2). The shuffle is the only phase that moves large volumes across the network, and therefore the only phase that really costs.
1) The input is divided into fixed-size splits: smaller splits give faster processing and better load balancing but more management overhead, and the optimal split size equals the DFS block size. 2) One map task per split, running the user-defined map function on each record. 3) The emitted pairs are sorted and stored on the local disk — map output is intermediate, so writing it to HDFS with replication would be overkill — and subdivided into partitions, one per reducer. 4) Map outputs are sent to the reduce nodes; the number of reduce tasks is specified independently, inputs from different mappers are merged and sorted by key, all values of a key reach the same reducer, and a reducer may handle several keys one at a time.
Only the mapper. Word Count emits (word, 1) — keys are the words, values are 1 — and the reducer sums the values to emit (w, m). Word Length Count emits (length, word) — the key is the length of a word, the value is the word itself — and the reducer counts the elements of the list to emit (l, m). The lesson is that designing a MapReduce job is choosing the key: the framework, the shuffle and the reduce skeleton are unchanged, yet the two jobs answer completely different questions.
First, the premise: a combiner pre-aggregates on the map side to cut intermediate data and network traffic, and it is legal only when the function is associative and commutative — grouping is still needed either way, since values of one key are spread across splits. Non-commutative — concatenation of alphabetically-ordered values, where f(a,b) ≠ f(b,a). For key 3 the values are z, a, u, h with z and a on the same map task. With a combiner they are folded into az before the shuffle, and the reducer produces azhu; without a combiner it receives z, a, u, h and produces ahuz. Non-associative — the average, where f(f(a,b),c) ≠ f(a,f(b,c)). For key c the values are 3, 9, 2, 8 with 3 and 9 on the same task. With a combiner they become 6, the reducer sees 2, 6, 8 and returns 5.33; without it the reducer sees 2, 3, 8, 9 and returns 5.5. The combined value arrives without its weight, so the average of averages is not the average.
Let p be the number of reduce tasks, either specified by the user or calculated by the system. The partitioner adopts a hash function that translates a key to a number from 0 to p−1; different keys may end up in the same partition. Each output key-value pair is written into one of p files, each destined for one reduce task, and each reduce task collects from every map task the partitions with the same hash value. With m map tasks that is m × p partition files.
Because a partitioner only considers the key and ignores the number of values. The simplest partitioner assigns approximately the same number of keys to each reducer, but in many text processing applications the amount of data per key is heavily skewed: the frequency of any word is inversely proportional to its rank in the frequency table, so the most frequent word occurs about twice as often as the second, three times as often as the third, and so on. A reducer that receives one very popular key does far more work than the others, and the job finishes only when the slowest reducer finishes.
Hadoop used to create only one global reduce task by default, an obvious bottleneck. One task per CPU with many keys per task maps work onto hardware directly, but different tasks may take very different times because of skewness — a random distribution of keys within tasks may mitigate it. Many tasks per CPU with fewer keys per task handles skew better, since a time-consuming task occupies one CPU fully while many quicker tasks run sequentially elsewhere, but there is overhead associated with each task. Choosing is “more of an art than a science”; the rule of thumb is that a task should run for about 5 minutes and produce at least one DFS block’s worth of output.
The mapper emits every record under the shared key, tagged with a flag identifying which dataset it came from: emit (sharedKey, (flag1, record)) or emit (sharedKey, (flag2, record)). The reducer receives all records for that key and performs a nested loop, emitting a triple for each pair of records with flag1 and flag2. In the example, BigData arrives with Enrico and Matteo (professors) and Mario (student), producing (Enrico, BigData, Mario) and (Matteo, BigData, Mario); DataMining arrives with only Lucia, the nested loop runs zero times, and nothing is emitted — the inner-join semantics come for free.
The programming model does not support sorting per se — map then reduce says nothing about order — but the implementations do, because the shuffle stage already performs grouping and ordering. The pattern is trivial: map (key, record) → emit (sortKey, record) and the reducer emits the records, so the map and the reduce do nothing. With 1 reducer you get sorted output; with many reducers you get partly sorted output — each partition sorted internally, but partitions unordered relative to each other — unless you use the TotalOrderPartitioner, which assigns key ranges instead of hash values.
Because the output of one stage feeds the next, the same output may serve several later stages, and it can be stored in the DFS as a materialized view. Since early stages represent the heaviest data access, building and saving them once for many downstream uses saves a lot of work. In the example, stage one emits concat(month, year, product) → qty and reduces to the sum, producing sales for a single product in a single month of a single year. Stage two emits concat(month, product) → (year, totalQty) — the year moves out of the key and into the value — so the 2010 and 2011 totals for the same month and product meet at the same reducer, which emits totals[2011]/totals[2010].
Each group was a cluster and each person a machine, with sales data spread in blocks and one constraint: you can only exchange data, not commands. The first task (convert USD to EUR at 10 USD = 9 EUR, compute partial totals by category in 2025, write them in separate messages) is a mapper with a combiner; the second (collect the partial totals of a category and total them) is a reducer. Only Cluster 5 reproduced the ground truth (Books 52.5, Clothing 80.5, Technology 75). The lesson is that the failures map one-to-one onto the guarantees a framework must provide: arithmetic slips call for deterministic functions and task re-execution, lost or misdirected messages for a mechanical partitioner and a tracked shuffle, and unreconciled partial results for the guarantee that all values of a key reach exactly one reducer.