Survey on Task Assignment Techniques in Hadoop
---
paper_title: MapReduce: simplified data processing on large clusters

paper_content:

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.
---
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: 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: 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.
---
paper_title: Learning based opportunistic admission control algorithm for MapReduce as a service

paper_content:

Admission Control has been proven essential to avoid overloading of resources and for meeting user service demands in utility driven grid computing. Recent emergence of Cloud based services and the popularity of MapReduce paradigm in Cloud Computing environments make the problem of admission control intriguing. We propose a model that allows one to offer MapReduce jobs in the form of on-demand services. We present a learning based opportunistic algorithm that admits MapReduce jobs only if they are unlikely to cross the overload threshold set by the service provider. The algorithm meets deadlines negotiated by users in more than 80% of cases. We employ an automatically supervised Naive Bayes Classifier to label incoming jobs as admissible and non-admissible. From the list of jobs classified as admissible, we then pick a job that is expected to maximize service provider utility. An external supervision rule automatically evaluates decisions made by the algorithm in retrospect, and trains the classifier. We evaluate our algorithm by simulating a MapReduce cluster hosted in the Cloud that offers a set of MapReduce jobs as services to its users. Our results show that admission control is useful in minimizing losses due to overloading of resources, and by choosing jobs that maximize revenue of the service provider.
---

Title: Survey on Task Assignment Techniques in Hadoop

Section 1: INTRODUCTION
Description 1: Write about the growing need for handling large-scale data and the role of Hadoop and MapReduce in processing such data. Explain the purpose of the paper, which is to illustrate various schedulers in Hadoop.

Section 2: Hadoop
Description 2: Give an overview of Hadoop, its components like Hadoop Distributed File System (HDFS) and Hadoop MapReduce, and how they contribute to data processing and fault tolerance.

Section 3: Hadoop Distributed File System
Description 3: Explain the architecture and functionality of HDFS, including block storage, replication, and the roles of NameNode and DataNode.

Section 4: Hadoop MapReduce
Description 4: Describe the MapReduce framework, its origin, and how it operates with components like JobTracker and TaskTracker. Discuss task failure handling and scheduling in MapReduce.

Section 5: Scheduling In Hadoop
Description 5: Introduce the importance of scheduling in Hadoop and provide an overview of various scheduling algorithms developed for Hadoop.

Section 6: Default FIFO Scheduler
Description 6: Detail the Default FIFO Scheduler, its functionality, simplicity, and limitations in resource sharing.

Section 7: Fair Scheduler
Description 7: Explain the Fair Scheduler, developed by Facebook, which aims to provide equal resource share to jobs and supports features like preemption and priority settings.

Section 8: Capacity Scheduler
Description 8: Describe the Capacity Scheduler, originally developed by Yahoo, which is designed for large clusters and supports queueing, prioritization, and access control.

Section 9: Longest Approximate Time to End (LATE)
Description 9: Discuss the LATE algorithm that improves task performance by using estimated remaining time instead of task progress.

Section 10: Delay Scheduling
Description 10: Explain Delay Scheduling, which improves data locality by temporarily relaxing fairness in task scheduling.

Section 11: Dynamic Priority Scheduling
Description 11: Introduce Dynamic Priority Scheduling, which dynamically allocates resources based on user-specified priorities and supports preemption.

Section 12: Deadline Constraint Scheduler
Description 12: Describe the Deadline Constraint Scheduler, which considers job deadlines and aims to improve system utilization by scheduling tasks that meet their deadlines.

Section 13: Resource Aware Scheduling
Description 13: Discuss Resource Aware Scheduling, which takes into account the availability of resources like CPU, memory, and disk IO to avoid node congestion.

Section 14: Learning Scheduler
Description 14: Explain the Learning Scheduler, which uses past job execution data and machine learning techniques to predict the impact of tasks on system resources and optimize scheduling.

Section 15: CONCLUSION
Description 15: Summarize the various scheduling strategies discussed in the paper, their pros and cons, and suggest future research directions in improving Hadoop scheduling.