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

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

3.2 因果关系图构建
基于在混沌实验中收集的系统性能数据集,本文提出的韧性风险分析方法将首先通过因果搜索算法构建
性能指标之间的因果关系图.因果关系图为由一系列表示性能指标的节点和表示性能指标之间因果关系的边
组成,因果关系图中所有的边仅表示性能指标之间的直接因果关系,不包含间接因果关系.若某个性能指标 X 影
响了另一个性能指标 Y,则用有向边 X→Y 表示.如果算法能明确两个性能指标 X,Y 之间存在因果关系但不能明
确是 X 影响了 Y 还是 Y 影响了 X,则用无向边 X—Y 表示.
本文中使用的因果搜索算法参考了 Sprite 和 Glymour 所提出的 PC 算法 [73] 的主要思想,最终,算法将输出一
张包含有向边和无向边的因果关系图.因果关系构建算法的具体流程如算法 1 所示,其主要包含两个步骤:因果
关系确立以及因果方向确立.在因果关系确立阶段,算法首先构建以数据集内性能指标为节点的完全图;随后,
对于任意两个性能指标 X,Y,算法通过判断 X 和 Y 是否条件独立来确定 X 和 Y 之间是否存在因果关系.若 X 和 Y
条件独立,说明 X 和 Y 之间不存在直接的因果关系,则在完全图中删除对应的边;最后得到初步的仅包含无向边
的因果关系图.在因果方向确立阶段,算法将先根据 d-分隔原则确定因果关系图中所有的 X→Y←Z 的结构,即
V-Structure;随后,根据在 V-Structure 中已经确定的有向边和一些逻辑推断规则(算法 1 伪代码的第 15 行~第 21
行),算法将进一步确定现有的因果关系图中部分剩余无向边的方向.例如,在已经确定图中所有 X→Y←Z 结构
的情况下,若发现结构 A—B←C,则可以直接判断边 A—B 的方向为 A←B.
算法 1. 因果关系图构建算法.
输入:混沌实验数据集 D,数据集 D 中的监控指标集合 V.
输出:因果关系图 G.
1. //因果关系确立
2. 以 V 中的元素作为节点,构建完全图 G
3. n←V 中元素的数量
4. for k from 0 to n:
5. for each X,Y 为 G 中的两个相邻节点,且邻接于 X 的节点数量大于 k:
6. for each 集合 W⊂V\{Y}为邻接于 X 的节点集合,且 W 的元素数量为 k:
7. if X,Y 条件独立于 W then:
8. 去除 X 与 Y 之间的边
9. 记录 W
10.
11. //因果方向确立
12. for each G 中相邻的 3 个节点 X—Y—Z:
13. if Y 不存在于所有使得 X 于 Z 独立的节点集合中:
14. 把 G 中 X—Y—Z 的方向修改为 X→Y←Z
15. for each G 中相邻的 3 个节点 X,Y,Z:
16. if X→Y—Z:
17. 把 Y—Z 的方向修改为 Y→Z
18. if X—Y and X→Z→Y:
19. 把 X—Y 的方向修改为 X→Y
20. if X—Y and 存在另一变量 L,使得 X—Z→Y 且 X—L→Y:
21. 把 X—Y 的方向修改为 X→Y
22. return G;
在确定两个性能指标 X,Y 之间是否存在因果关系的过程中,基于 d-分隔原则,需要判断 X 和 Y 在其他性能
指标为给定值的情况下是否条件独立.由于微服务架构系统中通过监控工具获取的系统性能数据大部分为连