Activiti引擎的无状态云工作流调度算法

林国丹，黄钦开，余 阳，潘茂林

(中山大学 数据科学与计算机学院，广东 广州 510006)

0 引言

近年来，云计算凭借其灵活、高效的资源供给特性受到了工业界和学术界的广泛关注。通过动态提供易扩展的通常是虚拟化的资源，云计算使得使用者按使用量付费，通常只需投入很少的管理工作[1]。业务流程管理系统(Business Process Management System, BPMS)通过现代化的工作流软件技术手段，整合人员、系统、信息和事物，为现代企业中业务过程的执行提供自动化支持，以此提高生产力，降低成本，实现企业的战略目标[2]。云计算带来的优势激发了企业在云上部署BPMS的需求，使其从传统的企业内部系统转变成以软件即服务(Software as a Service, SaaS)模式提供工作流管理服务的分布式系统，即云工作流[3]。云工作流根据工作流引擎的性能、资源使用量计费，通常是以分布式引擎的方式部署在云上，为用户提供并行化、高可用的工作流服务[4]。

云工作流分为有状态和无状态两种实现架构[5-6]。在有状态云工作流中，工作流引擎保存业务流程执行过程中的状态信息，一个流程实例的所有请求通常只能由同一个引擎执行[7-8]。相反，在无状态云工作流中，所有关于流程实例的状态、任务等信息均存储在数据库，引擎之间通过共享数据库通信，每个任务执行请求都能被特定的调度算法分配到任意部署的引擎实例所执行[6]。在云环境多租户的背景下，工作流引擎必定面临流程密集、请求密集的场景。相比于有状态实现架构，无状态云工作流可以使流程实例占据更少的系统资源，请求的调度更加灵活。同时，无状态的实现使得云工作流不用考虑状态和任务的迁移恢复而进行引擎实例的增减，对云工作流系统的伸缩性、稳定性更有保障[9]。

无状态云工作流的实现通常使用开源、轻量级的工作流引擎——Activiti[10]。无状态云工作流通过部署多个Activiti引擎实例，使用一般无状态服务调度算法，如轮询等，将流程请求分配到不同的引擎实例。然而，Activiti中业务流程请求执行过程往往需要工作流流程信息，每一个任务请求(查询请求除外)的执行都需要工作流引擎内存中存在流程模型，以便知道流程实例运转的下一个节点，否则引擎需要重新解析流程定义可扩展标记语言(eXtensible Markup Language, XML)文档构建内存模型，整个过程非常消耗时间和系统资源(XML解析总是如此)[6]。为了改善工作流执行性能，Activiti引擎底层通常使用固定大小的流程模型缓存来存储流程文档解析之后的结果，并使用最近最少使用(Least Recently Used, LRU)算法来更新替换缓存内容。但是，无状态调度的方式使得同一个流程定义下流程实例的请求会被分配到多个引擎实例上执行，在用户量大、流程定义多的云环境下，每个引擎都需要解析大量不同的流程定义文档并存储到引擎缓存中。同时，由于工作流流程实例常常是长时间运行的，引擎有限的流程模型缓存会出现频繁的替换更新过程，极端情况下，每个任务执行请求都需要引擎重新解析流程定义文档构建流程模型，这样会大大降低工作流引擎的服务性能质量。

因此，针对无状态云工作流引擎底层处理业务流程出现的上述问题，本文以Activiti为研究对象，根据Activiti引擎内存流程模型缓存机制，提出一种无状态云工作流流程实例任务请求的调度算法。对于每个请求对应的流程定义，该算法根据最近是否解析过该流程定义对引擎实例进行分组，使得同一流程定义下的流程实例请求尽量分配到少数的引擎，从而提高引擎内存流程模型缓存命中率，减少数据库查询次数和解析流程定义文档构建内存模型次数，提高工作流服务性能，节省系统资源。

1 云工作流调度

工作流调度是云工作流中非常重要的一个问题，合理的调度对系统的性能有着重要的影响，当前有很多文献研究了云工作流的调度问题。云工作流调度根据不同的功能性和非功能性需求将工作流任务映射到云上不同的虚拟机上，试图通过考虑各种调度目标和因素来优化解决NP-hard调度问题。文献[11-12]总结了目前在云工作流中存在的调度算法。现有的工作流调度算法分别考虑了包括时间、成本、吞吐量、资源利用率、调度成功率等各种因素，结合不同的使用场景应用于实际系统。例如，文献[13]考虑了可靠性、响应时间、成本和安全4个要素，针对不同服务质量(Quality of Service, QoS)要求，采用蚁群算法对流程调度进行优化；文献[14]考虑了资源利用率、完工时间和成本，提出基于粒子群优化(Particle Swarw Optimization, PSO)算法的启发式调度算法；文献[15]提出一种新的基于QoS的工作流调度算法，试图在满足用户定义的截止日期的同时，将工作流执行的成本降至最低；文献[16]考虑截止日期和预算两个因素，提出一个最小化执行成本同时满足交付结果的调度算法。

然而，目前存在的云工作流调度算法都是针对有状态云工作流，而对于无状态实现架构的调度算法研究几乎没有。当前针对云工作流调度问题的算法都是基于有状态工作流引擎的，即业务流程的执行是有状态的，并且常常是长时间运行的。一个流程实例的所有请求通常只能由同一个引擎执行。在此基础上，调度算法考虑的是以流程实例为单位，根据不同QoS要求来调度流程任务，以最少的成本完成工作流的执行，通常涉及到具体任务的执行。这种情况下，将目前存在的云工作流调度算法应用于有状态工作引擎上，是快速实现工作流服务云化的手段，但是，在无状态云工作流中，由于工作流引擎不再维护流程实例执行过程中的状态信息，业务流程请求通常被视为普通云环境下的无状态请求，在调度中可以使用现成的无状态服务负载均衡算法，如随机算法、轮询算法等。与有状态云工作流考虑以流程实例为单位调度不同，无状态云工作流的调度是以请求为单位，更小粒度地实现任务请求与引擎资源的映射，因此当前存在的云工作流调度算法并不适用于无状态的实现架构。

2 Activiti流程模型原理

Activiti是一个开源易用的工作流流程引擎，其核心是BPMN 2.0[17]。通常情况下Activiti引擎以一种无状态的方式工作，所有关于流程实例的状态、任务以及其他归档信息均存储在数据库中。在云工作流中，Activiti引擎允许以集群的方式部署，集群中的引擎节点之间通过操作同一数据库进行通信，当集群中的任意节点需要获取一些流程状态时，可以直接从数据库读取或写入[6]。

虽然使用Activiti引擎能够使云工作流以一种无状态的方式工作，而且目前已经有许多研究人员根据不同的应用场景和优化目标提出了很多无状态负载均衡调度算法[18]，然而，无状态云工作流的调度又与云计算中一般的无状态服务调度不同。虽然Activiti引擎在执行流程请求时不会记录保存操作者以及操作的数据，使得一个流程实例的请求能由不同的引擎实例执行，但是业务流程执行过程往往需要相应的流程模型，以便知道流程下一个任务节点的信息。在Activiti引擎中，流程模型其实就是引擎解析流程定义XML文档，构造BpmnModel对象并将流程节点信息设置到对象属性中，最终转化为内部可执行的并存储在内存数据库中的POJO对象，其通俗描述如图1所示。而引擎解析流程定义XML文档转化为BpmnModel对象的过程包括读取封装流程定义XML文档文件流、初始化元素解析器、进行元素解析等，其时序图如图2所示[6]，整个过程复杂且非常消耗资源。

为减少流程模型解析次数，提升流程实例的运转效率，Activiti引擎使用缓存来存储流程定义文档解析之后的结果[6]。引擎底层通常限制缓存对象容器的大小，并使用LRU算法根据对象的访问顺序来维护缓存的更新替换，这样一方面可以避免引擎解析过的流程模型一直保留在引擎内存中，长时间的累积造成内存溢出，另一方面可以将太久没访问过的视为流程执行完毕或不再使用的流程定义的流程模型从内存中删去，达到垃圾回收的效果。

在无状态云工作流中，如果将工作流流程实例执行请求以普通的无状态请求处理，同一个流程定义下流程实例的请求会被分配到多个引擎实例上执行,在请求密集、流程密集的云环境下，每个引擎都需要解析大量不同的流程定义文档并存储到引擎缓存中。由于缓存大小的限制，所有引擎都需要在有限的内存缓存中频繁解析更新替换新的流程模型。极端情况下，处理每个任务执行请求时引擎实例缓存中都不存在相应流程模型，引擎都需要重新执行解析操作并替换缓存，这样会恶化工作流引擎服务性能。因此，无状态云工作流的调度还需要考虑引擎缓存中流程模型的分布，这样才能提高缓存命中率，减少重复的流程模型解析过程。

3 调度算法

正如第1章所述，面向Activiti引擎实现的无状态云工作流的流程实例请求调度算法需要考虑区别于普通无状态服务调度的工作流执行特点以及Activiti流程模型缓存机制，本章首先定义算法中出现的基本概念，然后给出算法的问题描述，最后结合伪代码描述算法的设计。

3.1 基本概念定义

本文提出的调度算法考虑到工作流流程实例执行需要流程模型的特点，下面将具体描述算法中出现的基本概念。

定义1引擎繁忙程度。引擎繁忙程度是时间周期内分配到该引擎的请求数与其最多能处理的请求数的比值，其形式化定义如下：

(1)

式中：Rcount表示时间周期内分配到该引擎的请求数量，Rlimit表示时间周期内该引擎最多能处理的请求数量。

引擎繁忙程度是衡量一个引擎剩余处理能力的重要指标。由于在Activiti引擎中，一个流程实例的执行请求大部分是查询请求和完成任务请求，而查询请求只需查询数据库，不需要流程模型。因此，指定引擎单独处理查询请求后，其余引擎只需考虑完成任务请求，可以用上述定义来描述引擎繁忙程度。

定义2引擎加权移动平均繁忙程度。引擎加权移动平均繁忙程度使用了文献[5]中给出的定义，通过一个预先配置的加权因子对引擎繁忙程度进行指数加权移动平均计算，得到当前引擎繁忙程度，其形式化定义如下：

(2)

式中：α为取值范围0～1的权重因子(也称遗忘因子),代表参考过去历史信息的度；Bt是在t时引擎的繁忙程度；St是在t时参考历史数据计算得到的引擎的加权移动平均繁忙程度。在本文提出的调度算法中，综合考虑了引擎的历史繁忙程度，对不同阶段的引擎繁忙程度观察值赋以不同大小的权值。

定义3引擎组。引擎组(EngineGroup[ProcessDefinitionID])是一个关联变量，维护了一个流程定义ID到引擎集合的映射。引擎组集合有大小限制，表示有哪些引擎最近执行过该流程定义对应的流程实例，是由负载均衡器使用LRU算法维护。

3.2 问题描述

本文研究面向Activiti引擎实现的无状态云工作流的流程实例请求调度问题，该问题描述为：设有N个配置相同、处理能力相同的Activiti引擎E1,E2,…,EN，每个引擎的处理能力为C，每个引擎能缓存最多Y个流程模型；现有M个流程实例P1,P2,…,PM需要执行，在t时刻第i个流程实例的负载为Li,t，其中i∈[1,M]；执行完所有流程实例后统计计算N个引擎的缓存命中率γi，其中i∈[1,N]，调度算法的目标是最大化引擎的平均缓存命中率，减少流程定义文档解析转化为流程模型的次数。问题形式化定义如下:

(3)

s.t.

(4)

式(3)表示执行完固定流程实例后Activiti引擎实例的最大平均缓存命中率的求解目标；式(4)表示任意时刻总负载不得超过引擎总处理能力。而引擎的缓存命中率计算需要统计执行以上M个流程实例的整个过程中缓存命中数Hiti和缓存不命中数Missi，其中i∈[1,M]，最终由下式计算得到：

(5)

3.3 算法设计

针对Activiti引擎的无状态云工作流的请求调度问题，本文提出一种新的算法：带引擎组的最小繁忙程度调度(Least Busyness with Engine Group Scheduling, LBEGS)算法。假设有一组工作流引擎E={E0,E1,…,En-1}，St(Ei)表示当前t时引擎Ei的加权移动平均繁忙程度，Y为视为过载的引擎繁忙程度阈值设定值，EngineGroup[ProcessDefinitionID]是引擎组，MINSt(E)表示t时引擎集合E中综合繁忙程度最小的引擎，即最空闲的引擎。算法的伪代码如下。

算法1Least Busyness with Engine Group

Scheduling。

Input:a set of Activiti engines E

over load valueY

engines group EngineGroup[processDefinitionID]

output:Selected Engine e

1 if EngineGroup[processDefinitionId] is NULL then

2 e=MINSt(E);

3 if e is NULL or e is dead then

4 return NULL;

5 end if

6 add e into EngineGroup[processDefinitionId];

7 end if

8 else

9 e=MINSt(EngineGroup[processDefinitionId]);

10 if e is NULL or e is dead or

(St(e)>Y and there is an engine n∈E with St(n)

11 e=MINSt(E);

12 if e is NULL or e is dead then

13 return NULL;

14 end if

15 end if

16 add e into EngineGroup[processDefinitionId];

17 end if

18 return e;

算法1首先要通过压力测试，测出单位时间周期内各个引擎的最大处理请求数(即引擎最大处理能力C)，以及统计当前时间周期内负载均衡器分配给各个引擎的请求数，计算所有引擎的加权移动平均繁忙程度；当接收到客户端流程实例任务执行请求后，获取请求中的流程定义ID参数，判断维护的引擎组里是否有该流程定义ID对应的数据，如果不存在，直接选择所有引擎实例中最空闲的引擎处理请求，同时将该流程定义ID和选择的引擎添加到对应引擎组信息，结束调度；否则，从该流程定义ID对应的历史执行引擎中获取最空闲的引擎，然后判断若该引擎当前繁忙程度未超过过载阈值，选择该引擎执行请求，若超过过载阈值，则从所有引擎中选择最空闲的引擎执行请求，然后维护引擎组信息，结束调度。

本文第1章提到Activiti引擎中缓存通常需要限制大小，且使用LRU算法维护，因此，在LBEGS算法中判断流程定义存在相应的引擎组，证明引擎组中的引擎在最近一段时间执行过该流程定义下的流程实例，引擎的缓存中可能仍存在相应的流程模型，因此，将任务执行请求在不过载情况下尽量分配到该引擎，这样可以更大概率地减少流程模型解析次数。算法1实际上是使得同一流程定义文档下所有请求尽量分配到少数的已经执行过的引擎上，但这并不意味着总是由这些引擎来执行请求，因为如果总是由同一个引擎来执行该流程定义下的请求，无异于有状态云工作流调度。因此，算法1在结合工作流执行特色的同时，考虑了引擎的繁忙程度，设置了引擎繁忙过载阈值，当引擎负载值超过阈值后需要做出应对，避免出现当前引擎超载后请求仍然被分配到该引擎上，导致引擎整体服务性能下降，甚至比分配请求到其他引擎实例重新解析流程定义文档性能更差。

4 实验

为评估本文Activiti引擎的无状态云工作流的流程实例请求调度算法的性能，本章首先介绍仿真实验的设计，然后给出实验得到的结果并加以分析。

4.1 实验设计

为验证本文所提调度算法的优点与不足，实验中分别测试对比了采用Random算法、Round Robin算法和LBEGS算法作为调度算法的无状态云工作流的执行性能。为了模拟现实的云环境，实验中工作流引擎和负载均衡器均独立部署在虚拟机中，虚拟机配置都为单核CPU、1 GB内存，缓存流程模型个数限制为20，彼此互相隔离。实验中启动了3个相同配置的Activiti工作流引擎，同时分别启动了使用Random算法、Round Robin算法和LBEGS算法作为调度算法的负载均衡器。

实验中流程定义是文献[5]中旅游行程预订的一个流程模型，如图3所示。在这个流程定义中，共包含7个用户任务以及启动事件和结束事件，子流程中包容网关处订酒店分支判断条件一直设置为真，随机选择订航班或订汽车线路。因此，启动流程实例后，每个流程按照顺序会执行6个任务。实验中先后共部署了100个图3的流程定义。对于Activiti工作流引擎来说，先后部署这100个流程定义使其具有不同的流程定义ID，可以视为不同的流程定义。启动流程实例时引擎会根据流程定义ID从数据库查询加载不同的流程定义文件，最终解析成不同的内存流程模型。

为了测试不同算法的性能，模拟现实云工作流下的多租户环境，实验中使用了一个开源的并发模拟请求负载工具——Gatling[19]。实验使用Gatling工具模拟了不同租户，每秒启动6个流程实例，控制每秒的请求量。流程实例的启动是随机的，每次启动流程实例都会随机从100个不同的流程定义中选择一个启动。而且，在一个流程实例执行过程中，相邻任务请求执行过程会模拟现实人为处理或者调用外部服务处理任务，相应暂停1 000 ms，防止一个流程实例的所有请求会在短时间内执行，与现实不符，对实验结果造成影响。

在实验中仿真模拟请求，每个流程实例包含12个请求，包括1个启动流程实例请求、5个查询任务请求、6个完成任务请求。整体模拟的请求信息如表1所示。

表1 模拟请求信息

4.2 实验结果与分析

本节从引擎流程模型缓存命中率和替换次数、数据库查询次数、请求平均响应时间等4个性能指标对提出的LBEGS算法进行综合评价。除此之外，本文实验也测试了LBEGS算法在负载均衡上的表现。

图4展示了3种算法在引擎流程模型缓存命中率上的表现。正如第2章所述，LBEGS算法使得同一流程定义文档下所有流程实例的任务执行请求尽量分配到少数引擎上。因此，从图4可以看到，相比于Random和Round Robin算法，负载从每秒20个请求到每秒50个请求，LBEGS算法下引擎流程模型缓存命中率都更高。而且，随之负载逐渐增大，Random和Round Robin算法下的流程模型缓存命中率会随之下降，但LBEGS算法下的流程模型缓存命中率仍能保持在85%以上。

本文提出的LBEGS算法能够提高引擎内存流程模型的缓存命中率，随之带来的就是在数据库查询次数、流程模型缓存替换次数上的减少，图5和图6展示了3种算法在数据库查询次数、引擎内存流程模型缓存替换次数上的表现。可以看到，相比其余两种算法,在不同负载下，LBEGS算法在数据库查询次数上减少了约10 000次，在流程模型缓存替换次数上减少了400～1 000次。

实验中还测试统计了所有请求的平均响应时间，图7展示了3种算法在请求平均响应时间上的比较。

从图7可以看到，不同负载下，相比于Random算法和Round Robin算法，LBEGS算法能使请求平均响应时间更少，因为LBEGS算法能保持流程模型的高缓存命中率，因此Activiti引擎需要查询数据库获取流程定义文档，然后再执行解析文档的操作次数会相应减少，以此带来的响应时间性能优化是显而易见的。然而，由图7可以看到，每秒请求量为20时，LBEGS算法下请求的响应时间并没有明显比其他两种算法更少，这是因为LBEGS算法中加入了引擎组，同一个流程定义下的请求会尽量分配给之前已经执行过该流程定义的引擎实例。因此，当负载较低、请求量较小，引擎繁忙程度不超过算法设置的过载阈值时，总是由当前引擎去执行请求，这样会导致一部分引擎负载较高，而其他引擎处于较空闲的状态，虽然LBEGS算法中流程模型缓存命中率高、流程模型解析次数少，但在这种情况下，部分引擎组中的引擎处于较高负载状态，从而导致最终处理性能下降。由此可知，LBEGS算法在负载较高的情况下表现更好，毫无疑问，这正适用于多租户下请求密集的云环境。

作为一个调度算法，本文也通过实验验证了LBEGS算法在引擎负载均衡上的表现。第2章提到，在Activiti引擎中，流程实例执行请求大部分是查询请求和完成任务请求，同时，查询请求只需查询数据库，不需要流程模型，在实现时可以设置引擎单独处理查询请求，而其他引擎只需考虑完成任务请求，引擎繁忙程度也因此可作为引擎负载的体现。在此基础上，实验测试了在使用LBEGS算法，每秒50个请求下，3个Activiti引擎实例的繁忙程度的情况。图8展示了LBRGS算法在均衡负载上的表现，其中横轴是时间，纵轴是引擎繁忙程度。可以看出，LBEGS算法能够保证引擎实例的负载均衡。

综上所述，在负载较高时，LBEGS算法能够在保证负载均衡的前提下，通过使得同一流程定义下的流程实例请求尽量分配给少数引擎执行，提高引擎内存流程模型缓存命中率，减少流程定义解析次数和数据库查询次数，降低请求平均响应时间，节省系统资源。

5 结束语

为了应对云环境下，云工作流引擎面临的多租户、请求密集的场景，本文针对当前无状态云工作流的实现，提出一个面向Activiti引擎实现的无状态云工作流的流程实例请求调度算法，即LBEGS算法。对于每个流程实例请求对应的流程定义，LBEGS算法根据最近是否解析过该流程定义对引擎实例进行分组，综合考虑工作流流程实例执行需要流程模型的特点以及Activiti引擎缓存机制，使得同一流程定义下的流程实例任务请求尽量分配到少数的引擎。通过对比实验得出：LBEGS算法在实现了引擎实例负载均衡的前提下，提高了引擎的流程模型缓存命中率，减少了请求平均响应时间，同时，减少了数据库查询次数，节省了云上系统资源。

虽然本文提出的LBEGS算法在Activiti引擎实现的无状态云工作流调度问题上表现更好，但仍有一些工作需要改进。一方面是算法中加入了引擎组，请求到来时算法首先从引擎组选择引擎，然后判断是否过载，若是，则需要从所有引擎中重新选择负载最小的引擎。实验结果表明，引擎过载值的设定会影响云工作流执行性能。如何针对云环境下不同负载动态设置过载值，是未来研究的一个方向。另外，本文提出的LBEGS算法是针对Activiti引擎提出实现的，在Activiti引擎上使用效果理想，但是在其他无状态引擎上是否仍有这样的表现，未来仍需继续测试改进。