告别重复告警打扰--基于堆栈相似度的全新QAPM告警方案

导语 为了能够及时的发现问题并及时解决，QAPM提供了一套卡顿告警机制。正如同常规的阈值触发的告警机制一样，QAPM早期的告警也会使测试开发人员陷入告警风暴的影响，影响工作效率。在这种背景下，对告警进行聚类和去重的需求逐渐显现出来。Rebucket作为一个成熟的堆栈相似度计算的算法，曾被微软用于解决bug上报的聚类问题。相比于普通的前缀匹配的检测算法，ReBucket能够提供12%的准确率提升。我们期望利用Rebucket算法，找到那些重复出现的告警，从而提升用户体验，突出告警重点。本文将重点介绍rebucket算法原理以及如何利用该算法对我们的告警系统进行优化与改进，最后将讨论堆栈相似度算法在QAPM中潜在的其他应用场景。

背景

为了能够帮助用户更快更准的发现卡顿，QAPM早早的支持了卡顿告警功能。当VIP用户使用APP发生卡顿时，QAPM便会实时发出告警，提醒测试，开发人员及时修复卡顿问题。但是随着用户量的不断增多，每日触发告警的次数不断上涨，使得监测告警的人员陷入告警风暴之中。而且随着告警系统的持续运行，很多卡顿已经被开发解决，但是由于用户没有更新版本，导致告警重复出现。

为了能够缓解告警对测试开发人员的打扰，提升工作效率，QAPM想到了了堆栈相似度检测算法来判断告警是否重复。本文将重点介绍传统的告警缺陷，以及QAPM如何通过堆栈相似度算法来对告警进行重复检测的处理，从而实现一套既不漏报又能反映重复告警的告警功能。

QAPM的告警功能

QAPM上线的的告警功能是基于Grafana的告警功能的，具体流程是：

1. 手机端检测到卡顿之后，上报到APM后台，APM将数据处理之后存入Elasticsearch中
2. Grafana每隔一小段时间检测Elastic中的数据，判断是否有VIP用户发生了卡顿，如果发生了，就向有关人员发出告警。

图1 告警流程

告警的触发时间，告警的规则均可以在Grafana中十分方便的进行配置。由于Grafana对ES的良好支持，使得QAPM的告警接近零成本。只需要在QAPM上添加VIP用户，然后在Grafana中配置接收告警的产品负责人即可。

图2 告警配置

上图是QAPM配置的某产品的告警，在上图的配置中，配置了每隔50秒去检查是否有用户发生了卡顿。告警功能中的VIP可以是各个产品的负责人，高度的活跃用户，测试人员或者是自动化测试的机器等。当产品接入了QAPM的告警之后，可以在测试阶段通过告警发现隐藏的卡顿问题，也能够及时发现线上产品存在的卡顿问题而不需要从用户的反馈中发现卡顿问题。

图3 企业微信收到的告警信息

图4 详细告警信息（可以点击信息查看堆栈）

由于QAPM的告警十分的灵敏，当VIP用户频繁触发某一处告警时，相关的测试人员便会一直收到告警。每次收到告警之后都需要人工去查看堆栈，判断该堆栈是否已经出现过，从而影响了工作效率。我们发现，判断告警是否重复的这个过程，及时就是判断卡顿堆栈相似度的过程，因此想到了利用卡顿堆栈相似度来发现重复的告警，从而给用户更好的体验。

Rebucket堆栈相似度计算算法

衡量堆栈之间的相似度这个需求很早就出现在各种缺陷平台上了，目的是为了对缺陷报告进行聚合。类似于bugzilla等平台，当用户量很大时，同样的一个bug，会产生大量的bug堆栈。为了提升程序员解决bug的效率，避免重复bug的打扰，微软提出Rebucket算法来衡量堆栈的相似度，从而来对堆栈进行聚合。

图5 bug上报平台

堆栈相似度的定义与计算

QAPM的每次卡顿上报都会上传造成卡顿的堆栈信息以及卡顿的时长等信息。对于Android平台来讲，会上传一个堆栈。对于iOS来讲，会分时间片上传一系列的堆栈。

QAPM的堆栈顺序与函数调用顺序相反，也就是，栈顶是底层的系统函数，而栈底是我们的应用的main函数。我们有这样一个先验知识，那就是越靠近栈顶，越能反应这次bug的原因。因此，传统堆栈匹配可以使用一种前缀匹配算法（通过匹配栈顶的函数来判断堆栈之间是否相似），但是这种算法灵活性不足，准确性不高。

一个典型的安卓卡顿堆栈如下图所示。

图6 典型的安卓卡顿堆栈

因为每次卡顿都会上传这种堆栈，那么根据堆栈相似度计算重复变得可行。接下来来介绍一下ReBucket算法。

Rebucket算法的基本假设在于，越靠近栈顶的栈帧越能反应该堆栈的特征，因此在计算相似度中的权重应该越大。我们要判断堆栈的相似度，其实就是判断序列的相似度，而在这个序列中，头部元素的权重更大。在此我们做一个简单的理解。

首先我们以对应函数在不同堆栈之间的距离作为判断堆栈之间的距离。在下图中，f0和f0'的位置都是栈顶，那么他们的距离是0，同理，f1和f2'的距离是1，f4和f6'的距离是2。这个判断依据在公式中表现为：

另一方面，上文说到，越靠近栈顶的栈权重越大，这一部分反映在：

因此在计算相似度的过程中，基于上述两个因素，提出了如下的算法，其中c，o均为参数，可训练）：

首先假设有堆栈C1, C2,如下图所示：

图7 堆栈C1,C2

上图中绿色的部分表示该帧所对应的函数相同。现定义集合

其中，

在上述的公式中，c和o都是参数，c反应的是对应的函数到栈顶的距离的重要程度，而o反应的是两个堆栈的对应函数之间的位置差的重要程度。这些参数可以通过训练得到。

相似度算法的实现与实验

• 算法的实现与加速

如果按照上述公式直接实现代码，将会十分的耗时。论文中最长公共子串的算法给出了本算法的动态规划版本。从而加快了算法的效率。由于rebucket算法计算比较复杂，因此本文在实现rebucket的时候采用了C 编写，并且使用了openmp做简单的加速。为了验证性能，取数据集中5000个堆栈，不断注入聚类算法，当分类个数为4000时，各个版本的rebucket耗时如下：

• Python版：0.9368s
• C 未加速版：0.1359s
• C 加速版：0.0581s

算法准确性评估

在实现了论文的算法之后，我们采用了eclipse的数据集对算法进行了训练。并将其与简单的前缀匹配算法做了比较。

为了保证实验的有效，于是选择了开源数据集bugrepo1。本数据集目前已有多篇论文引用使用，因此具有一定的可靠性。Bugrepo中提供了四个项目(eclipse，JDT，Firefox以及Mozilla core)的bug报告以及该报告是否重复，其中部分报告含有与bug相关的堆栈。因此数据处理部分需要将相关的堆栈信息以及重复信息提取出来。并保存为相关的文件。从报告中提取堆栈的方法来自论文“Extracting Structural Information from Bug Reports”。

提取之后，相关数据如下：

为了客观评价算法，采用Purity，Inverse Purity，F-measure三个常见的聚类算法评价指标。最终的实验结果如下：

相对于前缀匹配的算法，Rebucket算法分类更加精准而且能够有效的减少漏报个数。以eclipse数据集为例，rebucket分类算法的准确率*为85.87%，漏报堆栈个数为60，而前缀匹配的算法准确率*为73.24%，漏报堆栈个数为301。

参数的训练

在Rebucket计算堆栈之间的相似度的过程中，涉及到两个参数c,o。这两个参数反应了rebucket算法计算结果对于堆栈位置的敏感度。这一点可以从上文中的计算公式中看出来。为了找到最合适的c和o，本文采用了论文中学习算法进行训练。训练参数如下。

使用训练集eclipse，取前200堆栈，每次迭代更改参数S = 0.01（类似与梯度下降中的learning rate）。最终得到相关参数如下：

• dist = 0.03
• o = 0.13
• c = 0.04

现行QAPM告警功能

新的算法于2019年1月5日开始部署试运行。目前已经发现了重复堆栈48例。而且随着时间的变化，随着积累的堆栈变多，发现的重复的能力会不断增强。

改进后的告警可以向用户给出一定的提示。让用户判断该告警是否重要。如果一个堆栈被监测到重复，而且已经提单的话，后续收到告警便能够不再关注。另外一方面，如果一个被忽视的堆栈多次重复出现，那么我们也可以根据其出现的次数和规律进行进一步的分析。

图8 新的告警提示

在新的告警详情页面，我们不仅统计了该卡顿堆栈重复出现的次数，还统计了用户重复出现某个堆栈的次数。以便于更好的跟踪和查找卡顿原因。

图9 新的告警详情

目前成效

• JOOX APM实践

目前的不足以及未来的改进

虽然目前告警功能已经初步具备了重复检测的功能，但是还是存在着很多的不足。比如：

1. 目前的告警只是给出了用户重复提示，没有更近一步的展示出堆栈的特征，用户还是需要点击链接跳转来查看堆栈信息
2. 目前只判断了是否重复告警，没有与提单状态结合。
3. 目前告警暂时有QAPM管理人员配置。（目前团队中正在开发业务方自主配置告警的相关功能）

堆栈去重可以不仅仅用于告警，堆栈去重在聚合bug单，减少重复提单等方面仍有较大潜力，在后续的QAPM的开发中，会不断的去完善堆栈去重的功能，尝试更多更智能，先进的算法，也会不断的拓宽算法的使用防伪，希望能够不断地提升QAPM的用户体验，提高大家的工作效率。

结语

感谢负责微视专项工作的同学对于旧版告警的反馈与建议，督促我们不断的去优化告警体验。虽然目前还存在很多不足和瑕疵，但是我们会持续不断优化，期望给大家带来更好的使用体验。

欢迎大家的反馈与建议！！！

了解更多QAPM相关内容，请咨询在线客服：QAPM

References (参考文献)

1. (https://github.com/logpai/bugrepo)
2. ReBucket: A Method for Clustering Duplicate Crash Reports Based on Call Stack Similarity

*注意：本处使用的准确率其实是 F 度量，这一部分将在后文中解释。这个值目前是比较权威的评价堆栈聚类的指标。