·论文链接: link.

摘要Abstract

主机负载的预测对于云计算对于提高资源利用率和达成服务级别协议至关重要。但是，在主机中准确预测主机负载仍然是一个挑战，因为负载类型会有所不同 。此外，选择用于主机负载预测的指标也是一项艰巨的任务。云系统中的指标如此之多，很难确定哪些指标将是有用的。为了解决这些挑战，本文提出了一种有效的深度学习模型，称为Sibyl，以提高预测的准确性和效率。 Sibyl包括两个部分：指标选择模块和神经网络训练模块。 Sibyl首先通过过滤不相关的指标来选择指标。之后，Sibyl应用了功能强大的神经网络模型，该模型以双向LSTM构建，可提前一步预测实际负载。我们使用Sibyl分析来自数据中心176台机器的40天负载跟踪。实验表明，Sibyl可以减少训练指标，同时保持预测准确性。此外，与其他基于自回归积分移动平均和长短期记忆的最新方法相比，Sibyl大大提高了预测准确性。

关键词Keywords

云计算·主机负载预测·时间序列分析·双向LSTM

1 介绍Introduction

主机负载预测在Cloud系统中对于指导负载平衡和保证服务级别协议（SLA）至关重要。随着云计算变得越来越流行，将不同类型的应用程序（例如Web服务器或批处理作业）部署到云系统中。但是，由于云的复杂度、大小和范围的增长，无法始终满足应用程序的资源需求，这导致违反SLA并严重降低了服务性能。主机负载的准确预测可以帮助改善资源配置并增强应用程序性能。 但是，在Clouds中选择用于主机负载预测的指标具有挑战性。许多云计算运营商提供了强大的监视工具（例如Google Stackdriver，Microsoft Cloud Monitoring，Amazon CloudWatch）。受益于这些工具，我们可以监视与主机负载相关的大量系统级指标。这些指标对于更好地理解服务性能以及预测负载的行为至关重要。但是很难确定哪种度量标准将是有用的，并且出于不同的目的，我们必须选择不同的度量标准。

由于负载的多样性，准确预测主机负载仍然是Cloud系统中的一个挑战。不同种类的负载具有不同的工作模式。有关负载预测的大多数先前工作都集中在基于传统时间序列的预测模型上，例如移动平均，自回归，自回归综合移动平均（ARIMA）和机器学习算法，例如隐马尔可夫模型[6-8]。假设未来的模式保持不变，这些模型可以很好地应对某些负载（例如批处理作业）[4]。但是，工作负载（例如Web服务器）的性能可能会急剧波动。这些模型无法处理这些复杂的观察结果。长短期记忆（LSTM）神经网络已被广泛用于解决此非线性问题[9,12,23]。由于LSTM模型使用非线性函数，因此可以更好地应对新模式的出现。但是LSTM仅在一个方向上处理数据，因此，它只能获得训练指标的部分功能，而错过了提高预测准确性的机会。

在本文中，我们设计并构建了Sibyl，这是一种有效的深度学习模型，用于选择指标并准确预测Cloud中的主机负载。 Sibyl由两个核心模块组成：（1）度量选择模块（MSM），可通过过滤掉不相关的度量来降低度量的维数；（2）应用双向长期短期记忆（BILSTM）的神经网络训练模块（BNT） 以捕获所选指标的特征并建立预测模型。

模块（1） 允许我们选择相关度量。基于度量的形状相似性，MSM将查找具有相似模式的度量，并过滤出无用的度量。 在巨大的指标空间中，有些指标与我们关注的指标无关。携带冗余信息的不相关度量标准对预测没有贡献。我们可能只需要训练几个指标而不是整个指标的预测模型。此外，降低指标的维数对于节省监视和存储额外指标的成本至关重要。

模块（2） 可以获取MSM选择的指标的特征，并准确预测主机负载。 BNT是使用BI-LSTM网络构建的。 BI-LSTM已被广泛用于文本分类和语音识别。据我们所知，我们的工作是第一个将BI-LSTM用于Cloud上下文中的主机负载预测的工作。我们建立了深层的BI-LSTM网络来双向处理数据，以更好地预测负载的趋势和大小。 BILSTM网络是端到端模型。它可以自动保存有用的数据信息。与基于LSTM的最新方法相比，我们的神经网络可以更好地捕获度量的特征并使预测更加准确。

我们使用具有176台机器的数据中心的40天负载跟踪来实施和评估模型。负载跟踪位于https://github.com/UCASzhangxiaofan/Host-load-trace。通过滤除无用的指标，我们在保持预测准确性的同时降低了训练指标的维数。与ARIMA和LSTM等其他最新方法相比，Sibyl具有更好的性能，并且预测误差最低。此外，Sibyl权值轻，可以适应各种需求。

本文的其余部分安排如下。第2节讨论了在Clouds中进行负载预测的相关工作。Sibyl的设计和实现在第3节中介绍。第4节介绍了实验评估。最后，我们在第5节中完成这项工作。

2 相关工作Related Work

有关主机负载预测的方法很多。流行的线性自回归模型，例如线性回归和ARIMA，已被广泛用于许多系统领域的负荷预测。 Nazarko等介绍一种基于ARIMA模型的预测模型，用于配电系统中的负荷预测。 Tran等使用ARIMA时间序列模型来预测用于自适应I / O预取的I / O请求的时间模式。通过使用基于卡尔曼滤波器的一般似然比（GLR）检验，Zhu等人估计ARIMA的参数，并将实际数据与预测数据进行比较，以发现是否发生异常。但是，因为某些类型负载的剧烈波动会显着影响预测精度，传统的基于时间序列的预测模型在云环境中表现不佳。

机器学习算法已被用来克服传统的基于时间序列的预测模型的局限性。 Di等使用贝叶斯算法对长期的工作量进行预测。由于该方法使用指数分段模式，因此存在局限性，并且随着分段长度的增加，平均负载无法反映负载的波动。 Dabrowski等使用网格系统的马尔可夫链模型进行主机负载的预测。 Akioka等结合马尔可夫模型和季节变化来做出更好的预测。 Byun等使用具有三个状态的马尔可夫链作为资源，并预测每30分钟状态之间的转换速率。但是云中的工作量比网格系统中的工作量具有更大的波动，这使得这些模型不再适用。神经网络具有强大的非线性泛化能力，在云中的负载预测上具有更好的性能。文献[9]中引入了进化神经网络来预测云数据中心的能源负荷。薛等设计了一个基于自相关特征和人工神经网络的框架，以提高负载的预测精度。 文献[11]使用基于多元时间序列和加权神经网络的短期负载预测方法。然而，这些神经网络无法学习长期依赖关系，这对于做出准确的预测很重要[22]。 LSTM旨在避免此问题。在[12,23]中已使用它来预测主机负载和服务器性能。但是LSTM只能捕获度量标准的部分功能，因为它仅在一个方向上处理数据，因而错过了提高预测准确性的机会。

3 设计与实现Design and Implementation

系统总览System Overview

Sibyl的系统架构如图1所示。Sibyl是基于历史性能指标的自动预测器，用于预测影响服务SLA的主机负载。 Sibyl的设计包括两个部分：指标选择模块（MSM）和Bi-LSTM网络训练模块（BNT）。与先前的工作不同，我们设计MSM并在训练之前使用它来减少指标，因为并非所有指标都与主机负载有关。 **MSM可以找到具有类似模式的指标，并将整个指标分为两组，一组与主机负载相关，另一组与主机负载无关。**实验表明，Sibyl可以在保持预测准确性的同时减少指标。凭借强大的非线性泛化能力，**BNT可以从训练指标中了解更多信息，并自动生成预测模型。**如实验所示。与ARIMA和LSTM相比，Sibyl神经网络可以对负载趋势和大小进行更准确的预测。

Sibyl的工作过程如下。我们首先使用监视工具来收集性能指标并将其存储在数据库中。在训练之前，性能指标将首先被送入MSM。 MSM将分析指标，并通过聚类将其分为两组，以便将行为相似的指标分组在一起。相关度量用作BNT的输入。 BNT将使用BI-LSTM网络获取训练指标的特征并生成训练后的预测模型。

3.1 指标选择模块（MSM）

降低指标的维度可以帮助我们过滤掉不相关的指标，从而可以节省监视额外指标的成本，同时保持预测准确性。研究指标对于主机负载预测非常重要。但是，总是很难从受监控的巨大空间中选择有用的指标，并且出于不同的目的，我们将选择不同类型的指标。例如，我们可能更关心网络I / O，以便更好地了解Web服务的性能，另一方面将通过内存使用情况来安排批处理作业。指标维度的增加也会导致预测负载变化的困难。

我们设计了一个指标选择模块（MSM），以找出用于主机负载预测的有用指标。 MSM应用k-Shape（一种用于基于形状的时间序列聚类的新颖算法）来帮助用户将大量指标转化为有用的见解。 k-Shape是一种与域无关，准确且可扩展的用于时间序列聚类的算法，其距离度量对于缩放和平移而言是不变的。还有其他特征降维方法，例如主成分分析（PCA）和随机抽样（RS）。但是，由于数据具有线性可分离性，PCA的有效性受到限制，而RS无法找到数据的隐藏特征，这在主机负载预测中必不可少。 k-Shape依赖于迭代精化过程，该过程可以对指标数量进行线性缩放，并生成均匀且分离良好的群集。

k-Shape应用了一种新颖的距离度量标准，即基于形状的距离（SBD），以比较指标的时间序列。 SBD基于**互相关（NCC）**的规范化版本。互相关是时滞序列相似性的一种度量。它比较时间序列之间的一对一点。给定两个序列x和y，SBD将找到互相关（NCC）最大化的位置ω。

基于SBD，k-Shape在每次迭代中都会计算新的聚类质心。这些质心用于更新对聚类簇的分配。

由于k-Shape是基于形状的时间序列聚类方法，因此即使一个时间维度在另一个时间维度之后，它也可以找到两个时间序列的相似性，这在选择用于主机负载预测的指标时十分重要。有时，一个指标的变化不会立即对其他指标产生影响。例如随着处理程序开始工作，占用更多内存以加载数据后，CPU使用率可能会增加。

此外，在k-Shape中，每个指标的时间序列将先进行规范化然后再进行比较，这在云系统中非常重要。由于不同的指标可能具有不同的单位，因此我们无法直接进行比较。

3.2 Sibyl网络架构Sibyl Network Architecture

如实验所示，由于某些类型的主机负载的剧烈波动，传统的线性自回归模型无法处理这种复杂的观测结果。与使用线性基函数的传统负载预测模型不同，神经网络使用非线性函数来更好地解决此问题。

Sibyl网络训练模块（BNT）使用MSM选择的度量作为输入来训练BI-LSTM网络。 BI-LSTM是一种特殊的递归神经网络。递归神经网络（RNN）已在时间序列分析中得到广泛使用。RNN是一种包含循环结构的网络，可以维护历史信息，这使模型可以根据历史信息的特征预测当前输出。 但是由于梯度消失的问题，传统的RNN无法通过长距离训练时间序列。但是，在Clouds中通常会有时间很长的时间序列。我们可以使用长短期记忆（LSTM）来解决此问题。 LSTM网络是一种特殊的RNN，能够发现数据中的长期依赖关系。 但是LSTM有一个缺点。由于LSTM只能单方向处理数据，而忽略数据变化的连续性，因此LSTM只能捕获指标的部分特征。

Bi-LSTM可以通过两个单独的隐藏层在两个方向上处理数据来获取更多的信息。图2显示了三个时间步骤中展开的BI-LSTM。
Bi-LSTM公式如下：

UF和WF是输入-前向层的权重矩阵。 UB和WB是输入-反向层的权重矩阵。 VF和VB分别表示输出-前向层和输出-反向层的权重矩阵。f和g是非线性激活函数，例如Logistic-Sigmoid和Tanh-Sigmoid。bF，bB和bO表示前向，反向和输出层的偏置。

我们首先使用Bi-LSTM构建Bi-LSTM网络，然后添加一个Dense层（全连接）进行预测，如图3所示。Dense层可以在保留有用信息的同时将高维转换为低维，如图4所示。

指标的时间序列的组织方式类似于A = [a1，a2，…，an]。例如，训练指标由图3所示的A，B，C，D，E组成，我们预测的主机负载为E。同一时间点t的训练指标的历史数据为mt = [at，bt，ct，dt，et]。 mt将用于形成Xt。主机负载的实际值是Yt = [et]。look-back是一个重要的变量，它是整数n，代表过去n个时间步训练指标的数据将用于预测目标绩效指标Pt。用户可以独立调整此变量以提高预测准确性。Xt被到送入Bi-LSTM， BI-LSTM中每个神经元的输出Bt将用作Dense层的输入。我们使用Dense层来降维并产生预测值Pt。Dense层公式如下：

其中Qt-n，…，Qt-2，Qt-1表示Bi-LSTM-Dense层的权重矩阵。 bD表示Dense层的偏置。

在网络训练期间，神经网络将连续比较预测值Pt和真实值Yt之间的误差。根据误差对每一层的权重矩阵和偏差进行调整，以更好地捕获历史数据的特征。

3.3 实现Implementation

我们用Python实现了Sibyl。 k-Shape的开源python实现用于对指标进行聚类。我们使用Keras构建我们的BI-LSTM网络。Keras是一个Python库，已广泛用于深度学习的生产中。

为了收集主机的性能指标，我们部署了开源监控工具Open-Falcon。 Open-Falcon已被广泛应用于云环境中，如京东，新浪微博，美团等。 Open-Falcon已经拥有400多个内置服务器指标，用户可以编写插件来收集其自定义指标。Open-Falcon以每分钟的细粒度收集指标。我们使用OpenTSDB后端来存储和提供大量时间序列数据，而不会丢失粒度。我们的系统从OpenTSDB读取数据并将其保存为CSV格式。

4 性能评估Performance Evaluation

我们的实验包括两个部分：评估简化指标的性能以及将预测准确性与其他两个模型进行比较。

所有的指标是从真实的在线云系统中收集的。我们在40天内从在线系统收集了17个性能指标，包括176台计算机的CPU，内存和磁盘。跟踪数据的最佳观察粒度为1分钟。与其他方法一样，我们仅预测CPU负载。我们将负载分为三类：（a）稳定负载，以批处理作业（例如科学计算）部署的机器； （b）周期负载，使用批处理作业部署的计算机，例如MapReduce； （c）抖动负载，使用Web服务部署的计算机，例如nginx。不同类别的主机负载如图5所示。

我们将跟踪数据分为两个持续时间，一个训练时间段（从开始到第39天）和测试时间段（第40天）。训练周期用于训练预测模型，例如，用于计算自回归模型的阶数（时间滞后数）、ARIMA的差异程度、或调整Sibyl网络的神经元权重。测试期用于评估预测模型的有效性。我们使用配备8核Intel Xeon CPU E5-2630-v3处理器和NVIDIA TESLA M40 GPU和24G内存的机器训练和评估我们的预测模型。

为了与其他模型比较预测精度，除了使用我们自己的Sibyl预测模型外，我们还实现了其他两种负荷预测方法，包括自回归综合移动平均（ARIMA）模型和长短期记忆（LSTM）。这些方法已被广泛用于负荷预测中。我们将使用这两个模型以及我们的模型对同一主机负载进行单步预测。

为了评估预测准确性，我们使用两个指标，均方误差（MSE）和均值绝对误差（MAE）。我们用Pi表示模型预测的值，用Yi表示实际观察到的值。

MSE可以用公式（6）计算，MAE可以用公式 （7）表示。其中N是预测时间窗口中预测值的总数。


我们希望最小化MSE和MAE以提高预测准确性。通常，MSE和MAE越小越好。

4.1 简化指标的性能Performance of Reducing Metrics

在训练预测模型之前，我们使用MSM选择有用的指标。 MSM将指标分为两类，一组与目标性能指标相关，另一组无关。我们选择CPU负载作为目标指标，并使用MSM对整个数据集进行聚类。结果示于表1。

我们分别使用由指标选择模块选择的指标和整个指标来训练我们的预测模型。 如图6所示，对于稳定负载，两种方法的MSE均为0.002，而MAE分别为0.032和0.03。对于周期性负载，使用选定指标的错误低于使用整个指标的错误，其MSE为0.04，MAE为0.149。使用整个指标的相应值分别为0.052和0.166。由于整个指标中都有噪音，因此减少指标可以帮助我们提高预测准确性。两种方法在抖动负载的预测中具有相同的MAE0.46，并且MSE大致相同，分别为0.387和0.385。根据结果​​，Sibyl可以过滤掉不相关的指标，而不会降低预测准确性。

4.2 负载预测模型准确率Accuracy of Load Prediction Model

三种方法（包括传统的预测模型ARIMA，先前的最新方法LSTM和我们的方法Sibyl）用于预测三种不同的主机负载。 均方误差（MSE）和均值绝对误差（MAE）用于确定预测性能。

稳定负载： 如图7所示，每种方法在稳定主机负载的预测中表现良好，且预测误差很小。 ARIMA的MSE为0.003，而LSTM的MSE为0.006，而Sibyl为0.002。部署有诸如科学计算之类的批处理作业的计算机往往具有稳定的负载，因为这些应用程序具有固定的工作模式，并且其资源使用量的变化很小。因此，很容易掌握其功能并准确预测主机负载。

周期性负载： 如图8所示，与ARIMA相比，LSTM和Sibyl均获得了预测精度的提高。ARIMA的MSE为0.171，MAE为0.279。LSTM的MSE降至0.104，MAE约为0.241。Sibyl的最低MSE为0.04，而MAE仅为0.149，胜过其他方法。偶尔或周期性出现负载峰值的计算机在Cloud中很常见。在数百万个神经元的帮助下，神经网络具有强大的功能提取能力，可以更好地检测系统状况并预测变化的到达时间。此外，Sibyl大大超过了LSTM，因为如上所述，它可以从数据中学到更多信息。

**抖动负载：**在图9中，我们可以看到Sibyl达到了最佳的预测性能，其MSE为0.387，MAE为0.46。尽管ARIMA表现最差，但其MSE为1.279，MAE为0.817。 LSTM的性能优于ARIMA，MSE和MAE较低，分别为0.735和0.626。随着网络请求的随机到达，具有Web服务的计算机的负载会出现更大的波动。由于负载的工作模式是动态变化的，因此具有线性函数的传统方法不适用于这种复杂的情况。通过使用非线性函数，神经网络可以更好地应对新模式的出现。与LSTM相比，Sibyl在两个方向上处理数据以查找更多隐藏特征并获得较低的预测误差。

5 结论Conclusion

在本文中，我们基于k-Shape和BI-LSTM开发了一种新颖的框架Sibyl，可用于预测主机负载。 Sibyl包括两个模块：指标选择模块和BI-LSTM网络培训模块。我们广泛使用实际负载跟踪来评估Sibyl。实验表明，我们的方法可以在不牺牲预测精度的情况下降低指标的维数。与传统的预测模型ARIMA和使用LSTM的神经网络相比，Sibyl的预测准确性有了显着提高。