# How partitioning in map-reduce work?

Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the same partition (within each mapper), and then each partition is sent to a reducer. Thus there might be a case in which there are two partitions with the same key from two different mappers going to 2 different reducers. How to prevent this from occurring? That is, how to send all partitions (from different mappers) with the same key to the same reducer?

Let's take a simple example, Counting word into a distributed set of documents:

each mapper takes in input a list of document, and returns a list of pairs word and how many times this word occurs. There is an intermediate layer that takes the outputs of all the mapper and groups values by key. After that the reducer will sum each of this value. This is a practical example:

Output of 3 mappers

1. Mapper1 (house,4) (dog,2) (cat,1)
2. Mapper2 (dog,3)
3. Mapper3 (cat,5) (house,6)

before give these data to the reducer the intermediate layer will group them by key. obtaining :

• (house, (6,4))
• (dog,(3,2))
• (cat,(5,1))

After that reducers take in input these pairs and sum values:

1. Reducer 1 (house ,(6,4))-> (house,10)

2. Reducer 2 (dog,(3,2)) -> (dog,5) (cat,(5,1)) -> (cat,6)

The MapReduce idea comes from a paper by google that you can find here: http://research.google.com/archive/mapreduce.html

reading this article you will notice that the mapper gives in output a list of pairs, but the reducer takes in input a pair of (key , list(value)) this implies that there is something in between that "lists" all values with the same keys. This task is done on the output of ALL the mappers, this task is optimized , sorting values ecc.. but as i say is in practice done on all the mapper.

If you know a little of java i suggest you to try something using the Hadoop framework by Apache

as you can see in the linked example the CombinerFunction(the intermediate layer that i've mentioned) works on the same input of the reducers.

• Thanks for your reply. The intermediate layer does not combine the intermediary results from different mappers! It just combine the intermediary results from one mapper. That is, in your example, there would be two records with key value "house", not just one. – HHH Dec 4 '12 at 19:01
• And that's what makes it more complicated – HHH Dec 4 '12 at 19:06
• i've edited the post with some clarification ;) – dbonadiman Dec 4 '12 at 19:29
• and this is something that makes you understand what's going on: slide 7 these are the slides of the paper mentioned above :) – dbonadiman Dec 4 '12 at 19:35