31-08-2016, 11:54 AM
1451715629-PRISM.doc (Size: 96.5 KB / Downloads: 12)
ABSTRACT:
Map Reduce has become a popular model for data-intensive computation in recent years. By breaking down each job into small map and reduce tasks and executing them in parallel across a large number of machines, Map Reduce can significantly reduce the running time of data-intensive jobs. However, despite recent efforts toward designing resource-efficient Map Reduce schedulers, existing solutions that focus on scheduling at the task-level still offer sub-optimal job performance. This is because tasks can have highly varying resource requirements during their lifetime, which makes it difficult for task-level schedulers to effectively utilize available resources to reduce job execution time. To address this limitation, we introduce PRISM, a fine-grained resource-aware Map Reduce scheduler that divides tasks into phases, where each phase has a constant resource usage profile, and performs scheduling at the phase level. We first demonstrate the importance of phase-level scheduling by showing the resource usage variability within the lifetime of a task using a wide-range of Map Reduce jobs. We then present a phase-level scheduling algorithm that improves execution parallelism and resource utilization without introducing stragglers. In a 10-node Hadoop cluster running standard benchmarks, PRISM offers high resource utilization and provides 1:3_ improvement in job running time compared to the current Hadoop schedulers.
KEYWORDS: Cloud computing, Map Reduce, Hadoop, scheduling, resource allocation.
PURPOSE:
1. Large scale data analytics.
2. Data intensive (sub division) computation.
3. Parallel computation approach in all applications.
MOTIVATION:
1. Maximizes resource utilization.
2. Minimizes job completion time and running time.
SCOPE:
1. Day –to- day decision business decisions are very easy.
2. New map reduce framework provides success solution for today internet companies.
EXISTING SYSTEM:
If we can assume that all map tasks (and similarly, all reduce tasks) have homogenous resource requirements in terms of CPU, memory, disk and network bandwidth. Indeed, current Map Reduce systems, such as Hadoop Map- Reduce Version 1:x, make this assumption to simplify the scheduling problem. These systems use a simple slot-based resource allocation scheme, where physical resources on each machine are captured by the number of identical slots that can be assigned to tasks. Unfortunately, in practice, run-time resource consumption varies from task to task and from job to job. Several recent studies have reported that production workloads often have diverse utilization profiles and performance requirements [8], [20]. Failing to consider these job usage characteristics can potentially lead to inefficient job schedules with low resource utilization and long job execution time.
DISADVANTAGES:
1. Performance and efficiency of map reduce frameworks have become critical.
2. Low amount of resources utilization.
3. Insufficient resources problems.
4. Delay problem.
5. Insufficient scheduler decision making.
6. subsequent phase of the task may not be scheduled immediately
PROPOSED SYSTEM:
In this project we present PRISM, a Phase and Resource Information-aware Scheduler for Map Reduce clusters that performs resource-aware scheduling at the level of task phases. Specifically, we show that for most Map Reduce applications, the run-time task resource consumption can vary significantly from phase to phase. Therefore, by considering the resource demand at the phase level, it is possible for the scheduler to achieve higher degrees of parallelism while avoiding resource contention. To this end, we have developed a phase-level scheduling algorithm with the aim of achieving high job performance and resource utilization. Through experiments using a real Map Reduce cluster running a wide-range of workloads, we show PRISM delivers up to 18 percent improvement in resource utilization while allowing jobs to complete up to 1:3 faster than current Hadoop schedulers. Finally, even though PRISM is currently designed for Hadoop Map Reduce, we believe our solution can be applied to Dryad and other parallel computing frameworks as well.
ADVANTAGES:
1. Improvement of resource utilization.
2. Achieving high job performance.
3. Resource utilization is high.
4. Faster than Hadoop schedulers.
MODULES DESCRIPTION:
1. Design of System Architecture
2. Phase level Scheduling Mechanism
3. Scheduler Design
4. Phase level Scheduling Algorithm
Design of System Architecture:
We present PRISM, a fine grained resource-aware scheduler that performs scheduling at phase-level. Unlike existing Map Reduce schedulers that only allow job owners to specify resource requirements at task-level, PRISM allows the job owners to specify phase level resource requirements. An overview of the PRISM architecture is shown in Fig. 4. PRISM consists of three main components: a phase-based scheduler at the master node, local node managers that coordinate phase transitions with the scheduler, and a job progress monitor to capture phase-level progress information.
Phase Level Scheduling Mechanism:
Each node manager periodically sends a heartbeat message to the scheduler. when a task needs to be scheduled, the scheduler replies to the heartbeat message with a task scheduling request (Step 1). The node manager then launches the task (Step 2). Each time a task finishes executing a particular phase (e.g. shuffle phase of the reduce task), the task asks the node manager for a permission to start the next phase (e.g. reduce phase of the task) (Step 3). The local node manager then forwards the permission request to the scheduler through the regular heartbeat message (Step 4). Given a job’s phase-level resource requirements and its current progress information, the scheduler decides whether to start a new task, or allow a paused task to begin its next phase (e.g., the reduce phase), and then informs the node manager about the scheduling decision (Step 5). Finally, once the task is allowed to execute the next phase, the node manager
grants the permission to the task process (Step 6). Once the task is finished, the task status is received by the node manager (Step 7) and then forwarded to the scheduler (Step 8).
Scheduler Design:
The responsibility of a Map Reduce job scheduler is to assign tasks to machines with consideration for both efficiency and fairness. To achieve efficiency, job schedulers must maintain high resource utilization in the cluster. Job running time is another possible measure for efficiency, as a lower job running time implies that resources are more efficiently utilized for job execution. In contrast, fairness ensures that resources are fairly divided among jobs such that no job will experience starvation due to unfair resources allocation. However, simultaneously achieving both fairness and efficiency in the context of multi-resource scheduling has been shown to be challenging, as there is usually a trade-off between these objectives.
Phase Level Scheduling Algorithm:
We formally introduce our scheduling algorithm in this section. Upon receiving a heartbeat message from a node manager reporting resource availability on the node, the scheduler must select which phase should be scheduled on the node. Suppose there are J jobs in the system. Specifically, each job j 2 J consists of two types of tasks: map tasks M and reduce task R. Let t(t)€ {M;R} denote the type of a task t. Given a phase i of a task t that can be scheduled on a machine n, we define the utility function of assigning a phase i to machine n.
Experimental Results:
We run each job in Hadoop 0.20.2 with different number of slots allocated to map and reduce tasks. Specifically, we first vary the number of map slots to find an optimal number that minimizes the map completion time. Using this number, we then vary the number of reduce slots to find an optimal number of reduce slots that minimizes the overall job completion time. Then we compute the task size using the optimal number of map and reduce slots per machine. shows the result for adjusting the number of maps slots and reduces for the sort job, respectively. Both figures show that the job running time has a non-linear relationship with the number of slots used. When the number of slots is small the job running time becomes long due to the low degree of task-level parallelism imposed by the slot allocation. On the other hand, when the number of slots is large the running time again becomes high due to multiple tasks competing for bottleneck resources. For the sort job, we found setting the number of map slots and reduce slots to 8 and 6 respectively achieves the optimal running time. The same process is repeated to create the profiles for all other jobs. Notice we adopt this approach mainly because we do not want to set task size used by Yarn to arbitrary values. In practice, the task size is specified by the user, and we can simply just collect the phase-level information with low overhead.
FUTURE ENHANCEMENT:
We believe there are many interesting avenues for future exploration. In particular, we would like to study the problem of meeting job deadlines under phase level scheduling. Also, in this paper we assume all machines have identical hardware and resource capacity. It is interesting to study the profiling and scheduling problem for machines with heterogeneous performance characteristics. Finally, improving the scalability of PRISM using distributed schedulers is also an interesting direction for future research.
System Requirements Specification:
Software Requirements:
Language : Java (JDK1.7.0)
Operating System : Microsoft Windows Xp Service Pack 3
IDE : my eclipse IDE 8.6
Front End : JAVA (Swings)