A Reduce Task Scheduler for MapReduce with Minimum Transmission Cost Based on Sampling Evaluation

다국어 초록 (Multilingual Abstract)

MapReduce is a popular framework for processing large datasets in parallel over a cluster. It has gained wide attention for its high scalability, reliability and low cost. However, its performance may be degraded by excessive network traffic when processing jobs, for such two problems as data locality in reduce task scheduling and partitioning skew. We propose a Minimum Transmission Cost Reduce task Scheduler (MTCRS) based on sampling evaluation to solve the two problems. The MTCRS takes the waiting time of each reduce task and the transmission cost set as indicators to decide appropriate launching locations for Reduce tasks. The transmission cost set is computed by a mathematical model, in which the parameters are the sizes and the locations of intermediate data partitions generated by Average Reservoir Sampling (ARS) algorithm. The experiments show that the MTCRS reduces network traffic by 8.4% compared with Fair scheduler.

목차 (Table of Contents)

• Abstract
• 1. Introduction
• 1.1. Data Locality in Reduce Tasks Scheduling
• 1.2. Partitioning Skew
• 2. Background and Related Work
• 2.1. The Process from Job Submission to Job Launching
• 2.2. Typical Network Topology of Hadoop Cluster
• 2.3. Research on Task Scheduling
• 3. The Design of the New Reduce Task Scheduler
• 3.1. ARS Sampling Algorithm
• 3.2. Transmission Cost Mathematical Model
• 3.3. MTCRS
• 4. Experiments and Evaluation
• 4.1. Environment and Datasets
• 4.2. ARS
• 4.3. MTCRS
• 5. Conclusion and Future Work
• Acknowledgements
• References