[网络领域顶会追踪系列#14][NSDI'22]一个基于任务抽样学习的集群工作调度案例

A Case for Task Sampling based Learning for Cluster Job Scheduling

背景

准确地估计任务的运行时属性的能力让一个调度器能够高效地调度工作（job）。当前最先进的在线集群工作调度器使用的是基于历史的学习，该方法使用过去的任务执行信息来预测新到来工作的运行时属性。

挑战

然而，随着集群技术（在软件和硬件方面）的快速发展以及变化的用户输入，工作的运行时属性会随着时间变化，这导致了不精准地预测。

工作

在本文中，作者通过主动采集和调度每个工作的一小部分任务（task），探索了实时学习运行时工作属性的潜力和限制。

这样的基于任务采集的方法利用了相同工作的各个任务运行时属性的相似性，是对变化的工作行为固有免疫的。

实验

分析和对3个有着不同偏移（skew）和工作分布的产品级trace的实验分析表明，在空间内学习可以大幅度地提高准确率。

作者在Azure仿真和试验床上进行了实验，在3个产品级的集群trace的情况下，两种针对通用工作调度器的两种学习方法表明，尽管有着在线开销，在空间内学习与最先进的基于历史的预测其相比，能够减少1.28倍、1.56倍和1.32倍的平均工作完成时间。

最后，作者展示了基于采样的学习如何扩展至调度DAG任务，并且实现与先进的基于历史的预测其相似的加速。

原文摘要

The ability to accurately estimate job runtime properties allows a scheduler to effectively schedule jobs. State-of-the-art online cluster job schedulers use history-based learning, which uses past job execution information to estimate the runtime properties of newly arrived jobs. However, with fast-paced development in cluster technology (in both hardware and software) and changing user inputs, job runtime properties can change over time, which lead to inaccurate predictions.

In this paper, we explore the potential and limitation of real-time learning of job runtime properties, by proactively sampling and scheduling a small fraction of the tasks of each job. Such a task-sampling-based approach exploits the similarity among runtime properties of the tasks of the same job and is inherently immune to changing job behavior. Our analytical and experimental analysis of 3 production traces with different skew and job distribution shows that learning in space can be substantially more accurate. Our simulation and testbed evaluation on Azure of the two learning approaches anchored in a generic job scheduler using 3 production cluster job traces shows that despite its online overhead, learning in space reduces the average Job Completion Time (JCT) by 1.28x, 1.56x, and 1.32x compared to the prior-art history-based predictor. Finally, we show how sampling-based learning can be extended to schedule DAG jobs and achieve similar speedups over the prior-art history-based predictor.