Abstract

In today’s world the amount of data being generated is growing exponentially and use of internet is also increasing it leads to handle lots of data by internet service providers. MapReduce is one of the good solutions for implementing large scale distributed data application. A MapReduce workload generally contains a set of jobs, each of job consists of multiple map and reduce tasks. Map task executed before reduce task and map tasks can only run in map slot and reduce tasks can only run in reduce slot. Due to that different job executions orders and map/reduce slot configurations for a MapReduce workload have different performance metrics and different system utilization. Makespan and total completion time are two key performance metrics. This paper proposes two algorithm for these two key metrics, The first class of algorithms mainly focuses on the job ordering optimization for a MapReduce workload under given slot configuration and the second class of algorithms perform optimization for slot configuration for a MapReduce workload.

References

• J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” in Proc. 6th Conf. Symp. Oper. Syst. Design Implementation, 2004
• J. Wolf, D. Rajan, K. Hildrum, R. Khandekar, V. Kumar, S. Parekh, K.-L. Wu, and A. balmin, “Flex: A slot allocation scheduling optimizer for mapreduce workloads,” in Proc. ACM/IFIP/USENIX 11th Int. Conf. Middleware, 2010
• A. Verma, L. Cherkasova, and R. H. Campbell, “Two sides of a coin: Optimizing the schedule of mapreduce jobs to minimize their makespan and improve cluster performance,” in Proc. IEEE 20th Int. Symp. Model., Anal. Simul. Comput. Telecommun. Syst.,2012
• S. Tang, B.-S. Lee, and B. He, “Dynamic slot allocation technique for mapreduce clusters,” in Proc. IEEE Int. Conf. Cluster Comput.,Sep. 2013, pp. 1–8.
• S. Tang, B.-S. Lee, and B. He, “Dynamicmr: A dynamic slot allocation optimization framework for mapreduce clusters,” IEEE Trans.Cloud Comput., vol. 2, no. 3, pp. 333–347, Jul. 2014.
• S. Tang, B.-S. Lee, and B. He,, “Mrorder: Flexible job ordering optimization for online mapreduce workloads,” in Proc. 19th Int. Conf. Parallel Process., 2013, pp. 291–304.
• G. J. Kyparisis and C. Koulamas, “A note on makespan minimization in two-stage flexible flow shops with uniform machines,” Eur. J.Oper. Res., vol. 175, no. 2, pp. 1321–1327, 2006.
• P. Agrawal, D. Kifer, and C. Olston, “Scheduling shared scans of large data files,” Proc. VLDB Endow., vol. 1, no. 1, pp. 958–969,Aug. 2008.
• T. Nykiel, M. Potamias, C. Mishra, G. Kollios, and N. Koudas, “Mrshare: Sharing across multiple queries in mapreduce,” Proc.VLDB Endowment, vol. 3, nos. 1/2, pp. 494–505, Sep. 2010.
• H. Herodotou, H. Lim, G. Luo, N. Borisov, L. Dong, F. B. Cetin, and S. Babu, “Starfish: A self-tuning system for big data analytics,”in Proc. 5th Conf. Innovative Data Syst. Res., 2011
• S. M. Johnson, “Optimal two- and three-stage production schedules with setup times included,” Naval Res. Logistics Quart., vol. 1, no. 1, pp. 61–68, 1954.