Kairos: Preemptive Data Center Scheduling Without Runtime Estimates

Abstract:

The vast majority of data center schedulers use task runtime estimates to improve the quality of their scheduling decisions. Knowledge about runtimes allows the schedulers, among other things, to achieve better load balance and to avoid head-of-line blocking. Obtaining accurate runtime estimates is, however, far from trivial, and erroneous estimates lead to sub-optimal scheduling decisions. Techniques to mitigate the effect of inaccurate estimates have shown some success, but the fundamental problem remains.

This paper presents Kairos, a novel data center scheduler that assumes no prior information on task runtimes. Kairos introduces a distributed approximation of the Least Attained Service (LAS) scheduling policy. Kairos consists of a centralized scheduler and per-node schedulers. The per-node schedulers implement LAS for tasks on their node, using preemption as necessary to avoid head-of-line blocking. The centralized scheduler distributes tasks among nodes in a manner that balances the load and imposes on each node a workload in which LAS provides favorable performance.

We have implemented Kairos in YARN. We compare its performance against the YARN FIFO scheduler and Big-C, an open-source state-of-the-art YARN-based scheduler that also uses preemption. Compared to YARN FIFO, Kairos reduces the median job completion time by 73% and the 99th percentile by 30%. Compared to Big-C, the improvements are 37% for the median and 57% for the 99th percentile. We evaluate Kairos at scale by implementing it in the Eagle simulator and comparing its performance against Eagle. Kairos improves the 99th percentile of short job completion times by up to 55% for the Google trace and 85% for the Yahoo trace.

Biography:

Pamela is a Computer Scientist at the Swiss Data Science Center (SDSC). She got her PhD from EPFL Switzerland in November 2018. Her thesis, entitled "Hybrid, Job-Aware, and Preemptive Datacenter Scheduling", focused on providing better scheduling and resource management solutions for data centers. Her research interests include data center scheduling, cloud computing, distributed systems and systems support for data science.

Her research was supported by Microsoft Research and made part of a project of the Swiss Joint Research Center at Microsoft. She was also recepient of the Google Anita Borg Memorial Scholarship on 2013 and the Swiss Government Excellence Scholarship for Foreign Students for her masters at EPFL.