Database Reference
In-Depth Information
Figure 2.3
Overview of the execution of a MapReduce program
The Master has many responsibilities. One is to create some number of Map tasks and
some number of Reduce tasks, these numbers being selected by the user program. These
tasks will be assigned to Worker processes by the Master. It is reasonable to create one Map
task for every chunk of the input file(s), but we may wish to create fewer Reduce tasks.
The reason for limiting the number of Reduce tasks is that it is necessary for each Map task
to create an intermediate file for each Reduce task, and if there are too many Reduce tasks
the number of intermediate files explodes.
Reducers, Reduce Tasks, Compute Nodes, and Skew
If we want maximum parallelism, then we could use one Reduce task to execute each reducer, i.e., a single key and
its associated value list. Further, we could execute each Reduce task at a different compute node, so they would all
execute in parallel. This plan is not usually the best. One problem is that there is over-head associated with each task
we create, so we might want to keep the number of Reduce tasks lower than the number of different keys. Moreover,
often there are far more keys than there are compute nodes available, so we would get no benefit from a huge number
of Reduce tasks.
Second, there is often significant variation in the lengths of the value lists for different keys, so different reducers
take different amounts of time. If we make each reducer a separate Reduce task, then the tasks themselves will exhibit
skew
- a significant difference in the amount of time each takes. We can reduce the impact of skew by using fewer
Reduce tasks than there are reducers. If keys are sent randomly to Reduce tasks, we can expect that there will be some
averaging of the total time required by the different Reduce tasks. We can further reduce the skew by using more Re-
duce tasks than there are compute nodes. In that way, long Reduce tasks might occupy a compute node fully, while
several shorter Reduce tasks might run sequentially at a single compute node.
The Master keeps track of the status of each Map and Reduce task (idle, executing at a
particular Worker, or completed). A Worker process reports to the Master when it finishes
a task, and a new task is scheduled by the Master for that Worker process.
Each Map task is assigned one or more chunks of the input file(s) and executes on it the
code written by the user. The Map task creates a file for each Reduce task on the local disk
of the Worker that executes the Map task. The Master is informed of the location and sizes
of each of these files, and the Reduce task for which each is destined. When a Reduce task
is assigned by the Master to a Worker process, that task is given all the files that form its
