本文主要介绍智能运维中「多维指标根因定位」问题及其解决方案，以下内容主要源于我们组内一位同学对该问题的概述传送门~，已得转载权限。笔者为清华大学博三在读研究生，主要研究领域为智能运维中的根因定位问题。
多维度指标的异常定位是AIOps领域的一个典型且有挑战的问题。在互联网服务运维中，当某个总指标（如总流量）发生异常时，需要快速准确地定位到是哪个交叉维度的细粒度指标（如“省份=北京&运营商=联通”的流量）的异常导致的，以便尽快做进一步的修复止损操作。由于运维中的指标维度多、每个维度取值范围大，导致异常定位时的搜索空间非常大，因此需要一个高效的算法解决该问题。
举说明：一个KPI指标根据多种属性分别监控，例如PageViews（PV），分别统计来自不同ISP和不同省份的PV。如Fig.1所示：
上表中的和分别表示PV的期望的正常值和观测值，我们看到红色的部分观测值和正常值不符，这些PV就是发生了异常。
多维根因定位算法解决的是定位发生异常时哪些维度的属性取值导致了异常，比如Fig.1中的根因维度是「(Province=Beijing&Shanghai,ISP=*)」
更详细的问题描述可以参考第二届智能运维挑战赛传送门~，赛题为「多维监测指标的异常定位」。
对于这个问题的解决方案可以参考获奖选手的答辩材料传送门~
主流的算法可以分为两类：
也有一些其他的方法，比如用神经网络去做多分类，但是方法我感觉不是很实用，也没有发在很好的会议上，就略去了。
主要有INFOCOM'16[^1]，SIGMETRICS'20[^2]和FSE'17[^3]
其中前两者都是首先对所有属性组合进行异常检测，然后用Apriori算法去搜索support超过阈值的属性组合，再根据confidence去筛选。
FSE'17可能原本目标的问题和这里的问题不太一致，但是比较类似。它使用的Contrastsetmining可以看为一种特殊的关联规则挖掘。contrastsetmining是挖掘在不同的类中分布（support）差别很大的属性组合，而前两者挖掘的是和某个特定的类（即异常）关联的属性组合。
就我个人的经验，关联规则挖掘在参数（support和confidence的阈值，异常检测的阈值）合适的情况下，可以取得非常好的效果。但是显然这些参数随着数据集和故障案例的不同会有不同的最佳取值，因此实际上这一类方法的效果可能不太稳定。
「1.Adtributor」[^4][NSDI'14]
假设根因只可能是一个属性出了问题，例如只有可能是某一个省份或者某一运营商的问题，而不会是某个省份的某个运营商的问题。即(Province=Beijing,ISP=*)和(Province=*,ISP=ChinaMobile)都是合法的根因，而(Province=Beijing,ISP=ChinaMobile)是不会出现的。这个假设大大简化了问题，但是明显是不能覆盖实际的需求的。
Adtributor提出了两个指标用来评估属性组合。一个是解释力，指的是该属性组合对应的指标变化和整体的指标变化的比例。另一个是surprise，一个属性下面的各个指标的取值的分布是否有变化，根因属性的话应该有明显变化。
因为是只考虑一个属性，所以搜索空间并不大，基本上就是搜索解释力和surprise最大的属性。
「2.iDice」[^5][ICSE'16]
首先iDice处理的问题是我们讨论问题的一个子集，它只专注处理issuereport数量增加的根因。即考虑的指标只有issuereport的数量。
iDice的目标函数如下
其中指的是属性组合对应的issuereport占所有issue的比例。和分别指的是异常时刻后（after）和前（before）。整个公式就是两个比例的fisherdistance。
为了加速搜索，iDice提出了三个剪枝策略。
「3RecursiveAdtributor」[^6]
这是一篇学位论文中提到的。RecursiveAdtributor主要是为了解决Adtributor的不合理的假设的问题。基本的思路是递归调用Adtributor。Adtributor会返回一个根因属性和对应的取值，RecursiveAdtributor就会在选出来的切片3.上递归调用Adtributor，得到下一个根因属性和对应的取值。
「4.HotSpot」[^7][IEEEAccess'18]
我们实验室之前的工作。
基于这个假设，Hotspot设计了一个目标函数叫potentialscore。这个分数评估两方面的内容：对于待评估属性组合的更细粒度属性组合，它们的指标应该是异常的并且服从rippleeffect；另一方遍，对于其他的属性组合，它们的指标应该是正常的。
HotSpot和其他工作例如iDice很不一样的一点就是，它显式地考虑了有多个根因同时作用的情况。因此搜索空间直接变成了属性组合数目的幂，搜索空间的极大地增加了。
为了解决这个问题，HotSpot采用了MCTS算法（蒙特卡洛树搜索，AlphaGo用过的）来进行启发式搜索。
「5.Squeeze」[^8][ISSRE'19]
我本人的工作。
Squeeze的目标函数也基本还是potentialscore，只是做了一些改进，使得对于根因的属性数量比较大，根因的指标变化相比整体不够显著的时候，算法效果稳健了很多。
最大的变化是搜索过程。Squeeze没有采用暴力搜索加MCTS优化。而是采用了一套启发式策略来大大加速搜索，同时避免性能损失。
首先，根据rippleeffect，我们发现同一个根因所影响的细粒度属性组合的指标变化比例是相同的。因此我们利用这种先对细粒度属性组合进行聚类。
之后，我们在每一类中再去搜索根因。因为此时已经不用考虑多根因同时作用的影响，所以问题简化了很多。
此时，我们又采用了一个启发式策论。基本的思路是，根因属性组合对应的细粒度属性组合的指标应该都是异常的。
「6.MID」[^9][FSE'20]
和iDice针对的是同样的问题，采用了iDice相同的目标函数。不同之处在于搜索策略不同。
MID采用了Meta-heuristicSearching的策略，它定义了四个操作，每个可以把一个属性组合更新为一个新的。然后定义了一个meta-heuristic函数，用来评测一个属性取值是不是更有可能在根因中。具体的做法是评估其熵。
最后在搜索过程中，在每一步中MID评测当前属性组合的目标函数值，然后随机选择一个操作，根据meta-heuristic函数选择操作要增删改的属性和取值，最后得到一个新的属性组合，进去下一轮循环。
这个方法看起来很简单，但是有个巨大的问题就是每次随机选择的操作有可能重复出现已经搜索过的节点。但是如果简单禁止重复，那么就无法在搜索路径上进行回溯。因此这里需要一个合适的策略，我不太清楚怎么做能达到最好的效果。可惜原论文没有提及方法的细节。
「7.ImpAPTr」[^10][ISSRE'20]
ImpAPTr只处理成功率下降的异常。
ImpAPTr提出了两个目标函数，和Adtributor用过的解释力和surprise基本思路一致。但是ImpAPTr并没有假设单属性组合。它还是会搜索多个属性的组合，然后用这两个目标函数分别排序。再用排序得到的排名的均值作为最后的排序依据。
这个方法在根因的属性数量不多以及单根因的时候效果很好。
「8.AutoRoot」[^11]
改进了Squeeze。
首先是提出一种对聚类方法的修改，主要是在聚类之前会用KDE对density做一遍平滑。应该是比较有作用的。
其次是把generalizedpotentialscore中的绝对误差改成了相对误差。这在指标的时序预测误差较大的时候会受很大影响。
最后使用了在类内搜索的时候采用了一种新的启发式策略，比Squeeze多考虑了一些。
[^1]:F.Ahmed,J.Erman,Z.Ge,A.X.Liu,J.Wang,andH.Yan,“Detectingandlocalizingend-to-endperformancedegradationforcellulardataservicesbasedontcplossratioandroundtriptime,”IEEE/ACMTransactionsonNetworking(TON),vol.25,no.6,pp.3709–3722,2017.
[^4]:R.Bhagwan,R.Kumar,R.Ramjee,G.Varghese,S.Mohapatra,H.Manoharan,andP.Shah,“Adtributor:Revenuedebugginginadvertisingsystems,”in11thUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI14),2014,pp.43–55.
[^5]:Q.Lin,J.-G.Lou,H.Zhang,andD.Zhang,“idice:problemidenticationforemergingissues,”in2016IEEE/ACM38thInternationalConferenceonSoftwareEngineering(ICSE).
[^6]:M.PerssonandL.Rudenius,“Anomalydetectionandfaultlocalizationanautomatedprocessforadvertisingsystems,”Master’sthesis,2018,g¨oteborg:ChalmersUniversityofTechnology.
[^7]:HotSpot:AnomalyLocalizationforAdditiveKPIswithMulti-DimensionalAttributesYongqianSun,YoujianZhao,YaSu,DapengLiu,XiaohuiNie,YuanMeng,ShiwenCheng,DanPei,ShenglinZhang,XianpingQu,XuanyouGuo.IEEEAccess2018.
[^8]:GenericandRobustLocalizationofMulti-DimensionalRootCausesZeyanLi,ChengyangLuo,YiweiZhao,YongqianSun,KaixinSui,XipingWang,DapengLiu,XingJin,QiWangandDanPei.ISSRE2019
[^10]:G.Rong,H.Wang,Y.You,H.Zhang,J.Sun,D.Shao,andY.Xu.2020.LocatingtheCluesofDecliningSuccessRateofServiceCalls.In2020IEEE31stInternationalSymposiumonSoftwareReliabilityEngineering(ISSRE),335–345.
[^11]:PengkunJing,YanniHan,JiyanSun,TaoLin,andYanjieHu.2021.AutoRoot:ANovelFaultLocalizationSchemaofMulti-dimensionalRootCauses.In2021IEEEWirelessCommunicationsandNetworkingConference(WCNC),1–7.