MapReduce: Detailed Design

Let’s discuss the MapReduce design in detail, including estimations and the detailed role of all the components—their internal mechanisms and the execution flow.

Estimations

In our design, we’ll have to specify the number of workers required to achieve the task based on the input file size. Let’s make some assumptions before we formulate the workers’ calculations.

Assumptions

• The input file size is $12.8\ TB$ (we assume this data size to simplify our calculations, as we will see shortly.)
• We will distribute the input data into splits of roughly $16\ MB$ to $64\ MB$ (we use multiples of 16 MB because the underlying storage of GFS’s chunk size is 64 MB, and we want to maximize data locality benefits).
• We can distinguish the tasks into two categories based on their executing functions— Map and Reduce.
• All workers are identical in their memory and computation resources.
• There are no malfunctioning workers.

Note: In this chapter, we’ll refer to workers as machines. Even though our design automatically handles the differences in workers’ memories and computation resources and the cases of faultiness, these calculations remain independent of these points.

Estimating the Map tasks (M)

We can estimate the number of Map tasks required using the following formula:

$Number\ of\ map\ tasks\ (M) = \frac{File\ size\ in\ MBs}{64\ MB}$

Using the file size under the assumptions section, we can estimate the number of Map tasks: $M = \frac{12800000\ MB}{64\ MB} = 200000$

Workers estimation

Based on the number of Map tasks (M), we can estimate the number of workers (W) as well, making each worker perform $100$ Map tasks.

$Number\ of\ workers\ (W) = \frac{Number\ of\ map\ tasks}{100}$

Using the number from the previous calculation for Map tasks, this estimation is as follows: $W = \frac{200000}{100} = 2000$

Estimating the Reduce tasks (R)

Mainly, the number of Reduce tasks (R) are user-defined as each task produces its separate output file. We usually estimate this number as a small multiple of the available workers in the cluster, $2.5$ as an example.

$Number\ of\ reduce\ tasks\ (R) = Number\ of\ workers\ available * 2.5$

Based on the number of workers above, we can estimate R as follows:

$R = 2000 * 2.5 = 5000$

You may change the input file size in the following calculator widget to see how it impacts M, worker count, and the R values.