MagicScaler: Uncertainty-aware, Predictive Autoscaling

MagicScaler.md

SUMMARISE

我读到的主要的一些亮点：

1. 阿里云机器需求是高度不确定的（因为集群是多租户需求的总和），使用高斯过程来量化t+1时刻的不确定性
2. 使用transformer模型中的attention机制来学习时间序列中复杂的依赖模式（非论文原创，之前一些论文也有这样的思路），设计了一种新颖的基于多尺度注意力算法来提取时间序列的特征
3. 将scaler的缩放过程建模为强化学习中的MDP过程
4. 使用蒙特卡洛方法，即采样有限视野的值来近似未来无限时间的最优成本策略

ABSTRACT

预测性自动扩展是优化阿里云计算平台云资源分配的关键推动因素，它根据预测的用户需求动态调整弹性计算服务 (ECS) 实例，以确保服务质量 (QoS)。然而，云中的用户需求往往非常复杂，高度的不确定性和尺度敏感的时间依赖性，因此对准确预测未来需求提出了巨大挑战。 论文提出了一种创新的基于预测的云资源主动弹性伸缩框架 MagicScaler，该框架主要包含一个基于多尺度注意力高斯过程的预测模型和一个考虑需求不确定性的弹性伸缩优化决策器。首先，预测器仔细地结合了两种成功预测方法的优点：多尺度注意力机制，擅长捕获复杂的多尺度特征；随机过程回归，可以量化预测的不确定性，从而实现了包含量化的不确定性下的准确需求预测。 其次，缩放器将量化的未来需求不确定性纳入具有随机约束的明智设计的损失函数中，从而实现运行成本和 QoS 违规风险之间的灵活权衡。 在中国不同城市的阿里云三个集群上进行的广泛实验证明了 MagicScaler 的有效性和效率，它优于其他常用的缩放器，从而证明了我们的设计选择是合理的。

1 INTRODUCTION

阿里云的Autoscaling工具是阿里云IAAS的基础工具，可以提供on-demand使用云资源的方式。传统的Autoscaling策略陷入了两个极端：如图1a这种基于历史需求数据的方式提供了超量的ECS实例方式，这种方式保证用户的需求总是能满足，但是带来了巨大的资源浪费，另一个极端是如图1(b)所示的被动策略，根据瞬时用户需求及时调整ECS实例数量，导致服务质量(QoS)下降。 这主要是由于实例的冷启动——启动新实例以增加云的容量需要一些时间。

预测性自动伸缩更接近图1(c)所示的理想策略，它提供了一种替代解决方案，通过使用预测模型来预测未来的需求，从而可以提前启动ECS实例，避免冷启动。 尽管此类研究正在研究中[1,2,17,30,45]，但由于以下三个限制，它们不能直接应用于我们的场景。

L1：缺乏对不确性需求的支持。现有方法[1,30,45]倾向于关注确定性预测自动扩展，其预测模块可能无法成功预测阿里云中常见的不确定需求。 例如，图2描述了特定Cluster-HZ的25天需求波动，其不确定性很高。 造成这些高度不确定的波动的原因是集群级需求是所有用户级需求的总和（公有云集群提供多租户模式），而这些异构用户可能具有完全不一致的行为模式。 这给预测性自动伸缩的实施带来了巨大的挑战。 也就是说，如果没有正确考虑高不确定性，不正确的确定性需求预测可能会导致 ECS 自动扩展的错误决策，最终影响 QoS。 为了解决这个问题，考虑需求预测和自动扩展阶段的不确定性的预测性自动扩展框架将是明智的。

L2：忽略规模敏感的依赖关系。 考虑图 2 中所示的示例，该示例检查了阿里云中 Cluster-HZ 的分钟、小时和日级别的需求变化。 显然，它们都不具有明确的周期性，这使得传统的基于周期检测的预测算法无法获得任何单一尺度序列的有效周期信息。 因此，基于单一尺度的预测自动伸缩框架无法实现精确的自动伸缩。 根据这一见解，考虑两种时间依赖性是有意义的——一种是尺度之间的依赖性（尺度间），另一种是单个尺度内的依赖性（尺度内）。 我们将这两种尺度敏感依赖关系的组合称为尺度敏感依赖关系，它具有捕获不确定性的复杂波动的巨大潜力，从而提高预测自动缩放的准确性。

L3：无法适应特定的业务场景。 尽管现有的缩放器（例如[25, 45]）已经证明了实例缩放的显着性能改进，但它们没有考虑到更具体和复杂的业务场景。 例如，在阿里云中，每个实例可能处于启动、运行和耗尽（draining）阶段，每个阶段都需要时间并产生不同的成本。 此外，当实例处于耗尽阶段时，可以立即重新启动。 然而，大多数缩放器在构建正式建模时都会简化这些现实场景。 在特定的业务环境中，可能会出现新的冲突，特别是在客户需求突然下降又迅速激增的情况下。 如果根据客户需求实时耗尽或启动实例，则更换资源的间接费用可能会很大。 相反，维持当前的实例数量可能会增加与资源利用相关的成本。 遗憾的是，简化建模的不足常常忽视了当前特定业务场景固有的复杂性。 为此，我们的MagicScaler旨在通过考虑实际业务场景中的这些复杂性因素，纳入需求预测的不确定性，以平衡实例成本和QoS。

本篇论文的贡献。为了解决上述限制，我们提出了一种新颖的预测自动缩放框架 MagicScaler，由基于多尺度注意力高斯过程的预测器和不确定性感知缩放器组成。 首先，预测器仔细地结合了两种成功预测方法的优点：多尺度注意力机制，擅长捕获复杂的多尺度特征；随机过程回归，能够量化预测的不确定性，从而通过量化来实现准确的需求预测。 不确定性水平。 其次，缩放器将量化的未来需求不确定性考虑到明智设计的损失函数中，并考虑到运行成本和 QoS 违规之间的灵活权衡，具有随机约束。 最后，我们列出我们的贡献如下：

（1）我们设计了一种新颖的基于多尺度注意力高斯过程的预测器，以准确预测具有量化不确定性的未来需求。 该预测器利用两阶段（即内部与外部）多尺度特征提取来捕获尺度敏感的时间依赖性，并利用提取的多尺度特征之上的高斯过程来实现准确的未来不确定需求预测。

（2）我们开发了一种具有感知不确定性能力的缩放器，它通过对 QoS 违规的不同容忍级别的随机约束来内化预测的不确定性，从而实现运行成本和 QoS 违规之间的灵活权衡。

（3） 针对需求预测和自动扩展进行了大量实验，证明了我们建议的有效性和效率。

2 RELATED WORK

2.1 Time Series Forecasting

存在各种时间序列分析方法，包括预测，例如统计方法、深度学习方法等[7,8,11,14,19,20,32,39,43,44,46,50]。为了简洁起见，我们从最先进的基于 Transformer 的方法开始。Transformer [35] 模型非常适合时间序列预测，因为它们可以捕获数据中的长期依赖性以及短期相关性。通过使用Transformer模型，预测调度算法可以对未来工作负载做出准确有效的预测，并通过资源分配做出更好的决策。

最近，时间序列Transformer [40,42,47]被引入用于预测任务，利用自注意力机制从时间序列数据中学习复杂的模式和动态。Binh和Matteson [33]提出了一种基于概率、非自回归Transformer的模型，并集成了状态空间模型。通过将稀疏性引入注意力机制中，利用Informer模型[48]的ProbSparse注意力和logSparse注意力机制，将原来的二次复杂度降低到$O(LlogL)$。虽然这种注意力机制是在逐点的基础上运行的，但Autoformer [22]使用基于互相关的注意力机制在子序列级别上运行。Triformer [10]引入了一种具有线性复杂度的新颖补丁注意力机制。当堆叠多个补丁注意力层时，提出了一种三角形结构，使得层大小呈指数缩小，从而保持线性复杂度。FEDformer[49]采用频率变换将序列分解为多种频域模式来提取特征，进一步提高了Autoformer的性能。然而，公共数据集中往往存在某些易于挖掘的模式（例如天气规律和电力的时空特征），这使得这些最先进的模型在它们上取得了近乎完美的结果。然而，当面对很少规律且高度不确定的需求序列时，这些方法可能无法取得令人满意的结果。

2.2 Predictive Autoscaling

预测性自动伸缩用于动态添加或删除实例、CPU、内存等计算资源，以紧密匹配不断变化的计算需求。 该技术对于云计算中有效的资源利用和令人满意的服务质量至关重要。 预测性自动缩放算法使用预测模型来预测未来的工作负载并做出有关资源分配和调度的决策。

现有的自动缩放器基于控制理论、强化学习、排队论和基于规则的方法生成缩放决策[4,5,9,24,27,41]。 这些方法中的大多数要么根据平均需求估计做出扩展决策而不考虑不确定性，要么以启发式方式处理不确定性。 例如，[30]中采用模型预测控制进行预测自动缩放，利用ARMA模型进行工作负载预测，并使用前瞻控制器进行资源分配，而不考虑不确定性。 自动缩放方案 RobustT2Scale [18] 将模糊控制器与在线学习机制集成在一起，可以应对不确定性，但不够通用，无法处理可变的周期性模式 [16, 38]。 相反，我们通过表达 QoS 要求的随机约束直接将工作负载不确定性纳入扩展决策中，以得出稳健的扩展决策。

最近，钱等人。 提出了一种名为 RobustScaler [25] 的新自动缩放框架，该框架使用非齐次泊松过程 (NHPP) 建模和随机约束优化来实现实例成本和服务质量 (QoS) 之间的卓越权衡。 但需要注意的是，RobustScaler 是针对按查询扩展的场景而设计的，这与本研究中的按集群扩展的场景不同。 在按查询扩展的场景中，实例通常在单个查询完成后终止，并且它们的利用率不会扩展以适应后续查询。 然而，我们的场景有所不同，因为我们的实例拥有跨多个查询重用的固有能力。 以类似的方式，薛等人。 [45]提出了一种基于端到端预测元模型的强化学习（RL）算法来维持云中稳定的CPU利用率。 他们的方法使用深度注意力周期模型来预测工作负载并通过注意力神经过程计算 CPU 利用率。 最后，基于模型的强化学习用于找到最佳的缩放决策器。 然而，这种方法没有考虑 CPU 利用率预测的不确定性和服务级别协议 (SLA) 的影响，因此不适合部署在现实世界的云服务中。 值得注意的是，RobustScaler 和基于 RL 的缩放器都忽略了各种业务场景的复杂性，其中每个实例可能处于启动、运行或耗尽阶段，且成本不同。 如果实例处于耗尽阶段，可以立即重新启动。 因此，RobustScaler 和基于 RL 的缩放器都不适合这种场景，因此，我们没有将它们用作基线方法。

3 PRELIMINARIES

3.1 Problem Defnition

我们首先介绍自动缩放中的关键概念。

• 实例：实例是ECS中资源调度的基本单位。实例包含特定的硬件配置（例如 2 核 CPU、4GB 内存）。供给和需求均由实例数量指定。
• 需求序列：时间序列由用户在每个时间戳下需求的实例数组成。
• 供应序列：时间序列由ECS 在每个时间戳提供的实例数组成。

基于上述概念，我们的问题定义如下。 在特定的时间戳 $t$ 上，给定历史需求时间序列 $\mathbb D_{t-H+1:t}$ 包含之前的 $H$ 个时间戳，我们的目标是在未来的 $F$ 时间戳上推荐一个最优供应序列 $\mathbb S_{t+1:t+F}$，使得资源成本和QoS损失最小化。

（1）资源成本：实例的生命周期分为三个阶段：启动、运行和耗尽。 该实例只能在运行阶段使用，在扩展阶段（即启动和耗尽）不可用。 然而，扩展阶段也有成本。 因此，实例的资源成本由两个主要部分组成，即运行成本和扩展成本。

（2）QoS 损失：在使用云服务时，客户通常通过与服务提供商的服务级别协议 (SLA) 指定不同的 QoS 要求。在本文中，我们将 QoS 损失定义为每个时间戳不满足客户 SLA 要求的实例数量。

基于上述关键概念，我们提出了全面的两阶段问题描述。

概率需求预测。给定时间戳 $t$ 的历史需求时间序列，回溯窗口大小为 $H$，表示为 $\mathbb D_t = ⟨d_{t−H+1}, d_{t−H+2}, \cdots, d_t⟩$，概率需求预测，旨在预测未来$F$时间戳的需求分布，即$$\mathbb{\hat W}t = ⟨\hat w{t+1},\hat w_{t+2}, \cdots,\hat w_{t+F}⟩$$，其中 $\hat w_{t+i}$ 表示时间戳 $t+i$ 的需求分布，即用户在未来时间戳 $t+i$ 请求实例数量的概率分布。根据预测的需求分布 $$\mathbb{\hat W}t$$，我们推导出 $$\mathbb{\hat D}t = ⟨\hat d{t+1}, \hat d{t+2}, \cdots, \hat d_{ t+F}⟩$$，其中 $\hat d_{t+i}$ 是分布 $\hat w_{t+i}$ 的平均值。 $\mathbb {\hat D}_t$ 用作预测出的确定性需求。

自动缩放。在时间戳 $t$，给定未来 $F$ 时间戳的预测用户需求分布，即 $$\mathbb {\hat W}t = ⟨\hat w{t+1} ,\hat w_{t+2}, · · · ,\hat w_{t+F}⟩$$，以及当前的云状态 $S_t$，例如当前正在运行的实例等（详细信息请参阅第5节），MagicScaler旨在找到最佳的缩放操作$A_t^\ast$，即启动新实例或关闭正在运行的实例，从而最大限度地降低实例成本和QoS损失风险。

$$ \begin{aligned} &AutoScale(\mathbb{\hat W}_t, S_t) \rightarrow A_t, &(1) \\ &A_t^\ast = argmin(InstanceCost(A_t), QosLoss(A_t)), &(2) \end{aligned} $$

3.2 Gaussian Process Regression

高斯过程[29]是遵循联合高斯分布的随机变量的集合。高斯过程回归是基于高斯过程的概率回归模型。它从多维点 $x_i$（例如历史时间戳中的用户需求）沿着其概率分布学习映射函数 $f(·)$ 到真实值（例如未来时间戳的用户需求）。这里，概率分布遵循高斯分布。形式上，我们有 $f(x_i) ∼ N (μ_i, σ_i^2)$。

假设我们有 $P$ 训练数据 $(x_{1:P}, y_{1:P})$，其中 $(x_p, y_p)$ 表示时间戳 $p$ 处的特定训练数据，且 $1 ≤ p ≤ P$ 。更具体地说，$x_p$ 是从时间戳 $p$ 到时间戳 $p−H+1$ 的历史时间窗口内的用户需求，$y_p$ 是 $p+1$ 处的用户需求，即下一个时间戳的需求。基于高斯过程建模，我们推导出 $P$ 训练数据的联合分布为：

$$f(x_{1:P}) ∼ N(m(x_{1:P}), K(x_{1:P},x_{1:P}), (3)$$

其中 $m(·)$ 是均值函数，$K$ 是从核函数 $k(x_i, x_j)$ 导出的协方差矩阵。通常使用的核 $k$ 是平方指数核： $k(x_i, x_j) = θ_fexp(−\vert \frac{(x_i −x_j)^2}{2Θ^2}\vert)$，方差为 $Θ^2$，按观测值的参数 $θ_f$ 进行缩放。

在推理阶段，我们将上述高斯联合分布作为先验。给定新窗口 $x^\ast$ 中的用户需求，下一个时间戳的预测需求分布被建模为后验分布：

$$f(x^\ast) ∼ N (μ(x^\ast), σ^2(x^\ast)), (4)$$

其中

$$μ(x^\ast)=k(x^\ast, x_{1:P})K(x_{1:P}, x_{1:P})^{-1}f(x_{1:P})$$

$$σ^2(x^\ast)=k(x^\ast, x^\ast)-k(x^\ast, x_{1:P})K(x_{1:P}, x_{1:P})^{-1}k(x^\ast, x_{1:P})^T$$

更具体地说，高斯过程通过遵循高斯分布 $N (μ(x^\ast), σ^2(x^\ast))$ 来预测下一个时间戳的需求。当我们需要对接下来的 $F$ 个时间戳进行预测时，我们以自回归的方式迭代调用高斯过程预测器 $F$ 次。

3.3 Overview of Framework

图3展⽰了该提案的概述。具体来说，MagicScaler由两个主要组件组成：Predictor和Scaler

（1）Predictor：预测器首先采用多尺度注意力特征提取器（MAFE）从历史需求序列中捕获多尺度特征。将提取的特征（而不是原始需求时间序列）输入高斯过程回归模型以预测未来的需求分布序列

（2）Scaler：缩放器将预测的未来需求分布作为输入，并将缩放决策建模为马尔可夫决策过程。 最后，通过考虑实例成本和 QoS 违规风险，缩放器返回最终的缩放决策，即启动新实例或删除现有实例

4 THE PREDICTOR

图4描述了预测器的整体工作流程。 预测器的输入是历史需求序列${\mathbb D}$。 通过内部和外部多尺度注意特征提取器（MAFE）提取多尺度特征$ξ_{t+1}$。 然后，将$ξ_{t+1}$输入到高斯过程回归（GPR）模型中，该模型推导出下一个时间戳 $t+1$ 的预测高斯分布。下面，我们详细介绍MAFE和GPR模块

4.1 Multi-scale Attentive Feature Extractor

集成不同时间尺度的信息对于准确建模和预测时间序列至关重要。 考虑图2中所示的示例，该示例检查了阿里云中特定 Cluster-HZ 的分钟、小时和日级别的需求变化。 它们都不具有明确的周期性，这使得传统的基于周期检测的预测算法无法获得任何单尺度序列的有效周期信息。 在第 1 节中，我们展示了云计算服务中预测自动缩放的关键特征，激励我们提高预测准确性。 因此，我们提出了一种两阶段多尺度注意力特征提取器（MAFE）来捕获尺度敏感依赖性，主要分为外部阶段External-MAFE和内部阶段Internal-MAFE

4.1.1 External-MAFE

我们首先提出External-MAFE来捕获尺度(scale)间的依赖关系，通过尺度之间的相关性提高预测效果的稳定性。 例如，如果多个尺度的时间序列都反映了某个时间段的流量峰值，则真正的流量峰值很有可能发生。如图5所示，External-MAFE以原始时间序列作为输入，并生成不同尺度的子序列，其中原始时间序列被视为最细尺度（标记为白色圆圈）的输入，而其他子序列通过平均池(average pooling)技术进行下采样（标记为不同颜色的圆圈）。通过从粗到细细化提取的特征，将捕获不同尺度之间的相关性。

External-MAFE从底部开始，即具有最粗尺度时间序列的输入时间序列（标记为蓝色）。我们直接获得Internal-MAFE提取的特征（将在4.1.2节中详细介绍，暂时可以将其视为黑盒函数）。然后，我们执行从粗到细的迭代步骤。在每一步中，输入时间序列都需要与上一步的特征融合，然后输入到新的Internal-MAFE中。算法1描述了External-MAFE的过程。首先，我们对尺度列表$L_{scale}$进行降序排序（第1行），以图5为例，排序结果为{12,4,2,1}。因此，我们处理的第一步是$scale = 12$的子系列。然后，迭代粗到细步骤（第2∼9行）与我们之前描述的相同。融合操作利用全连接的神经网络来调整上一步输出的特征的维度，然后与当前步骤的输入连接起来(concatenates)。请注意，第一步中没有融合操作，因为上一步没有输出。最后，我们得到原始时间序列的External-MAFE特征$ξ$。

4.1.2 Internal-MAFE

我们建议使用Internal-MAFE来捕获每个尺度中的注意力依赖关系（尺度内依赖关系）。与External-MAFE不同，Internal-MAFE一次性内在化了不同粒度的所有隐藏特征。 Internal-MAFE 将External-MAFE 确定的特定尺度的输入 ${\mathbb D}$ 作为输入，并返回综合的粗细粒度注意力特征 $ℏ^{out}$ 。这背后的直觉是，在高度不确定的时间序列中，底层模式只能通过不同粒度的数据之间的依赖关系来反映。 特别是，我们的InternalMAFE包括细粒度增强（Fine-grained Augmentation）模块和分层堆叠（Hierarchical Stacking）模块，如图6(b)所示。

注：6(a)中应该是 $H(⋅)$ 而非 $\mathcal H(⋅)$，怀疑论文图中画错

隐藏特征提取器。 在组织Internal-MAFE内的数据流逻辑之前，我们首先阐述一个基本算子，即隐藏特征提取器，用 $H(·)$ 表示。 如图6(a)所示，给定输入序列 $D = ⟨d_1, d_2, · · · , d_n⟩$，我们采用注意力机制[35]来提取 $D$ 的特征。首先，我们随机初始化一个可学习的特征占位符 $h$ 来充当 $Q$ ，然后感受区域(receptive field)中的 $D = ⟨d_1, d_2, · · · , d_n⟩$ 充当 $K$ 和 $V$ 。 其次，当每个 $K$ 参与 $Q$ 时，我们使用等式（5）迭代更新 $h$ ，如下所示

$$ \begin{aligned} &h = H (h, d) =\lbrace φ(\frac{h ⋅ (d_i ⋅ W_k)^T}{\sqrt {dim}}) (d_i ⋅ W_V)\rbrace _{i=1}^n, &(5) \end{aligned} $$

其中 $φ(⋅)$ 表示 softmax 算子。这种特征提取方法与基于池化的自注意力不同，后者使用的自注意力需要将 $d_i$ 视为 $Q$，因此其复杂度达到 $O(n^2)$。然而，在我们的解决方案中，$H(·)$ 中只有 $d_i$ 关注 $h$的部分是必须的，因此 $H(·)$ 的复杂度仅为 $O(n)$。此外，它不需要添加额外的池化层来降低特征的维度。

在介绍了基本算子 $H(·)$ 之后，我们进一步介绍序列级算子 $\mathcal H(·)$。其主要思想是将序列分割成许多补丁，然后对每个小序列执行 $H(·)$ 。 形式上，给定补丁大小 $ps$，输入序列 $D = ⟨d_1, d_2, · · · , d_N ⟩$ 可以分为 $N/ps$ 等大小的补丁，每个补丁执行 $H(·)$ 操作。然而，序列的分割补丁之间没有交互。为了补偿时间感受区域的减少并维持时间信息流，我们引入了门控循环连接（图 6(b) 中的蓝色箭头）来连接补丁的输出：

$$ h_{i+1} = tanh(a_1h_i+β_1) ⊙ sigmoid (a_2h_i+β_2)+h_{i+1}, (6) $$

其中 $α_1$、$α_2$、$β_1$ 和 $β2$ 是循环门的学习参数，⊙ 是点积。最后，${\mathbb D}$的隐藏特征序列生成为

$$ ℏ = \mathcal H({\mathbb D}, ps) = (h_1, h_2, ..., h_{N/ps}). (7) $$

下面我们就来介绍一下Internal-MAFE中的两个关键模块：

分层堆叠（Hierarchical Stacking）。首先，我们通过指定补丁大小列表 $L_{ps}$ 来确定Internal-MAFE的整体层次结构。例如，在图 6(b) 的右半部分，我们指定 $L_{ps} = {6, 2}$ 和输入序列的大小 $\vert{\mathbb D}\vert = 12$。这意味着我们将堆叠一个两阶段的Internal-MAFE，并且阶段1使用最大的补丁大小$ps = 6$（参考算法2的第1行）。然后，我们根据操作 $H(ℏ^0, 6)$ 获得该阶段的特征序列 $ℏ^1$ ，其中 $ℏ^0$ 是通过细粒度增强从 $\mathbb D$ 中导出的（第2~3行）。接下来，在第2阶段，我们对前一阶段输出的特征序列重复相同的操作，即 $ℏ^2 = \mathcal H(ℏ^1, 2)$（第5∼8行）。$ℏ_1$、$ℏ_2$分别表示 $\mathbb D$ 在不同尺度上的注意特征语义。 为了捕获这些多尺度语义，我们的直觉是连接每个阶段的所有特征序列，然后通过 DNN（全连接神经网络）层映射到最终表示（第12行）。在Internal-MAFE的实现中，我们首先在每个阶段将该阶段的特征序列聚合为单个特征序列，然后通过跳过连接获得最终表示的最短路径（第9∼11行）。

细粒度增强（Fine-grained Augmentation）。继续前面的例子，当第一阶段的patch大小为6时，细粒度信息将会丢失，因为每个patch只进行一次特征提取操作。但是，我们也不能直接将其转换为 $L_{ps} = \lbrace 2, 6\rbrace$，因为这会导致第一阶段的每个patch仅具有有限的接收字段，无法为下一步提取足够的信息。因此，在不影响下一阶段的情况下，弥补上述信息损失是很自然的。具体方法如图6(b)左半部分所示。 也就是说，我们从补丁大小列表 $L_{ps}$ 中选择最小的补丁大小（在本例中为 2）并获得 $ℏ^0 = \mathcal H({\mathbb D}, 2)$。然后，$ℏ^0$ 将使用原始输入数据执行跨尺度嵌入（CSE），类似于External-MAFE中的融合算子。

4.2 MAFE based Gaussian Process Regression

高斯过程回归（GPR）可以很好地对不确定性进行建模，对于时间序列预测的每个时间戳都可以获得其高斯分布表示，如3.2节所述。给定用于训练的整个需求时间序列数据 $D =⟨d_1, d_2, · · · d_K⟩$，我们使用大小为 $H$ 的滑动窗口生成 $N$ 个子序列 $S = ⟨S_1, S_2, · · · , S_N ⟩$ 与 , 其中

$$S_i = ⟨d_i, d_{i+1}, · · · d_{i+H-1}⟩.$$

对于子序列$S_i$，我们定义其未来需求$d_{i+H}$作为其标签，并在历史子序列$S_i$和时间预测观测值$d_{i+H}$之间建立时间相关性系列预测。换句话说，我们有 $N$ 训练数据 $\lbrace S_i, d_{i+H} \rbrace_{i=1}^N$ ，其中 $d_{i+H}$ 作为标签。这样，我们就可以使用方程 3 对联合分布进行建模。

在我们的方法中，我们利用高斯过程回归中学到的多尺度特征。 具体来说，我们不使用从需求时间序列导出的子序列$S_i$，而是让子序列首先经过MAFE以获得相应的多尺度特征$MAFE(S_i)$。 然后，我们获得训练数据 $\lbrace MAFE(S_i), d_{i+H}\rbrace_{i=1}^N$ ，用于方程 3 中构建联合分布。 GPR通过损失函数实现预测值 $\hat d_{i+H}$ 与预测观测值 $d_{i+H}$ 之间的误差，从而优化多尺度注意特征提取器和核函数中的参数。

给定一个新的子序列 $S^\ast$ ，使用方程4推理的目的是预测它的未来需求分布。类似地，我们使用 $MAFE(S^\ast)$ 作为方程4中的输入，来推导未来的需求分布。

5 THE SCALER

有效且高效的自动伸缩策略对于云资源的弹性伸缩至关重要，因为它有助于控制资源成本并防止QoS损失。图7展示了我们框架的概述，包括概率需求预测、MDP（马尔可夫决策过程）、优化器（Optimizer）和扩展决策执行器（Scaling Decision Executor）。 特别是，我们的框架以概率需求预测 $\mathbb{\hat W}_t$ 作为输入，这使得不确定性意识成为可能。随后，我们将用户需求扩展问题制定为马尔可夫决策过程，以进一步捕获环境中存在的不确定性。接下来，考虑到MDP优化是一个无限贝尔曼方程优化问题，我们引入了Receding Horizon最优框架，它将无限时域中贝尔曼方程的解转换为有限时域中的随机规划解，使我们能够找到最优解逼近贝尔曼方程最佳解的策略。最后，根据策略，我们的框架通过考虑每个实例的启动、运行和耗尽来进行扩展规划，以平衡实例成本和QoS。

5.1 Markov Decision Process

一般来说，马尔可夫决策过程（MDP）可以定义为5元组 $(S,A,r,p,γ)$，其中 $S$ 表示状态空间，$A$ 表示动作空间，$p$ 表示转移概率，$r$ 表示奖励，$γ ∈ [0, 1)$ 是折扣因子 [45]。为此，当给定 $s ∈ S$ 和 $a ∈ A$时，$r(s, a)$ 表示期望奖励, $p(s'\vert s,a)$ 是从状态 $s$ 采取动作 $a$ 达到状态 $s'$ 的概率。策略用于选择 MDP 中的操作，用 $π$ 表示。基于MDP背后的直觉，我们将扩展问题表述为MDP。考虑到概率需求预测（参见第 4 节），我们的目标是学习最佳 Scaler（即策略 $π$）以不断平衡实例成本（即启动、运行和耗尽成本）和 QoS。目标是保持较低的实例成本和较低的QoS损失。

5.1.1 MDP for Autoscaling

考虑到现实世界的业务场景，我们将扩展策略的MDP制定为：

状态空间 $S$：状态 $S_t = (x_t, l_t, sd_{1t}, sd_{2t}, sd_{3t}) ∈ S$ 表示时间戳 $t$ 时云的状态，其中 $x_t ∈ N^ +$是时间戳 $t$ 时正在运行的实例数量，$l_t$ 表示在 $t$ 时间之前由于资源配置不足而无法提供的实例数量。需要说明的是，ECS云计算平台有一个独特的功能：实例可以在“draining期间”重新启动，而不会产生任何额外的scaling成本。因此，跟踪这些实例并确定时间戳 $t$ 处于draining阶段的实例数量非常重要。通常，一个实例的draining阶段持续三个时间段。因此，我们使用 $sd_{1t}$、$sd_{2t}$、$sd_{3t}$ 分别表示处于draining阶段的第1、第2、第3个时间戳的实例数量。

动作空间 $A$：给定状态 $S_t$，我们定义动作空间 $\mathbb A_t(S_t)$ 为 $A_t := \lbrace λ_t, η_t, β_t\rbrace ∈ \mathbb A_t(S_t)$。特别是，在每个时间戳 $t$，决策者应该执行以下两个操作：（1）为了实现我们的扩展策略，我们使用名为 $λ_t$ 的二进制变量在每个时间戳做出决策。该变量将采用0或1值来表示实例的启动或耗尽。 我们还引入了一个名为 $η_t$ 的正整数变量，它将表示在 $t$ 时间启动或耗尽的实例数量。 为此，我们将 $λ_tη_t$ 制定为启动决策，即启动 $λ_tη_t$ 新实例，并将 $(1 −λ_t)η_t$ 制定为容量缩减决策，即在时刻 $t$ 将 $(1 −λ_t)η_t$ 运行实例放入draining阶段。 (2) 我们执行重新扩展决策，将实例draining尽阶段恢复到running阶段，以避免重复重新启动的资源成本。 为此，我们定义变量 $β_t ∈ N^+$ 来表示重新启动决策的数量，约束条件 $β_t ≤ sd_{1t} + sd_{2t}$ 因为重新缩放决策 $λ_t$ 是在时间戳 $t +1$ 处使用。因此，$t$ 时刻的重新缩放实例数应低于 $t$ 时刻的 $sd_{1t}$ 和 $sd_{2t}$ 的耗尽实例数。

成本：实例成本涉及两个关键组成部分，即运行成本和扩展成本。 相比之下，在经典 MDP 中，我们最大化奖励，但在这里我们最小化成本。 为了优化总体成本，降低运行成本非常重要，运行成本可能会受到供应过剩的负面影响，并导致额外的闲置运行成本。 因此，我们在每个时间 $t$ 制定一个成本函数为

$$ Cost(S_t, A_t) = \underbrace {W_1\mathbb E[(x_t-(l_t+w_t-ρ)+)+]}{C_1} + \underbrace {W_2λ_tη_t}{C_2} + \underbrace {W_3sd_{1t}+W_4sd_{2t} +W_5sd_{3t}}_{C_3} (8) $$

其中 $C_1$ 部分表示闲置资源成本。特别地，未处理的用户需求 $l_t$ 和新用户需求 $w_t$ 构成时间戳 $t$ 的总资源需求。当实例总需求小于物理资源 $ρ$ 时，不需要ECS实例。 当总实例需求大于 $ρ$ 时，总需求与物理机实例数量的差值定义为时间戳 $t$ 所需的ECS实例数量，记为

$$need = (l_t + w_t − ρ)_+$$

同样，在时间戳 $t$ 处，当实例供应量 $x_t$ 小于或等于 $need$ 时，不会产生空闲成本，而当 $x_t$ 大于 $need$，$x_t$ 与 $need$ 之间的差值定义为超额配置的资源量，即资源闲置成本，记为

$$idleCost = (x_t - need)_+$$

由于 $w_t$ 是概率分布，因此实例空闲成本被描述为 $\mathbb{E}[idleCost]$ 。此外，$C_2$ 和 $C_3$ 部分表示缩放成本。 特别地，$C_1$ 部分使用期望 $\mathbb E[idleCost]$，由于预测的用户需求 $w_t$ 是不确定的，$C_2$ 部分代表横向扩展成本，$C_3$ 表示不同draining阶段的draining成本。$W_1$、$W_2$、$W_3$、$W_4$ 和 $W_5$ 是每个成本的系数参数。此外，我们引入了容忍因子 $d$，以实现更灵活的策略，平衡实例成本和 QoS，其中 $d ∈ [0, 1]$。

5.1.2 State transition equation

在 $t$ 时刻，当 $A_t := \lbrace λ_t, η_t, β_t\rbrace ∈ \mathbb A_t(S_t)$ 时，状态 $S_t = (x_t, l_t, sd_{1t}, sd_{2t}, sd_{3t})$ 将在 $t+1$ 时刻更新为 $S_{t+1} = (x_{t+1}, l_{t+1}, sd_{1,t+1}, sd_{2,t+1}, sd_{3,t+1})$。我们将更新过程表示为如下

$$ \begin{aligned} &x_{t+1} = x_t + λ_tη_t + (λ_t-1)η_t + λ_tβ_t &(9a) \ &sd_{1,t+1} = (1 - λ_t)η_t &(9b) \ &sd_{2,t+1} = (sd_{1t} - λ_tβ_t)+ &(9c) \ &sd{3,t+1} = sd_{2t} - (λ_tβ_t - sd_{1t})+ &(9d) \ &l{t+1} = \mathbb{E}[((l_t + w_t − ρ)+ - x_t)+] &(9e) \end{aligned} $$

其中方程(9a)描述了可用自动缩放资源的更新过程，等式：(9b)到(9d)描述了不同阶段draining资源的更新过程，(9e)表示未满足实例需求的更新过程。

5.2 Optimizer

将缩放公式化为MDP后，下一步就是通过优化器找到最佳的缩放策略，包括策略学习、价值函数估计以及采样和搜索。

5.2.1 Policy learning

据我们所知，策略学习的目的是将状态 $S_t$ 投影到一组最优策略，该策略由 $π^\ast = \lbrace A_1^\ast, A_2^\ast, ..., A_i^\ast\rbrace ∈ Π$ 给出，并且具有马尔可夫和确定性策略 $Π$ 的可用性。为此，我们最小化无限域中的总期望成本，其公式为

$$ \begin{aligned} &Cost^*(S_1) = \min_{π∈Π}{\mathbb E[\sum_{t=1}^{\infty}{Cost(S_t, A_t^π(S_t)|S_1)}]} &(10) \end{aligned} $$

其中 $S_1$ 是系统的初始状态。贝尔曼方程对应的值函数为

$$ \begin{aligned} &V_t(S_t) = \min_{A_t∈\mathbb{A}\approx(S_t)}{Cost(S_t,A_t)+\mathbb{E}[V{t+1}(S_{t+1}|S_t,A_t)]} &(11) \end{aligned} $$

其中$V_t(S_t) = \mathbb{E}[\sum_{t=t'}^{\infty}{Cost(S_{t'}A_{t'}\vert S_t)}]$是系统从时刻 $t$ 开始的最佳期望成本，最优期望成本满足$V_1(S_1)=Cost^*(S_1)$。然而，据我们所知，直接求解无限域中的价值函数[21]以获得最佳策略是非常困难的。为了避免这种情况，我们借用模型预测控制（MPC）[3]中前瞻性优化背后的直觉来提供近似解决方案。

5.2.2 Value Function Estimation

正如第5.2.1节中提到的，直接求解方程具有挑战性，例如(11)在无限域中。为此，我们使用前瞻优化（即后退地平线最优receding-horizon optimal）来逼近价值函数，首先将无限域截断为有限的 $F$ 个horizons，然后进行后退地平线操作来估计有限域中层位的每个值，就可以当作未来 $F$ 步的最佳扩缩容策略。一般来说，我们在未来的有限视野（即 $F$ 步）中求解随机规划模型，以逼近时间戳 $t$ 处的最优策略。最后，我们对所有层位的值求和，表示为 $V_t(\hat{S}_t)$，作为 $V_t(S_t)$ 的值。 然而，我们只是采取了第一步作为我们当前的扩展策略。 具体来说，我们开发了相应的模型如下

$$ \begin{aligned} &\min{\sum_{i=0}^{F-1}{Cost(t+i)}} \ 满足 &x_{t+1} = x_t + λ_tη_t + (λ_t-1)η_t + λ_tβ_t &(12a) \ &sd_{1,t+1} = (1 - λ_t)η_t &(12b) \ &sd_{2,t+1} = (sd_{1t} - λ_tβ_t)+ &(12c) \ &sd{3,t+1} = sd_{2t} - (λ_tβ_t - sd_{1t})+ &(12d) \ &l{t+1} = \mathbb{E}[((l_t + w_t − ρ)+ - x_t)+] &(12e) \ &β_t ≤ sd_{1t} + sd_{2t} &(12f) \ &l_t ≤ E[w_td] &(12g) \ &x_t,sd_{1t},sd_{2t},sd_{3t},β_t,η_t,w_t ∈ N^+ &(12h) \ &λ_t ∈ \lbrace0,1\rbrace &(12i) \ &d ∈ [0,1] &(12j) \end{aligned} $$

其中(12a)至(12e)表示每个状态变量的状态转移方程。等式(12f)确保每个重新启动决策小于当前处于第一和第二draining阶段的实例的总和。接下来，等式(12g)将每个时间戳 $t$ 未满足的 ECS 需求限制为通过容差 $d$ 调整的固定值，这导致至少 $100 · (1 − d)%$ 满足 ECS 需求。如果我们想要优先考虑QoS损失而不是实例成本，我们可以将 $d$ 设置为0，这意味着未满足实例的数量 $l_t$ 不能大于0。通过改变容忍因子 $d$，可以灵活地允许不同级别的QoS损失。最后，等式(12h)到(12j)定义了每个变量的性质。

5.2.3 Sampling and Searching

为了通过在时间戳 $t$ 求解未来有限视野（即 $F$ 步骤）中的随机规划模型来近似最优策略，我们通常使用蒙特卡罗采样将随机约束转换为线性约束。然而，这可能会导致最终模型中出现许多额外变量，从而使优化变得更加复杂。幸运的是，随机约束（方程（12g））的左侧是单调递减的。随着 $x_t$ 的增加，左侧的期望减小，因此可以将随机约束转换为 $x_t$ 上的线性约束。我们提出了一种算法（参见算法3），该算法使用采样和搜索来近似求解

$$\mathbb E[((l_{t-1}+w_t-ρ)+-x_t)+] = \mathbb E[w_td]$$

导致 $x_t > x_t^\ast$

如算法3所示，我们使用蒙特卡洛方法采样$M$个样本$w_t^m，m = 1, 2, 3...M$。 特别是，我们使用 $$ \sum_{m=1}^{M}{((l_t+w_t-ρ)+-x_t)+/M} $$ 近似 $$\mathbb E[((l_t+w_t-ρ)+-x_t)+]$$ 考虑到 $$\mathbb E[((l_t+w_t-ρ)+-x_t)+]$$ 是分段线性且单调递减的，其斜率落在 $\lbrace l_{t-1}+w_t^m-ρ \rbrace_{m=1}^M$ 的范围内。在这种情况下，当 $\mathbb E[w_td]$ 出现在相应的段中时，我们就可以找到最优的 $x_t^\ast$。 由于采样排序阶段的时间复杂度为 $O(MlogM)$ 和搜索阶段的线性时间复杂度，算法3的整体时间复杂度为 $O(MlogM)$。 这使得我们的方法具有高度的可扩展性。最后，我们利用SciPy[36]等成熟的求解器以及其他类似的求解器来获得最优动作 $A_t^\ast$。

6 EXPERIMENTAL EVALUATION

6.1 Evaluation of Forecasting

6.1.1 Experimental Setup

数据集。我们考虑具有不同特征的3个公共数据集和3个私有商业数据集：

（1）ETTh1、ETTm1（电力变压器温度）2：ETTh1每1小时进行一次观测，ETTm1每15分钟进行一次观测。每个观测值由6个功率负载特征组成，使其成为6个变量时间序列。训练/验证/测试数据涵盖12/4/4个月。

（2）Weather3：该数据集包含2010年至2013年美国近1,600个地点的当地气候数据，每1小时收集一次数据点。每个数据点由目标值“湿球”和11个气候特征组成。训练/验证/测试数据涵盖28/10/10个月。

（3）阿里云：私有业务数据包括来自中国3个城市杭州（Cluster-HZ）、上海（Cluster-SH）、北京（Cluster-BJ）的3个阿里云集群的资源需求时间序列。所有私营企业数据采集时间为2022年11月1日至2022年11月30日，采样频率为1分钟。与上述数据集相比，该数据集的采样粒度要小得多。训练/验证数据涵盖11月1日至11月25日，测试数据涵盖11月26日至11月30日。

基线。由于ARIMA等经典模型和基本RNN/CNN模型的性能相对较差，如[48]所示，我们主要包括三种最先进的基于Transformer的模型和一种概率预测模型进行比较，即FEDformer[49] 、Triformer[10]、Informer[48] 和GP作为基线模型。

指标。我们考虑3种随机训练和验证设置。结果是3次运行的平均值。对于所有数据集，我们进行标准化，使变量均值为0，标准差为1。我们使用以下评估指标，即预测的MAE和MSE值来衡量预测误差。此外，加权分位数损失，也称为ρ-risk，被广泛用作概率时间序列预测的指标。对于给定的分位数 $ρ ∈ (0, 1)$，$q_t^{(ρ)}$ 表示 $y_t$ 的预测ρ分位数。

$$ ρ-risk=2\frac{\sum_i{[\mathbb I_{q_t^{(ρ)}\le y_t}(1-ρ)\vert q_t^{(ρ)} - y_t \vert + \mathbb I_{q_t^{(ρ)}\le y_t}ρ\vert q_t^{(ρ)} - y_t \vert]}}{\sum_i{\vert y_i \vert}} (13) $$

实验配置。MAFE的参数 $L_{ps} = \lbrace8, 3, 2\rbrace$ , $L_{scale} = \lbrace4, 2, 1\rbrace $。实验的预测任务中， $H=288$。最后，由于真实场景的业务需求，我们统一设置预测步长F满足一小时（例如，如果数据的采样频率为1分钟，则F为60）。

6.1.2 Experimental Results and Analysis

表1和表2总结了所有方法在多个数据集上的时间序列评估结果。最好的结果以粗体突出显示。如表1所示，我们可以观察到：（i）MagicScaler的预测精度几乎优于所有现有的最先进算法；(ii)MagicScaler的性能显着优于Triformer、FEDformer和Informer，因为它的多尺度特征提取器可以全面捕获不同尺度的模式，从而提高预测精度；(iii)MagicScaler在MAE上优于GP，平均下降 64.3%，这得益于深度神经网络强大的特征提取能力；(iv)MagicScaler在阿里云数据集上的出色表现表明，与其他基线模型相比，我们的模型更适合现实场景。

预测不确定性的量化结果如表2和图8所示。我们可以得到：（i）MagicScaler在0.5-risk和0.9-risk指标方面优于GP；(ii)从图8的可视化结果来看，MagicScaler 预测的置信区间（用蓝色阴影标记）能够在很大程度上覆盖真实值，甚至尖峰状点也能很好地覆盖在置信区间内。

6.1.3 Ablation Study

为了验证MagicScaler关键组件的有效性，我们分别对External-MAFE、Internal-MAFE和MAFE的Cluster-HZ数据集进行了消融研究。我们可以得出这样的结论：所有组件都在一定程度上对最终的最先进结果做出了贡献。如表3所示，MagicScaler超越了去除MAFE的模型，证明了MAFE在提取多尺度特征信息和增强模型预测性能方面的有效性。通过External-MAFE和Internal-MAFE的比较可以看出，External-MAFE更擅长捕获不同尺度的特征信息。值得注意的是，w/o Internal并不意味着该组件被完全删除，而是将其层次结构转变为单个阶段，而不执行细粒度的增强操作。这种方法相当于将Internal-MAFE转换为基于注意力的特征提取器，用于删除组件。

6.1.4 Eficiency

图 9 显示了MagicScaler与FEDformer和Informer的训练时间（秒/epoch），其中我们比较了5次运行的平均实际效率。当改变 $H$ 时：(i)MagicScaler由于其线性时间复杂度特征提取器比FEDformer和Informer 更快；(ii)MagicScaler和FEDformer比Informer更稳定。当改变 $F$ 时：(i)MagicScaler是所有设置中最快的；(ii)Informer的训练时间比MagicScaler和FEDformer长得多。

6.2 Evaluation of Autoscaling

基线。在本节中，由于阿里云环境的独特性，很难将现有的自动伸缩方法公平地迁移到我们的场景中，因此我们在真实集群工作负载数据上比较以下伸缩方法。

• Passive：被动扩展方法是一种被动方法，涉及根据每个时间戳的客户需求做出资源启动和耗尽决策。虽然此方法可能具有较低的资源成本，但它也与较高级别的QoS损失相关。
• Statistics：这是一种自动缩放策略，它利用过去一周时间 $t$ 的数据来生成统计数据，然后使用这些统计数据来预测未来值并使用缓冲区值执行自动缩放（类似于第1节中描述的保守策略）。
• MagicScaler-D：MagicScaler-D 是MagicScaler 的确定性版本，它将概率ECS 需求预测的平均值作为输入，并返回最佳扩展决策。特别是，我们为MagicScler-D设置 $F = 12$ 和 $d = 0$，这对于优先考虑超额配置实例以防止QoS损失的云服务提供商来说很有意义。
• MagicScaler：MagicScaler将概率需求预测作为输入，同时保持与MagicScaler-D相同的参数设置。

6.2.1 Overall Performance Evaluation for Autoscaling

我们比较了统计、反应式缩放方法（被动）、MagicScaler及其变体在阿里云的三个数据集（集群HZ、SH和BJ）上的性能。图10说明了我们的评估结果。第一个观察结果是，MagicScaler-D和MagicScaler在Cluster HZ和Cluster SH上的资源成本和QoS损失方面优于其他产品。具体来说，MagicScaler的QoS损失显着降低，与Passive和统计相比，QoS损失仅为11.7%和4.9%，但资源成本比Passive和统计增加了1.2%和43.9%。值得注意的是，尽管Statistics在cluster-SH上的资源成本指标上具有显着优势，但这却导致了QoS的显着损失，这对于云服务提供商来说是不可接受的。可见MagicScaler能够很好地平衡资源成本和QoS损失。我们还观察到MagicScaler-D在Cluster BJ上的表现很差，四天的资源成本几乎为零，并且QoS损失明显高于Passive和Statistics。这是因为Cluster BJ中的物理资源覆盖了几乎所有的ECS需求，而MagicScaler-D无法捕获突发的ECS需求，导致QoS严重损失。相比之下，MagicScaler在Cluster BJ上表现良好，因为它可以捕获突发的ECS需求（即高不确定性），从而确保较低的QoS损失。最后，我们发现统计数据对于不同数据集的鲁棒性较差。尽管与Passive相比，Statistics在Cluster-HZ上的表现相当好（图11(a)和11(b)），但在图11(c)和11(d)中，它显示出相当低的资源成本和显着更高的QoS损失。这表明Statistics对于不同的ECS需求数据集没有表现出良好的鲁棒性。相比之下，我们的MagicScaler在不同的ECS需求数据集上具有良好的鲁棒性。

6.2.2 Parameter Sensitivity Analysis

7 CONCLUSION

在本文中，我们提出了一种称为MagicScaler的新型预测自动缩放框架，它由预测器和缩放器组成。一方面，预测器利用了两种成功预测方法的优势：多尺度注意力机制，可有效捕获复杂的多尺度特征；高斯过程回归，可准确量化预测不确定性。另一方面，缩放器通过使用具有随机约束的复杂损失函数来考虑量化的未来需求不确定性，从而允许在运行成本和QoS违规之间进行灵活的权衡。需求预测和自动扩展的大量实验证明了我们提出的框架与其他广泛使用的基线方法相比具有优越的性能。特别是，MagicScaler的有效性已经通过阿里云的真实数据得到了证明。这表明我们的框架具有显着提高云计算系统中自动缩放的效率和有效性的巨大潜力。