The Hadoop ecosystem has evolved into its second generation, Hadoop YARN, which adopts fine grained resource management schemes for job scheduling. In YARN, there is no “slot” which is the building block in the old versions, and the system no longer distinguishes map and reduce tasks when allocating resources. Instead, each task specifies a resource request in the form of <2G,1core> (i.e., requesting 2G memory and 1 cpu core), and it will be assigned to a node with sufficient capacity. However, existing schedulers in YARN don't consider the efficiency of resource utilization for multiple jobs running concurrently in cluster.

Our Solution:

Motivated by above problem, we propose a new Hadoop YARN scheduling algorithm, named HaSTE, which aims at efficiently utilizing the resources for scheduling map/reduce tasks in Hadoop YARN and improving the makespan of MapReduce jobs. Specifically, our solution dynamically schedules tasks for execution when resources become available based on two metrics of each task:

• Fitness:
  Fitness is the metric for resource demands of tasks. It essentially refers to the gap between the resource demand of tasks and the residual resource capacity of nodes. We use the First Fit Decreasing (FFD) algorithm to calculate the fitness score of each task based on their resource demand and the remaining resource on the node.
  
  
  
  
  Furthmore, we adopt the FFD-DP method to schedule map and reduce tasks with two resource requirements: memory and cpu.
• Urgency:
  Urgency is the metric for dependency between tasks. It is designed to quantify the "importance" of a task in the entire process. It allows us to prioritize all the tasks from different jobs and more importantly, catches the dependency between tasks. Three conditions are take into consideration for the calculation of the urgency of each task:
  • A job with more progress of map phase, will be more urgent to schedule its map tasks.
  • A job with more resources allocated to reduce tasks will be more urgent to schedule its map tasks.
  • Reduce tasks are more urgent than map tasks if its resource occupancy rate is lower than the map progress.
Furthermore, we develop an aggregation function that combines the fitness and urgency to compare all candidate tasks and select the best one for execution.

The implementation of both HaSTE and FFD-DP are based on Hadoop YARN version: 2.2.0.



The Evaluation:
                          
Experiment Settings:
• Benchmarks: Terasort, Word Count, Word Mean, Inverted Index, PiEstimate
• YARN Cluster: 8-node cluster: each node with 8 cores and 8GB memory
• Schedulers in the evaluation
  • FIFO: first in first out
  • Fair Scheduler
  • DRF: Fair and Dominant Resource Fairness
  • FFD-DP
  • HaSTE
                          
Experiment Metrics:
• Makespan: the completion length of a set of MapReduce jobs.
• resource utilizations: the usages of memory and cpu in the cluster
                          
Experiment Results:
• 4 jobs with single benchmark (Word Count)
 

 
• 8 jobs with mixed benchmarks:
 

 

Publication :

HaSTE: Hadoop YARN Scheduling Based on Task-Dependency and Resource-Demand
[CLOUD'14 ]The 7th IEEE International Conference on Cloud Computing, Anchorage, AK, June 2014