Let's now turn to the map-reduce paradigm
itself.
As we just mentioned, it's a tailor
parallel, paradigm, with message passing.
It's also a pipelined procedure, where
there are two phases.
There's the map phase and the reduce
phase.
Further, as we also mentioned, it's a
higher level abstraction.
So programmers only need to specify what
each mapper actually does, and what each
reducer actually does And the map-reduce
implementation takes care of all the
message passing required between the two
phases.
In fact, one doesn't even need to worry
about how many processors there are, and
which one should be doing what kind of job
map-reduce.
That's all left to the map-reduce
implementation.
All the programmer needs to do is define
their task in terms of the map-reduce
paradigm which will come to in a moment.
Point the system at the data on which they
would like this task performed.
And the map-reduce implementation, figures
out which processors can be made available
to this task.
And does the rest without the programmer
having to worry about the details.
That's what makes map-reduce exceedingly
powerful for large scale data parallel
processing.
Since it bridges the gap between high
level specification of an algorithm, and
its massively parallel implementation in a
manner which has really never been
successfully done ever before in the
history of parallel computing.
As we shall see, many complex web
intelligence algorithms for machine
learning and processing big data are easy
to express using the mapreduce paradigm.
Making their large scale parallel
implementation much easier than if one had
to program these using either shared
memory or low level message passing as was
the case before map-reduce.
The most common example used to, explain
map-reduce is that of counting words and
documents.
Something we've seen last week when we
tried to compute inverse document
frequencies for example.
Suppose we are given many documents in
this case.
Say there are only ten documents here, but
there could be you know, hundreds or
thousands or even millions of documents.
And we need to compute the frequency that
each word takes across this whole set of
documents.
And we like to do it in parallel, using
many processors, so as to reduce the
overall execution time.
In our simple example we will take only
ten documents.
And three mapper processors which execute
map tasks.
Followed by two reducer processors that
execute reduced tasks.
Of course, once the mapper processors are
done they can start doing the reduced
work.
So the total number of, processors need
not be five, it might not even be as low
as three, or maybe four.
The mappers are given data, in this case
there are documents identified by document
IDs, which the map-reduce system randomly
distributes across the different mapper
processors.
Each mapper processor thus, gets a bunch
of documents.
It doesn't really know which documents
it's getting.
It just gets a bunch of them in any random
order.
Now, here's how the problem is defined in
terms of map and reduced tasks.
Remember, a mapper simply needs to perform
a whole bunch of map tasks on all the
documents that it gets.
So its getting a sequence of document IDs
followed by the contents of the document.
In other words its getting a key and a
value in a sequence as such key value
pairs.
A map task works on a key value pairs such
as a document ID and its contents and
produces a bunch of key value pairs in
this case words and the frequencies with
which they occur in this particular
document.
Remember that a map task acts on one key
value pair.
So, it needs to act in this case on one
document.
It is, however, free to emit many key
value pairs as its output.
In this case the many words that occur in
that document along with their
frequencies.
For example, the map tasks for the
document D1 would be to emit a W1 followed
by one.
A
W2 followed by one and W4 followed by a
one and similarly for the other documents.
In some cases such as the six, we would
emit a W2 followed by a two.
But in most other cases it would be a
count of one.
The second part of our problem definition
is the reduce phase, in which a list of
key value pairs corresponding to the same
W key, in this case is reduced or,
compressed, or combined, into one key
value pair, for that particular key.
So for example, all the counts for a
particular word are summed up in the
reduced phase to create one key value pair
for each word.
Now clearly in order to perform the reduce
function, all the key value pairs for
particular word need to be together if
they are to be so summed up.
Unfortunately, since each mapper acted on
an independent set of documents, it only
has access to those word count pairs for
the particular document it happens to see.
The best that a mapper can do is compute
the reduced function using the pairs that
it happens to have available.
So, for example, this mapper, it only had
these two documents D1 and D2, which had a
W1, so it computes a W1 comma two by
performing the map and reduced functions
on the set of documents that it has
available to it.
Similarly, this mapper adds up the sums
for W2 across all its documents to get a
value of W2, four.
Of course that is not enough, all these
partial summations themselves need to be
summed up and this is where the map
produce implementation comes in.
And this where the map-reduce
implementation comes in and sends all of
the key value pairs with the same key to
the same producer so that they are all
together and they can finally be reduced
to get the right answer.
So, all the pairs having W1 managed to get
to this reducer, where they can get added
up to get the correct value for W1.
So, we got W1 from here, we got a W1 from
here, we got a W1 from here.
And we added all of these up to get a
value of seven.
Similarly the second reducer also manages
to get all the key value pairs for each
word to be together, so that they could be
added up.
In this case the first reducer works on
pairs, where the keys are W1 and W2.
And the second reducer works on those,
where it's W3 and W4.
So now we're ready to define map-reduce
formally.
Mappers read data in the form of key value
pairs K1, B1 and for each such K1, B1
pair, a mapper may emit one or more pairs
of the form of K2, V2.
In our word counting example, K1 was
document ID.
And B1 was the contents of the document,
whereas K2 was the word and V2 the number
of times a word occurred in a particular
document.
The reduced function on the other hand
receives all the pairs for sum value of K2
and combines them through a reduce
function.
So the reduce of K2 and all the values
that came out of the map phase for that
particular value of K2 are combined using
a function F sub R.
And now we're counting example F sub R is
just a summation across all the
occurrences of a particular word in all
the documents that we process.
Some of you might have noticed that in our
example we actually did, some reduced work
within the mappers.
But we'll come to that point in a short
while.
For the moment.
The strict definition of a map function is
only a map that is from one key val-,
value pair produce one or more key value
pairs.
And reduce function is take all the key
value pairs for a particular value of the
key and apply the reduce function on them.
The map-reduce platform is responsible for
routing pairs to reducers, so that all the
pairs for the same key end up at the same
reducer.
Mapreduce essentially sorts the key value
pairs that come out of the map phase.
So that they land up in the right place.
Finally, a very important point to note is
that the map reduce process reads data,
possibly from a file system or a database,
and writes fresh data.
So, it's a batch process that always
produces more data.
Very different from a database, where one
is querying data and just getting an