Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-17-107, November 2017. Superseded by EuroSys ’18, April 23–26, 2018, Porto, Portugal.
Jun Woo Park, Alexey Tumanov‡, Angela Jiang, Michael A. Kozuch†, Gregory R. Ganger
Carnegie Mellon University
‡ UC Berkeley
† Intel Labs
The 3Sigma cluster scheduling system uses job runtime histories in a new way. Knowing how long each job will run allows a scheduler to more effectively pack jobs with diverse time concerns (e.g., deadline vs. the-sooner-the-better) and placement preferences on heterogeneous cluster resources. But, existing schedulers use single-point estimates (e.g., mean or median of relevant subset of historical runtimes), and we show that they are fragile in the face of real-world estimate error profiles. In particular, analysis of job traces from three different large-scale cluster environments shows that, while most job runtimes can be predicted well, even state-of-the-art predictors have wide error profiles with 8–23% of predictions off by a factor of two or more. Instead of reducing relevant history to a single point, 3Sigma schedules jobs based on full distributions of relevant runtime history, and explicitly creates plans that mitigate the effects of anticipated runtime uncertainty. Experiments with workloads derived from the same traces show that 3Sigma approaches the end-to-end performance of a hypothetical perfect predictor, and greatly outperforms a state-of-the-art scheduler using point estimates from a state-of-the-art predictor. 3Sigma reduces SLO miss rate, increases cluster goodput, and improves or matches latency for best effort jobs.
KEYWORDS: cluster scheduling, cloud systems
FULL TR: pdf
CONFERENCE VERSION: pdf