Page 124 - 《软件学报》2021年第5期

1348 Journal of Software 软件学报 Vol.32, No.5, May 2021

14: instSizeMap←calcInstNum(S n ,D n ) //计算满足给定用户需求所需的实例数量
15: while (s←getNextSvc(T s ))≠null do //优先部署不被其他服务调用的服务
16: if deployInsts(ns,n,s,instSizeMap[s])=true then
17: S n ←S n \{s}
18: end if
19: T s ←T s \{s}
20: end while
21: unDeployedSvc←unDeployedSvc∪S n
22: end for
23: for s in unDeployedSvc do
24: if otherNodesCanSupply(s)=false then
25: deployOnMostCloseNode(s,ns) //部署在最近的,有着足够计算资源的节点上
26: end if
27: end for
28: return calcDiff(ns,os), rules
该算法的基本思想是,尝试以最低的演化代价为每个边缘节点都提供最低的平均响应时间.因此,算法 1 先
对每个节点进行规划(第 4 行~第 22 行),然后再针对无法满足的用户需求进行全局规划(第 23 行~第 27 行).第 6
行~第 10 行针对所有的用户需求,在不考虑服务之间的版本依赖的情况下,挑选出能够以最少计算资源服务最
多用户的服务.pickOneService(⋅)遍历服务集合,并返回所需计算资源以及能够满足的用户数量的比值最小的服
务.getMetDemand(⋅)在挑选出服务 s 能够满足的用户需求集合时,会自动扩展版本依赖关系,通过版本号中的
Major 来判断不同版本服务接口之间的兼容性,并允许使用兼容版本满足用户需求.buildMiniSvcTree(⋅)用于从
服务集合 S 中计算出满足服务集合 S n 内服务依赖的最小服务集合.通过对 S n 中的所有服务按照广度优先依次
选择满足最多用户且消耗较少资源的服务,已经出现在集合 S n 中的服务优先选中.路由规则为树的边缘与叶子
节点组成的键值对集合.
第 14 行的 calcInstNum(⋅)通过每个版本的服务的最大用户数量与分配给该服务的用户数量,计算出集合中
的每个服务需要部署的实例数量.考虑到调用一个服务接口时,该接口可能会多次调用其他接口,该函数利用上
一时间窗内的 Gateway 存储的请求转发历史数据,计算出每个服务接口被调用一次导致的调用其他服务接口
的平均次数最为调用,并在计算服务之间的调用时,乘上该系数.例如:用户 A 请求了服务 s j 的接口 i m ,调用一次该
接口会调用服务 s k 的接口 i n 平均 2.8 次,则服务 s k 满足的用户数量增加 2.8.在存在着更长的调用链时,以此类推.
在第 15 行~第 20 行部署实例时,getNextSvc(⋅)返回服务集合中没有别其他服务调用且能够利用最少资源服务最
多用的服务.如果该节点上没有足够的资源部署剩余服务,则部署到其他节点(第 23 行~第 27 行).
运行阶段,算法通过查询规划阶段生成的路由规则,为每个带版本依赖的请求选择合适的服务,并在当前系
统中选择一个距离用户最近,且同时服务的用户数量不超过最大数量的实例作为目标实例.
2.2 支持DevOps流程中部署需求的自适应算法
系统中复杂的服务依赖,让服务的部署、删除、版本升级等 DevOps 流程中相关的操作变得更加复杂,开发
人员需要耗费大量的精力来确保 DevOps 过程中系统的正确性.该部分自适应算法考虑了 DevOps 过程中的常
见操作,能够在确保服务依赖被满足的情况下,自动执行相关指令.本文在 DevOps 自适应过程中,仅仅考虑
DevOps 流程中部署需求,不涉及到用户需求.
2.2.1 抽象描述
考虑到不同场景下的复杂需求,每个不同的操作均提供了响应的布尔值类型的标记位,用于表征是否考虑
服务之间的依赖关系.由于部分操作对原有系统中稳定的依赖关系具有一定的破坏性,如删除一个被其他服务
依赖的服务实例,这里仅遵守 DevOps 流程中部署的操作指令,不考虑因该操作指令导致的依赖缺失.