原创： 张闯赵国柱陈瑞 智能运维前沿
作者｜张闯、赵国柱、陈瑞
问题简述
在互联网服务运维中，当某个总指标（如总流量）发生异常时，需要快速准确地定位到是哪个交叉维度的细粒度指标（如“省份=北京 & 运营商=联通”的流量）的异常导致的，以便尽快做进一步的修复止损操作。
数据探索
这次比赛的数据的特点是数据比较稀疏，大部分都为0，且值的差异较大，有的KPI是个位数的值，有的是上万的。
异常发生时不同KPI变化的倍数差异也比较大。如下图：
可见第二个数据集1539325500000时刻有异常，i13&e11&p17下只有两个叶子节点（比较稀疏），i13&e11&p17&c5&l3约增长一万多倍，i13&e11&p17&c3&l3都为0，找出i38&e08&p24下有11叶子节点，可以看到i38&e08&p24&c1&l4和i38&e08&p24&c1&l2的增长很多，并且增长的倍数相近，有几百倍，但i38&e08&p24&c4&l4的增长倍数明显不同，只有几倍，而i38&e08&p24&c1&l3的增长倍数只看前面几个值难以确定。
第二个数据集中有14天数据，5分钟一个点，共4032个点，红点为给出的所有的需要定位根因的异常点。
第三个数据集中有14天数据，5分钟一个点，共4032个点，红点为给出的所有的需要定位根因的异常点。
下图为第三个数据集中3400到第3500个点的范围内的曲线，绿色实线为所有KPI的值的总和对应的曲线，黄色线为去掉异常点后进行插值得到的曲线，绿色线为二次指数平滑fit的曲线。
下图为第三个数据集第954到第1014个点的范围内的曲线，绿色实线为所有KPI的值的总和对应的曲线，蓝色线为去掉异常点后进行插值得到的曲线，绿色线为三次指数平滑fit的曲线。
下图为第三个数据集第3100到第3200个点的范围内的曲线，蓝色虚线为KPI (i06, e10, c5, p14, l3)对应的曲线，黄色线为去掉异常点后进行插值得到的曲线，绿色线为二次指数平滑fit的曲线，红点为给出的所有的需要定位根因的异常点，可以看到对于单个KPI曲线发生异常时变化幅度还是比较明显的。
预测方案
之前想过几种方案：
Prophet，每个大部分时间不为0的KPI训练一个模型，不仅能得到预测值，还能得到预测区间，顺带可以一定程度上做异常检测，但缺点是难以逐点检测。
如下图是KPI(i02, e08, c1, p03, l3)上缺省参数使用Prophet的效果，不仅能得到预测值，还能得到预测区间，顺带可以一定程度上做异常检测， (为了消除正常波动对根因定位的影响，曾经设想过对于真实值在区间内时将预测值设置等于真实值，这样可以消除正常波动的影响，凸显出异常)。
R forecast包中的ETS，也需要每个大部分时间不为0的KPI训练一个模型，不仅能得到预测值，还能得到预测区间，顺带可以一定程度上做异常检测，但是涉及到python调用R的接口，增加最终运行的docker环境的复杂性。
使用python实现指数平滑类（二次或三次指数平滑），每个KPI单独训练最佳参数，可以逐点预测，进行预测时速度会非常快，应该能满足性能需要。
但是在抽样查看数据集时发现，有些KPI在第二个第三个数据集里面形态不一致，并且在相同数据集中有个别的KPI的形态也会随时间发生变化，因为最后决赛时是不是会冷启动，能有多长时间的数据可供训练确定超参都不是很确定。并且因为开发时间不多，并且考虑到后期执行时可能会对执行时间的影响，以及需要检测预测效果，当预测偏差大时启动重新训练，增加代码复杂度。
观察周同比数据：
观察日同比数据：
为了防止图像比较乱没有画过多曲线进行比较，但是从抽样比较的效果来看，曲线不是很吻合。
上图中红色线为KPI总值的曲线，红点为需定位根因的时间点，绿色和紫色的线为两个异常KPI的曲线，蓝线为KPI总值减去两个异常KPI的值后余下KPI总和的曲线，黄色为前一天和后一天KPI总值曲线，黑色为KPI总值的移动中值曲线，选用中值是因为和均值比受异常值的影响小，历史同期期值不如移动中值更接近，最终只用了当前点和前几个点的中值作为预测值，编程简单，执行速度快，可以冷启动。
总体解决方案
预测直接用前几点和当前点的中值，简单快捷，不用太多历史数据，可以冷启动，部署后可以迅速开始工作，借鉴Hotspot中计算Potential Score的方法和Recursive Adtributor方法，实现多个决策器，最终加权投票得到最终结果，执行速度快，定位一个根因在10秒以内。
1 Adtributor方法
对于每个Attribute，分别计算此Attribute内的values的Surprise，而后排序，大于一定EP阈值的纳入根因集，Surprise做和，当总的EP大于总阈值时停止增加。
EP、Surprise的定义参见Adtributor: Revenue Debugging in Advertising Systems
原始的adtributor的处理流程如下：
2 迭代切片方法
综合各个论文的方法，我们用了迭代切片的方法，先从总的Cube对第一层使用类似adtributor的方法找到应该从哪个Attribute去切（找根因），找出相应的elements，并且将相应的element做为新的Cube，再次迭代用类似Adtributor的方法在新的Cube中找到应该从哪个Attribute中去切（找根因），依此类推。什么时候终止切片根据Isolation Power是不是能得到提升作为判断依据。
可以想象整个cube为一个大切糕，先用类似adtributor的方法找到应该从那个Attributes去切，比如应该从Attrbute C的维度找出Attrbute Values为c1的切片，则直接将C==c1的数据全取出形成一个新的切糕（cube），同时C这个Attribute后续不需要再考虑了，同时计算出c1的isolation power。
而后在这个新的切糕（cube）中，再用类似adtrbutor的方法找到应该从那个维度去切，比如Attribute B中找到了b1、b3 ，Attribute A 中找到了a3，计算总surprise，发现b1、b3的surprise更大，则本层应该从B切，切出c1&b1;c1&b3，计算c1&b1;c1&b3的isolation power来同上一层c1的isolation power比较判断是不是本次切是应该的。
如果c1&b1;c1&b3的isolation power大，则应该切，取出C==c1&B==b1的数据作为新的切片， C==c1&B==b3的数据也作为新的切片，继续判断余下的Attribute，以此类推，直到isolation不再下降为止。
如果c1&b1;c1&b3的isolation power小，则不应该切，直接返回c1为根因。
Isolation Power是出自论文iDice: Problem Identification for Emerging Issues：
次比赛的数据的特点是数据比较稀疏，大部分都为0，且值的差异较大，有的KPI是个位数的值，有的是上万的。
3 Surprise的问题
两个维度，箭头左侧为预测值，箭头右侧为真实值
A的Surprise为0.002084691793860817 EP为0.9
B的Surprise为0.0023829811435295764 EP为0.1
2的Surprise为0.0032082965862361007 EP为1
1的Surprise为0.003793113576346145 EP为0
按Adtributor原论文的方法进行计算应该会过滤掉EP为0的，计算总Surprise，选出A&B为根因，但是实际根因很明显是2：
解决方法1：遵从JS散度的原始定义，计算JS散度时考虑所有元素因此也包含1，而后根据JS散度最大的来决定应该选择那个Attribute，而在这个Attribute内选取根因时再过滤掉EP小的；
解决方法2：计算Surprise时乘EP，成为加权平均的Surprise。
实验证明有效，且两种解决方法可以互补。
4 迭代切片的各种实现
迭代切片的方法会有比较多的细节处理，细节处理的不同可以形成多种具体实现：
4.1 每一层总体判断应该从哪个Attribute去切，从而保证各层切的Attribute是一致的或各elements自己分别判断从哪个Attrbute去切（虽然中途可能路径不一致，但结果会一致）；
4.2 各个切片分别根据各自计算的isolation power来各自判断是不是继续切分下去，供后续投票或根据isolation power减少、相等和增加的数量综合判断决定是不是切到下一层（主要因为有很多为零的以及其他情况导致Isolation Power相等，因此是不是继续切要参考其他切片）；
4.3 先聚合再取移动中值或先移动中值再聚合；
4.4 先用所有的元素的Surprise计算总的JS散度后选总Surprise最大的属性，再在这个维度中找根因或先计算Surprise时乘EP，求得加权平均Surprise；
将上述不同方法进行组合，实现多个切片程序，将结果进行投票。
5 迭代切片的速度
切片的方法在普通服务器上执行定位一个根因约为1.1秒，在主办方的服务器上执行定位一个根因约为0.6秒。
6 HotSpot方法
每个cuboid找出根因集，比较各个cuboid的根因集得分，得到最终根因，详见论文 HotSpot: Anomaly Localization for Additive KPIs with Multi-Dimensional Attributes.
但在实际使用中发现如果预测不准时会有些小问题，如：
根因的element的真实值除预测值倍数，如果和此element各叶子节点的真实值除预测值倍数相符，则Potential Score会比较大，但是如果预测不准的话，会导致预测倍数不符，即使是真正的根因Potential Score会受影响而相对小些。
另外，有时会出现层次越深，同时根因集的elements增多时， Potential Score会越高，道理类似与回归树的树越深，会拟合的越好类似。本方案解决方法：层次越深且根因的elements明显增多则惩罚越重。
同层加入元素数量问题：加入元素越多， Potential Score趋向于越大，见下图Ad Unit3为可以理解为正常波动而不是根因，不应该被加入，但是加入后确实可以使Potential Score增大，论文中使用EP过滤掉正常波动，
本方案解决方法：除了用EP过滤正常波动也同时根据Potential Score增大的幅度开始明显变小停止增加（肘部法则）。
叶子节点问题：下图中{Partner 1, Partner 2} Potential Score是0.99但是所有叶子节点的Potential Score是1，论文中用另外的计算叶子节点Potential Score的方法。
本方案解决方法：每增加一个叶子节点同时综合看R值等值的变化和个数限制的方法来解决。
同时还参考另外两篇论文中的全局指标一起进行最终决策。
Adtributor: Revenue Debugging in Advertising Systems 中的EP：
iDice: Problem Identification for Emerging Issues 中的R值：
7 HotSpot方法速度
Potential Score方法在普通服务器上执行定位一个根因约为9秒，在主办方的服务器上执行定位一个根因约为6秒。
8 集成
最终用了集成的思想，多个基决策器集成，基决策器差异越大，集成效果越好，最终集成了Potential Score和迭代切片的方法，采用加权投票机制得到最终的答案，最终效果稳定。
Potential Score类程序，返回topn（目前是两个）的根因集，迭代切片类程序，返回一个根因集，每个程序单独执行，结果都会有一个平均分数，根据每个程序的得分作为权重，每个程序返回的根因集加权后得到各个根因的得分，最终选择排名最高的和同cuboid内的其他项(因为考虑到有的基决策器会漏项)。
参考文献
• Yongqian Sun, Youjian Zhao, Ya su, et al., “HotSpot:Anomaly Localization for Additive KPIs withMulti-Dimensional Attributes”, IEEE Access, 2018.
• R. Bhagwan, R. Kumar, and R. o. Ramjee, “Adtributor: Revenue debugging in advertising systems,” NSDI, 2014, pp. 43–55.
• Q. Lin, J. Lou, H. Zhang, and D. Zhang, “idice: problem identification for emerging issues,” ICSE, 2016, ACM,, pp. 214–224.
• Linnea Rudenius Moa Persson “Anomaly Detection and Fault Localization An Automated Process for Advertising Systems”
• http://iops.ai/competition_detail/? competition_id=8&flag=1
本文来自：https://mp.weixin.qq.com/s/51ebU8NOHOraklryIsm0Vg
网友评论