Multi-resource Low-latency Cluster Scheduling without Execution Time Estimation
Hidehito Yabuuchi, Takahiro Shinagawa · 2020
Cluster scheduling based on the prior estimation of job execution time is vulnerable to inaccurate estimates. To avoid performance degradation due to this misestimation, recent studies have proposed cluster schedulers that do not rely on prior estimation. However, they do not assume tasks with multitype heterogeneous computing resource demands, resulting in high job latency in real environments. Unfortunately, the optimal scheduling of such tasks is inherently difficult. In this paper, we present a cluster scheduler that heuristically handles multi-type heterogeneous resource demands without prior estimation. To reduce job latency, especially that of short jobs, our scheduler employs two techniques: (1) distributing tasks to nodes based on the similarity between resource demands and availability to simultaneously run as many tasks as possible, and (2) finding a suitable set of tasks for preemption in a node to minimize the number of task preemptions. Experimental evaluations using a real cluster and practical workloads confirm that our scheduler reduced the 90th percentile of slowdown rates by 6.4% and the 99th percentile by 29% compared to a naive extension of Kairos, an existing non-estimation-based scheduler. The experimental results also demonstrate that our scheduler is more effective when workloads have higher heterogeneity in resource demands.