基于启发式算法的混合云工作流调度算法

Hybrid Cloud Workflow Scheduling Algorithm Based on Heuristic Algorithm

摘要: 伴随着“互联网+”技术的飞速发展，世界各地的网络环境越来越好，通过云计算技术操作异地计算资源的情况也越来越多。其中当本地资源不足时，私有云、公有云混合的混合云方案被各大企业广泛应用，本文针对混合云环境中的工作流任务调度问题，研究在满足任务截止期约束的同时使私有云利润最大化，节约企业成本。在私有云环境中，本文提出了一种优化的蚁群算法(Ant Colony Optimization Workflow Scheduling, ACOWS)用于工作流在用户指定的期限内完成任务的执行。在此基础上提出混合云下的动态多工作流调度算法(Hybrid Cloud Deadline-Constrained Cost Workflows Scheduling, HCDCW)，该算法将优先在私有云中调度执行，当任务执行时间超出任务截止期约束时，使用公有云调度部分工作流。在实验阶段，利用WorkflowSim仿真平台对算法进行了验证，实验结果表明在不同截止期，该调度算法相比于传统混合云工作流调度算法能有效的帮助企业在使用混合云过程中降低租用公有云的费用成本，并获得更快的执行时间。

Abstract: With the rapid development of the “Internet+” technology, the network environment around the world is getting better and better, and there are more and more cases of operating remote computing resources through cloud computing technology. Among them, when the local resources are in-sufficient, the hybrid cloud solution of private cloud and public cloud is widely used by major enterprises. This article focuses on the workflow task scheduling problem in the hybrid cloud environment, and researches to maximize private cloud profits while meeting task deadline constraints, to save business costs. In a private cloud environment, an optimized Ant Colony Optimization Work- flow Scheduling (ACOWS) is proposed in the article for the workflow to complete the execution of tasks within the time limit specified by the user. On this basis, a dynamic multi-workflow scheduling algorithm (Hybrid Cloud Deadline-Constrained Cost Workflows Scheduling, HCDCW) under the hybrid cloud is proposed. The algorithm will be scheduled and executed in the private cloud first. When the task execution time exceeds the task deadline constraint, use the public cloud to schedule part of the workflow. In the experimental phase, the algorithm was verified using the Work-flowSim simulation platform. The experimental results show that compared with traditional hybrid cloud workflow scheduling algorithms, this scheduling algorithm can effectively help enterprises reduce the cost of renting public clouds in the process of using hybrid clouds at different deadlines, and get faster execution time.

1. 引言

云计算平台使用分布式计算、虚拟化等技术整合了大量的计算设备及基础设施，并通过网络为用户提供计算、数据存储等资源和相关服务，因其高效、廉价和易维护等特点被广泛应用。此外，它还可以帮助公司和企业在不增加成本的前提下利用高效的处理能力创建大型数据中心。其中混合云架构方案被各大企业广泛应用，混合云是公有云和私有云的混合体，企业需要结合使用私有云和公有云来利用它们所提供的独特优势：即应用工作负载在私有云中到达阈值水平后，突然进入公有云，获取额外的计算资源，利用公有云平台为用户节省了时间和金钱 [1]。对于云计算来说，如何管理云计算资源至关重要，特别是当多个服务同时在云上使用它们的应用程序时。因此，对于资源管理，云计算需要一个合适的调度策略。良好的任务调度算法可以优化服务质量参数(QoS)，如最大完工时间、响应时间、吞吐量、资源利用率、任务拒绝率、可靠性、可伸缩性、能耗、执行成本等，并可以在不违反服务级别协议(SLA)的前提下，考虑各类约束，例如截止日期、优先级、经济成本等，实现用户的硬指标约束，同时可避免负载不均衡发生。云工作流调度中的云资源的选择，是一个典型的NP困难问题‎ [2]。

在云计算领域，国内外学者关于工作流调度问题做了许多有价值的研究，提出一些静态调度算法 [3]。静态调度算法可以分为基于启发式的算法和随机搜索算法。启发式算法根据使用方的主要思路，又分为：1) 将任务首先按照一定规律进行拓扑排序，然后依次调度的列表类启发式算法；2) 将父节点的任务复制到子节点，从而减少数据传递消耗的任务复制算法；3) 将任务划分为多个集群进行调度的集群类调度算法。随机搜索算法则主要指遗传算法、鸟群算法等群体算法，将可能的调度结果作为一个单独的搜索节点组成搜索空间的方式，对调度策略进行选择，从而得到结果。根据调度目标的不同，工作流调度算法可以分为多种类型，最常见的工作流调度目标是如何在最短时间内完成工作流的策略，这也是早期网格计算环境中的工作流调度通常考虑的问题。例如，文献 [4] 中的最早时间优先 (Earliest Time First, ETF)算法在每次挑选下一个被执行的任务时，将从所有已经就绪的任务中选出开始时间最早的一个来调度，以保证所有任务的调度时间最短，而每个任务的开始时间，是该任务在所有处理器上运行的最早开始时间。当两个任务的开始时间相同时，算法将选择静态排序更高的任务，从而确保每次都能选出下一执行节点。文献 [5] 则是通过比较任务在不同处理器上的最早就绪时间、最早开始时间、最早结束时间等，将任务分配到最快完成的可用机器上去。

针对混合云环境下的任务调度，文献 [6] 针对混合云提出了两种兼顾完工时间和利润的工作流调度算法，第一种是基于截止时间约束的成本优化单目标混合云中的工作流调度算法DCOH (Deadline-Constrained Cost Optimization for Hybrid Clouds)，在DCOH的基础上，提出了一种以最大完工时间和利润为目标的混合云多目标工作流调度优化算法MOH (Multi-Objective Optimization for Hybrid Clouds)，仿真结果表明，与现有算法相比，DCOH可以很好地为用户减少使用公有云的花费，MOH可以提供很好的成本与完工时间协调方案。但是该方案没有考虑到任务执行时间变化带来的影响，因此本文提出一种考虑到任务截止期限的算法，通过蚁群算法 [7] (Ant Colony Optimization, ACO)来优化在私有云环境下的工作流调度问题，该算法目标是寻找到最优解进行高效的工作流调度。这种群体智能优化算法的灵感来源于蚂蚁在寻找食物过程中发现路径的行为。当执行任务的时间超过设定的任务截止期限时，使用本文提出的HCDCW (Hybrid Cloud Deaalindline-Constrained Cost Workflows Scheduling)算法来将部分工作流调度到公有云环境中执行。

2. 混合云工作流系统架构及模型

本节中描述了混合云环境中，工作流的系统架构，工作流的任务模型，混合云中的工作流问题定义。

Figure 1. Hybrid cloud workflow system architecture

图1. 混合云工作流系统架构

2.1. 混合云工作流系统架构

图1所示为混合云环境中工作流系统架构 [6]。整个系统架构由工作流调度系统、混合云资源组成。在该系统中，由工作流调度系统来接收并判断来自云用户发起的任务请求，当云用户发起的任务连续不断到达时，如果请求被工作流调度系统所接受，则会由工作流调度系统决定云用户的请求是使用私有云环境中的虚拟机调度还是使用公有云中已经租用的虚拟机进行调度。在工作流调度系统中主要分为四层模型，其中监视器层(Monitor)负责收集并整理云资源中私有云和公有云的QoS信息，其中包括云资源的运行状态、响应时间、吞吐量、任务拒绝率等信息。控制层(Controller)负责接收来自云用户的请求，当一个请求到达时会对到达的请求进行过滤，过滤垃圾请求，让系统发起一次合规的工作流调度。接着交由服务层(Service)来处理工作流调度，并根据Monitor传来的云资源信息来进行工作流任务的分配，本文所提出的算法既在Service层实现调度分配。最后通过Service层中所选择的工作流调度算法对工作流任务完成一次调度，与云资源的交互是交由Manager层来处理，Service层不直接与云环境中的虚拟机进行通信，是通过调度Manager层所提供的接口来与云虚拟机进行通信。

2.2. 混合云工作流任务模型

独立任务之间彼此没有依赖关系，只需由任务调度器指定到虚拟机即可，而工作流任务存在执行顺序，运行较为复杂。每一个工作流任务，是由一系列的子任务和任务与任务间的数据依赖关系构成，任务与任务之间存在数据上的交互，某些任务需要上一个任务的完成才能继续执行，由于这种依赖关系的复杂性，因此使用有向无环图(Directed Acyclic Graph, DAG)来描述一个工作流任务 [8]。图2中使用DAG图表示一个简单的工作流示例，其中包括了9个任务节点，和12个依赖关系，节点1~9代表了任务节点，边a-l代表了依赖关系。

Figure 2. Workflow task model

图2. 工作流任务模型

通常的工作流模型可以依据DAG图来进行建模， $\text{W}=\left(\text{T},\text{E},\text{WD}\right)$ 表示一个工作流任务， $T=\left\{t_1,t_2,\cdots ,t_n\right\}$ 表示该工作流的子任务集合， $E=\left\{\left(t_i,t_j\right)|t_i,t_j\in T,i\ne j\right\}$ 表示任务之间的数据依赖关系，工作流W使用截止期限来约束，这个截止期限可以描述为WD (Workflow Deadline)，要求所有的工作流在这个WD的截止期限内完成。任务间的依赖关系使用(t_i, t_j)表示，t_j任务的执行受到t_i的限制，需要获取t_i执行完成的数据才能使工作流继续执行，任务模型可以描述为 $t_i:\left\{\text{TL}\right\}$，TL (Task Length)表示的在一个虚拟机实例中执行一个工作流任务所需要的执行长度。

2.3. 混合云工作流问题描述

为云用户提供IaaS服务的云供应商需要事先告知用户云虚拟机的参数，比如CPU、RAM、磁盘等信息。其中云服务商提供的虚拟机又可称之为实例，一个虚拟机称之为一个云实例。云实例中的CPU计算能力的好坏会决定一个任务在云实例中执行所需要的时间，(t_i, t_j)在这个模型中，两个任务t_i, t_j之间需要进行数据传输，耗时主要取决于数据传输之间的带宽。在本文中我们仅考虑CPU性能和网络通信带宽为虚拟机实例之间传输的主要因素。因此，可以使用cu来表示CPU的计算能力。使用bw来表示带宽。

定义1. 私有云中的资源模型：一个虚拟机实例可以被描述为公式1：

$\text{pr}=\left\{\text{cu},\text{bw}\right\}$ (1)

可以使用公式2来表示所有私有云环境中的虚拟机实例，其中r_i代表私有云中虚拟机实例，n代表拥有的虚拟机数量：

$\text{PR}=\left\{{\text{pr}}_1,{\text{pr}}_2,\cdots ,{\text{pr}}_{\text{i}},\cdots ,{\text{pr}}_{\text{m}}\right\}$ (2)

定义2. 公有云中的资源模型：一个虚拟机实例在公有云中可以描述为公式3，其中price表示是租用一个公有云实例所需的花费：

$\text{pu}=\left\{\text{cu},\text{bw},\text{price}\right\}$ (3)

使用公式4来表示共有云环境中的虚拟机实例，pu_j代表公有云中的虚拟机实例，k代表所租用的公有云实例的数量：

$\text{PU}=\left\{{\text{pu}}_{\text{1}},{\text{pu}}_{\text{2}},\cdots ,{\text{pu}}_{\text{j}},\cdots ,{\text{pu}}_{\text{k}}\right\}$ (4)

定义3. 混合云中的资源模型：混合云中的资源模型由公有云和私有云共同组成可以被定义为公式5：

$\text{H}=\text{PR}\cup \text{PU}$ (5)

定义4. 混合云中的完工时间模型。

私有云中的一个工作流的完工时间可以由两部分组成，其中一部分为一个工作流中的所有任务t_i在虚拟机中的完工时间，使用公式6来表示工作流任务在虚拟机中执行所需要的时间，使用I_p来表示一个任务在一个虚拟机实例中的完工时间：

$T_{\text{comp}}\left(t_i\right)=\frac{\text{tl}\left(t_i\right)}{\text{cu}\left(I_p\right)},I_p\in PR\cup PU$ (6)

另一部分为工作流任务中数据传输所需要的时间可以使用公式7来表示，其中 $tt\left(t_i,t_j\right)$ 表示的是两个工作流任务之间数据传输成本， $V_p$ 代表一个虚拟机实例当 $V_p=V_q$ 时，指两个任务在同一台虚拟机中完成：

$T_{\text{comm}}\left(t_i,t_j\right)=\{\begin{array}{ll}\frac{tt\left(t_i,t_j\right)}{\min \left(bw\left(I_p\right),bw\left(I_q\right)\right)},\hfill & V_p\ne V_q\hfill \\ 0,\hfill & V_p=V_q\hfill \end{array}$ (7)

因此可以使用公式8来表示混合云中的任务完成时间其中HT表示的是混合云中执行一个工作流任务的总耗时，PT指的是在公有云中调度任务所花费的时间：

$\text{HT}={\displaystyle {\sum }_{i=1,j=i+1}^n\left(T_{\text{comp}}\left(t_i\right)+T_{\text{comm}}\left(t_i,t_j\right)\right)}+\text{PT}$ (8)

定义5. 混合云中的花费模型：可以用公式9表示混合云中的花费，其中 $P_v$ 表示的是租用的每一台共有云所花费的价格：

$\text{Cost}={\displaystyle {\sum }_{i=1}^m{P}_v}$ (9)

3. 混合云中的多工作流调度策略

3.1. 私有云环境中的多工作流调度算法

由于私有云中的算法无需考虑价格花费，而公有云中的算法需要云用户去花费大量金额去使用。因此，要最大化私用云的使用效率，本节中，讲诉了一种基于优化QoS为目标的Ant Colony Optimization Workflow Scheduling (ACOWS)。改算法基于优化的蚁群算法，基于蚁群算法的工作流调度优化技术已被用于资源调度优化的问题，因此采用本算法来进行私有云环境中的工作流调度，而传统的蚁群算法根据优化协商过程寻找最佳匹配会陷入局部最优解，因此本算法在执行工作流调度过程中引入一个随机匹配过程，来防止局部最优解，ACOWS的具体过程为：1) 确定任务需求，生成随机调度策略；2) 基于资源可用性启动多蚂蚁机制；3) 启动协商过程；4) 生成可行的调度方案；(5) 通过QoS对调度方案的效果进行评估；6) 生成合适的调度方案；7) 生成资源分配和调度方案。

ACOWS算法的伪代码如下：

该算法目标是寻找到最优解进行高效的工作流调度。这种方法是其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。由虚拟机帮助我们生成随机初始值，最后通过优化方案在虚拟机上寻找到最优的调度策略。

所提出的QRAS代码的工作原理如下：算法过程从用户任务的输入开始。然后，系统分析器对任务进行验证，同时将其列入可使用的列表。开始寻找空闲的资源，并将其放入可用性列表。由于可用性列表中有大量可用资源，多个蚁群系统启动协商过程。它通过查看所有可能的结果来生成初始解。该过程将继续生成解决方案，直到满足终止条件。这些解决方案存储在临时列表中以供评估。此外，基于QoS的评估确定了合理的解决方案，其他则发送到评估列表中。

这些标准化解决方案能够以可承受的成本和时间执行每项任务。此外，已经根据虚拟映射形成虚拟机的放置。它通过在所有的解决方案中找到最佳结果来定义最优调度。然后，任务执行过程开始，将最佳工作负载分配给资源。随着任务执行的结束，资源释放到可用状态。此过程将一直持续到用户完成任务为止。

3.2. 混合云环境中的多工作流调度算法

由于目前企业中大多采用混合云形式来部署任务节点，为了节省企业利润，提升私有云资源利用率，因此要最大化利用企业中的私有云资源，又要保证私有云中工作流调度的执行时长等效率问题，因此使用算法1的ACOWS算法在私有云环境中优先调度工作流任务，当工作流任务的执行时间超过了所期望的工作流调度时间(WD, Workflow Deadline)，则使用公有云环境调度部分工作流。本节中提出一种混合云环境中的调度算法Hybrid Cloud Deadline-Constrained Cost Workflows Scheduling (HCDCW)，很好的解决了上述问题。

HCDCW算法伪代码如下：

4. 实验与分析

本节中为了验证HCDCW算法在混合云环境下多工作流执行的有效性、时间成本、费用成本，使用WorkflowSim [9] 模拟器实现了HCDCW算法。WorkflowSim是基于CloudSim [10] 开发而来的云工作流模拟器，在CloudSim开源平台上增加了对工作流调度的实现，增加了对工作流的任务聚簇、资源配置、任务调度等功能。同时WorkflowSim它提供真实云环境的功能，如数据中心、虚拟机、用户、Cloudlet和带宽等，用于配置和定制。WorkflowSim工具要求使用JDK 1.6以上版本，可以使用Eclipse、NetBeans或者Ant来使用WorkflowSim。本文模拟实验使用的环境参数为MacBook Pro (16-inch, 2019)、处理器为2.6 GHz六核Intel Core i7、内存为32 GB 2667 MHz DDR4、JDK1.8。

本文将构建一个混合云环境，一个云服务厂商针对虚拟机实例提供多种收费机制。常见的收费机制有按需收费、预留收费和竞价收费，主要考虑按需收费机制，即对虚拟机实例按某个单位时间(例如Google以分钟计费，AWS、阿里云等以小时计费)支付计算时长费用，如果不满计费时长则按整计算时长收费。本文采用了表1的阿里云的计费方式。

Table 1. Types and prices of virtual machine instances billed by Alibaba Cloud on-demand

表1. 阿里云按需计费的虚拟机实例类型和价格

本实验中使用Montage数据集 [11]，根据仿真环境的配置，这两种数据集是适合于仿真环境的工作流数据，如图3所示为Montage工作流的形式。

Figure 3. Montage dataset

图3. Montage数据集

虚拟机的参数设置为表2所示。

Table 2. Virtual machine parameter settings

表2. 虚拟机参数设置

4.1. 执行时间

本节对比了HCDCW算法和传统MINMIN算法。

图4中表示了100个工作流任务的时候，私有云执行时间随wd最大截止期限的增大而变大。HCDCW算法的执行时长明显要低于MINMIN算法。因为HCDCW充分利用私有云资源，减少了私有云中虚拟机等待的空闲时间，提高了资源利用率。

Figure 4. Execution time of 100 workflow tasks

图4. 100个工作流任务的执行时间

4.2. 执行费用

本节对比了HCDCW算法和经典的HEFT (Heterogeneous earliest finish time) [3] 算法在费用成本上的比较。如图5所示，HCDCW算法相比于经典的HEFT算法，在执行花费上节省很多。

Figure 5. The execution cost of 100 workflow tasks

图5. 100个工作流任务的执行花费

5. 结语

本文以优化企业中日益增长的混合云工作流调度为研究目标，提出了混合云环境下动态多工作流优化算法。本文所提出的算法HCDCW在使用公有云的情况下为企业降低了费用成本，缩短了任务的执行时间。但由于企业中运行在私有云中的工作流任务，一旦调度到公有云执行，必然存在安全隐私等问题，后续可以考虑如何保证私有云到公有云中的安全传输。

基金项目

课题编号：2018YFB1700702；

课题名称：“互联网+”定制产品概念设计与智能互反馈方法；

计划类别：国家重点研发计划“网络协同制造与智能工厂”重点专项；

承担“互联网+”定制设计要素提取与设计意图理解的研究工作，研发“互联网+”定制产品概念设计与智能互反馈工具4个：设计要素提取工具、设计意图理解工具、概念设计案例采集工具、概念设计方案生成工具。