Page 109 - 《软件学报》2021年第9期

陈立哲 等:基于日志挖掘的微服务测试集缩减技术 2733

加请求触发页面信息,如果该信息不为空,说明该请求是通过前端页面触发,可判定该请求为用户请求.
(3) 用户请求链生成
用户请求链生成以用户请求为起点,构建与之关联的服务调用关系,包括聚集与用户请求相关联的服务间
请求列表和从该关联请求列表生成调用链等活动,流程图如图 2 所示.

将与当前用户请求具有同一
已遍历所有 从关联请求列表递
开始 否 追踪标识(trace id)的服务 结束
用户请求 归生成请求调用链
请求记录纳入关联请求列表
是
Fig.2 Flow chart of user request chain generation
图 2 用户请求链生成流程图

其中,关联请求列表的形成基于微服务架构的另一重要组件“服务调用链监控”来实现.服务调用链监控主
要通过“埋点”技术,在微服务系统运行过程中采集、分析和展示服务调用情况,为故障诊断、性能优化等提供支
撑,例如,大众点评的 CAT,Twitter 的 Open Zipkin 以及 Naver Pinpoint 等.关联同一用户请求的服务请求共享同一
个追踪标识(trace id),故通过判定追踪标识的一致性即可形成用户请求对应的关联请求列表.
请求调用链的树形结构特征则使得其生成需要采用递归算法来实现,表 1 展示了一种基于深度优先的递
归算法.该算法遍历关联请求列表中的每条日志(第 1 行),如果日志数据不在当前请求链中,则基于该日志构造
请求链上的新节点(第 2 行~第 4 行),并以该节点作为根节点、以剩余日志数组递归执行算法(第 5 行),直至关联
请求列表遍历完成退出递归.
Table 1 Request chains generation algorithm
表 1 基于深度优先的调用链生成算法
算法. generateRequestChain(logs,chain).
参数:logs,关联请求列表(输入);chain,请求链(输出).
1 for each (log,index)∈logs do
2 if not chain.descendants_contain(log) then
3 if chain.log.service=log.service then
4 node←new ChainNode(log)
5 generateRequestChain(log.slice_to_end(index+1),node)
6 chain.append_child(node)
7 end if
8 end if
9 end for
(4) 事务集生成
由于用户请求链的数据结构为树形结构,生成待挖掘事务集的过程就是生成从根节点到所有叶子节点路
径序列的过程.算法也是基于深度优先搜索树结构,伪代码见表 2.
Table 2 Transaction set generation algorithm
表 2 基于深度优先的事务集生成算法
算法. generateTransactions(node,stack,D).
参数:node,请求链节点(输入);stack,辅助栈(输入);D,事务集(输出).
1 stack.append(node.id)
2 if node.children=∅ then
3 D.append(stack.reverse(⋅))
4 else then
5 for each n∈node.children do
6 generateTransactions(n,stack,D)
7 end for
8 end if
9 stack.pop(⋅)