Latency Estimation of Big Data Processing Under the MapReduce . . .
109
1
2
3
4
5
6
7
8
9
10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Service rate (u)
y 0
y 1
The feasible
solution
y
y 2
u min
u max
Fig. 2. Intuitively demonstrating the proof.
Theorem 2. If Eq. (3) has multiple solutions, the tightest sufficient (not necessary) steady-state condition of the coupled queues for map and reduce stages is:
λ ≤ K 1 ˆ
μ min for the first queue and min{λ, K 1 ˆ
μ min }+ ≤ K 2 μ R for the second
queue.
3 Estimation of the Latency of Queueing Models
In this section, we address the estimation of the latency at the map and reduce
stages. The latency T
C
tot = T
M
W + T
M
S + T
R
W + T
R
S is composed of four parts:
(1) the waiting time to be served on the mappers T
M
W ; (2) the service time on
the mappers T
M
S ; (3) the waiting time to be transferred to reducers T
R
W ; and
(4) the service time on the reducers T
R
S . The average service time on the mappers
can be denoted as T
M
S = 1/μ 0 , and the average service time on the reducers can
be denoted as T
R
S = 1/μ R . In the following, we focus on the latency of T
M
W and
T
R
W .
3.1 Estimation of the Waiting Time to Be Served on the Mappers
In the following, we investigate how to compute the average waiting time to be
served on the mappers, and the process of data flow at the map end can be
modeled as a M/G/K 1 /∞ queue. The average waiting time of this queue can
be denoted as [5]
T
M
W =
1/μ +
P Q /μ
K 1 − λ/μ
1 + C
2
a
2
(4)
where C
2
a denotes the SCV of the service time at the map end, λ denotes the
arrival data rate, μ denotes the mean service rate for data processing at the map
end, P Q denotes the probability as