前言
毕设在做异常点检测与根因分析,就拿微软14年的文章作为主要参考文献了,这里把中文的翻译以及一些整理一起放在博客里,以作分享交流。
Adtributor: 广告系统中的收入调试
作者:Ranjita Bhagwan, Rahul Kumar, Ramachandran Ramjee, George Varghese, Surjyakanta Mohapatra, Hemanth Manoharan, and Piyush Shah Microsoft
原文地址:https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-bhagwan.pdf
名词对应
revenue debugging:收入调试
measure:指标
surprise:惊奇性
摘要
广告收入在支持免费网站方面起着至关重要的作用。当收入急剧下降或增加时,广告系统运营商必须找到并解决根本原因,例如通过优化基础设施的性能。这种收入调试类似于系统的文献中的诊断和根因分析,但更为普遍。基础设施元素的故障只是一个潜在的原因;其他一系列的因素(如广告商、设备类型)都可能是潜在的原因来源。此外,问题还因衍生的指标而变得复杂,如每次点击的成本,这些成本也与收入一起被追踪。
我们的论文首次系统地研究了收入调试问题。利用解释力、简洁性和惊奇性的概念,我们为广告系统的基本和衍生指标提出了一个新的多维根源算法,以确定最可能受到指责的部分。此外,我们在一个名为Adtributor的工具中实现了归因算法和可视化界面,以帮助故障排除者快速识别潜在的原因。基于对一个非常大的广告系统的几个案例研究和广泛的评估,我们证明了Adtributor的准确率超过95%,并可以帮助将系统故障排除时间减少一个数量级。
1 介绍
今天,许多免费网站都是通过广告(adds)产生的收入来支持的。网站广告有两种类型,搜索和展示。在搜索广告的情况下,终端用户进入一个发布者网站,如bing.com,并输入一个查询短语。对查询的回应是一个搜索结果页面,其中可能包含一个或多个广告。如果用户点击其中一个广告,出版商就能获得收入。在显示广告的情况下,最终用户可能会访问一个出版商的网站,如cnn.com,她可能会在页面的顶部或两侧看到广告,这些广告的展示为出版商赚取了收入。
广告系统促进了每天数以百万计的此类搜索和展示广告的产生和核算。除了上面提到的用户和出版商之外,还有两个与广告系统互动的关键成员,分别为广告商和欺诈经营者。显示给用户的广告是各个广告商之间的广告拍卖的结果,这些广告商通过投标来竞争将其广告显示给用户。在这中间,还有各种欺诈经营者[8],他们试图侵占广告收入的一部分。
广告系统管理着用户、出版商、广告商和欺诈经营者之间的互动。广告系统实施各种与广告有关的算法,在广告商之间进行实时的广告拍卖,将获胜的广告返回给出版商,监控用户的点击,检测和清除潜在的欺诈活动,计算每个显示或点击的广告的收入,向广告商收取适当的投标金额,并向出版商付款。广告系统的核心是一个大规模的分布式系统,由分布在几个数据中心的数千台服务器组成,执行广告算法并管理广告的服务和核算。
本文的重点是对广告系统的调试。通常情况下,广告系统监控器会在某一关注指标被确认为异常时发出警报(例如,收入或搜索次数急剧下降)。我们的目标是自动识别这种异常现象的潜在根源。我们称我们的方法为收入调试,尽管它适用于广告系统运营商的几个衡量标准,以承认收入指标的重要性。在本文中,我们描述了一种新的收入调试算法,该算法可以分析广告系统记录的大量数据,并将异常的潜在根源范围缩小到广告系统的一个子组件,以便由故障排除人员进一步调查。
根源识别和诊断是系统中一个古老的问题。过去已经提出了各种根因分析工具[1, 2, 3, 10, 14, 15]。但所有这些解决方案都集中在性能/故障调试上。在这里,我们解决一个类似但更普遍的问题:广告系统的诊断。虽然基础设施系统组件的性能/故障可能是异常指标的一个根本原因,但可能还有其他各种根本原因,例如与广告系统互动的其他组件。考虑到以下的例子:
- 教皇选举。我们注意到,教皇选举导致收入下降,因为许多搜索都是针对非货币化的查询词,如教皇或教皇选举,而广告商通常不会为其出价。显示的广告总数下降会导致收入的异常下降。虽然确定教皇选举的根本原因是不可操作的,但根本原因的识别仍然很重要,因为它消除了一个可操作的根本原因,如下面的例子。
- 浏览器广告失败。我们发现收入下降可能是由更新配置文件时的人工错误造成的,该文件的副作用是在某些浏览器版本上不显示广告。在这种情况下,快速识别可以帮助更正配置错误,从而恢复广告收入。表1中描述了更多的例子,并在第2.1节中讨论。
广告系统调试的第一个挑战是庞大的数据规模。每天有数以亿计的搜索和点击;在一个搜索或一个点击的层面上进行诊断是不可扩展的(想象一下,运行Mag- pie[3]或通过每一次点击会需要数百个系统组件跟踪一串系统调用)。因此,由于可扩展性的原因,广告系统调试是通过各种指标的集合来进行的。这些指标通常是在某些时间间隔内聚集的计数器(例如,在过去1小时内产生的收入)。根源识别只能由这些聚合计数器的异常行为触发。
与典型的系统故障排除相比,广告系统的第二个显著特点是出现了多个维度,需要首先对解释异常的维度进行等效。诸如收入等指标可以沿着不同的维度进行分解或预测,如广告商、浏览器或数据中心。例如,在例2中,如果收入是按照浏览器的维度来预测的,我们可以观察到一些浏览器版本没有产生其 "典型 "的收入份额。然而,如果同样的收入是按照广告商的维度来划分的,也许收入的分布就不会有明显的变化。
典型的系统根源算法,如SCORE[11],使用简洁性(奥卡姆剃刀)和解释力(根因能否解释变化?)作为他们的主要优化参数,不必考虑多个维度。为了对异常维度进行等效处理,我们引入了惊奇性的概念,通过量化每个维度上测量值的分布变化来体现。例如,在例2中,沿浏览器维度的收入分布的变化比沿广告商维度的收入分布的变化更令人惊讶。因此,我们在本文中的第一个贡献是第3节中描述的根因分析算法,该算法除了使用简洁性和解释力之外,还使用了惊奇性来识别广告系统中异常产生的根本原因。
广告系统的第三个独特特征是衍生指标的普遍性。考虑两个基本的衡量标准:每小时收入和每小时点击数。从这两个衡量标准中,我们可以定义一个衍生的衡量标准,即每点击成本,它只是收入除以点击次数。广告系统运营商监控和跟踪许多这样的衍生指标,它们是各种基本指标的函数(见图1)。例如,点击次数的变化和收入的变化本身可能很小,并不异常(例如,小于10%)。然而,相关的变化(例如,收入下降,同时点击量增加,各占10%)是异常的,并被派生的每次点击成本指标所捕获(20%的变化)。正如我们在第4节中所讨论的,将根本原因归因于衍生指标是具有挑战性的。为了解决这个问题,我们提出了一个新颖的部分衍生指标的归因解决方案,这是我们在本文中的第二个贡献。
我们的根本原因识别算法的结果是一组有可能解释异常现象的候选者。然而,这只是诊断过程中的第一步,如果合适的话,故障排除人员可以采取行动来解决这个问题。为了帮助故障排除人员快速识别潜在的根本原因,我们在一个叫做Adtributor的工具中实施了我们的根本原因识别算法和图形化的可视化工具,这是我们在本文中的第三个贡献。通过在生产系统中试点部署的经验,我们改进了Adtributor的可视化界面和数据表示技术,以进一步减少故障排除者的周转时间。
最后,我们对我们的根本原因算法进行了广泛的评估。首先,我们以表格形式列出并讨论了一组具有代表性的案例研究,这些案例研究强调了我们的根因分析工具的价值。其次,我们对2周内真实广告系统数据的128个异常警报进行了评估,发现我们的算法达到了95%以上的准确率。事实上,Adtributor甚至发现了一些被人工搜索遗漏的异常现象的根本原因。此外,该工具还将故障排除过程的速度提高了一个数量级。
2 问题陈述
在提供了系统概述之后,这一节中我们展示了真实问题的例子和它们的根本原因。接下来,我们将更准确地说明问题,并阐述我们的解决方案。
2.1 系统概述
图1显示了一个广告系统,并展示了诸如用户、欺诈操作者、出版商和广告商等直接与广告系统互动的实体。广告系统本身有不同的子组件,我们展示了其中的一些。
虽然日志基础设施确实跟踪了每个搜索请求或广告点击,但由于规模庞大,很难在单个请求层面上跟踪问题。取而代之的是,该系统监测一套综合指标,如图1所示。从原始日志中,它首先计算出每个时间间隔内收到的总搜索量、显示的总广告量、收到的总广告点击量以及这些点击量的总收入。这些指标都是相加的,并且可以沿着不同的维度进行切分。例如,总收入是使用该系统的每个广告商的收入之和。总收入也是来自广告系统活跃的不同地理区域的收入之和。我们称这种加法指标为基本指标。
此外,该系统还监测一组非加法派生指标,这些指标是基本指标的函数,如每搜索广告(广告/搜索)、每广告点击(点击/广告)、每点击成本(收入/点击)和每搜索收入(收入/搜索)。
这些指标中的任何一项出现异常的上升或下降,都表明这个指标出现了问题。因此,诊断系统需要首先检测出异常情况,然后进行根本原因分析。在本文中,我们专注于后期的根本原因分析,同时依靠著名的基于ARMA模型的方法[4]进行异常检测。异常检测器根据8周的历史数据生成一个基于模型的测量值预测,考虑到正常的时间和星期的波动。然后,它将实际值与预测值进行比较–当一个测量值的实际值与预测值有明显差异时,它将产生一个异常警报。我们产生警报的阈值差异是以与预期值的百分比偏差来衡量的。在目前的系统中,故障排除者根据经验手动设置这个值。对于每个警报,我们的目标是将异常的衡量标准归结为一个维度及其相应的元素。我们接下来定义这些术语。
维度:一个维度是一个轴线,可以沿着这个轴线投射一个测量值。维度是一个轴线,可以沿着这个轴线来预测一个指标。例如,我们可以沿着广告商的轴线来预测收入,并确定每个广告商的收入是多少。这种情况下的轴心是 “广告商”。衍生的指标也可以在不同维度上进行类似的预测。其他一些维度是 “发布者”、"数据中心 "和 “用户位置”。一般来说,一个广告系统要处理几十个这样的维度。请注意,一美元的收入可以在一个维度上加给广告主1,而在第二个维度上加给发布者3。
元素:每个维度都有一个称为元素的值域。例如,"广告商 "域可以有以下元素。{Geico, Microsoft, Toyota, Frito-Lay, …}。发布者维度可以有一些元素。{Bing, Amazon, NetFlix, …}。
表1提供了一些我们遇到的问题例子,有可操作的,也有不可操作的,需要检测并根治到相应的维度和元素。第1栏显示,问题可能发生在不同的层面。第3栏显示了异常的指标。第4栏显示了根本原因分析的输出,这是本文的重点。
请注意,第4栏只是走向根本原因的第一步,但它是至关重要的,因为它给故障排除者提供了问题实际所在的最佳指示。其他后处理技术(相关引擎、NLP技术、人工调查)使用多维分析的输出,对问题进行更深入的研究,以得出最终的根本原因,如第5栏所示,但是根本原因的这一方面不在本文的范围之内。例如,在第9行,虽然多维分析确实将问题缩小到几个查询字符串,但管理员必须从语义上解释这些字符串,以确定教皇选举是原因所在。
2.2 问题的定义和范围
收入调试的多维分析问题是要找到最能解释一个指标中的异常上升或下降的维度及其元素。在这种情况下,我们需要定义什么是对异常现象的 “最佳解释”。
考虑下面的例子。一个广告系统的收入被预测为在某一特定时间为100美元。在现实中,实际收入只有50美元。一个警报被触发了,这使故障排除者注意到了这个问题。
为了在这种问题发生时找到根本原因,广告系统持续地跟踪在一系列维度上产生的收入。在这种情况下,考虑到三个这样的维度。数据中心(DC),广告商(AD),和设备类型(DT)。表2、3、4显示了沿着这些维度的收入值的预测,以及归属于各个元素的值。
我们现在解释一下这些属性的语义。当广告系统收到一个搜索查询时,它将查询路由到一个数据中心,该中心反过来提供一些广告作为回应。归属于一个数据中心的收入是这个数据中心提供的广告点击所带来的总收入。每个广告都有一个相关的广告商。当用户点击广告时,系统会向广告商收取一笔预先确定的费用。归属于广告商的收入是所有对广告商的广告进行点击的总成本。用户使用一系列的设备进行搜索查询,这些设备可能是手机、平板电脑或个人电脑。归属于某一设备类型的收入是广告系统从该特定设备类型的广告点击中获得的所有收入的总和。
我们试图回答的问题是:我们如何将收入下降精确到正确的维度和它们的元素?我们把这个问题重述如下:
“根据维度及其元素,找到一个布尔表达式,使归属于该表达式的收入下降能够最好地解释总的收入下降。”
当我们很快研究如何确定 "最佳 "时,请考虑以下可以解释50美元收入下降的表达式。
例如,方程2指出,广告商表第1、3、4行的预测收入和实际收入之间的差异之和为51美元,这与总收入下降50美元非常接近。
一般来说,这样的表达可以包括多个维度,如收入下降(DT == PC ∧ DC == X),指的是来自数据中心X的PC用户的收入下降。根据大约一年的广告系统监测警报,我们通过人工研究以及使用归因算法,将异常情况归咎于多个维度,这种多个维度共同导致根源的情况非常罕见。因此,为了简化论述,在本文中,我们将讨论限制在寻找一个布尔表达式,该表达式包含一个单一的维度和一组解释异常变化的元素。
为了理解什么是 "最佳 "维度及其元素集,我们研究了几个标准。请看下面的稻草人方法,它激发了我们最后的问题陈述。
稻草人方法:找到一个维度和一组元素,其收入下降至少是总收入下降的一个阈值,TEP,并且是最简洁的。
我们将一组元素的解释力(EP)量化为它所解释的指标变化的百分比。我们将一组元素的简洁性(P)量化为表达中元素的总数。因此,稻草人方法将找到解释力至少为TEP的表达,并且使用最少的元素数量。
奥卡姆剃刀认为,只要能在一定的误差范围内解释下降,最简洁的集合就是最好的解释。根据这一论点,如果TEP设定为0.9,那么三个方程中的最佳维度和元素就在方程1中,因为仅数据中心X就可以解释总下降的94%。
然而,这种方法在存在多个维度的情况下,对根源性原因有缺陷。尽管数据中心X的收入下降占总收入下降的94%,但注意到预测收入和实际收入在两个数据中心X和Y之间平均分配。数据中心Y提供了两个价值中的6%。相比之下,在设备类型方面,PC设备类型贡献了50%的预测收入(100美元中的50美元),但占据了实际收入的98%(50美元中的49美元)。移动和平板电脑设备类型的贡献也相差很大,从预测收入的25%到实际收入的0%。广告商的贡献也有不同,但不如设备类型的贡献大。
总的来说,设备类型维度的不同元素对预测收入和实际收入的贡献的这种巨大变化是令人惊讶和意外的。
因此,我们建议,与我们只使用表达式的简洁性和解释能力相比,惊奇性是问题的一个更好的指示。假设这个收入下降的根本原因是由于一个配置文件错误,导致在手机和平板电脑上没有广告显示。虽然数据中心X仍然会显示出巨大的收入下降,因为它提供了94%的跨设备显示的广告,但实际的根本原因最好由设备类型维度以及移动和平板电脑等元素来解释。换句话说,公式3的表达是最好的,尽管它不是最简洁的。
为了捕捉这个观察结果,我们的方法包括一个与表达式相关的 “惊奇性"(S)的概念(第3节有确切的定义)。因此,对任何指标进行归纳,我们最终的收入调试问题声明可以用三个步骤来捕获。
- 对于一个维度,找到所有的元素集,这些元素集至少可以解释衡量标准中的一个阈值部分,即TEP(具有高解释力)。
- 在每个维度的所有这些集合中,找出在该维度中最简洁的集合。
- 在所有维度的所有此类集合中,找出在贡献率变化方面最令人惊讶的一个集合。
同样,在TEP=0.9的情况下,第一步将把数据中心的集合缩小到{X},广告商的{A1, A3, A4},以及设备类型的{手机,平板电脑}和{PC,手机,平板电脑}。第二步将每个维度的集合缩小到{X},{A1,A3,A4}和{移动,平板电脑}。第3步将使用惊奇性度量来挑选设备类型维度及其集合{Mobile, Tablet}作为对下降的最佳解释。
我们的算法使用每元素变化的阈值TEEP来增加成功率的概念。我们不仅希望得到最小的元素集合,还希望只有那些对异常现象至少有一部分TEEP贡献的元素。
我们在第3.4节中表明,在最坏的情况下,解决这个问题可能需要指数级的时间(以元素的数量计)。因此,我们使用一个贪婪的方法来近似解决这个问题。
3 根源识别算法
我们从一些符号开始,用它来正式定义解释力和惊喜。然后我们描述根源识别算法。虽然该算法对于基本和派生测量来说是相同的,但是派生测量的解释力和惊喜的计算方式更为复杂,将在第4节单独讨论。
3.1 符号
本节所使用的重要术语清单及其符号在表5中进行了总结。让指标的集合(如收入,搜索次数)表示为M = {m1,m2—,mk},让维度的集合(如广告商,数据中心)表示为D = {D1, D2, …, Dn}。此外,让给定维度Di的元素集表示为Ei = {Ei1, Ei2, …, EiCi },其中Ci是维度i的cardinality。例如,E21可能是 “Flowers123”,广告商维度的一个元素。
对于诸如收入或搜索次数这样的基本衡量标准,衡量标准的总体预测值F(m)和总体实际值A(m)在所有维度上都是相同的(例如,在前一节的例子中,预测收入为100美元,实际收入为50美元)。对于基本度量来说,总体度量只是各维度元素的度量值的总和,但对于派生度量来说,情况并非如此,因为它们不是相加的(第四节)。
因此,给定F(m)和A(m),该算法需要输出一个潜在的根本原因来解释两者之间的差异。为此,它使用了解释力和惊奇性,接下来对它们进行定义。
3.2 解释力
一个元素的解释力可以定义为衡量标准总体价值的变化中,由特定元素的价值变化所解释的百分比。对于基本指标来说,一个元素j在维度i中的解释力简单地说就是
例如,某小时的总搜索量从预测值100万偏离到80万,而某一数据中心DC1在同一小时的搜索量从预测值50万偏离到40万,则要素DC1的解释力为(0.4-0.5)/(0.8-1)=50%。
请注意,如果一个要素的变化与整体变化方向相反,那么这个要素的解释力可以超过100%,甚至是负数。然而,任何维度的所有元素的解释力之和应该达到100%。因此,解释力可以完全解释整体测量的变化。
3.3 惊奇性
正如在第2节的例子中所讨论的,一个在其分布上有很大变化的维度(如设备类型)比没有表现出这种变化的维度(如数据中心)更有可能成为根本原因。我们现在正式定义一个衡量惊讶的标准来捕捉这个概念。
对于每个元素Eij,让pij(m)表示预测值或先验概率值:
给定一个新的异常观察,让qij(m)为实际或后验概率值:
直观地说,如果后验概率分布与先验概率分布有明显的不同,那么对于一个给定维度的新观察结果是令人惊讶的。两个概率分布P和Q之间的这种差异可以用相对熵或Kullback-Leibler(KL)发散来表示[12]。然而,在我们的背景下使用KL发散有两个问题。首先,KL发散不是对称的。第二,KL发散只有在以下情况下才被定义:对于alli,qi=0,只有pi=0,这在我们的环境中不成立(例如,广告商暂停了他的活动)。
因此,我们使用一种相关的衡量标准,即Jensen-Shannon(JS)发散[12]来计算惊奇性,定义如下:
请注意,DJS(P,Q)是对称的,即使在qi=0和/或pi=0时也是有限的。此外,0≤DJS(P,Q)≤1。其中0表示P和Q之间的分布没有变化,数值越大表示差异越大。
因此,为了计算元素Eij的惊喜Sij,我们用p = pij(m)和q = qij(m)来计算
根因识别算法试图使用上述解释力和惊奇性的定义来解决第2节中规定的优化问题。
请注意,在最坏的情况下,获得该问题的最优解需要指数级的时间。这可以通过一个简单的例子来说明:考虑一个大小为n的集合,其中每个元素都有相同的解释力,我们要求该集合的n/2个元素来解释TEP。在这种情况下,每一个可能的大小为n/2的子集都是尽可能小的(简洁的),并且具有TEP的解释力。因此,我们必须对所有这些子集(其数量为n的指数级)的惊奇性进行比较,以找到具有最大惊奇性的子集,即最优解。
我们的算法(图2)没有列举各种具有至少TEP解释力的最小cardinality子集,而是采用了以下贪婪的方法。在每个维度上,在计算了所有元素的惊奇性之后(第1-5行),它首先按照惊奇性的递减顺序对元素进行排序(第8行)。然后将每个元素添加到一个候选集,只要该元素本身能解释至少TEEP的总异常变化(第12-15行)。参数TEEP有助于控制该集合的核心性(奥卡姆剃刀)。例如,如果TEEP是10%,TEP是67%,我们最多可以有7个元素来解释异常变化。此外,通过按照惊讶程度从高到低的顺序检查元素,我们贪婪地寻求最大限度地提高候选集的惊讶程度。该算法在每个维度上最多增加一个候选集合(第16-19行),只要该集合能够解释异常变化的主要部分(TEP)(解释力)。最后,该算法按惊奇性对各种候选集进行排序,并将最令人惊讶的前三个候选集作为潜在的根本原因候选人返回(第21-22行)。
4 派生指标
派生指标是基本指标的函数,由故障排除者追踪,因为它们比单纯追踪基本指标能揭示更多的信息。在这一节中,我们将讨论我们如何计算派生指标的解释力和惊奇性。
4.1 解释力
虽然将单个元素对派生指标的总体价值的贡献归于根源识别很重要,但这并不像计算基本指标那样简单。在这一节中,我们首先从一个说明性的例子开始,帮助定义派生指标的解释力,然后介绍我们对派生指标归属问题的解决方案。
示例:考虑表6和表7中的假设例子,它显示了在一个异常时期,四个不同的广告商的收入和点击数,分别是。对于这两个基本指标,使用解释力(公式4)将整体变化归因于每个广告商是很简单的,并显示在标有EP的一栏中。因此,对于收入下降,我们可以把它归因于广告商A1(400%),而对于点击量的增加,我们可以把它归因于广告商A2(200%)。
让我们假设,如果某项指标与预期值相差至少20%,就会出现异常情况。请注意,总体收入下降了10%,而点击次数上升了16%,这两者都没有超过异常阈值。相应的每次点击成本值显示在表8中,使用同样的20%的阈值,整体的每次点击成本(下降了22.5%)可以被标记为异常。 因此,我们可以看到,派生的指标在浮现异常方面是有用的,而仅仅检查基本指标是无法浮现的。我们在第6节中定量地确认这一点。
派生指标的归属问题如下:如何将每次点击的总成本从0.2(预期)下降到0.155(实际)归于每个广告商?如果我们研究一下表8中广告商的每次点击成本,我们会发现广告商A1、A2、A4的每次点击成本没有变化,而广告商A3的每次点击成本却在增加。因此,乍一看,似乎没有一个广告商可以为整体的下降负责,但肯定有一个或更多的广告商必须负责!鉴于这种情况,我们如何去做?鉴于这种情况,我们该如何为这些广告商的每次点击费用的变化分配解释力值呢?
对基本指标的研究确实有助于揭示更多的情况。例如,尽管A1的每次点击成本没有变化,但A1的收入和点击量与预测值相比,都有5倍的下降。鉴于A1的每次点击成本(0.5)高于整体价值(0.2),5倍的下降意味着A1确实在拉低整体的每次点击成本。如果我们使用A1的实际值,但假设其余的广告商都提供了各自的预测值,那么整体的每次点击成本就会下降到60/420=0.143,影响为-29%,这一事实可以进一步验证。
同样,虽然A2的预测收入为0,但A2的点击量有很大的增长,这最终降低了每次点击的总成本。同样,如果我们使用A2的实际值,但保持其他广告商的预测值,总体每次点击成本下降到100/660 = 0.152,影响为-24%。上述一次改变一个广告商的价值的做法也表明,A1比A2更有责任拉低整体的每次点击费用(因为使用A1的实际价值导致整体价值比A2低)。
现在考虑A3。在点击量没有变化的情况下,A3的收入比预想的要高,所以A3显然没有对整体下降做出贡献。在上述示例中使用A3的实际价值,实际上会使总体的每次点击成本增加到0.26,影响为+30%。
最后,A4的收入和点击量都没有变化。因此,A4对总体每次点击成本没有影响。
将单个影响值归一化,以便所有元素都能解释100%的整体变化,上述练习将使A1的解释力为125%,A2为106%,A3为-131%,A4为0%。
总结上述例子中的观察结果,我们可以看到,一个元素对衍生指标的解释力可以通过计算一个新的衍生指标值来确定,其中使用了给定元素的实际值和所有其他元素的预测值,并将这个衍生指标值与衍生指标的预期值进行比较。
现在,问题是我们如何将这种直觉正式化,以确定任意派生指标的解释力?接下来我们将对此进行描述。
衍生指标归属:我们对派生指标归属问题的解决方案是由偏导数和有限差分微积分改编的。我们对派生指标归属问题的解决方案是从偏导数和有限差分微积分改编而来的。回顾一下,偏导是衡量一个由多个变量组成的函数在其中一个变量变化时的变化情况。然而,由于我们在离散域中操作,我们使用有限差分微积分的偏导等价物[13]。
我们正式定义一个元素i对派生度量的解释力,即基本度量m1,…,mk的函数h(m1,…,mk),作为h(.)的有限差分中相对于i的偏导数,归一化,使二元的所有元素的值加起来为100%。
虽然上述定义是通用的,并且适用于作为基本度量的任意函数的派生度量(只要它们在有限差分中是可差的),但我们现在通过A(m1 )/A(m2 )形式的派生函数的具体例子来说明它,这构成了广告系统中的许多派生度量(图1)。例如,对于每次点击成本的衍生指标,我们有m1=收入,m2=点击量。
f(.)/g(.)的有限差分偏导的形式是(∆f∗g-∆g∗f)/(g∗(g+∆g)),与连续域偏导类似,只是分母中多了一个∆g。因此,元素j对维度i的解释力,对于形式为m1/m2的派生度量,由以下公式给出:
我们用上述公式计算每个要素的EPij,并将其归一化,使其加起来达到100%。
表8显示了用上述公式计算的每个广告商的解释力。我们可以看到,A1、A2、A4和A3的排序以及它们各自对整体变化的归因的解释力值与前面的直观观察一致。
4.2 惊奇性
回顾一下,我们在第3.3节中根据指标m值的先验和后验质量函数之间的相对熵(特别是JS分歧)定义了基本指标的惊奇性。
考虑上一节中的每次点击费用的例子。计算派生度量的惊奇性的一个简单方法如下。就像基本度量一样,我们可以为每个元素Eij计算每次点击成本的先验和后验概率值,例如pij(cost-per-click)和qij(cost-per-click),并像第3.3节中那样计算惊奇性。
然而,这种方法是行不通的。考虑表8中广告商A2的例子。因此,如果使用上述方法来计算A2元素的惊奇性,它的值将是0(没有惊奇性)。然而,我们发现A2对于A2的点击次数的变化所导致的每次点击成本的整体变化有很高的预测能力,即106%。
从相对熵的角度来考察这个问题,给定几个度量,我们首先需要计算度量的联合概率分布,然后计算联合概率分布函数的相对熵。如果这些指标是独立的,那么联合概率分布的相对熵(也是JS发散)只是各个指标的概率分布的相对熵之和。在广告系统中,这些指标并不总是严格独立的,因为其中一些指标可能是相关的(例如,随着搜索次数的增加,收入可望增加)。然而,作为一个近似值,我们假设指标是独立的,并计算衍生指标的惊奇性,作为衍生函数的一部分的单个指标的惊喜的总和。
5 仿真和经验
在这一节中,我们描述了我们在Adtributor工具中对上述算法的实现,并概述了我们在生产广告系统中的试点部署经验。
5.1 实施
在我们的实现中,数据库实时记录所有指标、维度和元素的计数,并将其作为支持多维分析查询的OLAP服务公开[19]。当系统触发一个异常事件时,Adtributor工具链首先收集与异常事件相关的数据,如异常时间、指标、各种指标的数据、维度和元素的数据。在从数据库中查询到数据后,Adtributor采用根源算法来发现给定异常现象的潜在根源。
回顾一下,指标不一定是相互独立的。某项指标的异常可能与另一项指标的值的变化相关联。因此,我们建立一个指标的依赖图,对于一个给定的异常指标,对每一个与之相关的指标运行根因分析算法。
Adtributor对候选的根本原因集进行过滤(如第3节所述),产生最终的根本原因列表。我们使用一个67%的TEP值和一个10%的TEEP值。这些阈值是由故障排除者在手工过程中已经使用的东西驱动的。另外,我们目前的实施方案单独列出了前三个方面的清单。故障排除专家根据他们自己的要求以及可视化的便利性,推荐了这个数字。如果数量较少,他们可能会错过有用的信息,而数量较多则会导致他们无法筛选出太多的信息。
最终的输出是一个独立的HTML5应用程序。图3显示了由Adtributor工具链产生的输出的一个例子。根本原因的可视化包含以下信息。
- 依赖关系图。系统中不同指标之间的依赖关系的图形表示(左半部分)。
- 指标历史图。描述指标的历史行为的图表(右上图)。
- 元素根源和历史图表。对于一个给定的指标和维度,最重要的元素是根本原因。元素根源按维度和它们的历史图表分组(在右上方的图表下)。
我们通过与故障排除专家的反复讨论得出了可视化的要求。依赖关系图使他们能够观察到不同测量值之间的因果关系,而每个维度的历史图则帮助他们对到底什么是根本原因做出更有说服力的选择。整个Adtributor工具链是用.NET框架4实现的,使用了12,500行代码,并为每个异常情况自动执行。
5.2 部署经验
我们在2013年5月1日和2013年5月10日之间对Adtributor进行了试点部署,与生产系统中的故障排除人员一起处理造成根源的异常情况,以了解Adtributor的有用性。这一部署在帮助故障排除人员处理他们的现有流程方面取得了部分成功。这个试点的发现导致了对我们的算法和可视化的一系列改进,这使得我们在第6节的评估中显示了显著的性能。
不稳定的维度:各种维度都可能是非常不稳定的,即使它们不一定是问题的根本原因,但沿着这些轴线的测量也会发生意外的变化。考虑到一个广告商经常改变其广告的预算分配的例子。当出现收入异常时,这有时会导致根因分析算法选择该广告商作为罪魁祸首,尽管该变化恰好发生在异常事件之前。这促使我们改进了我们的预测算法,通过增加预测模型中对近来的巨大变化所给予的权重,从而在很大程度上解决了这个问题,这就是与波动维度的元素有关的指标。
视觉化增强:问题调查者发现,相关指标的依赖图非常有用。然而,目前工具中的视图只限于一小部分指标。在广告系统中,还有数以百计的其他指标被监测,而这些指标的依赖关系并不为人所知。因此,我们使用贝叶斯结构学习算法[5]来推断这些依赖关系的一个子集,并计划用这些额外的指标来加强依赖关系图的可视化。
6 评价
在本节中,我们首先描述了四个案例研究,其中多维分析是得出最终根本原因的关键。接下来,我们对Adtributor的准确性进行了量化评估,并对我们使用该工具所节省的时间进行了评估。
6.1 案例研究
案例1:这是由营业额的异常下降引发的。在进行多维分析时,我们发现维度浏览器是应该对本次数据异常责任的。图4有助于解释Adtributor如何得出这个结果。
它显示了三个维度–浏览器、数据中心和桶–对预测收入和实际收入的贡献百分比(桶的定义见表1,例子3)。请注意,浏览器3的收入贡献被预测为12%,但它的实际收入为0%! 同样地,浏览器1的贡献被预测为60%,但实际却高得多,为74%。数据中心维度和桶维度都没有显示出这种惊人的贡献变化。这个问题是可操作的,因为进一步调查发现,一个配置错误导致没有广告显示在浏览器3的用户面前。纠正这个错误后,收入损失的问题也得到了进一步的解决。
案例2:我们注意到,在一个特定的时间内,收入出现了异常的增长,Adtributor将其归因于一组特定的六个广告商。这些广告商中有两个是机票供应商,两个是汽车租赁公司,其余两个是酒店。总的来说,他们完全解释了收入的变化。深入研究这个问题,我们注意到这些广告商在一定时期内故意增加了他们的预算。这些广告出现在一个周末长假即将到来的地理区域。因此,我们推断,这些广告商正试图利用并抓住用户在进行假期相关搜索时的注意力。显然,在这种情况下,收入的突然上升是由于广告商的行为,而不是由于系统中的一个可接受的错误。当广告商故意降低他们的预算时,也会出现一些这样的异常情况。
案例3:搜索的总数异常地高,分析表明大部分的增加是由于用户代理字符串的变化。从对这一结果的后处理中,推断出大部分带有重复的用户代理字符串的搜索来自一个小范围的IP广告,因此,可疑的是机器人流量的特征。特别是,这个机器人的目标是为搜索引擎优化(SEO)进行查询和收集信息。这是一个可操作的问题,通过过滤这个流量对各种指标的贡献,这个问题得到了及时的解决。
案例4:我们注意到有时候出版商改变了他们页面上的广告位置,这使得广告更(或更)显眼。这反过来又导致收入的相应增加或减少。这些显示为沿着页面上的广告位置这一维度的收入变化。例如,如果出版商将一个本应显示在页面侧面的广告移至页面顶部,这就表现为显示在顶部的广告收入的惊人增长。这是由于用户往往更容易点击显示在页面顶部的广告,而不是显示在侧面的广告。
6.2 比较研究
我们的定量评估是基于使用Adtributor对一个广泛部署的广告系统的问题进行根治。我们对所有产生的异常现象进行评估,共有12种指标,包括基本的和衍生的,涉及33个维度。我们在这里提出的结果使用的是2013年9月1日至2013年9月15日期间在8个人群中由超过10亿次搜索产生的128个有效异常的子集。美国、英国、法国和德国的PC和移动广告系统。在本研究中,我们不考虑异常生成过程中的假阳性,因为这些假阳性在应用根因分析过程之前已经被故障排除了。50%的测试异常是在派生指标上产生的,而在构成派生指标的各自基本指标上没有产生相关的异常。这表明,在总体根源分析中使用派生指标是极其重要的。
我们将Adtributor的多维分析输出与故障排除小组的输出进行了比较,后者在其他工具(不是Adtributor)的协助下,通过人工手段对这些异常现象进行了深入细致的分析。手动分析异常现象的原因有很多好处。故障排除人员知道大量的信息和领域知识,他们在故障排除过程中经常使用这些知识。像Adtributor这样的自动化工具不可能了解所有这些信息。此外,Adtributor只是缩小了根本原因的范围(表1的第4栏)–在许多情况下,可能仍然需要手动过程来确定最终的根本原因(表1的第4栏),因为下一步所需的一些数据可能无法用于自动过程(例如,验证出版商是否确实改变了广告的位置)。
然而,使用Adtributor的好处是,它可以通过以下方式帮助人工故障排除过程:1)使用多维根源分析来全面检查所有可能的维度(正如我们所展示的,在少数情况下,人工过程可能会忽略一个维度,导致得出错误的结论);2)显著加快处理速度,找出最可疑的原因。例如,有几十个维度,一些维度可能有成千上万的元素。
如第5节所述,Adtributor显示前三个维度和它们的元素作为潜在的怀疑对象。如果Adtributor在这三个位置中的任何一个显示出与人工根因分析过程相同的维度和完全相同的元素,我们就说Adtributor与人工根因分析过程的输出相符。
表9显示了Adtributor的输出与人工调查的比较结果。在128个异常点中,Adtributor在118个案例中与人工分析的结果相匹配。其中,81个(69%)在位置1中匹配,27个(23%)只在位置2中匹配,10个(8%)在位置3中匹配。在这10个与人工输出不匹配的异常中,我们与故障诊断专家进行了深入的探讨。经过仔细检查,我们发现在这10个异常中,有4个手动根因分析结果是错误的,而Adtributor在位置1的输出实际上是正确的根本原因。这显示了使用系统算法的效用,就像Adtributor那样,详尽地搜索所有维度来进行多维度的根源分析。
在剩下的6个异常情况中,人工输出的结果有5个是正确的,而Adtributor的输出是错误的。在所有这些案例中,Adtributor由于缺乏领域知识,或者缺乏对故障排除者明确知道的系统外部事件的了解而受到损害。然而,在一个案例中(标记为模棱两可),故障排除者认为由Adtributor指责的维度和元素与通过手工分析得到的维度和元素一样可能是真正的根本原因。在这种情况下,他认为需要进一步深入分析以确定正确的根本原因。考虑到人工错误,Adtributor的总体准确率为(118+4)/128,即95%。
我们还比较了使用Adtributor可以节省的潜在时间,与人工故障排除过程中的第一步相比,即确定可能是潜在根源的尺寸和元素。Adtributor使用多线程实现和缓存来加快研究每个维度和每个指标的过程。它对每个异常情况的处理时间约为3-5分钟。手动排除故障的过程中,最快的异常情况需要13分钟,最长的需要231分钟,平均周转时间为73分钟。因此,我们得出结论,Adtributor加速了最初的根因分析过程的一个数量级。
最后,我们通过将我们的算法与第2节中讨论的只使用简洁性和解释力的稻草人算法相比较,显示了使用惊奇性的价值。与Adtributor 95%的准确性相比,我们发现稻草人算法的准确性只有20%。这清楚地表明了使用惊奇性来识别正确的维度和元素作为根本原因的价值。
7 广告系统以外的适用性
我们相信,本文介绍的技术具有足够的通用性,可以在其他环境中发挥作用,比如说:
多维分析:考虑一个拥有全球观众的网络服务器,突然看到点击量急剧下降。本文考虑的许多维度,如数据中心或CDN、浏览器、用户位置、欺诈运营商/机器人等,都可能是潜在的根本原因,多维分析可以帮助区分。
衍生指标的归属:考虑以下问题。VoIP电话的平均意见分数(MOS)已经下降,调查人员想了解在电话路由中的哪条链路对这一下降负有最大责任。每条链路可能有不同数量的延迟、抖动和损失百分比,而MOS是延迟、损失和抖动等指标的复杂函数[6]。使用衍生的归因技术可以帮助计算每个链接的MOS下降的解释力。
8 相关工作
系统和网络的根本原因分析:以前的研究已经广泛地研究了系统和网络中导致性能和故障的根源问题[14, 2, 10, 1, 21, 15, 3, 20, 11, 18]。其中一些使用通过系统的单个请求的跟踪[3, 14]来诊断问题,而另一些则使用系统性能或配置值的集合计数器[15, 10, 20]来诊断问题。
Distalyzer [14] 是前一类的例子。它使用单独的事件日志,并学习事件之间的异常特征,以表明系统组件的性能问题。Ganesha [15] 是后者的一个例子。它使用聚类的方法,通过聚集的指标,如CPU使用率,来建立不同的MapReduce节点的专业文件。虽然我们的方法也使用聚合指标,但我们打算找到比性能问题或诊断故障更多的东西。
Q-Score[18]使用机器学习来得出根本原因。我们尝试过类似的方法,但决定不采用,因为选择正确的特征集来输入到机器学习算法中是一件必要的事情,但结果发现这是一项困难的事情。相反,我们发现建立一个定制化的算法更简单,更适合由我们的领域专家进行分析和反馈。
SCORE[11]利用简洁的解释将IP故障定位到底层组件。给定一组链路故障作为观察,它确定解释故障的最小的风险组集合。然而,正如我们所展示的,这种方法不足以进行跨维度的归因,而惊奇性的概念对于完成我们的解决方案是必不可少的。
总结的数据挖掘:以前的数据挖掘工作[17, 16, 7]集中在总结OLAP产品中的多维数据。其目的是为多个维度的数据值的差异提供一个容易解释的总结。这种总结技术也被应用于网络流量总结[9]。虽然多个维度的数据汇总与我们的工作有关,但它不符合我们的目标,即找到明显的变化来进行根本原因分析。事实上,我们的根本原因分析方法是对这些方法的补充,可以应用于它们所产生的总结。
9 结论
我们描述了一种算法、实现和评估的方法,该方法使用多维分析来处理大规模广告系统中的根本原因问题。我们发现,我们的方法有很高的准确性(95%),在大多数情况下比人工调查更准确地识别根源,并且能够大大减少故障排除时间。
10 鸣谢
我们要感谢我们的领导人VYAS SEKAR的宝贵意见和建议。我们还要感谢MURALI KRISHNA帮助我们验证了Adtributor的输出并确定其准确性。
内容整理
2014年,微软研究院提出了一种基于Adtributor算法的多维时间序列异常根因分析方法。同时,在AIOps技术研讨交流会暨2019国际AIOps挑战赛中,获奖的前五支团队无一例外地引用了该算法。国际AIOps挑战赛是由清华大学联合中国计算机学会发起的智能运维领域最具影响力的专业赛事,旨在以智能运维技术解决真实业务场景中的运维经典问题。Adtributer的作者团队经过长期的案例学习发现,一个异常的根因由多个维度共同导致的情况非常罕见,因此文章将问题限制在只在一个维度的元素组合中寻找异常的根因。
Adtributor多维根因分析流程主要包括四个步骤:
步骤1数据收集:收集KPI的多维时间序列数据,对于缺失值、死值等进行初步预处理,提升数据质量。
步骤2异常检测:采用ARMA时间序列模型或我们在上篇中使用的Isolation Forest对KPI进行实时预测,将预测值F和真实值A对比,判断KPI是否发生异常;预测值F和真实值A将用于Adtributor根因分析。
步骤3根因分析:Adtributor对异常KPI的所有维度和元素计算EP值和S值,并与TEP、TEEP阈值比对分析,从而筛选和定位出异常根因。
步骤4结果输出
Adtributor缺点及局限
(1)上述是针对基本类型的KPI的计算公式(例如PV、交易量),对于派生类型的KPI(多个基本类型KPI计算得到,例如成功率)就不太适用了
(2)将根因限定在一维的假设不太符合我们的实际场景,同时用解释性和惊奇性的大小来衡量根因也不完全合理。因为其没有考虑到维度之间的相互影响以及「外部根因」的可能
(3)Adtributor的根因分析严重依赖于整体KPI的变化情况,对于整体变化不大,但是内部波动较为剧烈的数据表现不好