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

殷康璘 等:基于混沌工程的微服务韧性风险识别和分析 1241

整个因果关系链路的构建算法如算法 2 所示.算法将输出已排序的若干以韧性风险所影响的服务性能指
标为最终节点的韧性风险影响链路,运维人员能够按照韧性风险影响链路中的性能指标对韧性风险所带来的
影响进行进一步分析.
算法 2. 因果关系链路构建算法.
输入:因果关系图 G,起始节点 N.
输出:因果关系链路集合 path_strings/
1. function searchSource(G,N)
//在因果关系图 G 中寻找异常性能节点 N 的影响链路
2. var search_result //图搜索结果,搜索的结果为一个树结构
3. search_result.node←N
search_result.children←[⋅]
4. _searchSources(G,N,search_result) //以 N 作为源节点开始链路搜索
5. //根据输出结果构建因果链路集合
6. path_strings←[⋅]; //待输出的链路集合
7. path_strings.push(N.name);
//将只有 N 一个节点的链路作为初始输入的缓存链路
8. _build_path_strings(search_result.children,path_strings[0]);
//通过图搜索结果构建韧性风险影响链路
9. return path_strings;
10. function _searchSource(graph,node,search_result)
//子算法:在 graph 中搜索影响节点 node 的节点,并把结果存在 search_result 中
11. links=getLinks(graph,node)
//获取 graph 中所有节点中包含 node 的边的集合 links
12. if links.length<1:
13. return;
//node 的邻接节点中没有继续需要追溯的节点,停止继续链路搜索
14. sub_graph=graph.remove(links);
//构建一张新的子图,在递归中使用子图进行根因搜索,以保证从两个方向都能追溯的边不会因为在
之前的递归中已经遍历而不会被再次搜索.
15. links=links.sort(links.weight) //根据边的权重排序,权重较高的边将优先输出
16. for link in links:
17. other_node←link 中除 node 外的另一个端点;
18. var child_result //将 link 的另一个端点当作下一个需要追溯的节点
19. child_reuslt.node←other_node
20. child_result.children←[⋅]
21. search_result.children.push(child_result);
22. _searchSource(sub_graph,sub_node,search_result.children[sub_node]);
//以递归的方式继续追溯链路
23. function _build_path_strings(node_children,cur_string)
//子算法:在缓存路径 cur_string 后根据 children 继续构建链路
24. if node_children.length<1:
25. return; //已没有后续节点,停止构建链路