Introduction to
MapReduce
Acknowledgement
Most of the slides are from Dr. Bing
Chen,
[Link]
Some slides are from SHADI
IBRAHIM,
[Link]
What is MapReduce
Origin from Google, [OSDI04]
A simple programming model
Functional model
For large-scale data processing
Exploits large set of commodity
computers
Executes process in distributed manner
Offers high availability
Motivation
Lots of demands for very large scale
data processing
A certain common themes for these
demands
Lots of machines needed (scaling)
Two basic operations on the input
Map
Reduce
Distributed Grep
matches
Split data
grep
grep
grep
Split data
grep
matches
Split data
Very
big
data
Split data
matches
matches
cat
All
matches
Distributed Word Count
count
Split data
count
count
count
Split data
count
count
Split data
Very
big
data
Split data
count
count
merge
merged
count
Map+Reduce
Very
big
data
M
A
P
Map:
Accepts input
key/value pair
Emits intermediate
key/value pair
Partitioning
Function
R
E
D
U
C
E
Reduce :
Accepts
intermediate
key/value* pair
Emits output
key/value pair
Result
The design and how it works
Architecture overview
Master node
user
Job tracker
Slave node N
Slave node 1
Slave node 2
Task tracker
Task tracker
Task tracker
Workers
Workers
Workers
GFS: underlying storage
system
Goal
global view
make huge files available in the face of node
failures
Master Node (meta server)
Centralized, index all chunks on data servers
Chunk server (data server)
File is split into contiguous chunks, typically 1664MB.
Each chunk replicated (usually 2x or 3x).
Try to keep replicas in different racks.
GFS architecture
GFS Master
Client
C0
C1
C5
C2
C1
C5
C3
Chunkserver 1Chunkserver 2
C0
C5
C2
Chunkserver N
Functions in the Model
Map
Process a key/value pair to generate
intermediate key/value pairs
Reduce
Merge all intermediate values
associated with the same key
Partition
By default : hash(key) mod R
Well balanced
Diagram (1)
Diagram (2)
A Simple Example
Counting words in a large set of documents
map(stringvalue)
//key:documentname
//value:documentcontents
foreachwordwinvalue
EmitIntermediate(w,1);
reduce(stringkey,iteratorvalues)
//key:word
//values:listofcounts
intresults=0;
foreachvinvalues
result+=ParseInt(v);
Emit(AsString(result));
How does it work?
Locality issue
Master scheduling policy
Asks GFS for locations of replicas of input file
blocks
Map tasks typically split into 64MB (== GFS
block size)
Map tasks scheduled so GFS input block replica
are on same machine or same rack
Effect
Thousands of machines read input at local disk
speed
Without this, rack switches limit read rate
Fault Tolerance
Reactive way
Worker failure
Heartbeat, Workers are periodically pinged by master
NO response = failed worker
If the processor of a worker fails, the tasks of that
worker are reassigned to another worker.
Master failure
Master writes periodic checkpoints
Another master can be started from the last
checkpointed state
If eventually the master dies, the job will be aborted
Fault Tolerance
Proactive way (Redundant
Execution)
The problem of stragglers (slow
workers)
Other jobs consuming resources on machine
Bad disks with soft errors transfer data very
slowly
Weird things: processor caches disabled (!!)
When computation almost done,
reschedule in-progress tasks
Whenever either the primary or the
Fault Tolerance
Input error: bad records
Map/Reduce functions sometimes fail for
particular inputs
Best solution is to debug & fix, but not always
possible
On segment fault
Send UDP packet to master from signal handler
Include sequence number of record being processed
Skip bad records
If master sees two failures for same record, next
worker is told to skip the record
Status monitor
Refinements
Task Granularity
Minimizes time for fault recovery
load balancing
Local execution for debugging/testing
Compression of intermediate data
Points need to be
emphasized
No reduce can begin until map is
complete
Master must communicate locations
of intermediate files
Tasks scheduled based on location of
data
If map worker fails any time before
reduce finishes, task must be
completely rerun
MapReduce library does most of the
Model is Widely Applicable
MapReduce Programs In Google Source Tree
Examples as follows
distributed grep
distributed sort
web link-graph reversal
term-vector / host
web access log stats
inverted index construction
document clustering
machine learning
statistical machine translation
...
...
...
How to use it
User to do list:
indicate:
Input/output files
M: number of map tasks
R: number of reduce tasks
W: number of machines
Write map and reduce functions
Submit the job
Detailed Example: Word
Count(1)
Map
Detailed Example: Word
Count(2)
Reduce
Detailed Example: Word
Count(3)
Main
Applications
String Match, such as Grep
Reverse index
Count URL access frequency
Lots of examples in data mining
MapReduce
Implementations
MapReduce
Cluster,
1, Google
2, Apache Hadoop
Multicore CPU,
Phoenix @ stanford
GPU,
Mars@HKUST
Hadoop
Open source
Java-based implementation of
MapReduce
Use HDFS as underlying file system
Hadoop
Google
Yahoo
MapReduce
Hadoop
GFS
HDFS
Bigtable
HBase
Chubby
(nothing yet but
planned)
Recent news about Hadoop
Apache Hadoop Wins Terabyte
Sort Benchmark
The sort used 1800 maps and 1800
reduces and allocated enough
memory to buffers to hold the
intermediate data in memory.
Phoenix
The best paper at HPCA07
MapReduce for multiprocessor systems
Shared-memory implementation of MapReduce
SMP, Multi-core
Features
Uses thread instead of cluster nodes for parallelism
Communicate through shared memory instead of
network messages
Dynamic scheduling, locality management, fault
recovery
Workflow
The Phoenix API
System-defined functions
User-defined functions
Mars: MapReduce on GPU
PACT08
GeForce 8800 GTX, PS3, Xbox360
Implementation of Mars
User applications.
MapReduce
CUDA
System calls
Operating System (Windows or Linux)
NVIDIA GPU (GeForce 8800
GTX)
CPU (Intel P4 four cores,
2.4GHz)
Implementation of Mars
Discussion
We have MPI and PVM,Why do we need MapReduce?
MPI, PVM
MapReduce
Objective
General distributed
programming model
Large-scale data
processing
Availability
Weaker, harder
better
Data
Locality
Usability
MPI-IO
GFS
Difficult to learn
easier
Conclusions
Provide a general-purpose model to
simplify large-scale computation
Allow users to focus on the problem
without worrying about details
References
Original paper
([Link]
[Link])
On wikipedia (
[Link]
ce
)
Hadoop MapReduce in Java (
[Link]
[Link]
[Link]
