MapReduce Explained

Context

To understand distributed processing, it is really important to understand how MapReduce works. MapReduce is the processing component of Hadoop architecture. MapReduce is a programming paradigm, which means, particular approach to solve a problem e.g procedural paradigm, Object oriented paradigm etc. In this case our problem is distributed processing, how to process single file on multiple machines (data nodes). Using MapReduce we can solve this problem in Hadoop. MapReduce is simply bundle of java files (jar files). One mapper file, One reducer file and one main file. As per the problem statement, Data engineer would write down the java files and execute these on the data files, this approach make one thing clear that MapReduce isn’t ideal choice for live stream data processing, where we need to process data dynamically as soon as it comes.

Working Principle

There are two phases in MapReduce:

1. Map phase
2. Reduce phase

1st of all we need to understand, what input map phase and reduce phase require in order to process the data.

Mappers and reducers take input in the form of key, value pairs. Now big question is how come a normal text, csv files will get converted into key value pairs? The answer to this is record reader.

Record Reader reads the files line by line and convert it into (k,v) pairs. And these pairs are given to the mappers as input.

Let’s understand this with the help of examples.

• input file : file1.txt 500 MB file
• Problem Statement: Count of each word
• no. of blocks = 500 MB/128MB = 4 blocks. block 1 = 128 MB, block 2 = 128 MB, block 3 = 128 MB, block 4 = 116 MB
• no. of mapper jobs = no of file blocks, in this case 4 mapper jobs will run in total.
• Assume we have 4 node cluster, then
• no. of parallel mapper job = no. of cluster nodes
• Let’s say file content is as below:

My name is Sharayu
I am a big data enthusiast
My name is Sharayu
I am a big data enthusiast
My name is Sharayu
I am a big data enthusiast
My name is Sharayu

Now as per above logic, content of this file will get divided in 4 parts as below and all will be stored in HDFS.

My name is Sharayu
I am a big data enthusiast              B1
==================================
My name is Sharayu
I am a big data enthusiast              B2
===================================
My name is Sharayu
I am a big data enthusiast              B3
====================================
My name is Sharayu                    B4

When user will run MapReduce file on data files, it will be transferred to the Data nodes to be executed on blocks of file present in HDFS. Then record reader comes into picture to convert each data in key, value format.

Output of record reader is as below. (Note: Key can be anything depending upon file format, here I have taken normal index for ease of explanation)

(0, My name is Sharayu)
(1, I am a big data enthusiast)             B1
==================================
(2, My name is Sharayu)
(3, I am a big data enthusiast)             B2
===================================
(4, My name is Sharayu)
(5, I am a big data enthusiast)             B3
====================================
(6, My name is Sharayu)                     B4

So above (K,V) pairs will be input to the mappers and based on mappers logic written output will get generated as (K,V) pairs.

Get Sharayu Salunke’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So this is happening inside mapper (Data Node). You need to remember that mappers and reducers are nothing but the same cluster nodes.

(0, My name is Sharayu)                            (My, 1)
(1, I am a big data enthusiast) ---> Mapper 1 ---> (name, 1)
                                                   (is, 1)
                                                   (Sharayu, 1)
                                                   (I, 1)
                                                   (am, 1)
                                                   (a, 1)
                                                   (big, 1)
                                                   (data, 1)
                                                   (enthusiast, 1)

(0, My name is Sharayu)                            (My, 1)
(1, I am a big data enthusiast) ---> Mapper 2--->  (name, 1)
                                                   (is, 1)
                                                   (Sharayu, 1)
                                                   (I, 1)
                                                   (am, 1)
                                                   (a, 1)
                                                   (big, 1)
                                                   (data, 1)
                                                   (enthusiast, 1)

(0, My name is Sharayu)                            (My, 1)
(1, I am a big data enthusiast) ---> Mapper 3--->  (name, 1)
                                                   (is, 1)
                                                   (Sharayu, 1)
                                                   (I, 1)
                                                   (am, 1)
                                                   (a, 1)
                                                   (big, 1)
                                                   (data, 1)
                                                   (enthusiast, 1)

(0, My name is Sharayu) ---> Mapper 4--->  (My, 1) 
                                           (name, 1)
                                           (is, 1)
                                           (Sharayu, 1)

Once mapper output is generated it is then transferred to reducer (any of one data node) and this is how shuffling comes into picture.

Once reducer has all of the data, then it does the sorting and aggregation on the data as below and gives us final output as (key, value) pairs.

(My, 1)             (a, 1)     
(name, 1)           (a, 1)
(is, 1)             (a, 1)
(Sharayu, 1)        (am, 1)
(I, 1)              (am, 1)
(am, 1)             (am, 1)
(a, 1)              (big, 1)
(big, 1)            (big, 1)
(data, 1)           (big, 1)
(enthusiast, 1)     (data, 1)
(My, 1)             (data, 1)
(name, 1)           (data, 1)
(is, 1)             (enthusiast, 1)
(Sharayu, 1)        (enthusiast, 1)
(I, 1)              (enthusiast, 1)    (a, {1,1,1})          (a, 3)
(am, 1)             (I, 1)             (am, {1,1,1})         (am, 3)
(a, 1)              (I, 1)             (big, {1,1,1})        (big, 3)
(big, 1)       ---->(I, 1)          -->(data, {1,1,1})  -->  (data, 3)
(data, 1)           (is, 1)            (enthusiast, {1,1,1}) (enthusiast,3)
(enthusiast, 1)     (is, 1)            (I,{1,1,1})           (I,3)
(My, 1)             (is, 1)            (is, {1,1,1,1})       (is, 4)
(name, 1)           (is, 1)            (My, {1,1,1,1})       (My, 4)
(is, 1)             (My, 1)            (Name, {1,1,1,1})     (Name, 4)
(Sharayu, 1)        (My, 1)            (Sharayu, {1,1,1,1})  (Sharayu, 4)
(I, 1)              (My, 1)
(am, 1)             (My, 1)
(a, 1)              (name, 1)
(big, 1)            (name, 1)
(data, 1)           (name, 1)
(enthusiast, 1)     (name, 1)
(My, 1)             (Sharayu, 1)
(name, 1)           (Sharayu, 1)
(is, 1)             (Sharayu, 1)
(Sharayu, 1)        (Sharayu, 1)

So, by now it is clear that mapper gives us more parallelism than reducers, so in order to be efficient, one should keep in mind that mapper should execute most of the work in order to achieve good performance.

By default no. of reducer are 1, but we can make it 0 or any numbers other that 1.

For example, if one wants to filter the data, we don’t need sorting and aggregation, in that case we can set no. of reducers to 0.

While, when we increase no. of reducers to more than one, output of the mapper need to go to the specific reducer only, and that is decided by hash function which is based on keys of the mappers outputs (One can customize the hash function according to their needs).

So, how can mappers do more work to avoid overhead on reducers?

That’s where combiners come into picture.

Lets consider simple example where we need to find out maximum number.

1, 7, 9,
8, 2, 5,
7, 3, 1

Let’s say above file gets divided in 3 blocks, and we are dealing with 3 node cluster.

So, mapper one will work on (1, 7, 9), mapper 2 will work on (8, 2, 5) likewise mapper 3 will work on (7, 3, 1). Since in this case, mappers don’t have much work to do they will pass this data to reducers. So now, reducers will work on entire data. Where we don’t get any parallelism and this is not the ideal case.

So when we introduce combiners we would run reducer code locally on individual mappers in order to reduce input given to reducer. Below is the pictorial representation of the combiners concept.

But when we introduce combiners in our logic we need to be very careful, as when we are dealing with requirements which deals with Average logic, then we might get wrong results. Because average of combiner’s output can mostly be different than average of direct mapper’s output.

Evolution of Spark

Below are the key bottlenecks due to which spark came into existence replacing MapReduce in Hadoop architecture.

Disadvantages of MapReduce

1. Need to write complex MapReduce code in java.
2. A lot of disk i/os overhead.
3. Only supports batch processing.
4. No flexibility to work on data like in spark.
5. One might need to think of how mappers and reducers will respond to the code, rather than thinking about main problem.