满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究 *

廖建锦，孙庆骁，杨海龙，栾钟治，钱德沛

(北京航空航天大学计算机学院，北京 100191)

1 引言

科学应用中不同计算任务之间往往存在复杂的依赖关系，为了更好地刻画不同计算任务之间的依赖关系，这些计算任务通常被组织成工作流，如CyberShake[1]和MapReduce[2]。工作流通常被表示成有向无环图DAG(Directed Acyclic Graph)，在本文场景下，DAG和工作流可以互相替换。此外，随着云计算市场的蓬勃发展，将工作流放置到云上计算可以更好地满足科学应用不断增加的计算需求。亚马逊云服务AWS(Amazon Web Services)、阿里云等云计算服务提供商可以提供大量大小不一且可靠的虚拟机计算资源。

然而，将工作流放置到云上计算存在着几个重要的挑战。一方面是工作流调度的复杂性，如何将虚拟机资源映射到各个任务以满足工作流执行时限的要求；另一方面，将工作流放到云上计算会产生大量的经济成本，如何在满足工作流执行时限的前提下降低成本也是个难题。其中，对于执行时限内降低工作流成本的问题，现有的研究工作提出了很多方法对工作流的虚拟机资源进行优化。例如，Abrishami等人[3]使用部分关键路径解决虚拟机资源的选择问题，但是其使用的虚拟机资源大部分是按需付费虚拟机实例[4]，这类计算资源较为可靠但价格固定，其成本优化空间相当有限。云计算服务提供商也提供了可抢占虚拟机实例[5,6]，其价格一般为按量按需付费实例的10%～20%。如果工作流虚拟机资源配置中可以利用好可抢占实例，会极大地减少工作流的计算成本。虽然可抢占实例价格低廉，但是其在执行过程中存在一定概率被云服务商收回释放，导致工作流无法按时完成。因此，如何在工作流执行过程中，可靠地利用可抢占实例，在满足执行时限要求的情况下，降低计算成本是一个新的挑战。

针对上述挑战，本文提出了满足工作流执行时限的可抢占虚拟机实例配置和调度方法，可以在满足工作流最长执行时限的前提下，最小化工作流执行的计算成本。本文提出的方法具有重要的实际经济价值。具体而言，本文的主要贡献如下所示：

(1)提出了基于马尔科夫模型的可抢占虚拟机实例价格预测模型。

(2)提出了针对单任务的成本估计方法。通过估计不同出价策略下的工作流计算成本，从中选择最优出价策略。

(3)提出了基于可抢占虚拟机实例价格特点的工作流配置和调度方法。

(4)基于阿里云真实数据，对本文提出的方法进行模拟验证，并与已有算法进行对比。

2 研究背景

2.1 可抢占虚拟机实例

可抢占实例是云计算市场中较为特殊的一类资源，其价格低廉，但生命周期不再只由用户决定，还和市场有关[5,7]。用户需要提供出价以创建可抢占实例，而创建可抢占实例是否成功还和市场价格以及资源是否充足有关。当用户出价大于市场价格且资源充足的情况下，用户可以成功创建可抢占实例。其中市场价格取决于市场供需关系，随时间发生波动。在用户成功创建可抢占实例后，云计算服务提供商会不断检查用户出价和市场价格，当市场价格大于用户出价或资源不足，那么该用户的可抢占实例就会被云计算服务提供商收回并释放。由此可知，当用户出价较高时，可抢占实例会更加稳定，但相应地价格也会更加昂贵。

可抢占实例的出价策略主要分2种：静态出价策略和动态出价策略。静态出价策略一般目标比较单一，常见的有依据历史价格出价和预测未来价格出价。Andrzejak等人[8]提出了一种概率模型，其证明当出价为最低价或者平均价格时，一般规律是出价越高成本越高，但相应地完成时间会更短。Baughman等人[9]利用LSTM预测未来价格变化，而Fabra等人[10]首先对各个可用区进行分类，然后根据其不同的价格特点分别建模预测价格。总而言之，静态出价策略比较简单，出价的高低对应着任务对时间和可靠性的要求。

Figure 1 Spot instance configuration and scheduling method proposed in this paper图1 本文提出的可抢占虚拟机实例配置和调度方法WCSSI

相比静态策略，动态策略可以协同优化计算成本和完成时间。对此，许多研究提出了在不同约束条件下的出价策略，比如限制成本或者计算时间等。Kamiński等人[11]提出了一种自适应的出价策略，该策略可以同时降低计算成本和实例回收带来的延迟。Zafer等人[12]则将此类问题建模为一般的离散时间动态规划问题，并提出了最优出价策略，该策略可以在固定时间内最大程度地降低计算成本。相对而言，动态出价策略可以在一定约束条件下获得比较好的结果，但是建模和求解会相对比较复杂。

2.2 工作流调度优化

众所周知，工作流调度是一个NP-complete问题[13]。当工作流放置到云上进行计算的时候，成本是研究关注的重点问题之一。在云上进行工作流调度，比较常见的场景包括有限时间内最小化成本和有限成本内最小化执行时间。除此之外，还有研究讨论云计算实例的计算能力和工作流的鲁棒性问题。

对于在有限时间内最小化成本的问题，一般的方法是选择较为廉价的资源分配给非关键路径上的任务，如此便可以在不增加工作流整体运行时间的基础上降低成本，其中比较常见的方式是通过时间分配来选择资源。例如，Yu等人[14]根据工作流中的依赖关系对各个任务进行分类，然后根据每个任务的类别来分配时间，最后按照分配的时间来为任务选择不同的资源。除此之外，也有研究利用关键路径来选择资源。例如，Gao等人[15]利用关键路径和最短路径对工作流中的各个任务进行分类，然后按照一定的优先级来逐步减少各个任务的计算成本，从而降低整个工作流的成本。Abrishami等人[3]则是利用部分关键路径并通过递归的方式来决定各个任务的资源分配。

鉴于可抢占实例比较廉价，部分学者在工作流中加入可抢占实例以降低工作流成本。Monge等人[16]提出了CMI(Cloud Multi-objective Intelligence)，其同时考虑了工作流的时间和出错概率，通过遗传算法求解。Poola等人[17]则是通过启发式算法来使用抢占式实例，进而降低工作流的成本。Zhou等人[18]用A star算法进行剪枝，然后调整各个任务的资源分配，从而以一定的概率使工作流不会超时。这些算法对于抢占式实例的出价大都以尽可能保证能够获得可抢占实例为主，并没有考虑进一步降低有限时间内获得可抢占实例的成本。另外，由于期限的不同，可抢占实例的期望价格也不一样，当工作流执行时限过大时会出现边际效应，会带来虚拟机利用率的问题。此外，不同可抢占实例的价格差异很大，这些差异很大程度上影响工作流整体的配置。上述算法如果能考虑到这些问题，那么可以进一步降低工作流的成本。

3 WCSSI方法设计实现

3.1 总体设计

本文提出的可抢占虚拟机实例配置和调度方法WCSSI(Workflow Cost Saver based on Spot Instance)的整体结构如图 1所示，具体包括价格预测、成本估计和工作流配置和调度3个部分。首先根据可抢占实例的价格特点，在工作流执行前通过工作流配置算法确定工作流中任务所选择的可抢占实例，在工作流配置的层次上降低计算成本。之后在工作流执行过程中，根据工作流的执行情况调整任务的执行时限和使用的可抢占实例资源。最后，在为任务购买可抢占实例时，通过成本估计和价格预测成本最低的方式，在单任务的层次上降低计算成本。

接下来对本文方法进行建模，首先做出如下假设：

(1)市场的可抢占实例资源充足，在购买可抢占实例时，只要用户出价大于或等于市场价格即可获得可抢占实例。

(2)可抢占实例只有可能在任务结束时或者市场价格大于用户出价时才会被释放。当可抢占实例被服务提供商释放时，会产生一定的成本，该成本为实例从最近检查点到被释放时产生的计算成本。

(3)可抢占实例的价格每小时变化一次，而且其收费也是按照小时收费。

(4)决策只针对单个任务，不会影响可抢占实例市场的价格变化。

(5)每小时执行一次检查点，并忽略进行检查的时间和从检查恢复的时间。

(6)忽略可抢占实例的性能变化，以及传输所需要的时间。

3.2 工作流配置和调度

一般来说，工作流调度的原则是让工作流尽可能使用价格低廉的资源。对于按需付费实例，其3xlarge、2xlarge、xlarge的关键指标，如CPU数量、内存大小，分别为large的6,4,2倍，而价格也是如此，所以单位计算资源的价格相同。但是，对于可抢占实例这类价格一直在变化的资源，很难直接判断资源的使用优先级。所以，本文根据可抢占实例的历史平均价格，对可抢占实例进行排序。

图 2是可用区(可用区是指云计算提供商的物理数据中心内，电力和网络相互独立的物理区域)cn-beijing-h的不同规格可抢占实例的平均价格相对于按需付费实例的价格。可以发现，其中3xlarge的价格最高，然后2xlarge、xlarge、large的逐渐降低，但降低幅度也越来越小。为了降低工作流的计算费用，整个工作流应该尽可能使用较低规格的实例。同时，还需要考虑各个规格之间的差价，工作流中各个任务的规格不能相差太大。除此之外，还需要考虑到各个任务对工作流执行时长的影响。在这里本文提出了BFRC(Branch First Reduce Cost)工作流资源调度算法。

Figure 2 Relative price of spot instances(compared with the price of on-demand instances of the same specifications)图2 可抢占实例的相对价格(与同规格的按需付费实例价格相比)

根据上述可抢占实例价格特点，首先进行工作流的配置和调度。配置算法如算法1所示：

算法1工作流资源调度(BFRC)

输入：工作流、工作流执行时限、可供选择的资源、可抢占实例的历史价格数据。

输出：工作流的资源调度。

步骤1工作流的全部任务选择最贵的资源(即算力最强)，计算整体工作流的执行时间；

步骤2对工作流的各个任务进行分类；

步骤3根据工作流执行时限和工作流的执行时间，分配各个任务的执行时限；

步骤4根据任务的执行时限，为各个任务选择合适的可抢占实例；

步骤5按照特定优先级，调整各个任务的资源使用。

步骤1是在工作流执行前的初始化配置，主要是为了得到整体工作流的执行时间，由此确定工作流是否能在执行时限内完成。

步骤2是对工作流中的任务进行分类，如图 3所示，这里借鉴了Yu等人[14]的分类方法，将任务分为简单任务和同步任务2类：前驱或者后继不止一个的任务分类为同步任务，其它任务为简单任务。同步任务在工作流执行的过程中起到了对其他任务的同步作用，这类任务对于工作流的影响比其他任务更明显。然后对简单任务进行筛选，如果简单任务为某同步任务的唯一后继或者唯一前驱，那么调整该简单任务所产生的影响和调整其相邻的同步任务所产生的影响类似，所以该简单任务也应该归属于同步任务。

Figure 3 Classification of workflow task图3 工作流任务分类

步骤3和步骤4是按照各个任务的工作量，分配相应的执行时间，这样使得每个任务的执行时间和选择的资源尽可能平均。

步骤5是为了利用工作流中剩余空闲时间，从而进一步降低各个任务的规格。如图 4中的任务A、B分别有1.7 h和1.6 h的执行时限,各自的计算时间为1.0 h，如果将时间碎片合并利用，A的计算成本可以进一步降低。除此之外，不同类型的任务对工作流计算的影响程度也不同，对此我们更倾向于优先降低简单任务的节点规格，如图 3所示，可以同时降低相同起点和终点的多个简单任务的计算成本。

Figure 4 Using time fragments in the workflow图4 利用工作流中的时间碎片

当完成工作流执行前的资源配置之后，需要考虑如何在工作流执行时使用可抢占实例，即设置任务的执行时限来减少计算成本。首先要保证每个任务的执行时限不会导致工作流超时，即每个任务都不能晚于最晚完成时间完成计算。其次图 5表示理想状态下，每种可抢占实例在不同执行时限的情况下的最低价格。从图5中可以发现，价格和执行时限有着非常大的关系，除了large和xlarge这2种可抢占实例的价格范围相近，其他类型之间的价格范围差距很大。考虑到这是理想情况下的结果，实际上各种出价策略下各个可抢占实例的价格变化可能会更小。因此，对于每个任务增加执行时限的比例不如降低规格所带来的成本降低更大。在这种情况下，每个任务的执行时限不应该过大，例如当任务的执行时限和计算时间的比例超过1.5倍时，反而有可能会出现如图4所示的时间碎片过多的情况。或者在任务的执行时限比较大的情况下将计算资源调整为更加廉价的可抢占实例。综上，对于每个任务的执行时限有2个上限，只需要选择其中比较小的作为任务的执行时限即可。

Figure 5 Spot instance relative minimum price图5 可抢占实例最低相对价格

3.3 成本估计方法

确定任务所选择的可抢占实例类型之后，还需要考虑如何降低可抢占实例的购买成本，从而在工作流执行时限内降低计算成本。这样问题就变为单任务的可抢占实例购买问题，本文给出了不同出价的成本估计方法，通过估计不同出价的成本可以得到成本最低的最优出价。

首先假设该计算任务一共需要ch完成，执行时限为th，假设代价函数为cost，那么根据可抢占实例的特点可以设置一些边界条件。

首先要保证该任务不能超时，还要考虑到可抢占实例可能会由于市场资源紧张而出现购买失败或者被释放的情况，所以在c=t时，必须使用按需付费实例来进行计算，此时cost=priceod*c，其中priceod是按需付费实例的价格。

s代表可抢占实例的市场价格，则s∈(0,priceod]。当c=t-1时，为了避免使用按需付费实例，用户出价应为priceod。根据上文的假设，可抢占实例一定会购买成功，且不会被释放，可以得到：

(1)

其中si代表ih后可抢占实例的市场价格。

cost(t,b)=g(b)*E(s)+(1-g(b))*

(2)

其中s≤b，如此可以将一个问题进行递归求解。当c≥2时，还需要考虑剩余的任务要如何处理，所以相比于c=1的情况，在成功购买时，这里又多了一项cost(c-1,t-1,b)，其中c代表所需要的计算时间，t代表执行时限，b代表用户出价。因此，计算成本可以表示为:

cost(c,t,b)=g(b)*

E(s+cost(c-1,t-1,b))+(1-g(b))*

(3)

3.4 价格预测模型

在得到了估计不同出价时计算成本的递归求解公式之后，接下来的问题就是如何得到其中的g(b)和E(s)等函数。这些函数很明显和可抢占实例的价格有着很大的关系，如果可以预测可抢占实例的未来价格，便可从中得到这些函数的计算结果。

这里使用马尔科夫模型来预测可抢占实例的价格变化。首先根据已有的历史价格数据得到概率转移矩阵P，其中pss′代表可抢占实例价格从s变为s′的概率，然后通过该矩阵来预测未来价格。由于未来价格还和当前价格有关，所以cost、g(b)等函数需要增加参数进行计算，其代表当前可抢占实例的价格。可以得到：

(4)

(5)

将式(4)和式(5)代入式(3)中化简得到：

cost(c,t,b,s)=

(6)

如果增加实例被释放或者购买失败的成本，则式(6)可以写为:

cost(c,t,b,s)=

(7)

其中，r是可抢占实例回收产生的成本。

如此便得到了计算不同出价的成本估计函数，用户出价b为成本估计的最小值：

(8)

4 实验评估

4.1 实验设置

工作流：本文使用由Pegasus[19]提供的具有代表性的工作流来进行测试，包括CyberShake、Sipht、Inspiral和Epigenomics。

资源设置：使用阿里云的不同可用区的数据，包括cn-beijing-h(北京地区h可用区)、cn-shanghai-f(上海地区f可用区)和cn-shenzhen-e(深圳地区e可用区)。本文使用g6系列的实例进行测试。此外，历史价格为可抢占实例在2019年10月10日到2019年12月19日的价格。这些历史价格的数据特征如表1～表3所示。

Table 1 Available zone cn-beijing-h g6 family price characteristics

对比算法：本文选取Poola等人[17]提出的AIB(Aggressive with Intelligent Bidding)算法作为对比，该工作也是利用可抢占实例来降低工作流

Table 2 Available zone cn-shanghai-f g6 family price characteristics

Table 3 Available zone cn-shenzhen-e g6 family price characteristics

的计算成本。基准实验为全部都用按需付费实例执行工作流。在实验验证中，每组实验进行30次取平均值，每次都随机选择开始时间。每次测试的工作流执行时限大小从工作流执行时间的1.1倍开始，然后逐渐递增到3.0倍。

最低成本下限：为了更好地理解不同算法对工作流计算成本的节省效果，这里定义了最低成本下限。为了简化计算，假设工作流从开始到结束只有一条路径，那么其配置最多有2种可抢占实例，例如只有3xlarge和2xlarge，所以其配置比例变化可以近似为如下不等式：

(9)

Figure 6 Relative cost of WCSSI and AIB, the benchmark is the cost of all on-demand instances图6 WCSSI与AIB的相对成本，基准为全部使用按需付费实例的成本

其中，w为计算任务大小，d为最长计算时间(deadline)，t1、t2分别是2种可抢占实例的执行时间，c1、c2分别是2种可抢占实例每小时能够完成计算任务的大小，p1、p2分别是2种可抢占实例每小时的价格，不妨假设c1>c2，根据图 5所展示的关系，有1

(10)

4.2 实验结果与分析

实验结果如图 6所示，其中WCSSI的成本比AIB的成本更低。在图 6中，WCSSI的成本是基线成本的 10.1%～19.8%(最高可节省89.9%)，平均为11.7%；相对于AIB为76.8%～104.2%(最高可节省23.2%)，平均为94.2%。这得益于对于任务的分类处理，通过优先对简单任务调整可抢占实例类型，使得更多简单任务也因此受益，从而使得工作流使用更多价格较低的可抢占实例，进一步降低工作流的计算成本。而AIB则是为先执行的任务分配廉价资源，再对后执行的任务分配。这样的结果是先执行的任务可抢占实例价格很低，但是执行时间特别长，而后执行的任务只能使用较为昂贵的资源，从而增大了工作流的计算成本，这也是在某个区间内工作流执行时限越大成本反而上升的原因之一。对于结构复杂的工作流，例如CyberShake，简单任务节点很少，甚至没有简单任务节点。这种情况下WCSSI的性能和AIB的性能类似，但是受益于资源平均分配的策略，WCSSI能够有效避免出现反常成本上升问题。

表4是WCSSI表现优于AIB的比例，在大部分工作流和可用区价格数据下都达到了90%以上(在Inspiral工作流与cn-shenzhen-e价格数据上，WCSSI优于AIB比例最低，为65.2%)。在WCSSI成本高于AIB的情况下，成本高出的平均比例为1.1%，差距并不明显。在其它WCSSI优于AIB的情况下，成本比例为89.7%～98.2%，平均为93.5%。在所有工作流和可用区价格数据组合下，当WCSSI成本高于AIB时，成本高出比例为0.5%～1.9%，平均为1.0%。

Table 4 WCSSI outperforms AIB experiment ratio

除此之外，WCSSI的成本最终收敛到基线成本的10%，结合图 5所示的平均价格，这可能代表计算成本优化已经接近上限，接下来将对此进行分析。

从图 6e和图6f可以发现，WCSSI的折线轨迹基本和最低成本下限一致。考虑到工作流Inspiral 中非简单任务的比重极少，且各个分支比重相当，可以近似为多个假设的工作流混合而成，所以认为WCSSI已经达到了最低成本下限。

而图 6g和图 6i中WCSSI成本低于最低成本下限，这是因为Epigenomics不符合且不可近似为上述假设的工作流，简单任务和非简单任务在工作流中都有着很大的比重。由于WCSSI优先降低简单任务的成本，所以低成本可抢占实例在工作流中所占的比重会比估计的要高，从而使得WCSSI的运行成本低于最低成本下限。

综上，WCSSI得出的工作流计算成本可以达到最低成本下限。

5 相关工作

云计算中可抢占实例的出现，为降低工作流执行成本提供了巨大优化空间，Poola等人[17]通过结合使用可抢占实例和按需付费实例，以在满足执行时限的要求下降低工作流的计算成本。其使用激进算法和保守算法来估计工作流中各个任务的执行时间，然后使用计算得到的最晚执行时限(按需付费下)来决定工作流在执行的过程中是否可以使用可抢占实例来降低成本。WCSSI相比于该算法，考虑了不同任务对于工作流执行时限的不同影响，通过对任务进行差异化处理可以更好地节省工作流计算成本。在购买可抢占实例的策略上，Zafer等人[12]将其建模为动态规划问题来得到最优出价策略，但是其没有考虑实例被释放所带来的成本，且价格模型比较简单。本文提出的成本估计方法则考虑了实例释放所带来的成本，且使用马尔科夫模型，更加贴近实际情况。

6 结束语

本文提出了满足工作流执行时限的可抢占虚拟机实例配置和调度方法，可以极大地降低工作流的计算成本。本文选取了有代表性的工作流负载，并在阿里云真实数据上进行了实验验证。实验结果显示，本文提出的工作流调度方法可以最高节省89.9%的成本开销。在未来的工作中，我们会考虑可抢占实例的性能变化因素，并在工作流配置和调度中考虑其对执行时限的影响。