Chapter 5

Hadoop MapReduce
This MapReduce chapter provides you the complete guide about each and everything in Hadoop
MapReduce.
You will explore what Hadoop MapReduce is, How the MapReduce framework works. The chapter
also covers MapReduce DataFlow, Different phases in MapReduce, Mapper, Reducer, Partitioner,
Cominer, Shuffling, Sorting, Data Locality, and many more.

The above figure depicts the schematic view of the traditional enterprise systems. The traditional
systems normally have a centralized server for storing and processing data. This model is not suitable
for processing huge amounts of scalable data.
Also, this model could not be accommodated by the standard database servers. Additionally, the
centralized system creates too much bottleneck while processing multiple files simultaneously.
By using the MapReduce algorithm, Google solved this bottleneck issue. The MapReduce framework
divides the task into small parts and assigns tasks to many computers.
Later on, the results are collected at a commonplace and are then integrated to form the result
dataset.

MapReduce Framework
MapReduce is the processing layer in Hadoop. It is a software framework designed for processing
huge volumes of data in parallel by dividing the task into the set of independent tasks.
We just need to put the business logic in the way the MapReduce works, and the framework will take
care of the rest things. The MapReduce framework works by dividing the job into small tasks and
assigns these tasks to the slaves.
The MapReduce programs are written in a particular style influenced by the functional programming
constructs, specifical idioms for processing the lists of data.
In MapReduce, the inputs are in the form of a list and the output from the framework is also in the
form of a list. MapReduce is the heart of Hadoop. The efficiency and powerfulness of Hadoop are
due to the MapReduce framework parallel processing.

How Hadoop MapReduce Works?

The Hadoop MapReduce framework works by dividing a job into independent tasks and executing
these tasks on slave machines. The MapReduce job is executed in two stages that are map phase and
the reduce phase.
The input to and output from both the phases are key, value pairs. The MapReduce framework is
based on the data locality principle which means it sends the computation to the nodes where data
resides.
Map phase − In the Map phase, the user-defined map function processes the input data. In the map
function, the user puts the business logic. The output from the Map phase is the intermediate outputs
and is stored on the local disk.
Reduce phase – This phase is the combination of the shuffle phase and the reduce phase. In the
Reduce phase, the output from the map stage is passed to the Reducer where they are aggregated.
The output of the Reduce phase is the final output. In the Reduce phase, the user-defined reduce
function processes the Mappers output and generates the final results.
During the MapReduce job, the Hadoop framework sends the Map tasks and the Reduce tasks to
appropriate machines in the cluster.
The framework itself manages all the details of the data-passing such as issuing tasks, verifying the
task completion, and copying data between the nodes around the cluster.

Key-Value pairs in MapReduce

The MapReduce framework works on the key, value pairs because it deals with the non-static schema.
It takes data in the form of key, value pair, and generated output is also in the form of a key, value
pairs.
The MapReduce key Value pair is a record entity that is received by the MapReduce job for the
execution. In a key-value pair:
Key is the line offset from the beginning of the line within the file.
Value is the line content, excluding the line terminators.

MapReduce Partitioner
The Hadoop MapReduce Partitioner partitions the keyspace. Partitioning keyspace in MapReduce
specifies that all the values of each key were grouped together, and it ensures that all the values of
the single key must go to the same Reducer.
This partitioning allows even distribution of mapper’s output over Reducer by assuring that the right
key goes to the right Reducer.
The default MapReducer partitioner is the Hash Partitioner, which partitions the keyspaces on the
basis of the hash value.

MapReduce Combiner
The MapReduce Combiner is also known as the “Semi-Reducer.” It plays a major role in reducing
network congestion. The MapReduce framework provides the functionality to define the Combiner,
which combines the intermediate output from Mappers before passing them to Reducer.
The aggregation of Mapper outputs before passing to Reducer helps the framework shuffle small
amounts of data, leading to low network congestion.
The main function of the Combiner is to summarize the output of the Mappers with the same key and
pass it to the Reducer. The Combiner class is used between the Mapper class and the Reducer class.
Data Locality in MapReduce
Data locality refers to “Moving computation closer to the data rather than moving data to the
computation.” It is much more efficient if the computation requested by the application is executed
on the machine where the data requested resides. This is very true in the case where the data size is
huge. It is because it minimizes the network congestion and increases the overall throughput of the
system.
The only assumption behind this is that it is better to move computation closer to the machine where
data is present instead of moving data to the machine where the application is running.
Apache Hadoop works on a huge volume of data, so it is not efficient to move such huge data over the
network. Hence the framework came up with the most innovative principle that is data locality, which
moves computation logic to data instead of moving data to computation algorithms. This is called data
locality.

Usage of MapReduce
1. Log analysis: MapReduce is used basically for analyzing log files. The framework breaks the big log
files into the split and a mapper search for the different web pages that were accessed. Every
time when a web page is found in the log, then a key, value pair is passed to the reducer where
the key is the webpage, and value is “1”. After emitting a key, value pair to Reducer, the Reducers
aggregate the number of for certain webpages. The final result will be the total number of hits for
every webpage.
2. Full-text indexing: MapReduce is also used for performing full-text indexing. The mapper in
MapReduce will map every phrase or word in one document to the document. The Reducer will
write these mappings to an index.
3. Google uses MapReduce for calculating their Pagerank.
4. Reverse Web-Link Graph: MapReduce is also used in Reverse Web-Link GRaph. The Map function
outputs the URL target and source, taking input from the webpage (source). The reduce function
then concatenates the list of all the source URLs which are associated with the given target URL
and it returns the target and list of sources.
5. Word count in a document: MapReduce framework can be used for counting the number of
times the word appears in a document.

Features Of MapReduce – Importance of MapReduce

Apache Hadoop is a software framework that processes and stores big data across the cluster of
commodity hardware. Hadoop is based on the MapReduce model for processing huge amounts of
data in a distributed manner.
This MapReduce Tutorial enlisted several features of MapReduce. After reading this, you will clearly
understand why MapReduce is the best fit for processing vast amounts of data.
First, we will see a small introduction to the MapReduce framework. Then we will explore various
features of MapReduce.
1. Scalability
Apache Hadoop is a highly scalable framework. This is because of its ability to store and distribute
huge data across plenty of servers. All these servers were inexpensive and can operate in parallel. We
can easily scale the storage and computation power by adding servers to the cluster.
Hadoop MapReduce programming enables organizations to run applications from large sets of nodes
which could involve the use of thousands of terabytes of data.
Hadoop MapReduce programming enables business organizations to run applications from large sets
of nodes. This can use thousands of terabytes of data.
2. Flexibility
MapReduce programming enables companies to access new sources of data. It enables companies to
operate on different types of data. It allows enterprises to access structured as well as unstructured
data, and derive significant value by gaining insights from the multiple sources of data.
Additionally, the MapReduce framework also provides support for the multiple languages and data
from sources ranging from email, social media, to clickstream.
The MapReduce processes data in simple key-value pairs thus supports data type including meta-data,
images, and large files. Hence, MapReduce is flexible to deal with data rather than traditional DBMS.

3. Security and Authentication

The MapReduce programming model uses HBase and HDFS security platform that allows access only
to the authenticated users to operate on the data. Thus, it protects unauthorized access to system
data and enhances system security.
4. Cost-effective solution
Hadoop’s scalable architecture with the MapReduce programming framework allows the storage and
processing of large data sets in a very affordable manner.
5. Fast
Hadoop uses a distributed storage method called as a Hadoop Distributed File System that basically
implements a mapping system for locating data in a cluster.
The tools that are used for data processing, such as MapReduce programming, are generally located
on the very same servers that allow for the faster processing of data.
So, Even if we are dealing with large volumes of unstructured data, Hadoop MapReduce just takes
minutes to process terabytes of data. It can process petabytes of data in just an hour.

6. Simple model of programming

Amongst the various features of Hadoop MapReduce, one of the most important features is that it is
based on a simple programming model. Basically, this allows programmers to develop the MapReduce
programs which can handle tasks easily and efficiently.
The MapReduce programs can be written in Java, which is not very hard to pick up and is also used
widely. So, anyone can easily learn and write MapReduce programs and meet their data processing
needs.
7. Parallel Programming
One of the major aspects of the working of MapReduce programming is its parallel processing. It
divides the tasks in a manner that allows their execution in parallel.
The parallel processing allows multiple processors to execute these divided tasks. So the entire
program is run in less time.
8. Availability and resilient nature
Whenever the data is sent to an individual node, the same set of data is forwarded to some other
nodes in a cluster. So, if any particular node suffers from a failure, then there are always other copies
present on other nodes that can still be accessed whenever needed. This assures high availability of
data.
One of the major features offered by Apache Hadoop is its fault tolerance. The Hadoop MapReduce
framework has the ability to quickly recognizing faults that occur.

Phases of MapReduce
MapReduce is one of the core components of Hadoop that processes large datasets in parallel by
dividing the task into a set of independent tasks. In this MapReduce Tutorial, you will study the
working of Hadoop MapReduce in detail.
It covers all the phases of MapReduce job execution like Input Files, InputFormat, InputSplits,
RecordReader, Mapper, Combiner, Partitioner, Shuffling, and Sorting, Reducer, RecordWriter, and
OutputFormat in detail.
The Hadoop MapReduce framework consists of:
 single master ResourceManager
 One worker NodeManager per cluster-node
 MRAppMaster per application

The applications specify the input and the output locations and supply the map and reduce functions
through the implementations of appropriate interfaces or abstract classes.
These and the other job parameters comprise job configuration.
Then, the Hadoop job client submits the job, that is, jar or executable, and configuration to the
ResourceManager. ResourceManager then assumes the responsibility of distributing the contribution
of software to the workers, scheduling tasks and monitoring them, and providing status and
diagnostic information to the job-client.
Though the Hadoop framework is implemented in Java, it is not needed to write MapReduce
applications in Java.

How Hadoop MapReduce works?

The whole process goes through various MapReduce phases of execution, namely, splitting, mapping,
sorting and shuffling, and reducing.

1. InputFiles
The data that is to be processed by the MapReduce task is stored in input files. These input files are
stored in the Hadoop Distributed File System. The file format is arbitrary, while the line-based log files
and the binary format can also be used.

2. InputFormat
It specifies the input-specification for the job. InputFormat validates the MapReduce job input-
specification and splits-up the input files into logical InputSplit instances. Each InputSplit is then
assigned to the individual Mapper. TextInputFormat is the default InputFormat.
Input files store the data for MapReduce job. Input files reside in HDFS. Although these files format is
arbitrary, we can also use line-based log files and binary format. Hence, In MapReduce, InputFormat
class is one of the fundamental classes which provides below functionality:
InputFormat selects the files or other objects for input.
It also defines the Data splits. It defines both the size of individual Map tasks and its potential
execution server.
Hadoop InputFormat defines the RecordReader. It is also responsible for reading actual records from
the input files.

How we get the data from Mapper?

Methods to get the data from mapper are: getsplits() and createRecordReader() which are as follows:
public abstract class InputFormat<K, V>
{
public abstract List<InputSplit> getSplits(JobContext context)
throws IOException, InterruptedException;
public abstract RecordReader<K, V>
createRecordReader(InputSplit split,
TaskAttemptContext context) throws IOException,
InterruptedException;
}

Types of InputFormat in MapReduce

There are different types of MapReduce InputFormat in Hadoop which are used for different purpose.
Let’s discuss the Hadoop InputFormat types below:
A. FileInputFormat
It is the base class for all file-based InputFormats. FileInputFormat also specifies input directory which
has data files location. When we start a MapReduce job execution, FileInputFormat provides a path
containing files to read.
This InpuFormat will read all files. Then it divides these files into one or more InputSplits.
B. TextInputFormat
It is the default InputFormat. This InputFormat treats each line of each input file as a separate record.
It performs no parsing. TextInputFormat is useful for unformatted data or line-based records like log
files. Hence,
Key – It is the byte offset of the beginning of the line within the file (not whole file one
split). So it will be unique if combined with the file name.
Value – It is the contents of the line. It excludes line terminators.

C. KeyValueTextInputFormat
It is similar to TextInputFormat. This InputFormat also treats each line of input as a separate record.
While the difference is that TextInputFormat treats entire line as the value, but the
KeyValueTextInputFormat breaks the line itself into key and value by a tab character (‘/t’). Hence,
Key – Everything up to the tab character.
Value – It is the remaining part of the line after tab character.

D. SequenceFileInputFormat
It is an InputFormat which reads sequence files. Sequence files are binary files. These files also store
sequences of binary key-value pairs. These are block-compressed and provide direct serialization and
deserialization of several arbitrary data. Hence,
Key & Value both are user-defined.

E. SequenceFileAsTextInputFormat
It is the variant of SequenceFileInputFormat. This format converts the sequence file key values to Text
objects. So, it performs conversion by calling ‘tostring()’ on the keys and values. Hence,
SequenceFileAsTextInputFormat makes sequence files suitable input for streaming.
F. SequenceFileAsBinaryInputFormat
By using SequenceFileInputFormat we can extract the sequence file’s keys and values as an opaque
binary object.

G. NlineInputFormat
It is another form of TextInputFormat where the keys are byte offset of the line. And values are
contents of the line. So, each mapper receives a variable number of lines of input with
TextInputFormat and KeyValueTextInputFormat.
The number depends on the size of the split. Also, depends on the length of the lines. So, if want our
mapper to receive a fixed number of lines of input, then we use NLineInputFormat.
N- It is the number of lines of input that each mapper receives.
By default (N=1), each mapper receives exactly one line of input.
Suppose N=2, then each split contains two lines. So, one mapper receives the first two Key-Value pairs.
Another mapper receives the second two key-value pairs.

H. DBInputFormat
This InputFormat reads data from a relational database, using JDBC. It also loads small datasets,
perhaps for joining with large datasets from HDFS using MultipleInputs. Hence,
Key – LongWritables
Value – DBWritables.

3. InputSplit
It represents the data for processing by the individual Mapper. InputSplit typically presents the byte-
oriented view of the input. It is the RecordReader responsibility to process and present the record-
oriented view. The default InputSplit is the FileSplit.
InputSplit is the logical representation of data in Hadoop MapReduce. It represents the data which
individual mapper processes. Thus the number of map tasks is equal to the number of InputSplits.
Framework divides split into records, which mapper processes.
MapReduce InputSplit length has measured in bytes. Every InputSplit has storage locations (hostname
strings). The MapReduce system places map tasks as close to the split’s data as possible by using
storage locations.
Framework processes Map tasks in the order of the size of the splits so that the largest one gets
processed first (greedy approximation algorithm). This minimizes the job run time.
The main thing to focus is that Inputsplit does not contain the input data; it is just a reference to the
data.

How InputSplits are created in Hadoop MapReduce?

As a user, we don’t deal with InputSplit in Hadoop directly, as InputFormat (as InputFormat is
responsible for creating the Inputsplit and dividing into the records) creates it. FileInputFormat breaks
a file into 128MB chunks.
Also, by setting [Link] parameter in [Link] user can change the value as per
requirement. Also by this we can override the parameter in the Job object used to submit a particular
MapReduce job.
By writing a custom InputFormat we can also control how the file is broken into splits.
InputSplit is user defined. The user can also control split size based on the size of data in MapReduce
program. Hence, In a MapReduce job execution number of map tasks is equal to the number of
InputSplits.
By calling ‘getSplit()’, the client calculate the splits for the job. Then it sent to the application master,
which uses their storage locations to schedule map tasks that will process them on the cluster.
After that map task passes the split to the createRecordReader() method. From that it obtains
RecordReader for the split. Then RecordReader generate record (key-value pair), which it passes to
the map function.

4. RecordReader
RecordReader reads the <key, value> pairs from the InputSplit. It converts a byte-oriented view of the
input and presents a record-oriented view to the Mapper implementations for processing.
It is responsible for processing record boundaries and presenting the Map tasks with keys and values.
The record reader breaks the data into the <key, value> pairs for input to the Mapper.
MapReduce is a simple model of data processing. Inputs and outputs for the map and reduce
functions are key-value pairs. Following is the general form of the map and reduce functions:

Map: (K1, V1) → list (K2, V2)

Reduce: (K2, list (V2)) → list (K3, V3)
Now before processing starts, it needs to know on which data to process. So, InputFormat class helps
to achieve this. This class selects the file from HDFS that is the input to the map function. It is also
responsible for creating the input splits.
Also, divide them into records. It divides the data into the number of splits (typically 64/128mb) in
HDFS. This is known as InputSplit. InputSplit is the logical representation of data. In a MapReduce job,
execution number of map tasks is equal to the number of InputSplits.
By calling ‘getSplit()’ the client calculates the splits for the job. Then it sent to the application master.
It uses their storage locations to schedule map tasks that will process them on the cluster.
After that map task passes the split to the createRecordReader() method. From that, it obtains
RecordReader for the split. RecordReader generates record (key-value pair). Then it passes to the map
function.

Hadoop RecordReader in MapReduce job execution uses the data within the boundaries that are
being created by the inputsplit. And it then creates Key-value pairs for the mapper. The “start” is the
byte position in the file.
At the Start, Hadoop RecordReader starts generating key/value pairs. The “end” is where RecorReader
stops reading records. In RecordReader, the data is loaded from its source.
Then the data are converted into key-value pairs suitable for reading by the Mapper. It communicates
with the inputsplit till the file reading is not completed.
How RecorReader works in Hadoop?

It is more than iterator over the records. The map task uses one record to generate key-value pair
which it passes to the map function. We can also see this by using the mapper’s run function given
below:
public void run(Context context ) throws IOException, InterruptedException{
setup(context);
while([Link]())
{
map([Link](),[Link](),context)
}
cleanup(context);
}
Although it is not mandatory for RecordReader to stay in between the boundaries created by the
inputsplit to generate key-value pairs it usually stays. Also, custom implementation can even read
more data outside of the inputsplit.

Then, after running setup(), the nextKeyValue() will repeat on the context. This populates the key and
value objects for the mapper. By way of context, framework retrieves key-value from record reader.
Then pass to the map() method to do its work.

Hence, input (key-value) to the map function processes as per the logic mentioned in the map code.
When the record gets to the end of the record, the nextKeyValue() method returns false.
Types of Hadoop RecordReader

InputFormat defines the RecordReader instance, in Hadoop. By default, by using TextInputFormat

ReordReader converts data into key-value pairs. TextInputFormat also provides 2 types of
RecordReaders which as follows:

A. LineRecordReader
It is the default RecordReader. TextInputFormat provides this RecordReader. It also treats each line of
the input file as the new value. Then the associated key is byte offset. It always skips the first line in
the split (or part of it), if it is not the first split. It always reads one line after the boundary of the split
in the end (if data is available, so it is not the last split).

B. SequenceFileRecordReader
This Hadoop RecorReader reads data specified by the header of a sequence file.
The maximum size of the single Record. By using below parameter we set maximum value.
[Link]("[Link]", Integer.MAX_VALUE);

5. Mapper
Mapper maps the input <key, value> pairs to a set of intermediate <key, value> pairs. It processes the
input records from the RecordReader and generates the new <key, value> pairs. The <key, value>
pairs generated by Mapper are different from the input <key, value> pairs.
The generated <key, value> pairs is the output of Mapper known as intermediate output. These
intermediate outputs of the Mappers are written to the local disk.
The Mappers output is not stored on the Hadoop Distributed File System because this is the
temporary data, and writing this data on HDFS will create unnecessary copies. The output of the
Mappers is then passed to the Combiner for further processing.
Mapper Class in MapReduce
Hadoop Mapper processes input record produced by the RecordReader and generates intermediate
key-value pairs. The intermediate output is completely different from the input pair.
The output of the mapper is the full collection of key-value pairs. Before writing the output for each
mapper task, partitioning of output take place on the basis of the key. Thus partitioning itemizes that
all the values for each key are grouped together.
Hadoop MapReduce generates one map task for each InputSplit. Hadoop MapReduce only
understands key-value pairs of data. So, before sending data to the mapper, Hadoop framework
should covert data into the key-value pair.

How is key-value pair generated in Hadoop?

InputSplit – It is the logical representation of data generated by the InputFormat. In MapReduce
program, it describes a unit of work that contains a single map task.
RecordReader- It communicates with the inputSplit. And then converts the data into key-value pairs
suitable for reading by the Mapper. RecordReader by default uses TextInputFormat to convert data
into the key-value pair.

InputSplit converts the physical representation of the blocks into logical for the Mapper. For example,
to read the 100MB file, it will require 2 InputSplit. For each block, the framework creates one
InputSplit. Each InputSplit create one mapper.
MapReduce InputSplit not always depends on the number of data blocks. We can change the number
of a split by setting [Link] property during job execution.
MapReduce RecordReader is responsible for reading/converting data into key-value pairs till the end
of the file. RecordReader assigns Byte offset to each line present in the file.
Then Mapper receives this key pair. Mapper produces the intermediate output (key-value pairs which
are understandable to reduce).

How many Map task in Hadoop?

The number of map tasks depends on the total number of blocks of the input files. In MapReduce map,
the right level of parallelism seems to be around 10-100 maps/node. But there is 300 map for CPU-
light map tasks.
For example, we have a block size of 128 MB. And we expect 10TB of input data. Thus it produces
82,000 maps. Hence the number of maps depends on InputFormat.
Mapper = (total data size)/ (input split size)
Example – data size is 1 TB. Input split size is 100 MB.
Mapper = (1000*1000)/100 = 10,000
6. Combiner
It is also known as the ‘Mini-reducer’. Combiner performs local aggregation on the output of the
Mappers. This helps in minimizing data transfer between the Mapper and the Reducer.
After the execution of the Combiner function, the output is passed to the Partitioner for further
processing.

The primary job of Combiner a “Mini-Reducer is to process the output data from the Mapper, before
passing it to Reducer. It runs after the mapper and before the Reducer. Its usage is optional.
How does Combiner work in Hadoop?

Now let us learn how things change when we use the combiner in MapReduce?

MapReduce program without Combiner

As we see in above diagram no combiner is there. Input is split into two mappers. The framework
generates 9 keys from the mappers.

So, now we have (9 key/value) intermediate data. Further mapper sends this key-value directly to the
reducer. While sending data to the reducer, it consumes some network bandwidth. It takes more time
to transfer data to reducer if the size of data is big.

MapReduce Program with Combiner

Now from the above diagram, if we use a combiner in between mapper and reducer. Then combiner
will shuffle 9 key/value before sending it to the reducer. And then generates 4 key/value pair as an
output.

Now, Reducer needs to process only 4 key/value pair data which are generated from 2 combiners.
Therefore reducer gets executed only 4 times to produce the final output. Thus, this increases the
overall performance.
Advantages of Combiner in MapReduce

 Use of combiner reduces the time taken for data transfer between mapper and reducer.
 Combiner improves the overall performance of the reducer.
 It decreases the amount of data that reducer has to process.
Disadvantages of Combiner in MapReduce

There are also some disadvantages of Hadoop Combiner.

 In the local filesystem, when Hadoop stores the key-value pairs and run the combiner later
this will cause expensive disk IO.
 MapReduce jobs can’t depend on the combiner execution as there is no guarantee in its
execution.

7. Partitioner
When we are working on the MapReduce program with more than one Reducer then only the
Partitioner comes into the picture. For only one reducer, we do not use Partitioner.
It partitions the keyspace. It controls the partitioning of keys of the Mapper intermediate outputs.
Partitioner takes the output from the Combiner and performs partitioning. Key is for deriving the
partition typically through the hash function. The number of partitions is similar to the number of
reduce tasks. HashPartitioner is the default Partitioner.

On the basis of key value, framework partitions, each mapper output. Records as having the same key
value go into the same partition (within each mapper). Then each partition is sent to a reducer.
Partition class decides which partition a given (key, value) pair will go. Partition phase in MapReduce
data flow takes place after map phase and before reduce phase.

Need of MapReduce Partitioner in Hadoop

In MapReduce job execution, it takes an input data set and produces the list of key value pair. These
key-value pair is the result of map phase. In which input data are split and each task processes the
split and each map, output the list of key value pairs.
Then, framework sends the map output to reduce task. Reduce processes the user-defined reduce
function on map outputs. Before reduce phase, partitioning of the map output take place on the basis
of the key.
Hadoop Partitioning specifies that all the values for each key are grouped together. It also makes sure
that all the values of a single key go to the same reducer. This allows even distribution of the map
output over the reducer.
Partitioner in a MapReduce job redirects the mapper output to the reducer by determining which
reducer handles the particular key.

Hadoop Default Partitioner

Hash Partitioner is the default Partitioner. It computes a hash value for the key. It also assigns the
partition based on this result.
How many Partitioner in Hadoop?
The total number of Partitioner depends on the number of reducers. Hadoop Partitioner divides the
data according to the number of reducers. It is set by [Link]() method.
Thus the single reducer processes the data from single partitioner. The important thing to notice is
that the framework creates partitioner only when there are many reducers.

Poor Partitioning in Hadoop MapReduce

If in data input in MapReduce job one key appears more than any other key. In such case, to send data
to the partition we use two mechanisms which are as follows:
The key appearing more number of times will be sent to one partition.
All the other key will be sent to partitions on the basis of their hashCode().
If hashCode() method does not distribute other key data over the partition range. Then data will not
be sent to the reducers.
Poor partitioning of data means that some reducers will have more data input as compared to other.
They will have more work to do than other reducers. Thus the entire job has to wait for one reducer
to finish its extra-large share of the load.
How to overcome poor partitioning in MapReduce?
To overcome poor partitioner in Hadoop MapReduce, we can create Custom partitioner. This allows
sharing workload across different reducers.

8. Shuffling and Sorting

The input to the Reducer is always the sorted intermediate output of the mappers. After combining
and partitioning, the framework via HTTP fetches all the relevant partitions of the output of all the
mappers.
Once the output of all the mappers is shuffled, the framework groups the Reducer inputs on the basis
of the keys. This is then provided as an input to the Reducer.

Shuffling is the process by which it transfers mappers intermediate output to the reducer. Reducer
gets 1 or more keys and associated values on the basis of reducers.

The intermediated key – value generated by mapper is sorted automatically by key. In Sort phase
merging and sorting of map output takes place.

Shuffling and Sorting in Hadoop occurs simultaneously.

Shuffling in MapReduce

The process of transferring data from the mappers to reducers is shuffling. It is also the process by
which the system performs the sort. Then it transfers the map output to the reducer as input. This is
the reason shuffle phase is necessary for the reducers.

Otherwise, they would not have any input (or input from every mapper). Since shuffling can start even
before the map phase has finished. So this saves some time and completes the tasks in lesser time.

Sorting in MapReduce

MapReduce Framework automatically sort the keys generated by the mapper. Thus, before starting of
reducer, all intermediate key-value pairs get sorted by key and not by value. It does not sort values
passed to each reducer. They can be in any order.

Sorting in a MapReduce job helps reducer to easily distinguish when a new reduce task should start.

This saves time for the reducer. Reducer in MapReduce starts a new reduce task when the next key in
the sorted input data is different than the previous. Each reduce task takes key value pairs as input
and generates key-value pair as output.

The important thing to note is that shuffling and sorting in Hadoop MapReduce are will not take place
at all if you specify zero reducers (setNumReduceTasks(0)).

If reducer is zero, then the MapReduce job stops at the map phase. And the map phase does not
include any kind of sorting (even the map phase is faster).

Secondary Sorting in MapReduce

If we want to sort reducer values, then we use a secondary sorting technique. This technique enables
us to sort the values (in ascending or descending order) passed to each reducer.

9. Reducer
Reducer then reduces the set of intermediate values who shares a key to the smaller set of values.
The output of reducer is the final output. This output is stored in the Hadoop Distributed File System.
Reducer in Hadoop MapReduce reduces a set of intermediate values which share a key to a smaller
set of values.
In MapReduce job execution flow, Reducer takes a set of an intermediate key-value pair produced by
the mapper as the input. Then, Reducer aggregate, filter and combine key-value pairs and this
requires a wide range of processing.
One-one mapping takes place between keys and reducers in MapReduce job execution. They run in
parallel since they are independent of one another. The user decides the number of reducers in
MapReduce.
Phases of Hadoop Reducer
Three phases of Reducer are as follows:
1. Shuffle Phase
This is the phase in which sorted output from the mapper is the input to the reducer. The framework
with the help of HTTP fetches the relevant partition of the output of all the mappers in this [Link]
phase
2. Sort Phase
This is the phase in which the input from different mappers is again sorted based on the similar keys in
different Mappers.
Both Shuffle and Sort occur concurrently.
3. Reduce Phase
This phase occurs after shuffle and sort. Reduce task aggregates the key-value pairs. With the
[Link]() property, the output of the reduce task is written to the FileSystem. Reducer
output is not sorted.

Number of Reducers in Hadoop MapReduce

User set the number of reducers with the help of [Link](int) property. Thus the right
number of reducers by the formula:
0.95 or 1.75 multiplied by (<no. of nodes> * <no. of the maximum container per node>)
So, with 0.95, all reducers immediately launch. Then, start transferring map outputs as the maps finish.
Faster node finishes the first round of reducers with 1.75. Then it launches the second wave of
reducer which does much better job of load balancing.
With the increase of the number of reducers:
 Framework overhead increases.
 Load balancing increases.
 Cost of failures decreases.

10. RecordWriter
RecordWriter writes the output (key, value pairs) of Reducer to an output file. It writes the
MapReduce job outputs to the FileSystem.

11. OutputFormat
The OutputFormat specifies the way in which these output key-value pairs are written to the output
files. It validates the output specification for a MapReduce job.
OutputFormat basically provides the RecordWriter implementation used for writing the output files of
the MapReduce job. The output files are stored in a FileSystem.

.
OutputFormat check the output specification for execution of the Map-Reduce job. It describes how
RecordWriter implementation is used to write output to output files.

Before we start with OutputFormat, let us first learn what is RecordWriter and what is the work of
RecordWriter in MapReduce?

1. RecordWriter in Hadoop MapReduce

As we know, Reducer takes Mappers intermediate output as input. Then it runs a reducer function on
them to generate output that is again zero or more key-value pairs.

So, RecordWriter in MapReduce job execution writes these output key-value pairs from the Reducer
phase to output files.

2. Hadoop OutputFormat

From above it is clear that RecordWriter takes output data from Reducer. Then it writes this data to
output files. OutputFormat determines the way these output key-value pairs are written in output
files by RecordWriter.

The OutputFormat and InputFormat functions are similar. OutputFormat instances are used to write
to files on the local disk or in HDFS. In MapReduce job execution on the basis of output specification;

 Hadoop MapReduce job checks that the output directory does not already present.
 OutputFormat in MapReduce job provides the RecordWriter implementation to be used to
write the output files of the job. Then the output files are stored in a FileSystem.

The framework uses [Link]() method to set the output directory.

Types of OutputFormat in MapReduce

There are various types of OutputFormat which are as follows:

A. TextOutputFormat

The default OutputFormat is TextOutputFormat. It writes (key, value) pairs on individual lines of text
files. Its keys and values can be of any type. The reason behind is that TextOutputFormat turns them
to string by calling toString() on them.
It separates key-value pair by a tab character. By using
[Link] property we can also change it.

KeyValueTextOutputFormat is also used for reading these output text files.

B. SequenceFileOutputFormat

This OutputFormat writes sequences files for its output. SequenceFileInputFormat is also intermediate
format use between MapReduce jobs. It serializes arbitrary data types to the file.

And the corresponding SequenceFileInputFormat will deserialize the file into the same types. It
presents the data to the next mapper in the same manner as it was emitted by the previous reducer.
Static methods also control the compression.

C. SequenceFileAsBinaryOutputFormat

It is another variant of SequenceFileInputFormat. It also writes keys and values to sequence file in
binary format.

D. MapFileOutputFormat

It is another form of FileOutputFormat. It also writes output as map files. The framework adds a key in
a MapFile in order. So we need to ensure that reducer emits keys in sorted order.

E. MultipleOutputs

This format allows writing data to files whose names are derived from the output keys and values.

F. LazyOutputFormat

In MapReduce job execution, FileOutputFormat sometimes create output files, even if they are empty.
LazyOutputFormat is also a wrapper OutputFormat.

G. DBOutputFormat

It is the OutputFormat for writing to relational databases and HBase. This format also sends the
reduce output to a SQL table. It also accepts key-value pairs. In this, the key has a type extending
DBwritable

The Practical Example: Word Count

The most common practical example is a word count job, which
counts the frequency of every word in a large collection of text
documents.
Input Data (across several files):
 T[0] = "it is what it is"
 T[1] = "what is it"
 T[2] = "it is a banana"


How MapReduce Works
1. Input Splitting & Record Reading: The large input data is divided into smaller, fixed-size pieces
called "splits" (e.g., each line or a block of lines is a record). Each split is processed by a
separate Map task.
2. Map Phase: A user-defined Map function processes each input record (key-value pair, e.g.,
<byte\_offset, line\_content>) and generates intermediate key-value pairs.

o Action: Each mapper tokenizes its assigned text and outputs each word with a count of
one, as <word, 1>.
o Example Output (from T[0]): <"it", 1>, <"is", 1>, <"what", 1>, <"it", 1>, <"is", 1>

3. Shuffle and Sort Phase: The framework automatically groups all intermediate values with the
same key together. This data is sorted and distributed to the appropriate Reducer task.

o Action: All <"it", 1> pairs are sent to the same reducer, all <"is", 1> pairs to another,
and so on.
o Example Input to Reducers:

 "a": [1]
 "banana": [1]
 "is": [1, 1, 1]
 "it": [1, 1, 1]
 "what": [1, 1]

4. Reduce Phase: A user-defined Reduce function aggregates the values for each unique key to
produce the final output.

o Action: Each reducer sums up the list of 1s for its key.

o Example Output:

 "a": 1
 "banana": 1
 "is": 3
 "it": 3
 "what": 2

5. Final Output: The final key-value pairs are collected and written to an output file in the
distributed file system (e.g., HDFS).

Real-World Applications
Beyond word counting, MapReduce is used in various large-scale
applications:
 Search Engine Indexing: Crawling web pages and organizing keywords and metadata into an
efficient, searchable index.
 Log Analysis: Analyzing server logs to identify popular pages, peak traffic times, or system
errors.
 Recommendation Systems: Processing user behavior (views, clicks, purchases) to suggest
products or media (e.g., Netflix, Amazon).
 Fraud Detection: Analyzing millions of financial transactions to flag unusual spending patterns
or suspicious activity.
 Genomic Data Analysis: Processing vast amounts of genetic sequence data to uncover
variations or mutations.