Understanding Map-Reduce Framework
Uploaded by
madhuri.bitcseUnderstanding Map-Reduce Framework
Uploaded by
madhuri.bitcse1
Map-Reduce
• Design pattern to take advantage of clustered machines
to do processing in parallel
• While keeping as much work and data as possible local to a single
machine
• Widely used open source implementation and is the part
of Hadoop project.
• Map function- Reads the records from the database
and emits key-value pairs.
• Reduce function- Takes several key-value pairs with the
same key and aggregates them with one.
2
Map-Reduce Example
• Let’s assume we have chosen orders as our aggregate, with each
order having line items.
• Each line item has a product ID, quantity, and the price charged. This
aggregate makes a lot of sense as usually people want to see the
whole order in one access.
• Sales analysis people want to see a product and its total revenue for
the last seven days. This report doesn’t fit the aggregate structure
• Such situation that calls for map-reduce.
• A map is a function whose input is a single aggregate and whose
output is a bunch of key value pairs.
• Reduce function takes multiple map outputs with the same key and
combines their values. It would reduce down to one, with the totals for
the quantity and revenue.
3
Map function
• Each instance of the map function is independent of all the others.
Takes a single aggregate record as input
• Hence a map-reduce framework can create efficient map tasks on
each node and freely allocate each order to a map task.
• A map function might yield 1000 line items from orders for “Database
Refactoring”
• While the map function is limited to working only on data from a single
aggregate
• Outputs a set of relevant key-value pairs
4
Map function
• Each application of the map function is independent of all
the others.
• Takes a single aggregate record as input
• Outputs a set of relevant key-value pairs
• Each instance of the map function is independent from all
others
5
Reduce function
• Takes multiple map outputs with the same key as input
• Summarizes (or reduces) there values to a single output,
uses all values emitted for a single key
6
Map-reduce framework
• The map-reduce framework arranges for map tasks to be
run on the correct nodes to process all the documents and
for data to be moved to the reduce function
• Arranges for map function to be applied to pertinent
documents on all nodes.
• Moves data to the location of the reduce function.
• Collects all values for a single pair and calls the reduce
function on the key and value collection.
• To run map-reduce job, programmers only need to supply
the map and reduce functions.
7
Partitioning and Combining
• The results of the mapper are divided up based the key
on each processing node.
• Results of mappers are divided based on the key of each
processing node
• Multiple keys are grouped together into partitions. The
framework then takes the data from all the nodes for one
partition, combines it into a single group for that partition,
and sends it off to a reducer.
• Partition framework takes the data from all nodes for that
partition, combines it into a single group for that partition
and sends it off to reducer.
8
Partitioning
9
Partitioning and Combining
• Reducer function operates on the results of single key.
Hence multiple reducers can be run in parallel.
• Multiple reducers can then operate on partitions in
parallel, with final results merged together.
• Combiner function cuts down repetitive data by combining
all the data for same key into single value.
• The reduce function needs a special shape for this to
work: Its output must match its input. We call such a
function a combinable reducer.
10
Combining
11
• Not all reduce functions are combinable.
• Consider a function that counts the number of unique customers for a
particular product. The map function for such an operation would need to
emit the product and the customer.
• The reducer can then combine them and count how many times each
customer appears for a particular product, emitting the product and the
count.
• But this reducer’s output is different from its input, so it can’t be used as a
combiner.
12
Composing Map-Reduce
Calculations
13
When making a count, each map emits 1, which can be summed
to get a total.
14
Calculation broken down into two map-reduce steps, which will be
expanded in the
next three figures
15
Creating records for monthly sales of a product
16
The second stage mapper creates base records for
year-on-year comparisons
17