基于微服务调用链双向搜索的故障根因定位方法*

邹丹丹，丁建兵，王希栋，叶晓舟，欧阳晔

（亚信科技（中国）有限公司 通信人工智能创新实验室，北京 100193）

0 引言

随着软件体系结构的不断优化和多样化发展，微服务架构已经广泛应用于通信、互联网等各类大型企业的业务中。微服务是将软件应用拆分所形成的多个相互协作的小服务，可极大提高开发及维护的效率。在传统软件系统中，使用较多的是将整个功能模块和数据作为整体的单体架构。与之相比，微服务架构将业务按功能拆分，使其拥有较高的灵活性和容错能力、良好的动态扩展性以及可持续的集成性[1]。与此同时，网络云化技术的发展也推动了微服务分布式计算系统的发展，面向微服务的各类网络云化方案逐步走上舞台。随着微服务技术和网络设备云化技术的广泛应用，应用程序中的服务数量激增且形成了负载庞大的网络。

微服务系统具有与分布式系统相似的固有复杂性和服务依赖性。由于各级微服务间存在大量且复杂的调用依存关系，因此当某一微服务出现故障时，会带来相应的雪崩效应，其依赖的各级服务会在短时间发出大量的告警信息，这些海量的告警信息会降低运维效率；因此，如何高效地检测故障，实现异常检测及根因定位成为亟待解决的问题。其中，故障是指服务无法执行其功能，而异常是指故障引发的可观测现象。异常检测是依据观测到的异常现象，判断故障类别的过程。根因定位是依托异常检测，分析服务运行过程中可能发生的故障，定位到发生故障节点的过程。为了保障服务的安全性和可靠性，必须在微服务体系下实现高速响应的故障异常检测和根因定位。

目前，研究人员已经提出了很多不同的方案，来解决微服务中故障的异常检测和根因定位问题。异常检测和根因定位主要依托于观测到异常的时间附近所记录的数据，这些数据包括和应用服务程序有关的关键性能指标（Key Performance Indicators，KPIs）、调用链、拓扑图和日志等信息。按照使用数据的类别，异常检测和根因定位可以分为基于日志、基于调用链和基于监测数据等不同的类别[3]。本文重点关注基于调用链实现的异常检测及根因定位方案。

调用链是分布式系统中的重要数据，它表明了一个完整服务在分布式系统中的执行顺序或流程。在分布式系统中，通常可采用无监督[4-5]、有监督[6]或跟踪比较技术[7-8]来实现异常检测。

根因定位可分为直接分析调用链和由调用链生成的拓扑图驱动分析两种方式。在直接分析调用链的早期，业务人员往往借助可视化工具来分析调用链，人工排查根因位置。人工排查的方法可以在系统中较为准确地定位根因，但是效率往往较低。后来，研究人员考虑对调用链中的服务响应时间进行分析来实现自动化方案[4,9]。此外，由调用链数据构成的拓扑图也可以帮助实现根因分析，例如，在拓扑图上执行随机游走[10-12]或广度优先搜索[13]进行探索。基于拓扑图的方法无论是利用随机游走还是搜索算法都存在耗时问题，而且在很多真实场景下，也会由于数据缺失等原因无法构建有效的拓扑图，进而导致误判，准确率无法得到保证。基于因果图的广度优先搜索方法[14-16]大多处于实验阶段。基于AI 的方案也是目前异常检测和根因分析的主要研究方向，其中，基于机器学习、深度学习的方案在小样本环境中精度高，但是在海量数据下则会相应增加较多的训练耗时。上述各类方案距离落地仍存在一定距离。

在实际应用中，调用链根因定位方案通常由运维人员按照调用链顺序自顶向下深度搜索，逐个排查故障，存在耗时较长和准确率不足等亟待解决的问题。而本文基于双向搜索的思想，设计一种基于调用链双向搜索的故障根因定位（Trace Bidirectional Search，TBS）算法。该算法先自顶向下搜索调用链，搜索过程中并不直接判别根因，简化为仅统计故障节点及疑似故障节点的信息；再自底向上按层级检索快速定位根因，其时间复杂度为常数阶。所提算法已在某省级运营商实际上线，其Top 3 根因的准确率达到87%，平均定位耗时为15 s。本文算法在异常时刻前后一定时间周期内搜索相关的调用链，依据节点间的连接关系、节点延时和调用状态来挖掘深层复杂的根因节点，有助于运维人员进一步解决根因定位问题。

1 微服务异常检测及根因定位方案

微服务系统下的异常检测及根因定位的流程如图1 所示。

图1 微服务异常检测及根因定位方案流程

其中，数据库中保存了日志、关键性能指标和调用链等各类数据。异常检测模块利用这些数据实时识别出当前时间段的服务是否存在故障。若判断出存在异常，则输出该段时间的全量调用链数据。调用链根因定位模块则会对调用链数据依次进行清洗与预处理，自顶向下搜索异常节点和疑似异常节点，自底向上计算根因概率并在最后输出概率排序最大的Top 3 根因节点。运维人员可以依据输出的结果快速定位并修复相关节点，极大地提升了运维工作效率，保障了微服务的运行稳定。

本文重点关注根因定位模块，对异常检测模块则采用了通用方法。目前已有大量成熟的异常检测方案可以实时对这些数据进行故障检测。为了达到满足用户需求的服务等级目标（Service Level Objective，SLO），通常利用服务水平指标（Service Level Indicator，SLI）来对应满足设定的SLO。SLI表示业务服务质量的具体黄金指标，例如网络延时、吞吐量等。在微服务场景下，数据库中保存了大量历史业务核心指标，利用这些历史数据，可以使用通用的异常检测方案[4-8]实现关键性能指标的异常检测。本文方案通过对时延和成功率这两种黄金指标的阈值判定，实现指标异常检测。当时延高于阈值或成功率低于阈值的调用链比例达到设定的异常阈值时，判定该时刻为异常并触发根因定位模块。在阈值设定方面，考虑到随着时间的增长业务的时延范围存在漂移现象，即业务的平均时延会增加，以及业务人员也希望能够通过阈值来控制报告异常的数量，因此采用人工可调的方式设定时延和成功率的判定阈值。

2 微服务调用链节点根因定位

当异常检测模块的输出结果是某时刻存在异常时，则在该时刻前后的时间周期T内可能存在不止一条异常调用链。在微服务下存在大量错综复杂的服务调用关系，而生成的调用链是单向传播的，调用链上层节点的故障异常往往受底层节点的故障影响。调用链节点根因定位算法的目的是，已知某一时刻系统服务存在异常，在该时刻前后时间长度为T的时间段内，根据调用链数据，查找到底层的故障发生位置，输出这些调用链所使用过的微服务节点中最有可能发生故障的前K个根因节点，即定位到根本原因。

在实际业务中，评估根因定位模块输出的根因有准确率和召回率两种指标。由于这两种指标是互相制约的关系，因此需要权衡侧重点。较大的召回率意味着根因定位模块会反馈较多的根因，这会使业务人员疲于检查，严重降低运维效率。此外，当某一底层微服务所在节点位置发生故障时，有可能导致告警风暴，即大量的告警和异常在同一时间爆发。考虑到更高的召回率会给服务器计算带来极大的压力，因此相比召回率，本文更加重视准确率，使算法输出较为准确的结果。

2.1 数据清洗与预处理

在微服务系统中，业务调用的各个节点都会保存相关信息至日志中，将所有数据连接成链式结构就形成了一条调用链。每条调用链都拥有唯一的调用链序号TraceID。通常，调用链的方向都是自起点开始单向传播的。调用链从头节点起，会逐层调用不同节点，定义这里的层级为调用的深度。

在本文方案所应用的业务场景中，核心指标为节点延时和调用状态是否异常。节点延时是指该节点运行相应服务的耗时，调用状态表示该节点执行相应服务是否成功。

调用链数据预处理主要分为调用链抽取和数据处理两个阶段，具体如下文所示。

（1）调用链抽取：由于每条调用链都有唯一的TraceID，根据调用链TraceID 将属于同一条链的所有数据抽取出来，再基于节点ID 和父节点PID构建父子关系进行拼接，将其串联为一条完整的调用链。

（2）数据处理：预先计算并保留算法中需要用到的结果，以提升算法效率，例如，当前节点后续所有子节点实耗时间（ElapsedTime）的总和、子节点个数、子节点调用成功数等，如表1 所示。

表1 调用链数据

2.2 调用链搜索和定位算法

某一条调用链的调用逻辑如图2 所示。调用链中不同的节点属于不同的服务类型。头节点依次向下调用其他子服务，或者调用自己本身，呈现单向的调用方式。各个节点数据包含了各自的延时数据和是否调用成功的信息。

图2 微服务完整调用链样例

定位算法流程如图3 所示，可分为自顶向下调用链搜索和自底向上调用链定位两部分。

图3 调用链搜索和定位算法流程

2.2.1 自顶向下调用链搜索算法

本节的目的是以服务节点为对象，计算并统计算法认定该节点为异常节点和疑似异常节点的次数。采用递归算法，从调用链的头节点往后逐步判断，若判定为异常节点则继续向后搜索，否则停止后续搜索。

算法通过以下4 个方面判断该节点是否为异常节点：

（1）当前节点存在延时异常。通常认为节点的延时是正态分布的，因此采用3-sigma 准则，将当前延时大于平均值3 个标准差的节点定义为异常节点。

（2）当前节点调用状态失败。每个节点都有二值的调用状态，可依据该字段判断节点是否调用成功。

（3）当前节点后续子节点存在调用失败情况。若后续节点异常，则必然会影响到当前节点。因此，当子节点的个数大于子节点调用成功数时，则认定当前节点为调用异常节点。

（4）当父节点异常时，当前节点延时tc占用父节点延时tp的一半及以上（只适用于非头节点的判断），具体如式（1）所示。在正常运行时，同一层级的节点往往在耗时上较为均衡，因此当前节点占用率过大即是异常节点。

然而，除了上述异常情况，在正常节点中存在这样一种情况：当网络出现较大波动时，当前节点传输到父节点的耗时会增大，这部分耗时会累加为父节点耗时的一部分。这些节点本身也有可能是异常的，但是并未在上述4 类异常定义中体现。为此，本文将这些正常节点定义为疑似异常节点。节点延时包含了自身耗时和后续调用的子节点耗时总和∑tc。若当前节点判断为正常节点，但是该节点的父节点自身耗时tp-∑tc占用了自身延时tp的一半及以上（只适用于非头节点的判断），则记录为疑似异常节点，与正常节点相同，也停止往后搜索，具体为：

自顶向下调用链搜索算法的伪代码如下：

至此，异常检测算法可以统计出在时间段T内，多条调用链所调用的服务节点的正常次数、异常次数和疑似异常次数。异常和疑似异常本质上两者均为异常。基于上述搜索结果，各个节点异常率的计算式为：

式中：nnormal为正常节点个数；nsuspected为疑似异常节点个数；nabnormal为异常节点个数。与传统顺序搜索并判断根因的方案相比，该部分方案更加简洁，仅做统计而省略了逐个判断根因的过程。

2.2.2 自底向上调用链定位算法

由于调用链底层节点为根因的概率更大，因此，采用自底层向上层搜索根因节点的方式更易于定位根因。从底层开始筛选，若存在异常则直接在该层定位。根因定位所依赖的评价标准主要是上一步骤中得到的故障次数和异常率，而单独采用故障次数或异常率都会严重影响定位精度。因此，判定依据应采用故障次数和异常率相结合的方式。

然而，若调用次数较少（调用一次且故障率为100%）或异常率较低（调用大量次数且有偶发性故障），该层的节点并不一定为根因。图4 表明了一个5 层的调用链中各层的调用次数分布情况，从上至下调用数量分别为721，6724，23716，6643，632，该结果近似于正态分布。在调用链的高层和底层都存在调用次数少的问题。因此需要设置阈值，对调用链数据进行筛选。

图4 调用次数分布

判定顺序如下：

（1）人为设定故障次数和异常率的阈值，筛选去除故障次数低于阈值和异常率低于阈值的数据；

（2）对当前层进行搜索，若该层存在单个异常节点，或者疑似异常节点，则直接作为根因节点；

（3）若存在多个异常节点，返回故障次数较多的节点作为根因；

（4）若存在多个异常节点且故障次数相同，则返回异常率较高的节点。

自底向上调用链定位算法的伪代码如下：

由于搜索的根因绝大多数在底层，在Depth 循环中的前几次判定就会返回，绝大多数在第1 次判定就直接返回结果。该部分的定位算法并未遍历所有Depth，因此算法速度极快，时间复杂度为常数阶。

3 效果评估

本文对某省级运营商自2021 年6 月份至10月份的微服务数据进行分析，获取的数据量为 382 674 条。检测区间为异常时刻前后各5 min（共计时间长度为10 min）的时间段。采用本文算法进行预测，输出TopK的异常故障根因，并反馈给运维人员进行人工审核，判断根因是否为真实故障节点并统计准确率。

图5 表明了Top 3 准确率随故障次数阈值的变化，其中横坐标为故障次数阈值，从0 至100，间隔为10。图中曲线表明，随着阈值从0 增加至30，样本中具有随机性的小样本根因节点被剔除，准确率有所上升。但是随着阈值的继续增大，真实的根因节点也会逐步被剔除，因此准确率会迅速下降。图6 表明了Top 3 准确率随异常率阈值的变化。当异常率阈值在0.05～0.15 之间时，随着异常率阈值的提升，准确率不断提升。这表明根因节点在底层，且异常率的提升过滤掉了一些干扰根因。但随着异常率提升到0.2～0.4，准确率出现了明显的下降，这是由于随着异常率的提升，靠近底层的根因节点逐渐被错误过滤。

图5 Top 3 准确率随故障次数阈值的变化

图6 Top 3 准确率随异常率阈值的变化

对于选取的前K个结果，本文也进行了讨论。表2 为在设定不同异常次数阈值和异常率阈值的情况下，选取不同数量的根因的准确率。结果表明，一方面，在异常次数和异常率的阈值设置为10 和0.15 时，在本数据集下效果最佳；另一方面，随着选取的可能根因从Top 1 增加到Top 3，更大概率能命中相应的根因节点，根因的准确率有所提高。

表2 不同异常次数阈值和异常率阈值下的Top K 准确率

表3 为某省客户管理系统（Customer Relation-ship Management，CRM）运营效果数据。其中，服务异常次数为异常检测所检测出的异常时刻的次数，平均定位耗时为执行一次算法程序所需的耗时。在算法效率优化方面，本文将串行搜索修改为多进程并行的方式。此外，还使用了更高效率的存储结构来进行加速，极大提升了算法的运行效率。在提升准确率方面，结合实际运营效果进行阈值的调节，根据服务和阈值间的敏感性，来对应调整不同服务的阈值，以达到更好的定位效果。

表3 某省客户管理系统运营效果数据

业务基准需求是准确率需达到0.7 以上并尽可能压缩平均定位耗时。如表3 所示，2021 年6 月准确率未达到要求，平均定位耗时为3 min。经过5 个月的实际业务上线测试，并结合业务优化调节阈值至更合理的值，在2021 年10 月的数据集上，Top 3 准确率达到了0.87。程序修改为多进程，最终平均定位耗时压缩到了15 s，准确率相较于首月提升了29.85%，耗时也从分钟级提升至秒级。综上，本文所提算法在调用链根因定位场景下，可以较为准确地定位根因，且在经过优化后，已能较好地满足业务需求。

4 结语

本文提出了一种基于调用链双向搜索的故障根因定位算法。基于微服务系统中故障时刻前后一定时间内的调用链数据，本文算法采用双向搜索的思路实现了对异常根因节点的深度挖掘及精准定位。所提算法已在国内某省级运营商项目中上线，Top 3根因的准确率达到了0.87，平均定位耗时为15 s。为了更好地满足运维工作人员的需求，上线版本对调用链搜索的统计结果进行了可视化。此外，所提算法虽然设计应用于微服务场景，但是也具备拓展到其他具有调用链故障定位场景的潜力。本文为微服务系统下的故障根因定位问题提供了更加快速有效的解决方案，也为智能运维领域拓展了新的研究思路。