In the reduce phase, there is more work to be done in pulling the data that
is needed for each one of these reducers.
Because, we know that the mappers have been executing
on different nodes of the computational cluster, and
they produce their intermediate results as files on
their local disk. And this worker that is
carrying out a particular split of the reduce operation
has to reach out and pull the data from all of the m mappers that have
stored their intermediate results on their respective local
disks. So there is remote read that is
involved. As the first thing in the reduce phase is to pull the data. This is
part of what I mean by the plumbing
that the runtime system provides is to recognize that,
for this reduce operation to work, it needs the mapping results from all the m
nodes that carried out the map function. And so it is going to do RPC in
order to get all this data from all the local disks of the nodes on
which the map was executed. And once it has all the data, it can sort it,
and then call the reduce function. The reduce function is
the one that has been written by the domain expert.
And this is the point at which the domain expertise
comes in, in saying, well, I've got the data now,
let me do the processing that I want to do
for the reduce operation. The sorting that is being done
as part of the programming framework may be to sort
the input that is coming in from all of these different
mappers, so that all the same keys are together in the input data set that is
going to be given to the reduce function. And once such sorting has been done,
the programming framework will call the user-supplied
reduce function for each key with the set
of intermediate values so that the reduce function
can do its thing, which is domain specific.
Each reduce function will then write to the final output file
specific to the partition that it is dealing with. So, if you think about the
original example that we started with, if, let's say, this guy is
accumulating all the instances of the name Kishore, then it
will write the output file that says oh, I've found so many instances of
the name Kishore in the input corpus of
data. And similarly, this guy may be doing
it for another name like Drew, or Arun,
and so on. And once each worker has completed
its work by writing its final output file
for this partition that it is responsible for,
then it informs the master, that, yes, I'm
done with the work that was assigned to me.
The user program can be woken up when all
the reducers have indicated to the master that they
have done the work, and at that point the
map reduce computation that was initiated by the user
program is complete. We said that there could be
m splits of the input dataset, meaning the input
key-value pairs, and there could be R splits of
the output that has to be generated by the application
as a whole. Now, the computational resources that
are available in the data center, N, may
be less than the sum m plus R. So there may not be a unique machine to
assign for each one of the m splits
that have been made. It is the responsibility
of the master to manage the machines and
assign the machines that are available to handing the
m input data sets as well as the R
reduce splits that need to be generated. So this is
part of the heavy lifting that has to be
done by the runtime. So, for instance, let's say that
I have only 100 worker nodes available as mappers.
And I have an input split of 1000, then what
I'm going to do is, I'm going to assign one split to
this worker. And when the guy says I'm done with
it, then I'd say, oh, you're done? Okay, take the next
split and work on it. Take the next split and work on
it. So that's how we're going to manage the available resources for carrying
out the work that needs to be done. So remember that this
is all done as part of the heavy lifting by the runtime,
the user doesn't have to worry about it. All that the user
did was write the map function and write the reduce function, and
the rest of it is magic so far as the map reduce
framework is concerned. And similarly, the number of
R splits specified by the user may be
more than the number of workers that are
available to carry that out. And in that
case, again, the master is going to assign a
particular split to this worker so that he
can compute and generate the output file corresponding
to that split. Once he's done with that and
notifies the master, then the master will say, okay,
now that you're done with that, work on the next
split. And it'll do all the work that is
associated with plumbing, meaning, bringing the data for the split
that a particular worker is working on right now,
sorting it to put all the corresponding keys together, and
then finally calling the reduce function that has been
written by the user. That's the kind of work that
goes on under the covers, in the programming framework of map reduce.