106
D. Lin et al.
such an assumption when processing big data under the MapReduce framework
refers to the curse of modularity [2]. Kune et al. in [3] adjust a few algorithms to
fit the MapReduce framework, including Naive Bayes algorithms, k-means algorithms, neural network algorithms, support vector machine algorithms, and show
that these algorithms can reduce the computation latency using the framework
of MapReduce. However, a few algorithms with iterations cannot be easily transformed into parallel algorithms, and consequently, these algorithms may not be
appropriate for the MapReduce paradigm in order to reduce the computation
latency [4].
All the above-mentioned studies focus on computing the individual latencies at the map and reduce stages, and do not consider the coupling effects
between these two stages. In this paper, we estimate the latency of big data
processing system under the MapReduce framework by establishing a two-stage
queueing model, and also present the impact of adding mappers or reducers on
the latency. To the best of our knowledge, this is the first study which studies the
coupling effects in the MapReduce framework. The primary contributions of this
paper include: (i) modeling the coupling effects of a MapReduce framework and
(ii) estimating the latency of data processing with different number of mappers
and reducers.
2 Models of Data Flow
In this section, we firstly demonstrate the data flow through the map and reduce
stages, and then, we estimate the latency of data processing within these two
stages.
2.1 Queueing Models of Data Processing
As shown in Fig. 1, we use queueing models to analyze the latency in each stage.
The model of characterizing the data process is composed of two queues: (1) The
data flow from arriving at the mappers (i.e., the memory area of map servers)
to leaving the mappers can be modeled as a M/G/K 1 /K 1 + Q queue, given
K 1 mappers in the server cluster and Q positions in the buffering area of the
mappers, e.g., the permanent storage areas of the mappers. In the following, to
simplify the model, we assume Q = ∞ and use a M/G/K 1 /∞ queue to model the
data flow arriving at and departing from the mappers since the size of buffering
area at the map servers is rarely the limiting factor. (2) The data flow arriving
at the reducers (i.e., the memory area of reduce servers) can be characterized
as a G/GI/K 2 /K 2 queue, in which the arrival process is general, the service
time is independent and identically distributed in a general distribution, and
the number of reducers is K 2 with no buffer capacity.
Model of Data Processing at the Map End Let λ denote the arrival data
rate and μ 0 denote the average rate of service at the map end without considering
the coupling effects with the reduce end. Due to the possibility of blocking the
D. Lin et al.
such an assumption when processing big data under the MapReduce framework
refers to the curse of modularity [2]. Kune et al. in [3] adjust a few algorithms to
fit the MapReduce framework, including Naive Bayes algorithms, k-means algorithms, neural network algorithms, support vector machine algorithms, and show
that these algorithms can reduce the computation latency using the framework
of MapReduce. However, a few algorithms with iterations cannot be easily transformed into parallel algorithms, and consequently, these algorithms may not be
appropriate for the MapReduce paradigm in order to reduce the computation
latency [4].
All the above-mentioned studies focus on computing the individual latencies at the map and reduce stages, and do not consider the coupling effects
between these two stages. In this paper, we estimate the latency of big data
processing system under the MapReduce framework by establishing a two-stage
queueing model, and also present the impact of adding mappers or reducers on
the latency. To the best of our knowledge, this is the first study which studies the
coupling effects in the MapReduce framework. The primary contributions of this
paper include: (i) modeling the coupling effects of a MapReduce framework and
(ii) estimating the latency of data processing with different number of mappers
and reducers.
2 Models of Data Flow
In this section, we firstly demonstrate the data flow through the map and reduce
stages, and then, we estimate the latency of data processing within these two
stages.
2.1 Queueing Models of Data Processing
As shown in Fig. 1, we use queueing models to analyze the latency in each stage.
The model of characterizing the data process is composed of two queues: (1) The
data flow from arriving at the mappers (i.e., the memory area of map servers)
to leaving the mappers can be modeled as a M/G/K 1 /K 1 + Q queue, given
K 1 mappers in the server cluster and Q positions in the buffering area of the
mappers, e.g., the permanent storage areas of the mappers. In the following, to
simplify the model, we assume Q = ∞ and use a M/G/K 1 /∞ queue to model the
data flow arriving at and departing from the mappers since the size of buffering
area at the map servers is rarely the limiting factor. (2) The data flow arriving
at the reducers (i.e., the memory area of reduce servers) can be characterized
as a G/GI/K 2 /K 2 queue, in which the arrival process is general, the service
time is independent and identically distributed in a general distribution, and
the number of reducers is K 2 with no buffer capacity.
Model of Data Processing at the Map End Let λ denote the arrival data
rate and μ 0 denote the average rate of service at the map end without considering
the coupling effects with the reduce end. Due to the possibility of blocking the