Explaining Map Reduce
Hadoop Map Reduce is a software framework for easily writing applications which process vast amounts of data (multi-terabyte data sets) in parallel, on large clusters of commodity hardware (thousands of nodes) in a reliable and fault tolerant manner.
A Map Reduce Job splits the input data-set into independent chunks which are processed by the map tasks in completely parallel manner. The framework sorts the output of map tasks which are then input to reduce tasks.
The Map and Reduce functions can be represented by following:
Explaining Map Reduce
This post attempts to explain map reduce in simple terms.
Problem Statement
It is easiest to understand Map Reduce by walking through an example. Let's consider a deck of 52 playing cards. Each deck has 4 suits: Hearts, Diamonds, Spades and Clubs. Each suit has 13 cards: 2 to 10 numeric cards, Jack, Queen, King and Ace.
The problem statement is to find sum of all numeric cards by suit. Therefore the expected answer is : Hearts (2+3+4+5+6+7+8+9+10) = 54. Similarly Diamonds = 54, Spades = 54 and Clubs = 54.
Intuition
The first step in decomposing a problem statement and evaluating whether Map Reduce paradigm can be applied or not, is to determine what (if any) steps can be parallelized. (Map Reduce is only suitable when a big chunk of data processing can be parallelized)
Considering the above example, since "each" playing card is independent and has no dependency on any "other" playing card, the summation activity can happen in parallel. (Note: it is not important whether the sum needs to be taken per suit or for the entire deck)
Lets imagine we have to solve this problem "manually" and we have 3 people who can do the task. How will we go about it ?
- The first step is to randomly divide 52 playing cards into 3 piles. (As there are 3 people. This is the split part in Map Reduce.
- Each person will independently calculate sum of all the cards in his/her pile per suit. This is the Map function in Map Reduce and multiple copies of the same function will be executed in parallel.
- Once all 3 people are finished, there will be a co-ordination activity where sums per suit of all 3 people are combined together to get ultimate answer. This is the Reduce function in Map Reduce.
Map Function
Definition
Input
For our specific problem statement, in whatever form the input might be, if we transform the input into a csv file with one record per line in the format: <suit>,<card_value> then we can use the csv file as an input to the map function. In this case the key: k1 will be one of 4 options: Spades or Diamonds or Hearts or Clubs and the value: v1 will be the actual card value. For example we can split the 52 playing cards and one of the splits can look like this:
Processing
In this example, the work, the map function will do, is do a summation of the numeric cards per suit that it receives. It will acheive this by first discarding inputs cards with value Jack, Queen, King or Ace and then adding values of remaining numeric cards. For example if the map function received the input represented above, then after summation of numeric cards per suit, it will store the following as an intermediate state:
Output
As per definition the output of map function is list(k2,v2). Therefore in the example, it will be a list of all suits with intermediate summation of the cards it has received.
Reduce Function
Defintion
Input
The input to Reduce function is the output of all Map function executions combined together by key: k2. Therefore value: v2 will be a list whose size will be equal to number of map tasks.
Processing
The goal of our program is to do summation per suit. The "per suit" aspect is already handled by key: k2. Therefore all the reduce function has to do is go through the list and perform summation.
Output
The reduce function will output the summation value.
Summary
Map Reduce paradigm takes advantage of clusters to machines to perform analysis of large datasets. The steps of analysis which can be executed in parallel are done so using the Map function. Subsequently the Reduce function combines results of multiple executions of the Map function to provide intended output.
