Research
Completion-time-aware Scheduler
Imagine that car rental companies such as Hertz rent out cars to their customers without knowing when they are going to return them. It is impossible for the companies to know how long the next customer has to wait until there is a car available for him/her, let along guaranteeing the quality of service (QoS) received by the customers. Similarly, the unawareness of jobs’ runtime is the reason why modern big-data analytic frameworks fail to provide QoS guarantee regarding the jobs’ completion time. The scheduling procedure in the modern big-data analytic systems is not time-aware due to the uncertainty of the jobs’ runtime contributed by unforeseen factors such as hardware heterogeneity, network traffic, data size, computational complexity of job, and so on. However, we believe that time-awareness can still be achieved through exploiting the task homogeneity introduced by the way that the big-data analytic system parallelizes the processes of the jobs.
This project aims to develop and implement a completion-time-aware scheduler for big-data analytic systems that is able to allocate resources in the cluster to jobs in order to maximize their chance of being completed within their desired timeframe. The time-awareness in the scheduling process opens up multiple doors toward intelligences which are previously impossible. We summarize the major achievements of the completion-time-aware scheduler as follows.
- Job finishing time predation: given the resource allocation, the scheduler calculates the projected finishing time of the jobs according to the runtime estimations of their subtasks.
- Job preemption: the scheduler systematically assigns higher priorities to jobs that are completion-time sensitive or have shorter overall runtime.
- Fair resource sharing: the scheduler produces resource partitioning scheme under which all the feasible jobs will be finished before their deadlines.
- Proactive job suspension: the scheduler is capable of locating infeasible jobs that cannot be finished in time. It suspends the infeasible jobs to free up resources for other jobs.
The completion-time-aware scheduler is implemented as a scheduler module for the Apache Yet Another Resource Negotiator (YARN) resource manager. For each submitted job, a machine learning module is introduced to estimate the distribution of the subtasks’ runtime. The user can submit parameters that describe his/her utility level regarding the completion-time of the corresponding job. Such utility determines how much the user values the job being finished at a certain time. The completion-time-aware scheduler performs resource allocation to jobs according to lexicographic max-min fairness. Such approach is Pareto-optimal in the sense that each user receives a fair utility which cannot be improved without jeopardizing the utility of others.
Please see the Robust Scheduler project's website for more information on our work.