The purpose of this unit is to get you beyond understanding what map-reduce is,
to the point where you can use a dupe or a, or a related system effectively.
I'm going to start with a story about a real problem that came up in
a live course I was teaching a while ago.
It will help us see a common mistake in designing map-reduce algorithms, and
in particular, what can be done about it.
I'll then introduce what I think are the key two parameters of a map-reduce
algorithm called Reducer Size and Replication Rate.
There is an interesting trade-off between them, and
good design is often a matter of picking the right point for the trade-off.
We'll introduce Mapping Schemas as a way to define problems and
get lower bounds on the reducer size as a function of replication rate.
Finally, I'm going to drill down on the important problem of
matrix multiplication.
Not only can we use the theory to get an optimal produced algorithm for
matrix multiplication, but we can extend the theory to a method that
uses a cascade of two map-reduced jobs for matrix multiplication.
And we conclude with the observation that the two-job method is in most cases,
more efficient than the one-job method.
I want to start by reviewing and
introducing some notations for describing important components of a map-reduce job.
We need to distinguish between map functions, map tasks, and
mappers, and do the same for reduce.
Remember, a map-reduce job is defined by a map function and a reduce function.
These are the two pieces of code you have to write to make the job go.
Everything else we do is really setting parameters for Hadoop or
another system like it.
A map task applies the map-function to each input in a chunk of the input file.
And a reduce task applies the reduce-function to each of a collection of
key value list pairs.
Remember that behind the scenes key value pairs are organized by key and
the reduce task is presented with pairs consisting in the key.
And the list of all the values associated with that key that
were generated by any of the map tasks.
When we talk about the computation cost of map-reduce algorithms, we
need terminology that is more fine grained than tasks, so I'm going to use the term
mapper to refer to the application of the map-function on one input.
A map task then consists of many mappers.
Similarly, I'll refer to the application of the reduce-function to a single key and
it's associated list of values, as a redcuer.
A reduce task, then, consists of one or more reducers.
It is important to observe that it doesn't matter how the mappers are grouped into
map tasks, nor does it matter how the reducers are grouped into reduce tasks.
In practice, the system will will group mappers according to
the physical location of their inputs.
And we'll group reducers in to as many reduce tasks as it uses based on
some random hash function.
The important point is that mappers and
reducers are the fundamental units of computation during a map-reduce job.
When we run a map-reduce job on a public cloud like EC2, we pay for
two things: rental of processors or
compute nodes, and the transportation of data across the network.
Different clouds may have different charging schemes, but
we can still separate the two costs into a computation cost
of executing the mappers and reducers plus the computation done by the system.
The system does many things including the management of tasks.
But the heaviest computation cost associated with the system is
the sorting of key-value pairs by key and
merging the values with a common key that are generated by different map tasks.
And then there is the communication cost.
This is really the cost of moving key value pairs from where they
are generated to where they are used by the reducers.
In general, no communication is needed to move data from the input to the mappers.
Generally it is preferable to move the code to the data rather than vice versa.
So we assume the map tasks run at the same compute node where their input chunk
is located.
On the other hand, we'll assume that every key value pair is
consumed by a reducer that is not at the node where it was generated.
By coincidence, the reduced task executing the consuming reducer
may execute at the same node where the map task that generated it was executed.
But this will, will be very rare, so
we'll assume it never occurs to keep the computation simple.
Here are a few important observations that will simplify our calculations of
the cost of Map-Reduce Jobs.
Okay. Typically, the computation done by
the mappers is proportional to the number of key value pairs generated.
This does not have to be the case since the map function could do
something very time consuming and produce very little output.
But in the common examples of map-reduce processing the map function does
something simple and its running time is proportional to its output.
We''ll assume the computation cost of the mappers is
proportional to the communication cost, and
it is in fact a small fraction of the communication cost.
So we'll neglect it or add it to the actual communication cost.
The system costs can be treated the same way.
It is principally the cost of organizing the key value pairs.
In practice, [INAUDIBLE] sorts by key so you might consider the system cost to
be proportional to n log n, where n is the number of key value pairs.
However, an external merge sort is in practice linear in end, so we'll assume
that either the sorting time is small compared with communication cost and then
is small enough that a main memory sort is possible or it is so large that the sort
must be done, done on disk and then it is proportional to the communication cost.
And another important point to remember is that on typical computing clusters,
communication is often the dominant cost and
accounts for the majority of the wall-clock time needed to
finish the job no matter how many compute nodes we used.
Gigabit ethernet, the typical communication network,
sounds fast, but in fact it can often fail to keep up.
When many compute nodes are generating and consuming data on the same network.
If you're using the service like Amazon's ZZ2,
you will pay them a certain amount to rent each processor you need.
And you will also pay them another amount for
each gigabyte you move between processors.
So if you want to minimize costs you need to find the optimum tradeoff between
computation and communication.
Unfortunately, there is a competing desire that may false,
force your costs to be higher than the minimum possible.
You want wall clock time to be low,
which means that you want there to be lots of parallelism available.
In some cases, what happens is that the more parallelism you use,
the more communication you need.
If communication is forced to be higher than what would give the minimum dollar
cost, then you need to trade off your desire to finish fast against your
desire to pay the least amount possible.
That's a harder tradeoff to quantify.
You have to decide how much finishing fast is worth to you.
Here's my attempt at a picture of what's going on.
The red line is a hypothetical tradeoff between the amount of communication and
the amount of computation.
The total cost is the sum of both costs.
So we want to find the point in which a 45 degree line is tangent to the curve.
And I've suggested that here.
[SOUND].
Now, here is another hypothetical function that involves wall-clock time.
I've shown the chart as if it were wall-clock time versus communication cost,
but technically, it is wall-clock time against points on the red line.
The simple case is where you're satisfied with a relatively high time to finish.
That means you're surely satisfied with the wall-clock time given by
the least cost algorithm.
Okay.
That is, we're here.
And that corresponds to, oh well, should be a straight line but but it's not.
That says we would be happy with a, an algorithm out here, but
you can do much better.
You can go right over there.
But, suppose you want the job to finish this fast.
And you can't, that is you can't afford to finish later.
And you need to pick an algorithm that is on the red line.
But, that has a higher total cost than the optimum,
that is you really have to pick this point over here.
Now, on the other hand, in another scenario you might want to finish
this fast, but you have in your mind some tradeoff between finishing time and
the dollars you have to pay to get the job done.
In that case, you might want to pick a point on the red line like this.
And as a somewhat higher cost than the optimum, but
it also finishes a little later than you would really like.
But, overall you're as happy as you are going to be with this trade-off.
There's a little more to the story of communication and computation trade-off.
It may be that abstractly you do the same computation at
the reducers no matter how you partition the work.
But, if you give one reducer so
much input that it has to swap data between main memory and secondary memory.
Then the time to do the same computation can go up radically.
[SOUND].
Unfortunately, it's also common that if you want a small amount of
input per reducer, you need to use a lot of communication, and
we'll see an example like this shortly.
The consequence is that the communication computation trade-off is
really a step function.
There is one computation cost if the communication is sufficiently high, and
another larger cost if the communication is too low.
So here's the same picture of communication computation trade-off, but
now the red line is a step function.
There's still an optimum point.
It is the point representing the computation cost assuming everything can
be done in main memory.
And the minimum communication necessary to allow reducers to
take that smaller amount of data.