Finally, let's take a peek inside, the real implementations of map-reduce that
is, not the light-weight octo simulation, but platforms such as The Duke.
The input files, as we shall see in next week's lecture, are picked up from a
distributed file system in chunks by worker nodes which are essentially
executing the map phase. They read chunks of data, perform map
operations on them and write the results to the local disk.
They sort the data before writing it and they write it in chunks, different chunks
for different reduce keys. It's very important to note that whereas
the input files are in a distributed file system, the local rights after each mapper
is done with its work, are on their local disks.
As a result there's no inter processor communication involved until these are
actually read by the different producers. When a mapper is finished with a
particular reduce key it informs a master node that it's actually done with that
key. That master note keeps getting such
messages from many different mappers task. And assigns reduce keys to difference
reduce processors depending on which are available.
Some times mapper themselves has finished their work and can be reassigned as
reducers. In other cases there are mappers and
reducers working parallel. When a reducer is informed by the master
node that a particular reduce key is ready, it's also told which mapper to pick
it up from. The reducer then issues a remote read to
that mapper process, which has a listener sitting on it, waiting for such remote
read requests, which it services. That is how the reducers actually grab
data from different mappers, as soon as they know where to get that data from.
Notice that even though a master can tell a reducer when a mapper has finished
working on a particular reduce key. The master also knows how many mappers
there are and can figure out when all the work that needs to be done in particular
reduce key is actually over and can inform the reducer assigned to that key that this
is the case so that it actually begins performing reduce operation on a
particular reduce key. Notice that a worker, rather a reduce
worker can pick up data from multiple mappers, but can't really start working on
a reduce key itself, that is, doing the reduce function until it knows that it has
all the data required for that key otherwise the results might be incorrect.
Because reduce functions don't actually have to be computative and associative as
we have seen earlier. Last but not least, the most important
part of map produced implementations that scale is their fault tolerance.
This was the reason why traditional data based technologies could not scale to
thousands or hundreds of thousands of processors.
The trouble is that processors are bound to fail in long tasks involving large
numbers of machines. Simple probability insures that is almost
always likely to happen. For example if the chance that a processor
will never fail in a particular time period is 99%.
Then if you have say, 100 such machines, the chance that none of them will fail is
somewhere around only 30%. That if you have 1,000 machines, the
chance that at least one will fail, is almost 100%.
You can work this out using very similar math to that we used in the locality
sensitive hashing example. So map produced computation that can take
hours or even days on large volumes of big data.
Need to be. Aware of the fact, and in fact, certain
that at least some of their, machines will fail during the computation, but the
computation itself should continue and complete successfully.
Here is how map-reduce ensures this. The master node maintains regular
communication with each of the worker nodes, whether they are mappers or
reducers. It also keeps track of which key ranges
have actually been successfully processed by each mapper and reducer.
Now if a mapper fails, then the master has to simply reassign the key ranges assigned
to that mapper to some other processor whenever it gets one available.
Since the data had to be read from the input in any case, the new reassigned
mapper simply rereads the data and reprocesses it.
Similarly if a reducer fails, the key ranges for whatever task it has not yet
finished, are assigned to some newly appointed reducer.
However, for the tasks we've just already completed before failing.
We don't have to worry because they have already been written out to the output.
This is how the master keeps track of how much of the MapReduce task is completed.
And when a failure is detected, it merely assigns those key ranges to other workers
for the appropriate map or reduce phase. In addition, the master also figures out
whether there are situations where some mappers are performing very slowly for
some unforeseen reason. It treats those as failure, and simply
reassigns their work to somebody else. Whoever finishes first, the data is taken
as done. Since it doesn't really matter if
something is computed twice by mistake. Now you might think that this master which
is a single node is in obvious point of failure and that is indeed the case.
If the master fails, the map produced task indeed does fail.
However, Map Produce works on large numbers and probabilities.
The chance of one amongst a 1000 processor machines failing is almost 100 percent as
we argued a while back. Even though the chance that any one of
them fails might be, less than a percent or even.1%, by that argument the chance
that this particular master fails might be a tenth of a percent or even less, but the
chance that any of the other processors fails if there are large numbers of them
is almost one. This still doesn't remove the fact that
the master is the single point of failure. But the probability of the map produce
task failing is still very, very small. So let's see what we have learnt this
week. We began with the review of parallel
computing ideas, the concept of speed-up, parallel efficiency and scalable
algorithm. We then went into the map-reduce
programming paradigm as a higher level attraction as compared to hand coded
parallel programming using shared memory and message passing.
We did a few examples. Discussed how the ocdo simulator works.
Showed how map-reduce could be applied to various machine learning and search tasks
that we have studied in the past weeks. And concluded with some discussion of the
parallel efficiency and internals of map-reduce.
Next week, we will turn our attention to the big data technology that is required
to make MapReduce actually work. In particular, distributed file systems
distributed no sequel databases. And how they differ from the traditional
relational variety And finally, emerging trends as to where this technology is
actually going in the future.