最小化云平台空闲资源SLO违规的调度方法

引言

目前，空闲资源占主流云平台数据中心容量的相当一部分。云平台以低服务水平目标(Service Level Objective, SLO)和低价格提供空闲资源，以吸引成本敏感的用户。尽管这些用户有容错能力，但他们仍然希望对空闲资源有一些SLO保证。云平台已经开始为空闲资源提供统计SLO，但尚未建模和最小化统计SLO的违规。在本文^[1]中，我们提出一种基于预测+优化的调度策略，命名为PUVAR，以明确建模并最小化云平台空闲资源的统计SLO违规。PUVAR的设计具有两大创新：

（1）明确量化空闲资源容量的预测不确定性，并迭代减少其对调度决策的影响；

（2）将空闲资源的SLO视为软约束，并通过常规请求和空闲请求的两阶段调度最小化其违规。

我们提供了PUVAR参数优化的理论收敛速率。对真实云平台轨迹的剥离分析的结果表明，与流行的基线算法相比，PUVAR可以显著减少空闲资源的SLO违规，而对当前的常规请求调度几乎没有额外成本。

我们明确地通过云平台中一个空闲请求在其生命周期中未分配资源的时间比例来建模其统计SLO。统计SLO违规最小化问题的离线版本可以用如下数学公式表述。

优化目标是最小化统计SLO的违规情况。其中pi是用户指定的空闲请求i的统计SLO，即被驱逐的频率不超过pi。vi是实际的驱逐频率，一旦vi超过pi，SLO的违规程度就通过vi和pi之间的差异来量化。Xijt∈ {0, 1}表示在t时刻是否在机器j上调度空闲请求i，而Yljt∈ {0, 1}表示是否在t时刻在机器j上调度常规请求l。约束（3）和（4）一起确保常规请求必须被调度，并且只能在一台机器上调度，其中约束（3）意味着对于机器j上的请求l，Yljt在其整个持续时间el,..., el + dl期间必须保持一致。约束（4）限制一个请求i在其到达时间ei最多只能在一台机器j上被调度一次。公式（5）定义了空闲请求i的违规频率。公式（6）表示对于任何机器j，在任何时间t，空闲资源的总容量等于1减去已使用的常规资源的总容量。不等式（7）意味着对于任何机器j，在任何时间t，分配在其上的所有活跃空闲请求的总需求不能超过该机器在时间t的空闲资源容量。约束（9）和（10）限制特定请求只能在其特定候选机器集合中的机器上进行调度。

在大型云平台中，面向常规用户的工作负载通常表现出可预测的趋势和每周模式。根据我们从跟踪数据和以往工作中的观察，云平台中常规请求的总需求可以分解为三个组成部分：长期趋势、星期模式和不规则噪声。我们假设每台机器j上常规需求的时间序列可以由随机过程Rj(t)近似，并采用通常使用的加法时间序列预测模型来预测这一随机过程，即

这里我们用clj表示常规请求l在机器j上的资源需求，并在j不在l的候选机器集时将其设为0。Rj(t)的值表示时间t时CPU需求的总量，Tj(t)是确定性趋势，Sj(t)是确定性的周期性星期模式，而ϵjt是时间t的不规则噪声，是一个随机变量。此外，一组参数β用于拟合常规需求到每台机器上常规利用率的线性映射关系。

对于趋势Tj(t)的估计，我们采用了简单有效的移动平均平滑方法。将最后d个历史样本记为R^j(t−d)，...，R^j(t−1)，得到移动平均（MA）

其中d是MA模型中的时间周期参数。对于每周模式，我们从历史数据中提取一个星期模板，并将该模板重复应用于新一周的模式预测。对于不规则噪声，我们通过高斯混合模型（GMM）来拟合其分布。

为了刻画实际预测的不确定性，本工作在模型中通过不规则噪声引入预测的不确定性。该不规则噪声通过一个高斯混合模型（GMM）刻画，概率密度函数（pdf）为：

其中，每个fk(ϵjt∣zk,θk)是参数为θk=(μk,σk2)的混合成分的高斯概率密度。z=(z1,...,zK)是一个由K个二进制指示变量组成的向量，这些变量是相互排斥且完备的，即有且仅有一个zk 等于1，其余等于0。wk=P(zk=1)是混合权重，代表一个样本ϵt 由第k个部分生成的概率。

GMM的完整参数集是：

其累计分布函数为

我们使用实际空闲容量小于预测容量的概率来近似闲置请求遭到近似的驱逐概率，即

将约束16整合到违规最小化问题中，原来的问题变为

在在线环境中，常规请求和空闲请求是实时到达的。我们通过使用分布的累积分布函数（CDF）将驱逐概率转换为容量约束条件，把预测整合进优化问题中。这个框架包含了一个预测模块和一个调度模块。调度模块被划分为两个阶段：优先调度常规请求和调度空闲请求。预测模块和调度模块协同迭代工作，旨在减少空闲资源的服务水平目标（SLO）违规情况。图1展示了我们设计的优化+调度框架PUVAR。

图1  优化+调度框架PUVAR

在云平台的调度中，当前最主要关注点之一是提高机器利用率，即最小化使用的机器总数并留出尽可能多的空闲机器，这通常通过最佳适应（Best-Fit）装箱算法实现。然而，考虑到最小化空闲资源服务水平目标（SLO）违规的目的，我们希望平均常规利用率，以保留更多的空闲资源容量。实现这一目标的著名算法是最差适应（Worst-Fit）装箱算法。我们在调度常规请求时考虑减少空闲资源的SLO违规，通过结合使用最佳适应和最差适应算法，而不会大幅增加使用的机器数量。在一个比较小的概率α下，常规请求的调度使用Worst-Fit，而以概率1−α使用Best-Fit。

在每轮调度后，PUVAR会优化调度策略中的参数α。我们采用贝叶斯优化方法来优化放宽概率α。贝叶斯优化是一种非常有效的方法，用于优化那些评估代价很高的函数，因此它非常适合云资源调度等场景，在这些场景中评估一个调度决策的影响可能会消耗大量资源。这里优化的目标不是传统的预测精度，而是在线调度算法的最终性能：SLO违规，f(α) = ∑(vi − pi)+，这是一个黑箱且评估成本高的过程（需要实际的调度）。实现贝叶斯优化的关键依赖于一个替代函数（surrogate function）来近似目标函数，以及一个获取函数（acquisition function）来指导下一个采样点。我们选择广泛使用的高斯过程回归（GPR）并配备径向基函数（RBF）内核作为替代函数，以及最流行的获取函数——预期改进（EI）作为获取函数，

其中，

这里μ 和 σ是使用可用样本在点 α的后验GPR的均值和标准偏差。α+是历史样本中的最佳点。Φ是标准高斯分布的CDF。ξ = 0.01 是探索与开发之间的权衡权重。下一个α 的采样点选择是为了最大化EI，即arg maxα EI(α)，在这个点上目标值最小或不确定性最高适合探索。关于迭代优化的收敛速率，我们证明了如下命题。

命题1：PUVAR优化α 的收敛速率是O(1/n)，其中n 是迭代次数。

我们在AzureTracesForPacking2020 数据集上评估了我们提出的PUVAR 调度策略的性能。我们的预测模型在测试数据（第二周）上的误差波动低于2%，而且误差波动的95th 百分位数小于1%。与纯粹的Best-Fit、无噪声的预测以及无迭代优化的调度相比，PUVAR对使用的机器数量影响不大，甚至与仅使用Best-Fit 相比也是如此，但显著减少了SLO 违规情况。图2 展示了我们的移动平均预测（黄色）与真实用户需求（绿色）的对比。图3 展示了模型的训练与测试误差。图4展示了不同调度策略的SLO违规对比。

图2 移动平均预测（黄色）对比真实用户需求（绿色）

图3 模型训练与测试误差

图4 SLO违规对比

本文中提出了PUVAR，一种基于不确定性感知预测+优化框架的调度策略。PUVAR在不显著增加使用的机器数量的情况下，实现了对空闲资源服务等级协议（SLO）违规的显著减少，让云平台可以以较小的额外成本显著改善空闲资源的用户体验。

参考文献

[1] Li J, Zhang H, Wang J. PUVAR: Minimize Idle Resource SLO Violations by Uncertainty-Aware Scheduling in Cloud Platforms[C]//2023 IEEE International Conference on Web Services (ICWS). IEEE, 2023: 713-715.

[2]https://aws.amazon.com/ec2/spot/

[3]https://aws.amazon.com/blogs/aws/new-ec2-spot-blocks-for-defined-duration-workloads/

[4]Ambati P, Goiri Í, Frujeri F, et al. Providing {SLOs} for {Resource-Harvesting}{VMs} in Cloud Platforms[C]//14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 2020: 735-751.

[5]Thorpe J, Zhao P, Eyolfson J, et al. Bamboo: Making Preemptible Instances Resilient for Affordable Training of Large {DNNs}[C]//20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). 2023: 497-513.