Elastic Scheduling for Microservice Applications in Clouds
（云环境下微服务应用的弹性调度）
摘要：
微服务被广泛用于灵活的软件开发。最近，容器已经成为微服务的首选部署技术，因为它启动速度快，开销低。然而，容器层使任务调度和云中的自动伸缩变得复杂。现有算法不适应由虚拟机和容器组成的两层结构，经常忽略流工作负载。为此，本文提出了一种针对微服务的弹性调度(ESMS)，它将任务调度与自动伸缩集成在一起。ESMS的目标是在满足期限限制的情况下最小化虚拟机的成本。具体来说，我们将微服务的任务调度问题定义为一个具有期限约束的成本优化问题，并提出了一种基于统计的策略来确定流工作负载下的容器配置。然后，我们提出了一种基于紧急度的工作流调度算法，该算法可以分配任务并确定可扩展实例的类型和数量。最后，我们将新容器到虚拟机的映射建模为一个变大小的装箱问题，并对其进行求解，以实现虚拟机和容器的集成扩展。通过与现有算法的比较，验证了ESMS在提高交期成功率和降低成本方面的能力。

1 介绍
今天，基于云的软件开发，如SaaS(软件即服务)，已经变得越来越流行，因为它提高了业务敏捷性并降低了软件维护成本。然而，业务需求的多样性和云中的弹性需要具有高可伸缩性和快速开发的软件架构。与传统体系结构相比，微服务通过构造具有独立生命周期的服务和降低服务的粒度，缩短了开发周期，降低了固有的复杂性，提高了可伸缩性。因此，微服务被广泛用于诸如Netflix这样的商业软件。
通常，部署在云中的应用程序需要满足性能要求，如响应时间，但也应该尽可能地降低云资源的成本。因此，在基于微服务的云应用中，任务调度和自动伸缩是需要解决的关键问题。在文献中，任务调度和自伸缩有不同的方法来有效地利用云计算资源。1)在任务调度中，应用程序被描述为一个工作流，其主要主题是调度任务在多个实例上的执行，以优化最大完成时间。当实例数量不足以满足性能需求时，算法会利用云资源创建新的实例，在性能和成本之间进行权衡。然而，扩展规则通常比较简单，不能满足更复杂的扩展需求，例如容器和虚拟机(vm)组成的两层结构的扩展。2)自动伸缩通过阈值或强化学习建立规则或建立性能预测模型，确定满足性能标准的资源数量。与任务调度相比，自动伸缩算法侧重于构建伸缩规则，但却简化或忽略了任务调度。事实上，不同的调度策略会导致不同的资源需求，需要不同的伸缩方案。不结合调度的伸缩算法的预测结果与实际可调度的资源量存在差异。由于资源供应不足，这种差异可能导致性能下降，或者由于过度供应[1]而导致不必要的额外成本。因此，我们有动力将云环境下微服务的自动伸缩与任务调度相结合，在最小化服务部署成本的同时，获得精确的伸缩资源需求，满足服务性能需求。
目前，云中的调度算法大多采用单工作流执行，基于当前工作流或预先设置的参数进行伸缩决策，忽略了流工作负载的动态特性。在流工作负载中，调度算法需要反复执行以服务于连续提交的工作流，而算法无法提前知道所有工作流的特征，如任务的执行时间。由于任务的执行时间会在运行时发生波动，因此调度算法在当前时刻做出的最优伸缩决策，如配置、新服务实例的数量等，并不能保证全局最优。因此，调度算法需要做出决策进行长期优化，以确保流工作负载下的系统性能。
在微服务系统中，容器由于其快速启动和低开销而成为部署微服务实例的首选技术。然而，容器层也给自动伸缩带来了新的挑战。1)云提供商以不同配置的虚拟机方式提供资源，形成两层容器的资源结构。它需要同时在容器层和VM层上进行伸缩，而传统的伸缩算法只适用于单层结构(无论是VM还是容器)。2)由于同一个VM中的容器共享镜像，新添加的容器可以部署在对应镜像的VM上，从而减少镜像的拉取时间和容器的启动时间。因此，缩放算法需要充分利用现有的图像来提高的缩放性能，需要考虑这两个因素来对vm进行缩放，然后在vm上放置实例。
为了解决这些问题，我们提出了一种基于最常用的随需应变模型的弹性调度算法(Elastic Scheduling for Microservices, ESMS)，该算法将任务调度和云中的自动伸缩集成在一起。首先，我们将微服务的任务调度定义为一个具有期限约束的成本优化问题，并使用基于统计的策略来确定流工作负载下的适当容器配置。然后，考虑容器图像的影响，提出了一种基于截止时间分配和紧急性的启发式任务调度算法，确定调度方案和新增容器的类型和数量。此外，为了实现虚拟机和容器的两层扩展，将新容器的部署问题描述为变尺寸装箱问题(VSBPP)。我们使用启发式算法来解决这个问题，并确定vm的伸缩方案和容器在vm上的映射。最后，我们使用真实的工作流应用程序(例如，蒙太奇)和*访问跟踪进行基于模拟的实验。与现有算法(如ProLiS)相比，ESMS被证明能够降低租赁成本并获得最高的满足期限约束的成功率。
本文的主要贡献如下:
1）我们提出了一种融合任务调度和自动伸缩的微服务弹性调度算法。利用基于紧急度的调度算法来获得调度方案，并准确地确定要伸缩的新实例。然后通过两层缩放算法得到缩放方案。
2）为提高微服务流工作负载下的利用率，设计了一种基于统计信息的配置求解算法。生成的配置用于创建新的容器和分配截止日期，以提高截止日期分布的准确性。
3）为了解决虚拟机和容器的两层伸缩问题，在任务调度中考虑了容器映像对容器初始化时间的影响。将自伸缩问题构造为VSBPP，以获得最优的虚拟机伸缩方案和容器部署方案，使虚拟机成本最小化。
通过实际工作流应用的仿真实验，验证了该算法在任务调度和自动伸缩方面的性能优于三种典型的任务调度和自动伸缩算法。
4）本文的其余部分组织如下。第二部分总结了相关工作。第3节定义了基于微服务的云应用的系统模型和弹性调度问题。第4节和第5节分别详细描述了提出的任务调度和自动伸缩算法。第6节介绍实验和评价。第七部分总结了全文。

2 相关工作
2.1 云环境下的任务调度
任务调度是一个著名的np完全问题，多年来一直是研究的热点。不同的目标导致了不同的优化思路，包括响应时间、成本、安全性等。在各种目标中，性能和成本是最受关注的。与传统的分布式系统不同，云通常被认为能够提供无限的资源，拥有更多资源的机器意味着更高的价格。因此，必须考虑性能和成本之间的权衡。云提供商根据使用的时间间隔的数量向用户收费，时间间隔的部分利用率将四舍五入为一个完整的时间间隔。因此，任务调度需要避免浪费时间间隔。
现有的云环境下的工作流调度算法主要分为期限约束的工作流调度和预算约束的工作流调度。
在期限约束的工作流调度中，性能需求表示为工作流的期限，目标是在满足期限约束的情况下使工作流的执行成本最小化。Abrishami等人定义了局部关键路径(Partial Critical Paths, PCPs)，并提出了IC-PCP算法以最小化总代价。Wu等人在HEFT中扩展了向上秩，并定义了概率向上秩。提出了两种工作流调度算法，即ProLiS和LACO。Wu等人提出了一种四步算法MSMD，通过减少虚拟机数量和实例小时来最小化成本。Thiago等人提出了l -粒度方法来加快有截止时间约束的工作流调度。
预算约束的工作流调度可以在用户定义的预算范围内最小化工作流的完成时间。Zheng等人[18]对经典的HEFT[17]进行了扩展，提出了BHEFT，即通过评估备用预算来选择可能的最佳服务。Bao et al.建模了WANG et al.: ELASTIC SCHEDULING FOR MICROSERVICE APPLICATIONS IN CLOUDS 99的微服务性能，并提出了GRCP算法，该算法使用贪婪策略将任务映射到现有或新的实例。Qin et al.提出了剩余最便宜的预算，以满足预算约束，保证解决方案的可行性。
然而，这些研究只关注单个工作流的调度，忽略了更一般的流工作负载和多工作流。云资源可以在多个工作流之间共享，提高资源利用率，降低基础设施成本。前人研究了多工作流调度，但它们局限于资源受限的场景，不适用于云计算。Rimal和Maier提出了多租户云计算的CSWA算法，但只考虑了一次性调度;也就是说，同时提交多个工作流，并在已知所有工作流特征的情况下执行算法，忽略一般的流工作负载。在流工作负载中，多个工作流以不同的时间戳提交，需要在不知道后续工作流信息的情况下重复执行调度算法。在为新实例分配资源时，算法应该充分利用剩余的资源，并考虑后续的工作负载。请注意，工作流中的任务调度与流数据处理中的任务调度不同，在流数据处理中，“任务”被定义为某个操作符的副本，并负责处理数据。因此，流处理中的任务类似于微服务系统中的服务实例，任务调度对应于微服务中的服务实例放置。
许多任务调度算法采用简单的策略向外扩展实例，例如创建最便宜的服务实例或采用基于规则的扩展策略。一个新的实例将直接在VM上创建。但是，在由容器和VM组成的两层结构中，这些策略不能解决如何确定容器的配置、应该创建哪种类型的VM以及应该将VM的新容器放置在哪种位置等问题。虽然部分文献都描述了微服务的两层资源结构，但没有讨论相关的伸缩问题，只考虑了容器的伸缩，忽略了vm的伸缩。

2.2 自动伸缩云
根据方法的不同，自动标度可分为三类:基于规则的方法、时间序列分析方法和模型分析方法。
基于规则的方法被广泛应用于行业，如Amazon EC2。这些方法需要一些阈值或基于先验知识的扩展规则来触发响应动态工作负载的扩展操作。Zheng等人设计了两个基于规则的自动标度器，它们成为了他们的sla感知微服务框架SmartVM的一部分。
时间序列分析使用一组数据点来发现重复模式或预测未来的值，例如未来的请求量或周期趋势，通常是通过机器学习技术。Kan使用二阶自回归移动平均方法预测短时间后的每秒请求量。Fernandez et al.利用五种不同的统计模型来适应四种类型的工作负载。
在模型分析中，建立数学或概率模型来预测性能和作出决策。最典型的例子就是排队论。排队理论被用来对微服务的响应时间和供应资源进行建模。此外，基于马尔可夫过程的强化学习、回归模型和基于Petri网的分析模型也是应用广泛的技术。
但上述算法不涉及具体的调度方法，会影响系统性能。这些模型的结果可能与实际调度结果不一致，不能准确反映实际对资源的需求。在中，作者提出了几种调度算法与基于规则的伸缩算法相结合。每次提交请求时，调度和伸缩算法依次执行。评价结果表明，不同调度策略的延迟时间和平均成本存在显著差异，说明了将调度与自动伸缩相结合的必要性。
此外，这些自动伸缩算法只考虑了单层资源的结构，直接将服务实例部署在虚拟机上。存在以下两种情况:1)Amazon Auto Scaling[9]和某些算法假设实例是同构的，并且它们的配置是提前手动设置的。自动伸缩器需要做的是调整实例的数量。2)其他研究考虑云中的异构资源，因为云提供商提供不同配置的各种vm。用户可以组合不同类型和数量的虚拟机，生成最优的伸缩方案。但是，虚拟机的高开销和长时间的启动降低了这些伸缩算法的灵活性。
与vm相比，容器启动时间快、开销小，成为部署服务实例的首选。最近，微服务的部署主要基于容器。现有的容器相关研究集中在性能分析或容器被用作虚拟机的替代品的情况下。现有的容器相关研究很少考虑虚拟机和容器的两层伸缩。Heenisch等人的分析了容器和虚拟机的水平和垂直伸缩，提供了一个四倍伸缩模型。但是，没有相关的性能模型，实例的容量仅由一个参数表示，而没有考虑整个应用程序的整体性能。Guerrero等人的讨论了在包含两层结构的多云环境中部署容器化微服务，但他们只研究了初始部署，而没有研究运行时的自动扩展。初始部署假设容器的配置和数量不会改变，这与自动扩展的核心问题不同，自动扩展的核心问题是是否扩展以及如何扩展。
尽管虚拟机和容器的两层扩展类似于在数据中心(dc)中放置虚拟机，但它们的优化目标是不同的。除了与性能相关的目标外，VM在DCs中的部署主要是试图最小化与能源相关的成本，这与主机和冷却系统的能源成本有关;而在云中扩展则试图减少与云提供商的价格模型相关的租赁成本。两种成本目标的差异导致了两种问题的模型和解决方案的不同。此外，容器之间共享映像的特性在vm中是不可用的。

3 系统模型和问题表述
图1显示了一个请求序列，该序列包含基于微服务的系统中接收到的所有用户请求。由于调度算法需要花费时间来执行一系列步骤，所以请求被划分为不同的执行周期，称为调度周期。调度周期由时间戳t唯一标识。在每个调度周期中，可以调度多个请求，并且可以根据需要添加或删除服务实例。
微服务系统通常由三层组成:工作流层、微服务实例层和虚拟机层。在工作流层，微服务应用程序的结构由工作流定义。每个请求触发一个工作流实例的执行。因此，一个调度周期内的多个请求可以用多个工作流实例表示，如图1中的WF1和WFl。微服务实例层包含几个处理任务的微服务实例。每个实例都部署在一个容器中;因此，微服务实例层也称为容器层。虚拟机层代表云中的微服务应用所占用的虚拟机资源，虚拟机通过供应商的网络进行通信。相对于虚拟机的单层结构，容器层的引入使得资源管理更加细粒度。轻量级容器使快速创建或删除服务实例成为可能。

有两个优化问题需要解决。1)将工作流中的任务调度到微服务实例中，满足截止时间约束，减少资源使用;2)创建新的容器和虚拟机，并将新的容器映射到虚拟机，降低云中租用虚拟机的总成本。
大多数云中的工作流调度算法只考虑了第一个优化问题，简化或忽略了容器是如何创建的。这些算法要么假设一个服务实例占用整个虚拟机，而不考虑容器层，要么假设在同一个虚拟机上放置多个容器，不限制其占用的资源，这样容器之间就会相互干扰。前者完全忽略了容器层，而后者会导致不可预知的性能干扰。因此，这些方法不能直接应用于真实场景。
与工作流调度算法类似，现有的自动伸缩算法关注于传统的vm，或者简单地使用容器作为伸缩单元。这些算法很少考虑虚拟机和容器的两层结构，主要研究微服务实例层的伸缩方案，忽略了第二个优化问题。这些方法采用了一些简单的调度策略，如FCFS (First Come First Serve，先到先得)，不能很好地解决任务之间的依赖关系和多工作流之间的公平性问题，因此往往不能很好地解决第一个优化问题。
本文提出的算法将综合考虑这两个优化问题，实现云环境下基于微服务的应用的弹性调度。

3.1 系统模型
表1给出了主要变量和参数。如图1所示，每个工作流对应一个请求被描述为一个二元组，表示工作流中的任务和表示任务之间的依赖关系。如果在ti和tj之间存在一条边ei,j，则只有在ti完成后才能执行ti。任务ti称为tj的前辈任务，tj是ti的后继者任务。没有上一个任务或后继任务的任务分别称为进入任务tentry或退出任务texit。使用wi和datai,j两个属性分别描述ti的计算负荷和ti到tj的数据传输量。注意ti是唯一的标识符，因此两个不同的工作流实例不会同时包含任务ti。
在微服务实例层中，每一种类型的微服务都部署为多个服务实例，例如，第一种类型的微服务有两个实例ms1, 1和ms1, j。不同类型的微服务之间没有功能重叠;因此，任务t1只能被相应类型的微服务实例(ms1, 1和ms1, j)处理。通常，每个实例msi, j部署在容器ci, j中，容器所拥有的资源数量决定了其处理速度，用si,j表示。注意，每个实例和每个容器之间是一对一匹配的;因此，它们在下文中并不相互区分。在大多数工作流调度算法中，一个服务实例在每个实例时间只能执行一个任务。
在云环境中，计算资源主要以虚拟机的形式提供，微服务实例通过容器部署在虚拟机上。云提供商提供多种配置和价格不同的虚拟机。根据时间间隔的数量和虚拟机的类型对用户进行计费，每个部分时间间隔将作为一个完整的时间间隔进行计费。例如，在Amazon EC2中，时间间隔为1小时，3.4小时四舍五入为4小时。系统使用的虚拟机由集合表示。对于VM vmi，其价格为pricei，租期为durationi。两个虚拟机vmi和vmj之间的带宽和网络时延分别用bi、j和di、j来描述。

3.2 案例研究
为了说明由于流工作负载而产生的优化问题，我们考虑一个如图2所示的简单案例。

我们称之为三个调度阶段，根据时间戳的顺序，其中周期表示时间戳T之前的任何调度周期。类似地，时期是时间戳T之后的任何调度时期。在图2中，每个虚线框表示实例运行的持续时间，每个实线框表示实例执行任务的持续时间。每个虚线框的高度表示实例的处理速度，每个实线框的长度表示任务的执行时间。ms1,1和ti代表在周期创建的实例和分配的任务。类似地，ms2,1、tj和tk分别是在T时期创建的实例和分配的任务，tl表示在时期计划的任务。
由于云中的资源是根据时间间隔计费的，所以虚拟机或容器不会在一个时间间隔结束后关闭。在周期T中，上一周期使用的部分vm和服务实例继续运行，如图2中的ms1,1。因此，利用这些剩余资源和尽量减少费用是优先事项。同时，当需要创建新的服务实例时，新添加的实例可以继续运行，直到，如图2中的ms2,1。
这些新实例拥有的资源数量是时间戳T时调度算法必须考虑的。在图2a的调度周期T中，任务tj和tk等待被调度。因为实例ms1,1继续运行，算法将利用现有资源尝试将tj分配给实例ms1,1。然后，该算法创建一个新的实例ms2,1来处理tk，因为没有相应类型的实例。在传统的调度算法中，新增服务实例的速度是任务满足其子截止日期的最小速度，因此ms2,1的速度足以在其子截止日期之前完成tk。该策略确保了单个工作流在截止日期约束下的最小成本。然而，在流工作负载中，服务实例不仅需要处理当前工作流中的任务，还可能服务于后续工作流。在随后的时期，由于任务执行时间的波动，工作量较大的未分配任务tl需要较长的执行时间，这可能导致tl超过其子期限。
当任务tl被调度时，可能会发现现有的实例ms2,1的速度无法满足它的子deadline，必须创建一个新的更快的实例来及时完成tl，如图2b中的ms2,2所示。然而，这会造成资源浪费:在期间，ms2,1没有被使用，并且增加了一个额外的实例，ms2,2，增加了资源消耗和成本。
图2b的实例的浪费是因为ms2,1的速度不满足tl的要求。因此,如果添加合理的冗余在创建实例ms2,1时,如图2c所示,使它的速度更快,tl可以分配给ms2,1满足其subdeadline,没有必要创建ms2,2,这提高了资源利用率，降低了成本。因此，在创建一个新的服务实例时，确定实例及其容器的配置是本文讨论的关键问题之一。
为了验证资源冗余的可行性，我们以LIGO工作流中的两类任务TmpltBank和Inspiral作为实验对象。它们的执行时间数据在[39]中提供。我们比较了两种创建新实例的策略，最便宜的和冗余的策略，并计算了它们的成本和使用的实例数量。成本最低的策略以满足子截止日期所需的最少资源创建服务实例。冗余策略将在4.1节中介绍。其他实验设置与第6节中描述的设置相同，包括在vm上部署新容器的方法。TmpltBank的数量和子截止时间分别为240秒和8秒，Inspiral的数量和子截止时间分别为480秒和24秒。结果如表2所示。可以观察到，合理的冗余可以减少新实例的数量和成本。

3.3 问题公式化
当实例的能力不足时，我们可以通过1)在现有的虚拟机上创建新的容器，例如vm3中的c2, j, ms2, j，来快速添加新的容器和服务实例;2)或者租用一个新的虚拟机，然后在上面创建一个新的容器，例如vmk中的c5, j。因此，基于微服务的应用弹性涉及两个优化问题:工作流调度和容器与虚拟机的集成伸缩。这是一个重复的过程，需要在每个调度周期进行优化。在调度周期T中，定义任务调度方案M和伸缩方案N:

其中mi,j,k,l表示工作流WFl的任务ti分配给实例msj,k，从开始时间。nj,k,x表示微服务e实例msj,k部署在VM vmx中，从租期开始的时间开始占用资源R(cj,k);到租赁结束时间。cj,k的处理速度sj,k取决于。
对于调度方案M，需要确定任务ti到实例msj, k及其开始时间的映射关系;其中msj,k可能是一个新实例。对于扩展方案N，我们需要确定容器cj,k和VM vmx之间的映射，其中vmx可能是一个新的VM。由于msj、k和vmx都可能是新创建的，因此还需要确定新容器的配置、新虚拟机的类型(vmx)以及容器和虚拟机的数量。需要注意的是，伸缩方案N只影响当前调度周期内新建的容器和虚拟机。现有的实例和容器保持不变。
当任务ti分配给微服务实例msj,k时，它的执行时间和完成时间定义为:

和可以由msj, k上所有任务的开始时间和结束时间来确定:

其中，表示分配给实例msj,k的所有任务。值取决于任务对不同实例的最早启动时间(EST)。因为有几个实例可以处理ti，所以EST在不同的实例上有不同的值，等于所选实例的EST。在以成本最小化为目标的情况下，任务不一定要分配给EST最小的实例，因此大于或等于最小的EST值:

其中为tp到ti之间的数据传输时间。我们假设能够处理任务ti和tp的实例部署在vmx和vmy上的容器中，两个vm之间的带宽和延迟分别为bx,y和dx,y。为前一个任务tp的实际完成时间，有效是实例msj,k准备处理下一个任务时的时间戳:

在那里为调度周期T中实例msj,k的初始化时间，根据容器和虚拟机的状态有四个值:

1)如果msj,k不是新创建的，可以在时间戳T处立即使用;
2)如果msj,k是在一个虚拟机及其镜像中创建的，则需要额外的容器启动时间;
3)如果msj,k是新创建的，并且没有虚拟机和它的镜像，则增加一个额外的容器镜像的拉取时间;
4)如果msj,k和vmx都是新创建的，则需要添加一个新的VM，然后在其上创建一个容器，所以vmx的启动时间被添加到。
对于调度方案M和伸缩方案N，每个工作流的响应时间(rtl)和虚拟机的成本可通过以下公式计算:

其中VM表示所有租用的VM, pricex和durationx分别为每个VM vmx的价格和租用期限;interval是云提供商的时间间隔，例如Amazon EC2中的一个小时。
每个请求的响应时间都受到截止日期Dl的限制。微服务应用弹性调度的优化定义是在满足所有请求的截止日期约束的情况下，最小化虚拟机的成本:

4 URGENCY-BASED工作流调度
我们的ESMS由三个部分组成:配置求解、基于紧急度的工作流调度和自动伸缩，如图3所示。ESMS以调度时段T收到的工作流WF为输入，得到调度方案M和伸缩方案N。首先，该算法利用任务计算工作量的统计信息，计算出与每种微服务类型对应的容器的成本效益配置(CE)，该配置是离线完成的。然后，系统每次接收到工作流时，在CE的基础上执行基于紧急度的工作流调度算法UWS。在UWS算法中，截止时间分配是根据CE为每个任务分配子截止时间。在紧急度计算中计算调度紧急度，并根据任务的紧急度对任务进行排序。任务映射按照优先级的顺序为每个任务选择适当的服务实例。最后，包含所有新创建的服务实例和容器的集合被用作集成伸缩算法IFFD的输入。在这里，我们关注前两部分，详细的缩放算法在第5节中介绍。UWS和IFFD是实时执行的。

据我们所知，Netflix Conductor将应用程序建模为一个工作流，并控制由任务队列调度的任务的执行顺序。此外，自定义插件可以通过Kubernetes提供的REST API来调整配置和运行容器的数量，Kubernetes可以结合云API来实现虚拟机的伸缩。基于这两个工具，ESMS的功能与现有工具兼容。
如图1所示，这是一个流工作负载，而不是一个单一的工作流。多个工作流将被划分为同一时间段的T，共享服务实例。因此，调度算法需要保证调度的公平性。调度算法在连续调度周期内重复执行，使不同的周期相互关联。因此，需要解决的具体问题总结如下:
1）如何保证调度的公平性。
2）如何充分利用剩余实例，降低整体成本。
3）考虑到后续任务的工作负载，如何确定新实例及其容器的配置。
在UWS中加入了旨在回答这些问题的策略，其伪代码在算法1中给出。UWS遵循列表调度的基本结构:1)任务排序阶段，计算启发式信息并对任务进行排序;2)任务映射阶段，将每个任务分配给服务实例。在列表调度中，选择哪个度量作为任务的优先级至关重要;因此，我们提出任务的调度紧迫性作为任务排序的基础。对于第一个问题，我们采用了多工作流调度中常用的合并策略。对于第二个问题，我们在任务映射中考虑以下两个方面:1)将任务分配给现有的实例会增加成本;2)根据容器镜像对现有vm的影响，会提前部署一些新创建的容器。对于第三个问题，我们提出了一种基于统计的算法来确定每种类型微服务的合理容器配置，并将该配置作为截止时间分布和容器创建的基础。

4.1 容器的配置
由于每个服务实例和每个容器之间都有一对一的匹配，所以应该确定的是相应容器的配置。对于不同工作流中相同类型的任务，应增加适当的资源冗余，以解决执行时间的波动，如图2所示。
为此，我们首先统计各种任务的计算工作量的历史数据，然后根据这些数据计算出每种类型微服务实例的经济高效配置。假设有h种微服务类型，得到容器配置方案，其中cej是一个向量，表示第j种微服务的服务实例的配置，例如CPU内核数。当应用程序需要增加第j个微服务的服务实例的数量时，将优先创建配置为cej的容器。
通过分析提供的几个工作流中任务的执行时间，我们发现它们的分布呈现两种模式:1)方差较小，呈正态分布;2)方差较大，具有相似的均匀分布。对于前者，我们根据3σ准则选择平均执行时间对应的计算工作量，或者均值加3σ。对于后者，选择与最大执行时间相对应的工作负载。如果工作负载较大的任务发生，则会在任务映射阶段执行一个特殊的策略。
由于用户不是直接为容器付费，而是为虚拟机付费，为了将容器的配置和价格与虚拟机的配置和价格关联起来，我们提出以下转换策略:1)容器配置的离散化，例如，离散单元的内存是500MB，然后，内存的数量是500MB的倍数。2)容器价格的转换。容器价格根据容器配置与VM配置的比例确定。以Amazon EC2提供的虚拟机为例，一个2vCPU、8GB的m4.large虚拟机每小时的价格为0.10美元，一个1vCPU、2GB的容器每小时的价格为0.05美元，因为它占用了一半的CPU和1/S4的内存;较高的比率用于确定成本。具体配置步骤如下:
1）用最少的资源将CE中的所有cej初始化为配置。在离散化之后，每个资源的最小数量等于它的单位资源，例如，最小的内存数量是500 MB。
2）假设第j个类型的微服务（msj,k）的每个实例都运行在一个配置为cej的容器上，使用配置方案CE计算工作流的预期完成时间:

其中，T的值为0,msj,k的速度为cej容器对应的速度。
3）如果预期的完成时间大于最后期限，我们将第j个微服务的配置替换为包含更多资源的配置cej。通常，资源的增加量等于一个离散化资源单位。新方案是。替换cej的增益可计算为:

其中durationj,k和pricej,k分别为容器的运行时间和价格。
因为有h种类型的微服务，我们逐一替换每种类型的微服务的配置，并获得几个增益，，其中gainj对应于替换第j个微服务配置的增益。我们选择gainj最大的方案CEj代替原来的CE，然后过程返回到步骤2。请注意，成本取决于集装箱的价格和持续时间。有可能成本保持不变或下降，因为价格上升，但持续时间减少。
4）如果预期的完成时间满足最后期限约束，流程就会停止，并且当前的CE是具有成本效益的容器配置方案。

4.2 最后期限分布
本文采用[4]中的分布公式计算每个任务的子截止时间:

任务ti的子截止时间sdi由任务的执行时间和任务的等级决定。HEFT[17]中rank的含义是ti到退出任务的预期执行时间的长度，类似于工作流的关键路径。因此，根据ti和tentry的等级比例来分配截止时间是合理的。
在原始公式[4]中，执行时间是根据最快的服务实例的速度计算的。然而，我们的目标是在满足期限限制的情况下最小化成本。虽然原来的公式可以在最快的实例上满足任务执行的最后期限，但它也增加了不必要的成本。此外，任务将分配给不同速度的实例;因此，基于相同速度的子截止日期是不准确的。因此，我们选择在CE中配置为cej的容器的速度来计算执行时间。部署在这样一个容器中的服务实例用ms*j。由于任务映射阶段的以下策略将创建尽可能多地配置为cej的容器，因此实例的实际速度将接近截止日期分发中使用的速度。

4.3 任务命令
处理multi-workflows,我们结合工作流通过添加任务到一个工作流的前任任务所有入口任务和后续任务的任务退出所有任务(1号线算法1)。计算工作量和其他任务之间的数据传输和添加的任务为零。该策略能保证多工作流调度的公平性。
我们计算合并工作流中每个就绪任务的调度紧急性ui，作为任务排序的基础。就绪任务是其前任任务已完成的任务，而入口任务始终是就绪任务。

其中hop(ti)表示从ti到退出任务的关键路径上未分配的任务数，XFT(ti)为预期完成时间，定义为:

其中MS(ti)是一组可以处理ti的实例。因为所选的实例仍然未知，所以计算EFT所需的实例的速度被设置为实例msj*，与(18)相似。
sdi与XFT(yi)的差值越小，超过子截止日期的风险越高。待调度的后续任务越多，ti延迟的影响越大，因为它直接导致后续任务的延迟，增加了工作流的最大完成时间。因此，ui值越小，ti的调度紧迫性越高。

4.4 任务映射
根据紧急程度，选择ui最小的准备任务进行调度。任务映射需要考虑如何充分利用现有资源，以及如何创建新的服务实例和容器:
1）如果存在能够按时完成任务的实例，则选择成本增量最小的实例;
2）如果需要一个新的实例，首先创建具有CE配置的容器;
3）如果有一个工作负载更大的任务，或者它超过了它的子截止日期，则会创建一个新的实例来满足截止日期约束;
4）如果在某个VM中创建新实例需要映像，则首先将该实例部署到该VM中。
具体如下(算法1第5-34行):
为MS(ti)中所有实例的计算值:

如果存在为非负的情况，表示可以在任务的子期限前完成任务，则计算将ti分配给msj,k造成的成本增加incrCostj,k，并将任务分配给incrCostj,k最小的实例:

其中cost和cost’分别是分配任务之前和之后的成本。
如果值均为负值，表示没有满足该子截止日期的实例，则计算满足该子截止日期所需的新实例的最小速度minSpeed，并根据其值选择策略:

1）如果minSpeed为负或大于可用的虚拟机的最大速度,表明是不可能及时完成,我们计算的EFT两个计划:a)将任务分配给现有的实例和b)创建一个实例的最大速度,然后将任务分配给它。选择EFT较小的方案。
2）如果minSpeed小于配置为cej的容器的速度，则创建一个实例及其配置为cej的容器，并将任务分配给它。
3）如果minSpeed介于配置为cej的容器的速度和可用VM的最大速度之间，则创建速度略大于minSpeed的实例及其容器，其中速度通常是离散化单元的倍数，然后分配任务。
重复上述步骤，直到将所有任务分配给现有实例或新实例。

在时间复杂度方面，如果有m个工作流，每个工作流有n个任务，则任务总数为mn，计算EST、sdi和ui的复杂度为O(m2n2)。查找就绪任务需要O(mn)。当存在p个实例时，任务映射步骤的复杂性为O(pm2n2)。为了确定每个容器的配置，需要计算预期的完工时间，其复杂性等于计算EST的复杂性。如果离散化后有l种配置和h种微服务，计算CE的复杂度为O(lhm2n2)。因此，总的复杂性是O((l*h+p)m2n2)。

5 容器he虚拟机上的自动扩展
正如相关工作中所讨论的，大多数现有的扩展算法直接将服务实例部署到VM。如图4a所示，缩放算法确定要添加的三个实例以及运行这三个实例的vm的类型。如果将这些算法直接应用于两层缩放，则新容器的数量和类型可由用于VM的先前策略确定，如图4b所示。然而，新创建的容器需要进一步部署到VM，并且不允许它们占用VM的所有资源，而是与其他容器共享VM，例如图4c中vm1中部署的ms1,1和ms2,1。缩放算法要求确定容器到虚拟机的映射，包括确定哪些容器部署到同一虚拟机以及选择什么类型的虚拟机，这是一个多对多映射问题。现有的算法主要关注服务实例和虚拟机的一对一映射，没有解决上述问题的策略和第3节中描述的第二个优化问题。

与第3.2节中的情况类似，缩放算法需要充分利用现有VM，并结合容器图像的影响解决第二次优化。因此，需要解决的问题如下：
1）如何确定新容器占用的资源数量；
2）如何确定新虚拟机的类型和数量；
3）如何确定新容器和虚拟机之间的映射。
第一个问题用调度算法求解。针对另外两个问题，提出了一种基于VSBPP的两层缩放算法。
如（10）所示，存储在VM中的映像将影响容器的初始化时间。因此，ESMS首先尝试使用所需的映像将新容器部署到VM。具体而言，遍历存储所需映像的VM，并通过最佳拟合（BF）策略选择VM，该策略选择VM的剩余资源与容器所需资源之间差异最小的VM。此策略添加到UWS中，因为它会影响任务的实际完成时间和预期完成时间（算法1中的第27-29行）。请注意，提前部署的容器不会通过缩放算法进行部署。
根据UWS的结果，需要部署的新容器被收集到set newIns中。首先，我们尝试将newIns部署到现有vm。如果现有虚拟机的剩余资源不足，将租用新虚拟机以容纳新虚拟机。首先，newIns的所有容器都按所需资源量的升序排序。然后，通过BF策略将容器部署到现有VM。如果现有VM的资源不足以部署所有新容器，我们将剩余容器的部署建模为VSBPP。
定义1 给定容器集newIns={msj,k}和VM类型集Type={Typei}，每个容器的大小是R(msj,k)，每个VM类型的大小和价格分别是R(Typei)和pricei。我们希望将每个容器部署到一个VM，以便将租用这些VM的成本降至最低，并且容器占用的资源不会超过每个VM提供的总资源。
与原来的VSBPP不同，租赁虚拟机的成本不仅与虚拟机的类型有关，还与时间间隔有关，如（12）所示，时间间隔随虚拟机的类型而变化。为了解决这个问题，我们采用了一种基于FFD（first fit Desculation）的启发式算法IFFD[40]，其中容器和虚拟机按容器所需或虚拟机提供的资源量降序排序。一个可行的解决方案被描述为集合B=，其中的每个元素表示一个VM和部署在其上的容器。这些元素按照创建时的时间戳顺序排列；例如，B1首先创建，B2在B1之后创建。
在极端情况下，新实例的数量等于任务的数量，mn。如果现有VM的数量为q，VM类型的数量为r，则第一个循环的复杂性为O(mnq)，第二个循环的复杂性为O(rmn)。第三个循环遍历所有任务一次，因此需要O(mn)。因此，IFFD的复杂性为O((q+r)mn)。由于虚拟机的数量（q）小于任务的数量(mn)，并且虚拟机类型的数量（r）小于容器类型的数量（l），因此ESMS的总复杂度为O((lh+p)m2n2)。

为了评估ESMS的复杂性，我们列出了第6节中使用的三种比较算法的复杂性：ProLiS[4]、SCS[14]和IC-PCPD2[5]。它们的复杂性分别为和O((l+p)m2n2)，其中x是SCS中载荷向量的长度。根据l、p、h和x的不同值，这四种算法具有不同的复杂性，并且差异不大。

6 评价
在本节中，我们使用[39]提供的工作流来模拟基于微服务的应用程序。仿真实验验证了算法的性能。

6.1 实验设置
基于[4]中提供的仿真工具，我们构建了一个用Java实现的仿真平台，该平台可以读取DAX格式文件中的工作流，并生成工作流的请求序列。该平台运行在Windows 10 64位PC上，具有i7 2.6 GHz CPU和16 GB RAM，JDK 1.8.0。
四个工作流应用程序用于模拟实验：蒙太奇、LIGO、基因组和SIPHT。这些工作流广泛应用于工作流调度的研究[4]、[5]、[6]、[42]，它们涵盖不同类型的工作流：蒙太奇是I/O密集型的，基因组是数据密集型的，LIGO和SIPHT是CPU密集型的；SIPHT是不对称的，其他的是不对称的。DAX格式文件[4]提供了工作流的详细信息，其中提供了名称、计算工作量、数据传输量和任务之间的依赖关系。任务的计算工作量定义为其在标准计算服务上的执行时间（以秒为单位）。我们将工作流应用程序用作基于微服务的应用程序，其中每种类型的任务对应一种微服务，而每种微服务只能处理一种类型的任务。[39]和[48]中提供了每个任务的执行成本和其他详细信息。

在实验中，我们使用了8种不同类型的虚拟机，如表3所示。与云计算中的相关工作[4]、[14]、[42]类似，我们使用虚拟机的ECU来表示其计算能力和虚拟机提供的资源，并假设离散化单元为0.5 ECU。此外，我们根据相关工作[36]和[38]设置了VM和容器的启动时间。
我们选择了两种云中的工作流调度算法ProLiS[4]和IC-PCPD2[5]，以及一种云中的自动缩放算法SCS[14]作为比较算法。这些算法还关注具有截止日期约束的成本优化。ProLiS基于列表调度，其中每个任务分配给满足其子截止日期的最便宜VM。由于IC-PCP使多个任务在同一实例上执行，这与微服务的单一功能特性不兼容，因此我们使用IC-PCPD2作为比较算法。IC-PCPD2通过PCP将截止日期分配给各个任务，然后将它们分配给满足子截止日期的VM。SCS确定需要通过负载向量添加的VM数量，然后通过最早的死线优先（EDF）算法调度任务。由于算法忽略了容器层，我们对其进行了修改以适应双层结构。原始算法确定任务和服务实例（即容器）之间的映射，并通过最佳大小最佳拟合（BFB）策略解决容器和虚拟机的集成伸缩问题。BFB策略通过BF策略将容器部署到现有VM。如果现有VM的资源不足，则租用其资源量最接近新容器所需资源量的VM。为了模拟流式工作负载，我们从Wikipedia access traces[43]中随机抽样，形成三个工作负载模式为稳定、减少和增加的请求序列。三个序列中的每个请求都将创建一个带有截止日期约束的工作流实例。为了设置合理的截止日期，我们计算每个工作流的关键路径的平均长度，并设置一个截止日期因子来控制截止日期约束的严格程度，范围为[1.0,2.0]。

6.2 度量
虽然目标是将成本降至最低，但有些工作流可能无法满足最后期限约束。如果没有满足约束条件的可行解，则最小化成本是毫无意义的。因此，我们设置以下指标：
成功率定义为满足截止日期的工作流数量与计划工作流总数的比率：

此外，成功率为100%的调度和扩展方案称为可行解。获得的可行解的数量也用作度量。
成本是租用的虚拟机的成本，由（12）计算。
基于上述两个指标，评估规则如下：
1）若第一个方案的成功率高于第二个方案，则第一个方案更好；
2）如果两种方案的成功率均为100%，则成本较低的方案效果更好。

6.3 结果
我们进行了几组实验来测试每个算法在不同工作流、不同工作负载模式和不同工作负载下的性能。
6.3.1 不同的工作流应用程序
我们选择一个稳定的工作负载模式，并在不同的工作流应用程序中执行算法。工作流的大小（即每个工作流中的任务数）设置为大约50（SIPHT的大小约为30，因为其独特的结构）。不同因子值下的成功率和成本如图7，8所示。可行解决方案的数量如表4所示。

我们观察到，随着因子的增加，成功率逐渐增加，SCS除外。结果表明，ESMS系统的性能优于其他系统。从图8中的数据点数量和表4中的数据可以看出，ESMS可以获得比其他方法更可行的解决方案。特别是在LIGO实验中，ESMS的成功率分别比ProLiS、SCS和IC-PCPD2高18.31%、36.39%和6.02%。SCS的成功率波动很大，没有可行的解决方案。SCS算法不同于其他三种算法。SCSfirst在EDF调度算法之前通过负载向量估计所需的实例数。然而，负载向量的预测结果与EDF调度算法的需求之间存在微小差异，这导致一些任务*排队。由此产生的延迟在工作流执行期间逐渐累积，最终导致工作流超时。此外，随着因子的增加，VM的成本效益类型发生变化，其配置也逐渐减少。因此，即使最后期限因素放宽，成功率也不会增加。另外三种算法都是基于任务调度的，可以通过一种调度方案来确定资源需求，因此它们的成功率较高。结果还证明了任务调度与自动伸缩相结合的有效性。
IC-PCPD2的性能也不稳定：它可以获得高成功率、低成本和接近ESMS的GENOME可行解数量，但在Montage中无法获得任何可行解。对于SIPHT，图9a显示IC-PCPD2的平均成功率接近ESMS，但IC-PCPD2只有三种可行的解决方案，如图8d和表4所示。这是因为IC-PCPD2的大多数成功率高于99%，但低于100%。尽管其他三种工作流的成功率差异很小，但ESMS的成本最低。

在成本方面，我们从具有不同因子值的实验中收集所有可行的解决方案，标准化它们的成本并计算平均成本，如图9b所示。ESMS的成本显著低于ProLiS，分别降低了79.08%、6.80%、15.37%和18.29%。除了IC-PCPD2在Montage中没有可行的解决方案外，ESMS在其他三种工作流中的成本分别比IC-PCPD2低4.57%、0.58%和11.39%。
在图8a中，ProLiS的成本始终很高，并且不会随着因子的增加而降低。这是由于期限分配不合理造成的。在蒙太奇中，mAdd和mShrink之间的数据传输更多，ProLiS使用最快的速度分发截止日期，导致mAdd的子截止日期太小。因此，在任务mAdd之前执行的所有任务都必须在短时间内完成，这需要更多的实例和更高的速度，从而导致更高的成本。例如，在某个工作流实例中，mAdd的子截止日期为10.5909，工作流的生成时间为53.7460，远小于截止日期71.9009。ESMS使用CE对应的速度分配截止日期，使mAdd 33.8911子截止日期和最大完成时间69.6119更接近截止日期，减少了不必要的成本。在其他三个工作流中，ESMS的成本最低，因为每种类型的实例都添加了合理的冗余，从而减少了资源浪费，如图2和表2中所述。
由于UWS中有以下两种策略，ESMS的成功率较高：1）创建新实例的策略（算法1中的第13-20行）和2）考虑容器图像的影响（算法1中的第27-29行）。在前者中，当任务超过子截止日期时，ESMS会尝试尽早完成，从而减少超时任务对后续任务的影响；尽管创建新实例会增加成本。事实上，即使任务超过其子期限，后续调度也可能使工作流按时完成，这也是IC-PCPD2无法在Montage中获得可行解的主要原因。当现有实例和新实例都不能满足子期限时，IC-PCPD2中没有相应的策略，导致在许多情况下成功率低于100%。在后者中，如（10）所示，VM是否包含容器所需的映像将影响容器的初始化时间，进而影响任务的完成时间。如果创建了新实例，则应将其部署在存储所需映像的VM上，从而缩短初始化时间和工作流的完成时间。因此，ESMS实现了更高的成功率。
根据表5，我们的ESMS使用最少的机器，同时保持最低的成本。更少的机器也可以降低操作和维护的复杂性。在Montage中，ProLiS使用的机器最多。正如前面所分析的，它不合理的截止时间分布会导致更多更快的实例，从而占用更多的虚拟机。当然，成本不仅取决于虚拟机的数量，还取决于虚拟机的配置。但是，当成本接近时，虚拟机越少越好。

6.3.2 不同的工作负载模式
为了评估算法在不同工作负载模式下的性能，我们访问LIGO和GENOME（简称L和G）以及增加和减少（简称I和D）的工作负载。这两个工作流应用程序可以表示第6.3.1节中检查的两种成本变化模式。工作流的大小仍然设置为50。结果如图10和表6所示。在表6中，符号“（L，D）”表示工作量减少的LIGO应用程序。

结合图7b，7c，8b，8c，我们可以确定，不同工作负载模式的实验显示出类似的结果：
1）SCS的成功率仍然是随机的，可行解的数目为0。因此，在图10b中没有成本条。
2）在LIGO的三个实验中，ESMS保持了最低的成本和最高的成功率。
3）在GENOME的三个实验中，ESMS优于ProLiS和SCS，ICPCPD2的性能接近ESMS。
4）如表4和表6所示，ESMS可以获得比其他算法更可行的解。
为了显示ESMS相对于比较算法的改进，我们在表7中列出了四种工作流应用程序（简称M、L、G和S）和三种工作负载模式（简称S、D和I）的成功率和成本改进，包括12组。从表7可以看出，就成功率而言，ESMS算法通常比ProLiS增加0.16-1.30%；特别是，LIGO的改善率高达18.31%。在成本方面，改进率在6.80%到22.66%之间，Montage的改进率达到85.84%。与SCS相比，除82.01%和99.8%的两种特殊情况外，成功率的增加通常在27.50%和67.62%之间。就成本而言，SCS无法进行比较，因为它无法获得可行的解决方案。如上所述，IC-PCPD2可以在基因组中获得接近ESMS的性能，但在某些情况下，如Montage组和第11组，它无法获得可行的解决方案。ESMS在成本方面的性能改进为0.5814。与IC-PCPD2相比，ESMS的成功率一般比IC-PCPD2高0.00-7.40%，Montage的成功率可达72.97%。

为了比较我们的战略IFFD和基准BFB的绩效，任务调度算法固定为UWS，并与IFFD和BFB相结合。请注意，表8中的“UWSþIFFD”是我们的ESM。由于任务调度算法相同，且UWS中考虑了容器图像的影响，表8中两种算法的成功率相等；因此，我们只比较它们的成本。结果列于表8。一般来说，我们的IFFD在蒙太奇和LIGO方面优于BFB。与简单的装箱问题不同，云中的虚拟机可能会被移除，或者它们的租用时间可能会延长，具体取决于后续调度中的调度方案。因此，IFFD对BFB的改进不如原来的料仓包装问题。
使用相同的缩放策略（BFB），UWSþBFB比ProLiS和IC-PCPD2获得更高的成功率。这表明我们的任务调度算法UWS可以提高成功率。

6.3.3 不同的工作量
与工作负载模式不同，工作负载是指每个调度周期中的请求数或工作流中的任务数。为了确定工作负载对算法性能的影响，我们选择第二种工作负载模式，并通过以下方式调整工作负载：1）假设工作流的大小为50，请求数从131增加到2100；2） 假设请求数为1051，工作流的大小将从50增加到600。
四种算法的标准化成功率和成本如图11所示。图12显示了不同大小工作流的类似结果。在每个请求数和工作流大小的值下，有11组不同因素的实验，从1.0到2.0。这11个结果显示在方框中，或显示在箱线图中的异常值中。

图11a中的方框图反映了ESMS获得的解决方案的成功率聚集在100%左右，而ProLiS和IC-PCPD2的分布更为分散。此外，图11中的异常值反映了当因子较小时算法的较低成功率。因此，可以从这些异常值中发现，当最后期限约束严格时，ESM的成功率明显高于其他ESM。图11b还指示由ESMS获得的解决方案的成本最低。除262个请求的实验外，ProLiS的成本低于IC-PCPD2。当请求数为525时，SCS可以获得可行的解决方案。
图12所示的结果与图11的结果相似。请注意，当工作流大小为200和400时，ProLiS没有获得可行的解决方案，当工作流大小为50时，IC-PCPD2只有一个可行的解决方案。
在最极端的工作负载下，即每个工作流中有600个任务，系数为1，四种算法的成功率分别为0.00%、0.00%、0.38%和20.99%。

6.3.4 运行时间
为了评估算法的开销，我们使用相同的工作负载模式、相同的工作流大小和不同的请求数测试算法的运行时，如图13所示。鉴于IC-PCPD2的性能不稳定，我们仅比较ProLiS和ESMS。
当请求数很小（小于525）时，运行时很短，差异很小。随着数量的增加，运行时间也会增加，每种算法都有自己的优势。当数字为1051时，ProLiS的运行时间最短。当数字为1573时，中间运行时基本相同，ProLiS和ESMS相似。随着数量的进一步增加，ProLiS的运行时间最长且分布最广，而ESMS的运行时间较短。一般来说，这些算法的复杂度差别不大。

7 结论
在本文中，我们提出并开发了一种弹性调度算法ESMS，用于云中的微服务，以集成的方式处理任务调度和自动伸缩。该算法基于工作负载的统计信息确定容器配置，并适应流式工作负载。提出了一种基于VSBPP的缩放算法，解决了由于引入容器层而引起的两层缩放问题，并考虑了容器图像的影响。通过使用工作流应用程序的仿真实验，验证了所提算法提高云中微服务成功率和成本的能力。
在未来，我们计划研究如何为基于微服务的系统构建一个通用的性能模型，以准确预测不同配置下每个微服务的响应时间。其次，本文重点研究了云中的水平缩放。将进一步研究水平缩放和垂直缩放的组合。第三，考虑到云资源的多样性，Spot等其他计费模型将是我们的研究方向之一。