Welcome to AIKTC

Module 2|

Prof. Nusrat Jahan,

Department of Computer Engineering.
AIKTC – Anjuman-I-Islam’s Kalsekar Technical Campus.
 Module 2

A.I. Kalsekar Technical Campus, New Panvel

 Module 2: Hadoop HDFS and MapReduce
• Distributed File Systems: Physical Organization of Compute Nodes, Large-
scale File-System Organization.
• MapReduce: The Map Tasks, Grouping by Key, The Reduce Tasks,
Combiners, Details of MapReduce Execution, Coping With Node Failures.
• Algorithms Using MapReduce: Matrix-Vector Multiplication by
MapReduce, Relational-Algebra Operations, Computing Selections by
MapReduce, Computing Projections by MapReduce, Union ,Intersection, and
Difference by MapReduce
• Hadoop Limitations

A.I. Kalsekar Technical Campus, New Panvel

Large Scale File System Organization

A.I. Kalsekar Technical Campus, New Panvel

Hadoop Distributed File System

A.I. Kalsekar Technical Campus, New Panvel

HDFS contd…
• HDFS is the primary storage system used by Hadoop applications.
• It is based on Google File system(GFS)
• It Provides high-performance access to data across Hadoop clusters.
• Key tool for managing pools of big data and supporting big data analytics applications.
• HDFS uses Master/slave architecture.
• It has two main components: Name Node and Data Node.
• Name Node manages the metadata of file system.
• Data Node store actual data .
• The file content is split into large blocks and each block of file is independently replicated at
multiple Data Nodes.
• Name Node maps the blocks to Data Node.

A.I. Kalsekar Technical Campus, New Panvel

Features Of HDFS
• Cost Effective
• Large datasets/ variety and volume of data
• Replication
• Fault tolerance and reliability
• High availability of data.
• Scalability
• High throughput (processing time decreases thus throughput is high)
• Data locality: Data locality is the process of moving the computation close to where
the actual data resides on the node, instead of moving large data to computation.
This minimizes network congestion and increases the overall throughput of the
system.

A.I. Kalsekar Technical Campus, New Panvel

Physical organization of Compute Node
• The new parallel-computing architecture, sometimes called cluster computing, is
organized as follows.
• Compute nodes are stored on racks, perhaps 8–64 on a rack.
• The nodes on a single rack are connected by a network, typically gigabit Ethernet.
There can be many racks of compute nodes, and racks are connected by another level
of network or a switch. The bandwidth of inter-rack communication is somewhat
greater than the intra-rack Ethernet, but given the number of pairs of nodes that
might need to communicate between racks However, there may be many more racks
and many more compute nodes per rack

A.I. Kalsekar Technical Campus, New Panvel

Physical organization of Compute Node
• Some important calculations take minutes or even hours on thousands of compute
nodes. If we had to abort and restart the computation every time one component
failed, then the computation might never complete successfully. The solution to
this problem takes two forms:
• Files must be stored redundantly.
• Computations must be divided into tasks, such that if any one task fails to execute
to completion, it can be restarted without affecting other tasks.

A.I. Kalsekar Technical Campus, New Panvel

 Introduction to Map-Reduce
• MapReduce is a processing layer in a Hadoop environment. MapReduce works on
tasks related to a job. The idea is to tackle one large request by slicing it into smaller
units.
• Map reduce performs the processing of large dataset in a distributed and parallel
manner.
• It consists of two distinct tasks-Map and reduce task.
• You can use an implementation of MapReduce to manage many large-scale
computations in a way that is tolerant of hardware faults.
• Two essential daemons of MapReduce: Job Tracker and Task Tracker

A.I. Kalsekar Technical Campus, New Panvel

JobTracker and TaskTracker

A.I. Kalsekar Technical Campus, New Panvel

JobTracker and TaskTracker
• A JobTracker controlled the distribution of application requests to the
compute resources in a cluster. Since it monitored the execution and the
status of MapReduce, it resided on a master node.

• A TaskTracker processed the requests that came from the JobTracker.

All task trackers were distributed across the slave nodes in a Hadoop
cluster.

A.I. Kalsekar Technical Campus, New Panvel

A.I. Kalsekar Technical Campus, New Panvel
A.I. Kalsekar Technical Campus, New Panvel
A.I. Kalsekar Technical Campus, New Panvel
A.I. Kalsekar Technical Campus, New Panvel
A.I. Kalsekar Technical Campus, New Panvel
 MapReduce Algorithms
• MapReduce is a Distributed Data Processing Algorithm introduced by Google.
• MapReduce Algorithm is mainly inspired by the Functional Programming model.
• It is useful to process huge amount of data in parallel, reliable and efficient way in
cluster environment.
• A MapReduce program mainly consists of map procedure and a reduce method to
perform the summary operation like counting or yielding some results.
• The MapReduce system works on distributed servers that run in parallel and
manage all communications between different systems.
• The model is a special strategy of split-apply-combine strategy which helps in
data analysis. Mapping is done by the Mapper class and reduce task is done by
Reducer class.

A.I. Kalsekar Technical Campus, New Panvel

Why Should We Use MapReduce Algorithm?

• MapReduce is an application that is used for the processing of huge datasets.

• These datasets can be processed in parallel. MapReduce can potentially
create large data sets and a large number of nodes.
• These large data sets are stored on HDFS which makes the analysis of data
easier.
• It can process any kind of data like structured, unstructured or semi-
structured.

A.I. Kalsekar Technical Campus, New Panvel

Working with MapReduce Algorithm
• To work with MapReduce Algorithm, you must know the complete process of how
it works.
• The data which is ingested goes through the following steps:

A.I. Kalsekar Technical Campus, New Panvel

 Working with MapReduce Algorithm
1. Input Splits: Any input data which comes to MapReduce job is divided into
equal pieces known as input splits. It is a chunk of input which can be consumed by
any of the mappers.
2. Mapping: Once the data is split into chunks it goes through the phase of
mapping in the map-reduce program. This split data is passed to mapping function
which produces different output values.
3. Shuffling: Once the mapping is done, the data is sent to this phase. Its job is to
amalgamate the required records from the previous phase.
4. Reducing: In this phase, the output from the shuffling phase is aggregated. In
this phase, all values are shuffled and brought together by aggregation so that it
returns a single output value. It creates a summary of the complete data set.

A.I. Kalsekar Technical Campus, New Panvel

Working of MapReduce Algorithm
• MapReduce Algorithm mainly works in three phases:
• Map phase
• Sort & Shuffle phase
• Reduce phase
• Let us discuss each function and its responsibilities.

A.I. Kalsekar Technical Campus, New Panvel

Map-Reduce

A.I. Kalsekar Technical Campus, New Panvel

The overall MapReduce Word Count process Example

A.I. Kalsekar Technical Campus, New Panvel

Combiners

• Usually, the output of the map task is large and the data
transferred to the reduce task is high. So to reduce the volume of data
transfer between Map and Reduce we use the Combiner class in between the
Map class and the Reduce class.
• It runs after the mapper and before the Reducer and its use is optional.
• Many repeated keys are produced by maps. It is often useful to do
a local aggregation process done by specifying combiner.
• The goal of the combiner is to decrease the size of the data. It has the same
interface as reducer and often are the same class.

A.I. Kalsekar Technical Campus, New Panvel

MapReduce – Combiners
• Combiner always works in between Mapper and Reducer.
• The output produced by the Mapper is the intermediate output in terms of key-value
pairs which is massive in size.
• If we directly feed this huge output to the Reducer, then that will result in increasing
the Network Congestion.
• So to minimize this Network congestion we have to put combiner in between Mapper
and Reducer.
• These combiners are also known as semi-reducer.
• Combiner is also a class in java program like Map and Reduce class that is used in
between this Map and Reduce classes.
• Combiner helps us to produce abstract details or a summary of very large datasets.

A.I. Kalsekar Technical Campus, New Panvel

MapReduce
program
without
Combiner

A.I. Kalsekar Technical Campus, New Panvel

A.I. Kalsekar Technical Campus, New Panvel
How does combiner work?

A.I. Kalsekar Technical Campus, New Panvel

 Coping with Node Failure
• The worst thing that can happen is that the compute node at which the Master
is executing fails.
• In this case, the entire map-reduce job must be restarted.
• But only this one node can bring the entire process down; other failures will
be managed by the Master, and the map-reduce job will complete eventually.

A.I. Kalsekar Technical Campus, New Panvel

Matrix-Vector Multiplication by MapReduce
• MapReduce is a technique in which a huge program is subdivided into small
tasks and run parallelly to make computation faster, save time, and mostly used
in distributed systems. It has 2 important parts:
• Mapper: It takes raw data input and organizes into key, value pairs.
• Reducer: It is responsible for processing data in parallel and produce final
output.

A.I. Kalsekar Technical Campus, New Panvel

The Map Function

A.I. Kalsekar Technical Campus, New Panvel

The Reduce Function

A.I. Kalsekar Technical Campus, New Panvel

Let us consider the matrix multiplication example
to visualize MapReduce. Consider the following
matrix:

2×2 matrices A and B

Now One step matrix multiplication has 1 mapper and 1 reducer. The
Formula is:

Mapper for Matrix A (k, v)=((i, k), (A, j, Aij)) for all k
Mapper for Matrix B (k, v)=((i, k), (B, j, Bjk)) for all i

A.I. Kalsekar Technical Campus, New Panvel

Therefore computing the mapper for Matrix
A:

A.I. Kalsekar Technical Campus, New Panvel

Computing the mapper for Matrix B

A.I. Kalsekar Technical Campus, New Panvel

 The formula for Reducer is:
• Reducer(k, v)=(i, k)=>Make sorted Alist and Blist
(i, k) => Summation (Aij * Bjk)) for j
Output =>((i, k), sum)

A.I. Kalsekar Technical Campus, New Panvel

The output is

Final output of Matrix multiplication

A.I. Kalsekar Technical Campus, New Panvel
 Relational-Algebra Operations
• Relational algebra operations work on one or more relations to define another relation
without changing the original relations.
• Both operands and results are relations, so output from one operation can become input
to another operation.
• Allows expressions to be nested, just as in arithmetic. This property is called closure.
• Five basic operations in relational algebra: Selection, Projection, Union, Intersection
and Set Difference.
• These perform most of the data retrieval operations needed.

A.I. Kalsekar Technical Campus, New Panvel

 Selection Operation
• selection(WHERE clause in SQL) lets you apply a condition over the data you
have and only get the rows that satisfy the condition.

Selection operation to select only rows where age is greater than 20

A.I. Kalsekar Technical Campus, New Panvel

Projection Operation
• In order to select some columns only we use the projection operator. It’s analogous
to SELECT in SQL.

Projection operation to select only Name, Is Active column

A.I. Kalsekar Technical Campus, New Panvel

 Union Operation
• We concatenate two tables vertically. Similar to UNION in SQL, but the duplicate rows are removed
implicitly. The point to note in the below output table is that (Smith, 16)was a duplicate row so it appears
only once in the output where as (Tom, 17) , (Tom, 19) appears as two, as those are not identical rows.

Union the two tables

A.I. Kalsekar Technical Campus, New Panvel
 Intersection Operation
• Same as INTERSECT in SQL. It intersects two tables and selects
only the common rows.

Intersection of two tables

A.I. Kalsekar Technical Campus, New Panvel

Difference Operation
• The rows that are in the first table but not in second are selected for output. Keep in
mind that (Monty, 21) is not considered in the output as its present in the second table
but not in first.

Difference between the two tables

A.I. Kalsekar Technical Campus, New Panvel

Data Representation For a Table
• In a distributed storage system the entire table isn’t stored on a single
node(computer), the most relevant reason being it doesn’t fit completely on a single
system because of its large size.

• So in order to store a table the table is partitioned into small files which are
distributed across the nodes available in the system.

• Let’s have a simple abstraction on how data is stored in the system. Think of tables as
being stored as small CSV files which if concatenated will represent the table.

A.I. Kalsekar Technical Campus, New Panvel

Actual storage of a table on distributed
file system

Actual storage of a table on distributed file system

A.I. Kalsekar Technical Campus, New Panvel

Relational-Algebra Operations using MapReduce

Selection Projection

Union Intersection

Difference Natural Join

A.I. Kalsekar Technical Campus, New Panvel

Selection Using Map Reduce
• To perform selections using map reduce we need the following Map and Reduce
functions:

• Map Function: For each row r in the table apply condition and produce a key value
pair r, r if condition is satisfied else produce nothing. i.e. key and value are the same.

• Reduce Function: The reduce function has nothing to do in this case. It will simply
write the value for each key it receives to the output.

For our example we will do Selection(B <= 3). Select all the rows where value of B is less
than or equal to 3.

A.I. Kalsekar Technical Campus, New Panvel

Let’s consider the data we have initially
distributed as files in Map Workers, And
the data looks like the following figure

Initial data distributed in files across map workers representing a single table

A.I. Kalsekar Technical Campus, New Panvel

• After applying the map function (And grouping, there are no common keys in
this case as each row is unique) we will get the output as follows, The tuples are
constructed with 0th index containing values from A column and 1st index
containing values from B. In actual implementations either this information can
be sent as some extra metadata or within each value itself, making values and
keys look something like ({A: 1}, {B: 2}), which does look somewhat
inefficient.

Data after applying Map function which filtered

A.I. Kalsekar rows having
Technical Campus,B value
Newless than 3
Panvel
After this based on number or reduce workers (2 in our case). A hash function is
applied. The files for reduce workers on map workers will look like:

Files for reduce workers created at map worker based on hash function

A.I. Kalsekar Technical Campus, New Panvel

After this step The files for reduce worker 1 are sent to that and reduce worker 2 are
sent to that. The data at reduce workers will look like:

Data at reduce workers sent from map workers

A.I. Kalsekar Technical Campus, New Panvel

The final output after applying the reduce function which ignores the keys and just
consider values will look like:

The points to take into consideration here are

that we don’t need to shuffle data across
the nodes really. We can just execute the
map function and save values to the output
from map workers itself. This makes it an
efficient operation (When compared to
others where reduce function does
something).

Output of selection(B ≤ 3)

A.I. Kalsekar Technical Campus, New Panvel

Projection Using Map Reduce

• Map Function: For each row r in the table produce a key value pair r', r’,
where r' only contains the columns which are wanted in the projection.
• Reduce Function: The reduce function will get outputs in the form of r'
:[r', r', r', r', ...]. As after removing some columns the output may contain
duplicate rows. So it will just take the value at 0th index, getting rid of
duplicates.

A.I. Kalsekar Technical Campus, New Panvel

Let’s see it in action, by computing projection(A, B) for the following table:

Initial Data distributed on map workers

A.I. Kalsekar Technical Campus, New Panvel

After application of map function (ignoring values in C column) and grouping the
keys the data will look like:

A.I. Kalsekar Technical Campus, New Panvel

The keys will be partitioned using a hash function
as was the case in selection. The data will look
like:

Files generated for reduce workers

A.I. Kalsekar Technical Campus, New Panvel

The data at the reduce workers will be:

Data at reduce workers

A.I. Kalsekar Technical Campus, New Panvel

At the reduce node the keys will be aggregated again as same keys might have
occurred at multiple map workers. As we already know the reduce function operates
on values of each key only once.

Data after aggregation by key at reduce workers

A.I. Kalsekar Technical Campus, New Panvel

The reduce function is applied which will consider only the first value of the values
list and ignore rest of the information.

The points to remember are that

here the reduce function is required
for duplicate elimination. If that’s
not the case (as it is in SQL) We can
get rid of reduce operation,
meaning we don’t have to move
data around. So, this operation can
be implemented without actually
passing data around.

Output of projection(A, B)

A.I. Kalsekar Technical Campus, New Panvel

Union Using Map Reduce
• Both selection and projection are operations that are applied on a single
table, whereas Union, intersection and difference are among the operations
that are applied on two or more tables.
• Let’s consider that schemas of the two tables are the same, and columns are
also ordered in same order.
• Map Function: For each row r generate key-value pair (r, r) .
• Reduce Function: With each key there can be one or two values (As we
don’t have duplicate rows), in either case just output first value.
• This operations has the map function of the selection and reduce function
of projection.

A.I. Kalsekar Technical Campus, New Panvel

Let’s see the working using an example. Here yellow color represents one table and
green color is used to represent the other one stored at two map workers.

Initial data at map workers

A.I. Kalsekar Technical Campus, New Panvel

After applying the map function and grouping the keys we will get output as:

Map and grouping the keys

A.I. Kalsekar Technical Campus, New Panvel

The data to be sent to reduce workers will look like:

Files to be sent to reduce workers

A.I. Kalsekar Technical Campus, New Panvel

Data at reduce workers after will be:

Files At reduce workers

A.I. Kalsekar Technical Campus, New Panvel

At reduce workers aggregation on keys will
be done.

Aggregated data at reduce workers

A.I. Kalsekar Technical Campus, New Panvel

The final output after applying the reduce function which takes only the first value
and ignores everything else is as follows:

Here we note that in this

case same as projection we
can do this without moving
data around in case we are
not interested in removing
duplicates. And hence this
operation is also efficient it
terms of data shuffle across
Final table after union machines.

A.I. Kalsekar Technical Campus, New Panvel

Intersection Using Map Reduce
For intersection, let’s consider the same data we considered for
union and just change the map and reduce functions
Map Function: For each row r generate key-value pair (r, r) (Same
as union).
Reduce Function: With each key there can be one or two values (As
we don’t have duplicate rows), in case we have length of list as 2 we
output first value else we output nothing.
As the map function is same as union and we are considering the
same data lets skip to the part before reduce function is applied.

A.I. Kalsekar Technical Campus, New Panvel

As the map function is same as union and we are considering the same
data lets skip to the part before reduce function is applied .

Data at reduce workers

A.I. Kalsekar Technical Campus, New Panvel

Now we just apply the reduce operation which
will output only rows if list has a length of 2.

Output of intersection

A.I. Kalsekar Technical Campus, New Panvel

Difference Using Map Reduce

• Let’s again consider the same data. The difficulty with difference arises with the fact that we want
to output a row only if it exists in the first table but not the second one. So the reduce function
needs to keep track on which tuple belongs to which relation. To visualize that easier we will
keep those rows green which come from 2nd table and yellow for which come from 1st table
and purple which comes from both tables.

• Map Function: For each row r create a key-value pair (r, T1) if row is from table 1 else product
key-value pair (r, T2).
• Reduce Function: Output the row if and only if the value in the list is T1 , otherwise output
nothing.

A.I. Kalsekar Technical Campus, New Panvel

The data taken initially is the same as it was
for union

Initial Data

A.I. Kalsekar Technical Campus, New Panvel

After applying the map function and grouping the
keys the data looks like the following figure

Data after applying map function and grouping keys

A.I. Kalsekar Technical Campus, New Panvel

After applying map function files for reduce workers will be created
based on hashing keys as has been the case so far.

Files for reduce workers

A.I. Kalsekar Technical Campus, New Panvel

The data at the reduce workers will look like

Files at reduce workers

A.I. Kalsekar Technical Campus, New Panvel

After aggregation of the keys at reduce workers
the data looks like:

Data after aggregation of keys at reduce workers

A.I. Kalsekar Technical Campus, New Panvel
The final output is generated after applying the
reduce function over the output.

For the difference operation we

notice that we cannot get rid of the
reduce part and hence have to send
data across the workers as the
context of from which table the
value came is needed. Hence it will
be more expensive operation as
compared to selection, projection,
union and intersection.

Output of difference of the tables

A.I. Kalsekar Technical Campus, New Panvel

Hadoop Limitations
• Not fit for small files.
• Slow speed: Hadoop works with massive amounts of distributed
data which slows down the processing.
• Not easy to use.
• Lengthy Line of Code
• Latency:MapReduce requires a lot of time to perform these tasks
thereby increasing latency.

A.I. Kalsekar Technical Campus, New Panvel

Important Questions
1. Describe the structure of HDFS in a Hadoop ecosystem using diagram.
2. What is MapReduce? Explain the role of a Combiner in map-reduce Framework?
3. Use of Sqoop in Hadoop?
4. Illustrate map reduce pseudo code to multiply two matrices. Examine with an example showing
all steps.
5. Articulate shuffle & short phase and Reducer phase in MapReduce.
6. What is MapReduce? Explain how MapReduce work.
7. Write algorithm for the following relational operations using MapReduce. Also explain the steps
with example.
1) Selection 2)Projection 3) Union 4)Intersection 5) Difference

A.I. Kalsekar Technical Campus, New Panvel

1. Describe the structure of HDFS in a Hadoop ecosystem using diagram.
2. What is MapReduce? Explain the role of a Combiner in map-reduce
Framework?
3. Use of Sqoop in Hadoop?
4. Illustrate map reduce pseudo code to multiply two matrices. Examine
with an example showing all steps.
5. Articulate shuffle & short phase and Reducer phase in MapReduce.
6. What is MapReduce? Explain how MapReduce work.
7. Write algorithm for the following relational operations using
MapReduce. Also explain the steps with example.
1) Selection 2)Projection 3) Union 4)Intersection 5) Difference

A.I. Kalsekar Technical Campus, New Panvel

A.I. Kalsekar Technical Campus, New Panvel