Survey on Improved Scheduling in Hadoop MapReduce in Cloud Environments
---
paper_title: The Google file system

paper_content:

We have designed and implemented the Google File System, a scalable distributed file system for large distributed data-intensive applications. It provides fault tolerance while running on inexpensive commodity hardware, and it delivers high aggregate performance to a large number of clients. While sharing many of the same goals as previous distributed file systems, our design has been driven by observations of our application workloads and technological environment, both current and anticipated, that reflect a marked departure from some earlier file system assumptions. This has led us to reexamine traditional choices and explore radically different design points. The file system has successfully met our storage needs. It is widely deployed within Google as the storage platform for the generation and processing of data used by our service as well as research and development efforts that require large data sets. The largest cluster to date provides hundreds of terabytes of storage across thousands of disks on over a thousand machines, and it is concurrently accessed by hundreds of clients. In this paper, we present file system interface extensions designed to support distributed applications, discuss many aspects of our design, and report measurements from both micro-benchmarks and real world use.
---
paper_title: Scheduling Hadoop Jobs to Meet Deadlines

paper_content:

User constraints such as deadlines are important requirements that are not considered by existing cloud-based data processing environments such as Hadoop. In the current implementation, jobs are scheduled in FIFO order by default with options for other priority based schedulers. In this paper, we extend real time cluster scheduling approach to account for the two-phase computation style of MapReduce. We develop criteria for scheduling jobs based on user specified deadline constraints and discuss our implementation and preliminary evaluation of a Deadline Constraint Scheduler for Hadoop which ensures that only jobs whose deadlines can be met are scheduled for execution.
---
paper_title: Dynamic proportional share scheduling in Hadoop

paper_content:

We present the Dynamic Priority (DP) parallel task scheduler for Hadoop. It allows users to control their allocated capacity by adjusting their spending over time. This simple mechanism allows the scheduler to make more efficient decisions about which jobs and users to prioritize and gives users the tool to optimize and customize their allocations to fit the importance and requirements of their jobs. Additionally, it gives users the incentive to scale back their jobs when demand is high, since the cost of running on a slot is then also more expensive. We envision our scheduler to be used by deadline or budget optimizing agents on behalf of users. We describe the design and implementation of the DP scheduler and experimental results. We show that our scheduler enforces service levels more accurately and also scales to more users with distinct service levels than existing schedulers.
---
paper_title: Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling

paper_content:

As organizations start to use data-intensive cluster computing systems like Hadoop and Dryad for more applications, there is a growing need to share clusters between users. However, there is a conflict between fairness in scheduling and data locality (placing tasks on nodes that contain their input data). We illustrate this problem through our experience designing a fair scheduler for a 600-node Hadoop cluster at Facebook. To address the conflict between locality and fairness, we propose a simple algorithm called delay scheduling: when the job that should be scheduled next according to fairness cannot launch a local task, it waits for a small amount of time, letting other jobs launch tasks instead. We find that delay scheduling achieves nearly optimal data locality in a variety of workloads and can increase throughput by up to 2x while preserving fairness. In addition, the simplicity of delay scheduling makes it applicable under a wide variety of scheduling policies beyond fair sharing.
---
paper_title: Improving MapReduce Performance in Heterogeneous Environments

paper_content:

MapReduce is emerging as an important programming model for large-scale data-parallel applications such as web indexing, data mining, and scientific simulation. Hadoop is an open-source implementation of MapReduce enjoying wide adoption and is often used for short jobs where low response time is critical. Hadoop's performance is closely tied to its task scheduler, which implicitly assumes that cluster nodes are homogeneous and tasks make progress linearly, and uses these assumptions to decide when to speculatively re-execute tasks that appear to be stragglers. In practice, the homogeneity assumptions do not always hold. An especially compelling setting where this occurs is a virtualized data center, such as Amazon's Elastic Compute Cloud (EC2). We show that Hadoop's scheduler can cause severe performance degradation in heterogeneous environments. We design a new scheduling algorithm, Longest Approximate Time to End (LATE), that is highly robust to heterogeneity. LATE can improve Hadoop response times by a factor of 2 in clusters of 200 virtual machines on EC2.
---
paper_title: Dynamic proportional share scheduling in Hadoop

paper_content:

We present the Dynamic Priority (DP) parallel task scheduler for Hadoop. It allows users to control their allocated capacity by adjusting their spending over time. This simple mechanism allows the scheduler to make more efficient decisions about which jobs and users to prioritize and gives users the tool to optimize and customize their allocations to fit the importance and requirements of their jobs. Additionally, it gives users the incentive to scale back their jobs when demand is high, since the cost of running on a slot is then also more expensive. We envision our scheduler to be used by deadline or budget optimizing agents on behalf of users. We describe the design and implementation of the DP scheduler and experimental results. We show that our scheduler enforces service levels more accurately and also scales to more users with distinct service levels than existing schedulers.
---
paper_title: Scheduling Hadoop Jobs to Meet Deadlines

paper_content:

User constraints such as deadlines are important requirements that are not considered by existing cloud-based data processing environments such as Hadoop. In the current implementation, jobs are scheduled in FIFO order by default with options for other priority based schedulers. In this paper, we extend real time cluster scheduling approach to account for the two-phase computation style of MapReduce. We develop criteria for scheduling jobs based on user specified deadline constraints and discuss our implementation and preliminary evaluation of a Deadline Constraint Scheduler for Hadoop which ensures that only jobs whose deadlines can be met are scheduled for execution.
---

Title: Survey on Improved Scheduling in Hadoop MapReduce in Cloud Environments

Section 1: INTRODUCTION
Description 1: This section introduces cloud computing and its significance, particularly focusing on the definition and advantages of cloud computing, and provides an overview of the paper's structure.

Section 2: HADOOP
Description 2: This section provides an overview of Hadoop, including its components such as Hadoop Distributed File System (HDFS) and Hadoop MapReduce, and their relevance in cloud environments.

Section 3: HDFS-Distributed file system
Description 3: This section discusses the Hadoop Distributed File System (HDFS), its architecture, and how it manages data storage across multiple nodes.

Section 4: Hadoop MapReduce Overview
Description 4: This section explains the MapReduce programming model, its components, and the execution process within the Hadoop framework.

Section 5: SCHEDULING IN HADOOP
Description 5: This section details the various scheduling algorithms used in Hadoop, including the default FIFO Scheduler, Fair Scheduler, and Capacity Scheduler, highlighting their characteristics and differences.

Section 6: Default FIFO Scheduler
Description 6: This section describes the default FIFO scheduling algorithm in Hadoop and its limitations in a multi-user environment.

Section 7: Fair Scheduler
Description 7: This section elaborates on the Fair Scheduler developed by Facebook, including its approach to fair resource allocation and preemption capabilities.

Section 8: Capacity Scheduler
Description 8: This section explains the Capacity Scheduler developed by Yahoo, focusing on its method of ensuring fair resource distribution among a large number of users.

Section 9: SCHEDULER IMPROVEMENTS
Description 9: This section covers recent advancements and proposed improvements in Hadoop scheduling, including Delay Scheduler, Dynamic Proportional Scheduler, and others.

Section 10: Longest Approximate Time to End (LATE) - Speculative Execution
Description 10: This section discusses the LATE algorithm for speculative execution to optimize job performance in heterogeneous clusters.

Section 11: Delay Scheduling
Description 11: This section explains the concept of delay scheduling and how it improves data locality and scheduling fairness.

Section 12: Dynamic Priority Scheduling
Description 12: This section outlines the Dynamic Priority Scheduler and its mechanism for dynamic capacity allocation based on user priorities.

Section 13: Deadline Constraint Scheduler
Description 13: This section covers the Deadline Constraint Scheduler, which aims to meet job deadlines while optimizing system utilization.

Section 14: Resource Aware Scheduling
Description 14: This section introduces resource-aware scheduling mechanisms that consider various system resource metrics to enhance job scheduling efficiency.

Section 15: CONCLUSION & FUTURE WORK
Description 15: This section summarizes the findings of the paper and discusses potential future research directions, particularly focusing on scheduling in heterogeneous Hadoop clusters.