A novel decentralized asynchronous scheduler for Hadoop

In cloud computing systems, such as Hadoop, system performance is a significant target for improvement. In classic master node-central schedulers, decision is made in the heartbeat time scale, and idle slots during a heartbeat, remain idle until allocated a task by the master node. In this paper, we propose a novel scheduler named multiple queues scheduler (MQS) that improves the throughput of the system by increasing data locality rate of map tasks, reducing thereby the average completion time of jobs. To achieve this, we associate slave nodes with individual queues, and distribute the tasks of a job at arrival to those nodes that contain the associated input data, based on data locality. To reduce the load on overloaded slave nodes, task migration is performed asynchronously between nodes within a rack, without the intervention of the master node. Our results demonstrate the effectiveness of the proposed algorithm. The benefits of MQS are three-fold: first, it decreases the probability of allocating map tasks to non data-local nodes; second, it decreases the time wasted between heartbeats; these two aspects immediately improve the system performance; and third, it mitigates the stress on the master node by assigning part of the scheduler´s functions to slave nodes.