Copy from MIT pdos
6.824 Lecture 5: Distributed Programming: MapReduce, Dryad, and DryadLINQ
Todo:
Handout with MapReduce word count app
Outline:
Why, designs, challenges
MapReduce (Google)
Dryad (Microsoft)
DryadLINQ
Lab 2
Since writing a distributed application has a number of additional
challenges over sequential programming, it would be nice if there ways
to simplify it. Today we see two designs for making writing parallel
applications easier on distributed computer systems: MapReduce and
Dryad.
This lecture is also a case study of:
Use of distributed computer systems
Distributed computing challenges: programming, fault tolerance,
consistency, concurrency, etc.
One usage of distributed computer systems is running large
computations. Typically the application is partitioned in
computations running in parallel that somes communicate.
Applications
Scientific applications
Large-data processing apps (indexing, search, ...)
Etc.
Designs:
Cluster computing
using PCs connected by a high-speed network
Grid computing
using a high-speed network of supercomputers
Volunteer/Personal computers
aggregates Pcs on the Internet
Challenges:
Parallelize application --- How to handle share state?
Network is a bottleneck typilally
Embarrasing parallel (run same app for different inputs, users, ..)
Coarse-grained (computation versus communication ratio is low)
Fine-grained (typically require parallel computer)
How to write the application?
Explicit messages (RPC, MPI)
Shared memory
Balance computations of an application across computers
Statically (e.g., doable when designer knows how much work there is)
Dynamically
Handle failures of nodes during computation
With a 1,000 machines, is a failure likely in a 1 hour period?
Often easier than with say banking applications (or YFS lock server)
Many computations have no "harmful" side-effects and clear commit points
Scheduling several applications who want to share infrastructure
Time-sharing
Strict partitioning
MapReduce
Design
Partition large data set into M split
a split is equal to a 64 Mbyte part of the input typically
Run map on each partition, which produces R local partitions
using a partition function R
Run reduce on each intermediate partition, which produces R output files
Programmer interface:
map(string key, string value)
reduce(string key, iterator values)
Example: word count
split file in big splits
a map computation
takes one split as input
produces a list of words as output
the output is partitions into R partitions
a reduce computation
takes a partition as input
outputs the number of occurences of each word
Implementation:
caller invokes mapreduce library
library creates worker processes
run map or reduce computations
library creates one master process
master assigns a map and reduce tasks to workers
master is comm channel between map and reduce workers
handles failures of workers
map workers communicate locations of R partitions to master
reducer works asks master for locations
sorts input keys
run reduce operation
when all workers are finished, master returns result to caller
Fault tolerance
when worker fails
master resets all map and reduce tasks to idle
maps need to be reset because map's output is local and unavailable
when map is reset, inform all reduce tasks to read input from new worker
when master fails
nothing!
Semantics:
if user map and reduce functions are deterministic, then
output is the same as non-faulty sequential run of the program
when reduce completes, worker renames tmp output file atomically
reduce commit point!
Load balance: M + R tasks
ideally M + R is much larger than number of workers
challenge: stragglers
Locality
manager runs mappers close to where one of the 3 replicas of input is
Dryad
Similar goals as MapReduce, but different design
Computations expressed as a graph
Vertices are computations
Edges are communication channels
Each vertex can have several input and output channels
Nice C++ use to make it easy to construct graphs
See figure 3 of Dryad paper
Example: how does the graph look like for the word count example
Answer: figure 6 (before)
How is the reduce run in parallel?
Figure 6 (after), dynamically
Or change graph to have R reduce nodes
Implementation
Job manager
execution records for each vertex
when all inputs are available, vertex becomes runnable
vertices may express preferences
dynamic graph refinements
Daemon
creates processes to run vertices
Stage manager
locality
replicated stages to avoid straggler problem
channels
files, TCP pipes, or shared memory
Load balancing
Greedy scheduling
Fault tolerance
Job manager fails, computation fails
Vertex computation fails
restart vertex with different version #
previous instance of vertex may run in parallel with new instances
Semantics
Assumption: Vertex are non-deterministic
Each vertex runs one or more times
Stop when all vertices have completed their execution at least
once
Locality
stage manager
MapReduce versus Dryad
Many similarities
Dryad computation graphs, while MapReduce a series of maps and reduces
Each vertex can take n inputs, while map takes one input
Each vertex can produce n outputs, while map generate n output
DryadLINQ
Goal: sequential programming
LINQ front-end for Dryad
Query-like language integrated with imperative language (e.g., C#)
.Net objects (encapsulate data)
See figure 2 for execution overview
Look at word frequency handout (from the DryadLINQ tech report)
What does each statement do?
How is this executed? (a dryad graph, see figure 7)
MapReduce in DryadLINQ
see 3.3 + 4.2.4
Optimizations
Rewrites graphs
Static optimizations: pipelining, remove redundancy, eager aggregation
When are the optimization applied? Greedy.
Dynamic optimizations: dynamic aggregation, optimization orderby
Based on run-time information
Example: figure 5 (2 is EPG, 3 and 4 are drayd graphs)
Compiler takes OrderBy and compares it into a EPG
Based on the properties of M+S, compiler uses pipeline opt
stream operators are pipelined, pipeline stops at partition op
One a data set is partition, the attribute is set, and redundant
partitioning can be removed.
Runtime optimizations
When DS runs, repartitions input (input size / max unit) (2->3)
H bins and takes the first key as the beginning of the key range
D decides on two partitions (3->4)
Debugging through standard Microsoft tools, including distributed breakpoints
Execution overhead
table 2
Lab 2:
What is Fuse?
file system operations are translated in fuse messages sent to yfs_client
there is a fuse module inside the OS kernel that does this.
Code walk through for an operation
