1 Introduction
2 Related work
3 Background
-
Prepare. The source data in the local disk is uploaded to HDFS in this phase. According to the predefined partition size of the data segmentation, source data are segmented in blocks first and then stored a copy to the data node in the pipeline way according to the network topology distance.×
-
Map. Each mapper reads data blocks from HDFS and generates key-value pair <k1,v1> of the input data. Then, it executes a user-defined map method which generates intermediate data <k2,v2>.
-
Copy. It is also called shuffle. The intermediate data from the mapper nodes is passed to the appropriate reducer based on the key. The process is from the completion of the first map wave to all intermediate data mapper outputs having been transferred to the reducer.
-
Sort. This stage occurs before the reduce phase. The values of the output data from the map are sorted by the sort algorithm in accordance with the different keys and output the key-value pairs <k2,list(v2)> for the reduce phase. All the values are sorted in list(v2).
-
Reduce. In this phase, the user-defined reduce method are executed to generate the key-value pairs <k3,v3> as the final result.
4 Design of the genetic algorithm-based job scheduling model
4.1 Overall design of the GA-based approach
5 Performance estimation module of job execution
5.1 Assumption
-
About the reduce wave, we use recommendations in [16] and assumes that the maximum number of reduce that can be executed simultaneously is 1.
-
We do not support speculative execution. That means, we will not repeat map or reduce execution and select the faster as the final result, killing the slower one, for it proved to have little contribution to improve the overall execution time.
5.2 Total execution time overview
Type | Symbol | Explanation |
---|---|---|
Cluster | DC
i
| the ith data center i∈[1,N
dcs
] |
B
ii
| Bandwidth between nodes in DC
i
| |
V
dw
| Speed of writing data to the local disk | |
Hadoop&HDFS |
P
i
| Partition size |
N
sm
| Number of simultaneous maps executed | |
in one node | ||
N
cr
| Number of simultaneous reduces executed | |
in one node | ||
\(N_{\text {cp\_threads}}\)
| Number of i/o threads copy to one reduce | |
node | ||
\(V_{\text {cp\_thread}}\)
| Theoretical maximum copy speed of one | |
copy thread | ||
\(V_{\text {reduce\_rep}}\)
| Theoretical maximum output replication | |
speed of one copy thread | ||
N
Spaths
| Number of sort paths for copy | |
N
reps
| Number of replicas in HDFS | |
S
buff
| Sort buffer size for copy | |
App | DS
i
| Input data size in the ith data center |
N
p
| Number of partitions | |
N
reduces
| Number of reduces | |
M
thruput
| Average map throughput of each node | |
R
thruput
| Average reduce throughput of each node | |
RIOmap
| Ratio of map output to input size | |
RIOreduce
| Ratio of reduce output to input size | |
Module |
T
total
| Total execution time |
T
prepare
| Total execution time for raw data input into | |
HDFS | ||
T
job
| Total execution time for a job | |
T
map
| Time for a map wave | |
T
copy
| Time for a copy wave | |
T
sort
| Time for a sort phase | |
T
reduce
| Time for a reduce phase | |
T
rp
| Time for reduce processing | |
T
ro
| Time for reduce output writing | |
N
mw
| Number of map waves |
6 Evaluation
6.1 Setting of the experiment
Job
i
| DS
i
(G) | RIO
map
| RIO
reduce
|
---|---|---|---|
0 | 1 | 0.18 | 0.17 |
1 | 2 | 0.18 | 0.17 |
2 | 4 | 0.18 | 0.17 |
3 | 8 | 0.18 | 0.17 |
4 | 1 | 1.25 | 1.5 |
5 | 2 | 1.25 | 1.5 |
6 | 4 | 1.25 | 1.5 |
7 | 8 | 1.25 | 1.5 |
8 | 1 | 1 | 1 |
9 | 2 | 1 | 1 |
10 | 4 | 1 | 1 |
11 | 8 | 1 | 1 |
Clus
i
|
N
nodes
|
N
reduces
|
P
i
(M) |
---|---|---|---|
0 | 2 | 2 | 64 |
1 | 2 | 2 | 128 |
2 | 4 | 2 | 64 |
3 | 4 | 2 | 128 |
4 | 4 | 4 | 64 |
5 | 4 | 4 | 128 |
6 | 8 | 4 | 64 |
7 | 8 | 4 | 128 |
8 | 8 | 8 | 64 |
9 | 8 | 8 | 128 |
Type | Symbol | Value |
---|---|---|
Cluster |
V
dw
| 50.96MB/s |
Hadoop&HDFS |
N
sm
| 4 |
N
sr
| 2 | |
\(N_{\text {cp\_threads}}\)
| 30 | |
\(V_{\text {cp\_thread}}\)
| 10 MB/s | |
\(V_{\text {reduce\_rep}}\)
| 10 MB/s | |
N
Spths
| 10 | |
N
reps
| 3 | |
S
buff
| 716 | |
App |
M
thruput
| 1.18 MB/s |
R
thruput
| 15.47 MB/s |
Time (s) | Clus
i
| |||||||||
---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
Job
i
| ||||||||||
0 | 237.9 | 237.9 | 127.5 | 237.9 | 124.4 | 234.7 | 124.4 | 234.8 | 122.8 | 233.1 |
1 | 475.7 | 475.7 | 255.0 | 255.0 | 248.7 | 248.7 | 138.4 | 248.7 | 135.2 | 245.6 |
2 | 951.4 | 951.4 | 510.0 | 510.0 | 497.5 | 497.5 | 276.8 | 276.8 | 270.5 | 270.5 |
3 | 1902.8 | 1902.8 | 1020.1 | 1020.1 | 994.9 | 994.9 | 553.5 | 553.5 | 541.0 | 541.0 |
4 | 329.8 | 329.8 | 219.5 | 329.8 | 170.4 | 280.7 | 170.4 | 280.7 | 145.81 | 256.1 |
5 | 659.7 | 659.7 | 439.0 | 439.0 | 340.7 | 340.7 | 230.4 | 340.7 | 181.2 | 291.6 |
6 | 1319.3 | 1319.3 | 878.0 | 878.0 | 681.4 | 681.4 | 460.7 | 460.7 | 362.5 | 362.5 |
7 | 2638.7 | 2638.7 | 1755.9 | 1755.9 | 1362.8 | 1362.8 | 921.5 | 921.5 | 724.9 | 724.9 |
8 | 284.6 | 284.6 | 174.2 | 284.6 | 147.7 | 258.1 | 147.7 | 258.1 | 134.5 | 244.8 |
9 | 569.2 | 569.2 | 348.5 | 348.5 | 295.5 | 295.5 | 185.1 | 295.5 | 158.6 | 269.0 |
10 | 1138.3 | 1138.3 | 696.9 | 696.9 | 590.9 | 590.9 | 370.2 | 370.2 | 317.2 | 317.2 |
11 | 2276.6 | 2276.6 | 1393.9 | 1393.9 | 1181.8 | 1181.8 | 740.5 | 740.5 | 634.4 | 634.4 |
Cost($) | Clus
i
| |||||||||
---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
Job
i
| ||||||||||
0 | 0.04 | 0.04 | 0.05 | 0.09 | 0.05 | 0.09 | 0.09 | 0.18 | 0.09 | 0.18 |
1 | 0.09 | 0.09 | 0.10 | 0.10 | 0.09 | 0.09 | 0.10 | 0.19 | 0.10 | 0.19 |
2 | 0.18 | 0.18 | 0.19 | 0.19 | 0.19 | 0.19 | 0.21 | 0.21 | 0.20 | 0.20 |
3 | 0.36 | 0.36 | 0.39 | 0.39 | 0.38 | 0.38 | 0.42 | 0.42 | 0.41 | 0.41 |
4 | 0.06 | 0.06 | 0.08 | 0.12 | 0.06 | 0.11 | 0.13 | 0.21 | 0.11 | 0.19 |
5 | 0.12 | 0.12 | 0.17 | 0.17 | 0.13 | 0.13 | 0.17 | 0.26 | 0.14 | 0.22 |
6 | 0.25 | 0.25 | 0.33 | 0.33 | 0.26 | 0.26 | 0.35 | 0.35 | 0.27 | 0.27 |
7 | 0.50 | 0.50 | 0.66 | 0.66 | 0.51 | 0.51 | 0.70 | 0.70 | 0.55 | 0.55 |
8 | 0.05 | 0.05 | 0.07 | 0.11 | 0.06 | 0.10 | 0.11 | 0.20 | 0.10 | 0.18 |
9 | 0.11 | 0.11 | 0.13 | 0.13 | 0.11 | 0.11 | 0.14 | 0.22 | 0.12 | 0.20 |
10 | 0.22 | 0.22 | 0.26 | 0.26 | 0.22 | 0.22 | 0.28 | 0.28 | 0.24 | 0.24 |
11 | 0.43 | 0.43 | 0.53 | 0.53 | 0.45 | 0.45 | 0.56 | 0.56 | 0.48 | 0.48 |
Symbol | Value |
---|---|
Population size | 50 |
Max evaluations | 2000 |
Crossover operator | Single-point crossover |
Crossover probability | 0.9 |
Mutation operator | Bit-flip mutation |
Mutation probability | 1/number of variables |
Selection operator | Binary tournament2 |
6.2 Results
Job
i
| Clus
i
| Time | Cost |
---|---|---|---|
0 | 1 | 237.9 | 0.04 |
1 | 1 | 475.7 | 0.09 |
2 | 2 | 510.0 | 0.19 |
3 | 7 | 553.5 | 0.42 |
4 | 0 | 329.8 | 0.06 |
5 | 0 | 659.7 | 0.12 |
6 | 4 | 681.4 | 0.26 |
7 | 8 | 724.9 | 0.06 |
8 | 4 | 147.7 | 0.55 |
9 | 5 | 295.5 | 0.11 |
10 | 5 | 590.9 | 0.22 |
11 | 9 | 634.4 | 0.48 |
Total | 989.5 | 2.6 |
Job
i
| Clus
i
| Time | Cost |
---|---|---|---|
0 | 1 | 237.9 | 0.04 |
1 | 9 | 245.6 | 0.19 |
2 | 2 | 270.5 | 0.20 |
3 | 7 | 553.5 | 0.42 |
4 | 7 | 280.7 | 0.21 |
5 | 7 | 340.7 | 0.26 |
6 | 9 | 362.5 | 0.27 |
7 | 1 | 2638.7 | 0.25 |
8 | 7 | 258.1 | 0.20 |
9 | 7 | 295.5 | 0.22 |
10 | 6 | 370.2 | 0.28 |
11 | 6 | 740.5 | 0.56 |
Total | 2638.7 | 3.10 |