A NOVEL APPROACH FOR MAP REDUCES USING DYNAMIC JOB ORDERING AND SLOT CONFIGURATIONS
A MapReduce workload generally contains a set of jobs, each of which consists of multiple map tasks followed by multiple reduce tasks. Due to 1) that map tasks can only run in map slots and reduce tasks can only run in reduce slots, and 2) the general execution constraints that map tasks are executed before reduce tasks, different job execution orders and map/reduce slot configurations for a MapReduce workload have significantly different performance and system utilization. This paper proposes two classes of algorithms to minimize the makespan and the total completion time for an offline MapReduce workload. Our first class of algorithms focuses on the job ordering optimization for a MapReduce workload under a given map/reduce slot configuration. In contrast, our second class of algorithms considers the scenario that we can perform optimization for map/reduce slot configuration for a MapReduce workload. We perform simulations as well as experiments on Amazon EC2 and show that our proposed algorithms produce results that are up to 15 _ 80 percent better than currently unoptimized Hadoop, leading to significant reductions in running time in practice. INTRODUCTION MapReduce and Hadoop are used to support batch processing for jobs submitted from multiple users (i.e. MapReduce workloads) Despite many research efforts devoted to improving the performance of a single MapReduce job, there is relatively little attention paid to the system performance of MapReduce workloads. Therefore, this paper tries to improve the performance of MapReduce workloads. Makespan and total completion time (TCT) are two key performance metrics. Generally, makespan is defined as the time period since the start of the first job until the completion of the last job for a set of jobs. It considers the computation time of jobs and is often used to measure the performance and utilization efficiency of a system. In contrast, total completion time is referred to as the sum of completed time periods for all jobs since the start of the first job. It is a generalized makespan with queuing time (i.e. waiting time) included. We can use it to measure the satisfaction of the system from a single job's perspective through dividing In this paper, we target at one subset of production MapReduce workloads that consist of a set of independent jobs (e.g. each of jobs processes distinct data sets with no dependency between each other) with different approaches. one MapReduce can only start only when its previous dependent jobs finish the computation subject to the inputoutput data dependency. In contrast, for independent jobs, there is an overlap computation between two jobs, i.e. when the current job completes its map phase computation and starts its reduce phase computation, the next job can begin to perform its mapphase computation. ISSN: 2455 2631 (c) August 2018 IJSDR Volume 3, Issue 8 IJSDR1808024 International Journal of Scientific Development and Research (IJSDR) www.ijsdr.org 151 LITERATURE SURVEY AUTHORS: P. Agrawal, D. Kifer, and C. Olston We study how best to schedule scans of large data files, in the presence of many simultaneous requests to a common set of files. The objective is to maximize the overall rate of processing these files, by sharing scans of the same file as aggressively as possible, without imposing undue wait time on individual jobs. This scheduling problem arises in batch data processing environments such as Map Reduce systems, some of which handle tens of thousands of processing requests daily, over a shared set of files. As we demonstrate, conventional scheduling techniques such as shortest job first do not perform well in the presence of cross job sharing opportunities. We derive a new family of scheduling policies specifically targeted to sharable workloads. Our scheduling policies revolve around the notion that, all else being equal, it is good to schedule nonsharable scans ahead of ones that can share IO work with future jobs, if the arrival rate of sharable future jobs is expected to be high. We evaluate our policies via simulation over varied synthetic and real workloads, and demonstrate significant performance gains compared with conventional scheduling approaches. AUTHORS: W. Cirne and F. Berman In most parallel supercomputers, submitting a job for execution involves specifying how many processors are to be allocated to the job. When the job is moldable (i.e. there is a choice on how many processors the job uses) an application scheduler called SA can significantly improve job performance by automatically selecting how many processors to use. Since most jobs are moldable, this result has great impact to the current state of practice in supercomputer scheduling. However, the widespread use of SA can change the nature of workload processed by supercomputers. When many SAs are scheduling jobs on one supercomputer, the decision made by one SA affects the state of the system, therefore impacting other instances of SA. In this case, the global behavior of the system comes from the aggregate behavior caused by all SAs. In particular, it is reasonable to expect the competition for resources to become tougher with multiple SAs, and this tough competition to decrease the performance improvement attained by each SA individually. This paper investigates this very issue. We found that the increased competition indeed makes it harder for each individual instance of SA to improve job performance. Nevertheless, there are two other aggregate behaviors that override increased competition when the system load is moderate to heavy. First, as load goes up, SA chooses smaller requests, which increases efficiency, which effectively decreases the offered load, which mitigates long wait times. Second, better job packing and fewer jobs in the system make it easier for incoming jobs to fit in the supercomputer schedule, thus reducing wait times further. As a result, in moderate to heavy load conditions, a single instance of SA benefits from the fact that other jobs are also using SA. AUTHORS: J. Dean and S. Ghemawat MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day. ISSN: 2455 2631 (c) August 2018 IJSDR Volume 3, Issue 8 IJSDR1808024 International Journal of Scientific Development and Research (IJSDR) www.ijsdr.org 152 PROPOSED SYSTEM In this paper, we target at one subset of production MapReduce workloads that consist of a set of independent jobs (e.g. each of jobs processes distinct data sets with no dependency between each other) with different approaches. For dependent jobs (i.e. MapReduce workflow) one MapReduce can only start only when its previous dependent jobs finish the computation subject to the input output data dependency. In contrast, for independent jobs, there is an overlap computation between two jobs, i.e. when the current job completes its map phase computation and starts its reduce phase computation, the next job can begin to perform its map phase computation in a pipeline processing mode by possessing the released map slots from its previous job. Have a theoretical study on the Johnson's Rule based heuristic algorithm for makespan, including its approximation ratio, upper bound and lower bound makespan. Propose a bi criteria heuristic algorithm to optimize makespan and total completion time simultaneously, observing that there is a tradeoff between makespan and total completion time. Moreover, we show that the optimized job order produced by the proposed orderings algorithms does not need to change (i.e. stable) in the face of server failures via theoretical analysis. Propose slot configuration algorithms for makespan and total completion time. We also show that there is a proportional feature for them, which is very important and can be used to address the time efficiency problem of proposed enumeration algorithms for a large size of total slots. Perform extensive experiments to validate the effectiveness of proposed algorithms and theoretical results. ADVANTAGES OF PROPOSED SYSTEM: We evaluate our algorithms using both testbed workloads and synthetic Facebook workloads. Experiments show that, for the makespan, the job ordering optimization algorithm achieve an approximately 14 36 percent improvement for testbed workloads, and 10 20 percent improvement for Facebook workloads. In contrast, with the map/reduce slot configuration algorithm, there are about 50 60 percent improvement for testbed workloads and 54 80 percent makespan improvement for Facebook workloads; Experiments show that, for the total completion time, there are nearly 5_ improvement with the bi criteria job ordering algorithms and 4_ improvement with the bi criteria map/reduce slot configuration algorithm, for Facebook workloads that