面向交叉微服务链的任务调度优化

张宇鹏，吴自力，陈 鸣，张璐璐

(西安电子科技大学 计算机科学与技术学院，陕西 西安 710071)

随着云计算和容器技术的发展[1]，微服务架构已经越来越多地被应用程序设计和开发采用[2-3]。基于微服务的应用程序运行时，通常涉及多个微服务的执行和互操作，每个微服务独立实现、部署、更新[4-5]。尽管这种新的架构给开发人员带来了便利，但系统维护多个并发服务正常运行的同时，还需要保证服务之间的交互协作，这为基于微服务开发的任务调度带来了挑战[6-7]。

目前，已经有许多基于微服务架构的任务调度研究。文献[8]利用合作博弈论提出了一个多目标函数，通过考虑内存、CPU、用户预算等不同约束条件来降低节点能耗和任务最大完工时间。文献[9]考虑计算资源的异构特点，提出了一种针对异构多云环境的多目标任务调度算法。文献[10]考虑计算及存储资源的成本，设计了考虑定价机制的多目标云工作流调度模型，有效提高了云平台资源利用率。文献[11]同时考虑任务调度与微服务的伸缩性，在满足任务截止时间的同时最小化部署服务的成本。文献[12]提出了一个基于多代理的开发框架，用于处理微服务体系结构中的分布式事务。

在已有的研究中，研究人员较多考虑容器调度和资源管理对基于微服务的应用程序性能的影响，而忽略了多条微服务链访问共享微服务时产生的资源竞争问题。然而，用户每发起一次请求往往牵扯多个微服务的调用，当需要处理大量用户请求时，多条微服务链会产生多个交叉点，从而导致微服务间资源的竞争问题。综上所述，笔者将主要工作聚焦于微服务之间的竞争问题，设计了一种面向链的微服务任务调度算法来解决微服务链的交叉竞争问题，在提高资源利用率的同时，降低了任务执行的全局响应时间。

1 系统模型

假设一个小型应用程序中微服务的调用关系如图1所示，图中有4条微服务链，经过9个微服务。其中，2号、5号、6号都是可能发生交叉竞争的微服务，若调度策略不当，则会导致服务响应时间增加。

图1 一个小型应用程序中微服务的调用关系

为了对微服务链关系进行清晰表征，采用二进制编码的方式进行描述，服务间的调用关系可以表示为

1.1 响应时间模型

每个任务的完工时间包含当前执行任务的前继任务的结束时间以及自身执行任务花费的时间。单个物理节点的完工时间取决于在该节点上执行的任务队列中最后一个任务的结束时间。

微服务链i上服务j在物理节点p上处理任务的执行用时ri，j为

ri，j=hi，j/xp，

(1)

其中，hi，j表示链i上服务j所需处理的任务大小，xp表示物理节点p的处理能力。

链i上服务j的开始执行的时间为bi，j，物理节点p的完工时间fp可表示为

fp=max(ri，j+bi，j) 。

(2)

请求响应时间取决于最晚结束工作的物理节点的完工时间，全局响应时间Tglobal计算如下：

Tglobal=max(fp) 。

(3)

为保证单条服务链能合理执行，必须对任务的处理顺序进行约束，即在同一条链上，调用顺序靠后的服务必须在它的前继服务完工后才能执行，约束如下：

bi，j+1-bi，j≥ri，j，

(4)

其中，bi，j+1为链i上依赖于服务j的服务j+1的开始时间。

用Zi，j，p来表示链i上的服务j是否在物理节点p上处理。如果是，则Zi，j，p=1；反之，则取Zi，j，p=0。为保证在同一时刻有且仅有一个服务能够在物理节点p上运行，设计以下约束：

Zi，j，p=Zv，w，p=1，bv，w-bi，j≥ri，j。

(5)

该约束表示链i上的服务j和链v上的服务w都需要在物理节点p上处理时，服务w的开始时间要大于等于服务j的结束时间。

1.2 资源利用率模型

在集群物理资源有限的情况下，应尽可能最大化的利用物理资源。定义矩阵A来表示链和服务之间的关系：

A=(ac，m)C×M，

(6)

其中，C是微服务链的总数，M是微服务类型总数。ac，m∈{0，1}，ac，m取0时表示微服务链c没有穿过微服务m，反之取1。

应用的特征表示为〈Gset，Grelation〉，其中Gset是应用程序的微服务集；Grelation是服务之间的消费关系集。当一个微服务需要其他微服务生成的结果时，将建立消费关系，表示为(mcons，mprov)∈Grelation。矩阵S表示微服务节点上的资源分配情况：

S=(sc，m)C×M，

(7)

其中，sc，m表示链c上服务m所需要的资源数。

每个物理节点所拥有的资源数量用Im表示，则总资源数I可以表示为

(8)

链中微服务分配的资源不能超过部署该微服务的节点拥有的资源数，具体限制如下：

(9)

将单位时间内节点的资源利用率Ut形式化为

(10)

其中，E表示单位时间内正在执行的链的集合。时间Tglobal内的总体资源利用率U计算如下：

(11)

1.3 多目标优化模型

基于上述两小节的时间模型和资源模型可以得出以下多目标优化模型：

maxU，

(12)

minTglobal，

(13)

(14)

bi，j+1-bi，j≥ri，j，

(15)

Zi，j，p=Zv，w，p=1，bv，w-bi，j≥ri，j。

(16)

式(12)表示当总资源数一定时，最大化每一时刻的资源利用率之和同整条服务链的响应时间之比；式(13)表示最小化最晚响应服务的物理节点的全局响应时间；式(14)表示分配给任务的资源数不能超过节点的资源量；式(15)表示链中服务必须在其前继服务结束之后开始执行；式(16)表示每个节点在同一时刻只能处理一个任务请求。

2 面向交叉微服务链的任务调度算法设计

基于上述系统模型，为解决微服务调用链间的竞争问题，受闫群民等人[13]的启发，笔者将蚁群算法同模拟退火算法结合，提出了一种面向交叉微服务链的任务调度算法(Chain-Oriented Task Scheduling Algorithm，COTSA)。COTSA在蚁群并行寻求可行解过程中加入模拟退火的降温和Metropolis准则[14]，来降低蚂蚁走到局部最优的可能性。

2.1 关键函数及算法实现

2.1.1 蚁群的路径选择算法

算法将服务调用链看作一个森林，根据服务间的调用关系进行拓扑排序，排序结果构成n棵树。每次蚂蚁k必须选择森林中的根节点，将根节点加入待访问集合Callow(k)。当蚂蚁k基于转移概率选择Callow(k)集合中节点n作为下一个访问对象时，将该节点从Callow(k)中删除，此时在树中n的子节点将成为新的根节点加入集合Callow(k)供蚂蚁k进行下一次的访问。蚂蚁选择路径的转移概率为

(17)

其中，Callow(k)表示满足约束条件的一组可用节点；τi，j(t)表示链i上服务j在t时刻的信息浓度函数；ηi，j(t)表示链i上服务j在t时刻的启发函数；λ1和λ2分别是信息素和启发式信息的调节器，值越大表明启发函数对选择路径的影响越大。启发函数可表示为

(18)

其中，bi，j+ri，j表示截止到t时刻，链i执行到服务j的总时间；Tave表示在当前最优解情况下每个节点处理请求的平均运行时间。蚂蚁的路径选择算法如算法1所示。

算法1蚂蚁的路径选择算法。

① 输入任务拓扑排序结果集合

② for 序列 in 拓扑 do

③ if 存在以序列初始节点为根的树 then

④ 根据节点的前后继关系使用深度搜索构建树

⑤ else

⑥ 将当前序列的初始节点初始化为新的根节点

⑦ end if

⑧ 将新的根节点存入森林集合cforest

⑨ end for

⑩ for n in do

一旦蚂蚁遍历所有微服务，它经过的路径就可以作为一个可行解。为了得到最佳的可行解，需要对得到的可行解进行评估。根据笔者建立的多目标优化模型，将评估函数可表示为

E(X)=αU(X)+β[Tglobal(X)]-1，

(19)

其中，α和β分别是资源利用率和响应时间的权重系数。E(X)的值越大，X越接近最佳值，文中经过多组实验对比，将α和β的数值选定为0.8和0.2。

2.1.2 信息素更新

信息素更新如下所示：

τi，j(t+1)=(1-ρ)τi，j(t)+Δτi，j，

(20)

其中，τi，j(t)是路径ri，j时间t时的信息素；τi，j(t+1)是更新的信息素；信息素初始值为τi，j(t0)=1；信息素的消散因子为ρ，ρ∈(0，1)；1-ρ是信息素的挥发程度；Δτi，j是一次迭代后路径ri，j上增加的信息素浓度。Δτi，j的计算公式为

(21)

(22)

2.1.3 模拟退火算法中生成新可行解的扰动策略

为了能够加快蚁群算法的收敛速度，引入模拟退火算法，即每次蚂蚁遍历完所有服务后并不是立即返回到源点，而是随机交换在树中层数相同的两个节点生成新的可行解。将生成的新解的评估值同扰动前的解的评估值根据

ΔE=Ek-Q，

(23)

进行比较，得到两个解的差值。其中，Ek表示新的可行解的评估值；Q表示最优可行解的评估值；ΔE是评估新的可行解同当前最优可行解的差值，如果小于0，则表示新产生的可行解不如当前最优解。如果新产生的任务执行序列的资源利用率和任务响应时间优于当前解，则将其更新为最优解；否则，根据模拟退火的Metropolis准则判断是否接受新解。根据下式计算接受新解的概率：

(24)

2.2 算法流程

初始将多只蚂蚁都放置在超级源点上，蚁群会根据用户请求的不同随机爬行到不同的起始服务上，设定模拟退火中的初始温度并将初始信息素设定为固定的数值。随后通过上述中蚂蚁对路径的选择策略，选取要经过的节点。当所有蚂蚁都走到终点的时候，将路径上的信息素更新，同时保留所有爬行路径。COTSA算法伪代码如算法2所示。

算法2COTSA算法。

① 初始化信息素矩阵

② whileT>Tmindo

③ foriinN

④ 将所有蚂蚁放置在超级源点上

⑤ forkinKdo

⑥ 对服务之间的依赖关系进行拓扑排序

⑦ 分析排序结果得到蚂蚁行走的可行点集合

⑧ 蚂蚁k根据算法1的路径选取策略，从当前点走到下一个满足条件的物理节点，并将该点加入ri，j

⑨ end for

⑩ 根据式(21)对信息素矩阵进行更新

3 实 验

3.1 实验设置

将COTSA算法与先来先服务算法(First Come First Service，FCFS)和传统的蚁群算法(Ant Colong Optimization，ACO)从全局响应时间和资源利用率两方面进行比较。实验测试数据集采用阿里巴巴集群跟踪V2018集群数据集[15]。该数据集由6张表组成，提供了机器和容器的信息及资源使用情况，事件信息和工作负载的实例信息。表1描述了微服务之间的依赖关系以及微服消耗的资源数。Cconsume(i)表示微服务i消费的微服务集合，Rresource(i)表示微服务之执行时需要的物理资源数，Nrequest(i)表示微服务i的请求数，Nscale(i)表示部署了微服务i的容器数。

表1 微服务属性参数

通过评估参数对算法的影响，设定参数如表2所示。

表2 COTSA中的参数设置

3.2 相关算法比较

对比实验中，用户请求数在100～500之间变化，初始请求个数为100。

3.2.1 全局响应时间

图2所示为3种算法在用户请求的全局响应时间上的实验对比。实验结果表明，ACO算法的全局响应时间高于COTSA算法和FCFS算法的；当用户请求数小于300时，COTSA算法和FCFS算法的全局响应时间相近；当用户请求数高于300时，COTSA算法的全局响应时间相较ACO算法和FCFS算法分别降低了约12.67%和7.71%。这是由于COTSA算法结合了模拟退火算法的扰动策略，具有较好的局部搜索能力，提高了蚁群跳出局部最优的概率，故而找到了更好的可行解。

图2 不同用户请求数下的全局响应时间对比

3.2.2 单位时间内资源利用率

图3分别展示了用户请求量从100增加到400时，3种算法单位时间内的资源利用率。

(a)100个用户请求时资源利用率

图3中每条折线结束位置对应的时间即为3种算法求得调度序列所需要的执行用时。可以看出，相较于FCFS，COTSA和ACO算法的资源利用率变化较为平缓。这是因为这两种算法在进行调度优化时将平均资源利用率纳入考虑范围，在不影响服务之间前后继关系的前提下，调度排在后面的任务执行，以尽可能地减少物理资源的空闲时间，提高单位时间内资源利用率。

3.2.3 整体资源利用率

针对请求处理过程中的整体资源利用情况，对FCFS、ACO和COTSA 这3种算法进行了对比实验，实验结果如图4所示。

图4 不同用户请求数下的整体资源利用率对比

从图4可以看出，使用FCFS算法时，集群的资源利用率随着用户请求数的增多而逐渐降低，而ACO和COTSA由于任务调度的不确定性使得资源利用率的整体趋势呈上升状态。此外，COTSA在产生可行解的时候增大了跳出局部最优的概率，随着用户请求数的增多，解空间变大，COTSA通过在当前解的邻域中随机置换生成新的可行解，从而比ACO算法更容易找到全局最优解，故整体的资源利用率会高于ACO算法。结果表明，COTSA算法在资源利用率方面是优于FCFS算法和ACO算法的，相比这两种算法分别提高了约61.29%和44.68%。

4 结束语

针对微服务调用链间的资源竞争问题，以减少请求的全局响应时间及提高整体资源利用率为优化目标，笔者建立了多目标优化模型。同时，结合蚁群算法并行计算与模拟退火算法局部扰动的优势提出了COTSA算法对优化模型进行求解，得到调度决策。与FCFS算法和ACO算法相比，COTSA算法在减少请求的全局响应时间以及提高集群的整体资源利用率方面具有明显优势。