Survey on Improved Scheduling in Hadoop MapReduce in Cloud Environments

1. INTRODUCTION

• Cloud computing provides shared, on-demand computing resources, and the paper adopts the NIST definition for its essential aspects.The introduction also describes cloud resources as scalable and able to provide redundancy and backup.Source: §1 · p. 1
• Increasing amounts of data stored on the web motivate cloud computing, while distributed cloud resources make data processing an important research problem.The paper identifies MapReduce as a parallel programming model widely used for scalable, fault-tolerant applications deployable on clouds.Source: §1 · p. 1

2. HADOOP

• Hadoop combines HDFS, which stores large amounts of data across clusters, with MapReduce, a framework for distributed data processing.Hadoop hides parallelization details so developers can focus on their computation.Source: §2 · p. 1

2.1 HDFS- Distributed file system

• HDFS stores large files across multiple machines and replicates data across servers for reliability.The architecture has a NameNode that maps blocks to DataNodes and manages filesystem operations; DataNodes create, delete, and replicate blocks.Source: §2.1 · p. 2, Figure 1 · p. 2

2.2 Hadoop MapReduce Overview

• Map tasks process partitioned input and emit key-value pairs, which are shuffled by key to Reduce tasks for processing and output.A JobTracker assigns tasks to TaskTrackers, each with fixed map and reduce slots; HDFS stores and replicates job inputs and outputs.Source: §2.2 · p. 2, Figure 2 · p. 2
• Because Hadoop jobs share cluster resources, a scheduling policy determines when their tasks execute; FIFO was the earlier default.Later research developed schedulers suited to different environments.Source: §2.2 · p. 2

3.1 Default FIFO Scheduler

• The default FIFO scheduler queues tasks and assigns them to free slots in job-submission order, so jobs typically wait for their turn to use the cluster.Priority assignment is supported but disabled by default.Source: §3.1 · p. 2, §3 · p. 2

3.2 Fair Scheduler

• The Fair Scheduler aims to give users a fair share of cluster capacity over time, using pools, preemption, and task interleaving.It tracks each job’s time deficit against its ideal fair allocation and schedules the job with the highest deficit; short jobs can finish quickly while longer jobs are not starved.Source: §3.2 · pp. 2–3

3.3 Capacity Scheduler

• The Capacity Scheduler allocates configurable map and reduce slot capacity to user queues, sharing free capacity across queues.When a slot becomes free, it chooses the least-loaded queue and then the oldest remaining job, emphasizing capacity sharing among users.Source: §3.3 · p. 3

4. SCHEDULER IMPROVEMENTS

• The surveyed policies address different scheduling problems, but the paper notes that the discussed schedulers assume homogeneous Hadoop clusters.It identifies heterogeneous clusters as future work.Source: §4 · p. 3

4.1 Longest Approximate Time to End (LATE) - Speculative Execution

• LATE changes speculative execution to prioritize tasks by estimated time remaining rather than progress so far, improving straggler assessment in heterogeneous clusters.Default speculation assumes uniform task progress and computation across nodes; speculation is an optimization, not a fix for bugs that make tasks hang or run slowly.Source: §4.1 · p. 3

4.2 Delay Scheduling

• Delay scheduling temporarily relaxes fairness by skipping a job that cannot run locally, then permitting non-local tasks if it has waited long enough to avoid starvation.It seeks node locality first and rack locality when node locality is unavailable.Source: §4.2 · p. 3

4.3 Dynamic Priority Scheduling

• Dynamic Priority Scheduling redistributes capacity among users according to priority and supports preemption when allocated slots remain unused.Its allocation interval is typically 10 seconds to 1 minute; variable pricing and budget decisions can affect whether users obtain capacity during demand periods.Source: §4.3 · p. 4

4.4 Deadline Constraint Scheduler

• The Deadline Constraint Scheduler uses an execution-cost model and deadline input to admit jobs only when its schedulability test indicates they can finish on time.Its estimates assume homogeneous nodes, uniformly distributed input, reduces starting after maps finish, and input already available in HDFS.Source: §4.4 · p. 4

4.5 Resource Aware Scheduling

• Resource-aware scheduling targets the mismatch between fixed task slots and heterogeneous CPU and disk capabilities, which can cause resource-intensive tasks to be placed on slow or congested machines.The paper proposes tracking CPU utilization, disk I/O, and page faults; it describes dynamic slot advertisement and prioritizing or filtering free slots by resource availability.Source: §4 · p. 3, §4.5 · pp. 4–5

• Current Hadoop scheduling uses statically configured slots, making resource awareness an emerging research problem.Source: §5 · p. 5
• Surveyed Hadoop schedulers consider one or more resources, including CPU, memory, job deadlines, and I/O.Source: §5 · p. 5
• All schedulers discussed assume homogeneous Hadoop clusters; future work will consider heterogeneous clusters.Source: §5 · p. 5