Welcome back to Mining
of Massive Datasets.
In, the previous section will be
studied the Map-Reduce model and
how to solve some simple
problems using Map-Reduce.
In this section, we're going to go under
the hood of a Map-Reduce system and
understand how it actually works.
Just to refresh your
memory a Map-Reduce system
has simple Map-Reduce
system has three steps.
In the Map step,
you take a Big a document which is
divided into chunks and
you run a Map process on each chunk.
And the map process go through
each record in that chunk and
it outputs an intermediate key value pairs
for each vector in that, in that chunk.
In the second set step which is
a group by step you group by key.
You you bring together all the values for,
for the same key.
And in the third step, is a reduce step.
You apply a reducer to each
intermediate key value pair set.
And you create a final output.
Now, here's a schematic of how it actually
works in in a distributed system.
The previous schematic was how it
worked in a, in a centralized system.
In a distributed system, you actually,
have multiple nodes and map and
reduced tasks are running in
pattern on multiple nodes.
So the here are the few chunks of the
file, input file might be on on node 1.
Few chunks on node 2 and
a few chunks on node 3.
And you have map tasks running on,
on each of those nodes.
And and producing producing it to be
intermediate key value pairs on each of
those nodes.
And once the,
once the intermediate key value pairs
are produced, the underlying system
the Map-Reduce system uses a partitioning
function which is just a hash function.
So the the the Map-Reduce system
applies a hash function to
each intermediate key value.
And the has function will tell
the Map-Reduce system which,
reduce node to send
that key value pair to.
Right, this ensures that all all the,
the same key values,
whether they are map task 1, 2, or 3 end
up being sent to the same reduce task.
Right?
So, in this case the key key 4.
Regardless of where it started from,
whether at 1, 2, or 3.
Always end up at reduce task 1.
And the key,
key 1 always ends up at reduce task 2.
Now, once once the reduce
task has a reduce task has
received input from all
from all the map tasks.
All the map tasks have completed,
then you can start the reduced tasks.
And the, the reduced tasks first job is,
is to sort, it's input, and
group it together by key.
And so in this case, there are three
values associated with the key key, key 4,
they're all grouped together.
And once that is done, the reduce task
then, works the reduce function which is
provided by the programmer on each each
such group and creates the final output.
Okay.
So remember, the programmer provides
two functions, Map and Reduce, and
specifies the input file.
The Map-Reduce environment take,
has to take care of a bunch of things.
It takes care of
Partitioning the input data.
Scheduling the program's
execution on a set of machines.
Figuring out where the map tasks run,
where the reduce tasks run, and so on.
It performs a gr,
the intermediate group by step.
And while all this is going
on some nodes may fail.
And the environment make sure
that the node failures are hidden
from the from the program.
And finally the Map-Reduced Environment
also Manages all
the required inter-machine communication.
[SOUND] So, we're going to take,
take a look at exactly how what's,
what's going on in a.
So, let's look at the data flow that's
associated with with, with map reduce.
Now the the input and
the final output of a Map-Reduced program
are stored on the distributed file system.
And the scheduler tries
to schedule the map task
close to the physical storage
location of the import data.
What that means is that recall
the input data is, is a file.
And the file is divided into chunks.
And there are replicas of the chunks
on different chunk servers.
The Map-Reduce system try to schedule each
map task on a chunk server that holds
a copy of the corresponding chunk.
So, there's no actual copy.
A data copy associated with the map
step of the Map-Reduce program.
Now, the intermediate results are, are at
least not stored in the distributed file
system but stored in the local file
system of the map and reduce workers.
what, what are intermediate results?
Intermediate results, intermediate results
could be the output of a map step.
An intermediate result
could be something that,
that limited why, why in the process
of computing the reduce.
Now why, why are such debated results not
stored in the distributed file system?
It turns out that there's some
overhead to storing data in
the distributed file system.
Remember there are multiple replicas
of the data that need to be made.
And so there's a lot of copying.
And network shuffling involved in,
in storing new data in
the distributed file system.
So, whenever possible, intermediate
results are actually stored in
the local file system of the Map and
Reduced workers,
ended up being stored in the distributed
file system to avoid more network traffic.
And finally, as you'll see in
future examples the output
of a Map-Reduce task is often being
the input to another Map-Reduce task.
Now, the master node takes care of all the
coordination aspects of a Map-Reduce job.
The master node keeps, you know,
associates a task status with each task.
A task to see the map tasker reduce task.
And each task has has a status flag.
And the status flag can either be idle,
in progress, or completed.
The master schedules idle tasks
whenever workers become available.
Whenever, there is a free a node that
is tha, that's available for, for
scheduling tasks.
The master goes through it's queue of idle
tasks, and schedules an idle task on that,
on that worker.
When the, when a map task completes,
it sends the the master the location and
sizes of it's the R intermediate
files that it, that creates.
Now, why, R intermediate files?
There's one intermediate file
that's created for each reducer.
Because the data, the output of the mapper
has to be shipped to each of the reducers,
depending on the, on the key value.
And so there R intermediate files,
one for each reducer.
So, whenever, a map task completes,
it let it's, it's,
it's stores the R intermediate files.
On it's local file system,
and it let's the master know what
the names of those files are.
The master pushes this inf,
information to the reducers.
Once the reducers know that all
the mappers map tasks are completed,
then they copy the intermediate
file from each of the map tasks.
And then they can proceed with their work.
Now, the master also per,
periodically pings the workers,
to detect whether a worker has failed.
And if a worker has failed,
the master has to do something.
And we're going to,
see what that something is.
If a map worker fails, then the,
all the map tasks that were scheduled.
On that on that map
worker may have failed.
So, the the tricky thing is that
the output of a map task is written to
the local file system of the,
of the map worker.
So, if a map worker fails,
then the node fails.
Then all intermediate output created
by all the map tasks that have
ran on that worker, are lost.
And so the, what the master does,
is that it resets to idle,
the status of every task that was either
completed or in progress on that worker.
Right, and so all those tasks need to be,
eventually be done, and
they will eventually be rescheduled
on other workers in the course.
If a reduced worker
fails on the other hand,
only the in progress
tasks are set to idle.
The tasks that are actually been
completed by the reduced worker,
don't need to be set to idle.
Because, the output of the reduced
worker is a final output, and
it's written to
the distribute file system.
And not to the local file
system of the reduced worker.
Since, the output is written to
the distributed file system.
The output is not lost even
if the reduce worker fails.
So, only in-progress tasks
need to be set to idle.
While completed tasks
don't need to be redone.
Right?
And so, the and
once again the Idle reduce tasks will be
restarted on other workers eventually.
What happens if the master fails?
If the master node fails,
then the map reduce tas, task is aborted.
The client is notified, and
the client can then do something
like restarting the map reduce task.
So, this is the one scenario
where the task will have to be
restarted from scratch.
Because, the master is typically not
applicated in the Map-Reduce system.
So, you might think that, this is
a big deal, that that the, the master
failure means the the map-reduce task is
aborted, and the task has to be restarted.
But remember,
node failures are actually, rather rare.
A node fails actually recall once every
three years, or once every 1,000 days.
And the master is, is a single node,
and therefore, the chance of the master
failing is actually quite, you know, it,
it, it's quite an uncommon occurrence.
the, the,
the problem that you have with if,
you have a multiple workers associated in,
in a map reduce task.
It's much more likely that,
one of many workers failed,
rather than the master failing.
So, the final question to think about is,
how many map and
how many reduced jobs do we need?
[NOISE] Supposed you know, they're both
throughout M map tasks and R reduce tasks.
Our goal is to determine M and R.
The, this is part of the input that
given to the map reduce system to let it
know how many tasks tasks
it needs to schedule.
The Rule of thumb is to make M much larger
than the number of nodes in the cluster.
You might think, that it's sufficient how
one map task per node to the cluster.
But, in fact, it the rule of thumb is
to have one map task per DFS chunk.
The reason for this is simple.
Imagine, that there is one map
task per node in the cluster and
during you know during
processing the node fails.
If a node fails then that map
task needs to be rescheduled.
On another node in,
in the cluster when it becomes available.
Now in, some, since all the other
nodes are processing, you know,
one of the map tasks has to, one of those
nodes has to complete before this map task
can be scheduled on that node and so,
the entire computation is slowed down.
By the time it takes to com,
you know, complete this map task.
The failed redo the failed map task.
So, if instead of one map task on a given
node, there are many small map tasks on
a given node, and that node fails, then
those map tasks can then be spread across
all the available nodes and so
the entire task will complete much faster.
On the other hand, the number produces
R is usually smaller than M and
is usually even smaller than the total
number of nodes in the system.
And this because the the output file is,
is spread across spread across R
node where R the number of reducers.
And if it's usually convenient
to have the output spread across
a small number of nodes rather than
across a large number of nodes.
And so usually R is set to
a smaller value than M.