Paper Infomation
Data Replica Location-Aware Joint Scheduling of Map and Reduce Tasks
Full Text(PDF, 1069KB)
Author: Yuqi Fan, Bo Gao
Abstract: MapReduce is a popular data parallel processing framework in data centers. MapReduce splits a job into multiple map tasks and reduce tasks so that the tasks can be executed in parallel. Before running the map and reduce tasks, the task nodes communicate with the data nodes to fetch the data required by the execution of the tasks. The network traffic between the nodes accounts for a big part of the running time of the MapReduce job. Therefore, careful map and reduce tasks scheduling is critical for MapReduce performance. Most of the current task scheduling algorithms only perform the scheduling for either map tasks or reduce tasks without the joint consideration of the impact of both map and reduce tasks scheduling on the network traffic. In this paper, we deal with the joint scheduling of map and reduce tasks problem with the aim to reduce the network traffic. We also propose a data replica Location-Aware Joint Scheduling of map and reduce tasks algorithm (LAJS). The algorithm determines the scheduling locations of map and reduce tasks according to the node processing capabilities and the data replica locations of the input data for the map tasks. We finally conduct experiments through simulations. Experiment results show that the proposed algorithm LAJS can effectively reduce the data traffic during job processing and improve job makespan performance.
Keywords: MapReduce; Task scheduling; Data Location; Network Traffic
References:
[1] Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113.
[2] Apache Software Foundation, "HDFS Users Guide," Hadoop Documentation. Accessed Dec 13, 2024.http://Hadoop.apache.org/docs/stable/Hadoop-project-dist/Hadoop-HDFS/HDFSUserGuide.html.
[3] Song, Jie, Sun Zongzhe, Mao Keming, Bao Yubin, and Yu Ge. "Research advance on MapReduce based big data processing platforms and algorithms." Journal of Software 28.3 (2017): 514-543.
[4] Babu, LD Dhinesh, and P. Venkata Krishna. "An execution environment oriented approach for scheduling dependent tasks of cloud computing workflows." International Journal of Cloud Computing 3.2 (2014): 209-224.
[5] Guo, Yanfei, Rao Jia, Cheng Dazhao, and Zhou Xiaobo. "ishuffle: Improving hadoop performance with shuffle-on-write." IEEE transactions on parallel and distributed systems 28.6 (2016): 1649-1662.
[6] Xue, Ruini, Gao Shengli,Ao Lixiang, and Guan Zhongyang. "BOLAS: bipartite-graph oriented locality-aware scheduling for MapReduce tasks." 2015 14th International Symposium on Parallel and Distributed Computing. IEEE, 2015.
[7] Lydia, E. Laxmi, Ch Sudhakar, and T. Madhuri. "An improved optimal task selection strategy for hadoop scheduling." 2017 International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS). IEEE, 2017.
[8] Zhao, Hui, Zheng Qinghua, Zhang Weizhan, and Wang Jing. "Prediction-based and locality-aware task scheduling for parallelizing video transcoding over heterogeneous mapreduce cluster." IEEE Transactions on Circuits and Systems for Video Technology 28.4 (2016): 1009-1020.
[9] Jeyaraj, Rathinaraja, and V. S. Ananthanarayana. "Dynamic performance aware reduce task scheduling in MapReduce on virtualized environment." 2018 IEEE 16th International Conference on Software Engineering Research, Management and Applications (SERA). IEEE, 2018.
[10] Geetha, J., N. UdayBhaskar, and P. ChennaReddy. "Data-local reduce task scheduling." Procedia Computer Science 85 (2016): 598-605.
[11] Hammoud, Mohammad, M. Suhail Rehman, and Majd F. Sakr. "Center-of-gravity reduce task scheduling to lower mapreduce network traffic." 2012 IEEE Fifth International Conference on Cloud Computing. IEEE, 2012.
[12] Hu, Chao, Liu Bo, Xing Changyou, Yue Zhenjun, Song Lihua, and Chen Ming. "Queueing model based analysis on flow scheduling in information-agnostic datacenter networks." 2016 IEEE International Conference on Communications (ICC). IEEE, 2016.
[13] Zhou, Qihua, Li Peng, Wang Kun, Zeng Deze, Guo Song, and Guo Minyi. "Swallow: Joint online scheduling and coflow compression in datacenter networks." 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2018.
[14] Wang, Shuo, Zhang Jiao, Huang Tao, Pan Tian, Liu Jiang, and Liu Yunjie. "Multi-attributes-based coflow scheduling without prior knowledge." IEEE/ACM Transactions on Networking 26.4 (2018): 1962-1975.
[15] Duan, Jingpu, Zhi Wang, and Chuan Wu. "Responsive multipath TCP in SDN-based datacenters." 2015 IEEE International Conference on Communications (ICC). IEEE, 2015.
[16] Li, Zhao, Shen Yao, Yao Bin, and Guo Minyi. "OFScheduler: a dynamic network optimizer for MapReduce in heterogeneous cluster." International Journal of Parallel Programming 43 (2015): 472-488.
[17] Fan, Yuqi, Liu Wenlong, Guo Dan, Wu Weili, and Du Dingzhu. "Shuffle scheduling for MapReduce jobs based on periodic network status." IEEE/ACM Transactions on Networking 28.4 (2020): 1832-1844.
[18] Wang, Weina, Zhu Kai, Ying Lei, Tan Jian, and Zhang Li. "Maptask scheduling in mapreduce with data locality: Throughput and heavy-traffic optimality." IEEE/ACM Transactions On Networking 24.1 (2014): 190-203.
[19] Tan, Jian, Meng Shicong, Meng Xiaoqiao, and Zhang Li. "Improving reducetask data locality for sequential mapreduce jobs." 2013 Proceedings IEEE INFOCOM. IEEE, 2013.
[20] Arslan, Engin, Mrigank Shekhar, and Tevfik Kosar. "Locality and network-aware reduce task scheduling for data-intensive applications." 2014 5th International Workshop on Data-Intensive Computing in the Clouds. IEEE, 2014.
[21] Lee, Woo-Hyun, Hee-Gook Jun, and Hyoung-Joo Kim. "Hadoop Mapreduce performance enhancement using in-node combiners." arXiv preprint arXiv:1511.04861 (2015).
[22] Wang, Yandong, Tan Jian, Yu Weikuan, Zhang Li, Meng Xiaoqiao, and Li, Xiaobing. "Preemptive ReduceTask Scheduling for Fair and Fast Job Completion." 10th International Conference on Autonomic Computing (ICAC 13). 2013.
[23] Levin, Asaf. "Approximating the unweighted k-set cover problem: greedy meets local search." SIAM Journal on Discrete Mathematics 23.1 (2009): 251-264.
[24] Tanimoto, Steven L., Alon Itai, and Michael Rodeh. "Some matching problems for bipartite graphs." Journal of the ACM (JACM) 25.4 (1978): 517-525.
[25] Cheng, Li-Wei, and Shie-Yuan Wang. "Application-aware SDN routing for big data networking." 2015 IEEE Global Communications Conference (GLOBECOM). IEEE, 2015.
[26] Apache Software Foundation, "MapReduce Tutorial," Hadoop Documentation. Accessed Dec 13, 2024. http://hadoop.apache.org/docs/r3.2.0/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html\#Mapper