数据库被广泛用于美团的核心业务场景上,对稳定性要求较高,对异常容忍度非常低。因此,快速的数据库异常发现、定位和止损就变得越来越重要。针对异常监测的问题,传统的固定阈值告警方式,需要依赖专家经验进行规则配置,不能根据不同业务场景灵活动态调整阈值,容易让小问题演变成大故障。
而基于AI的数据库异常发现能力,可以基于数据库历史表现情况,对关键指标进行7 * 24小时巡检,能够在异常萌芽状态就发现风险,更早地将异常暴露,辅助研发人员在问题恶化前进行定位和止损。基于以上这些因素的考量,美团数据库平台研发组决定开发一套数据库异常检测服务系统。接下来,本文将会从特征分析、算法选型、模型训练与实时检测等几个维度阐述我们的一些思考和实践。
在具体进行开发编码前,有一项非常重要的工作,就是从已有的历史监控指标中,发现时序数据的变化规律,从而根据数据分布的特点选取合适的算法。以下是我们从历史数据中选取的一些具有代表性的指标分布图:
从上图我们可以看出,数据的规律主要呈现三种状态:周期、漂移和平稳[1]。因此,我们前期可以针对这些普遍特征的样本进行建模,即可覆盖大部分场景。接下来,我们分别从周期性、漂移性和平稳性这三个角度进行分析,并讨论算法设计的过程。
在很多业务场景中,指标会由于早晚高峰或是一些定时任务引起规律性波动。我们认为这属于数据的内在规律性波动,模型应该具备识别出周期性成分,检测上下文异常的能力。对于不存在长期趋势成分的时序指标而言,当指标存在周期性成分的情况下,$\int f(x) f(x+t) dx \leqslant \int f(x)f(x+T)dx = \int f^{2}(x)dx$,其中T代表的是时序的周期跨度。可通过计算自相关图,即计算出t取不同值时$\int f(x) f(x+t) dx$ 的值,然后通过分析自相关峰的间隔来确定周期性,主要的流程包括以下几个步骤:
具体过程如下:
对于待建模的序列,通常要求它不存在明显的长期趋势或是存在全局漂移的现象,否则生成的模型通常无法很好地适应指标的最新走势[2]。我们将时间序列随着时间的变化出现均值的显著变化或是存在全局突变点的情况,统称为漂移的场景。为了能够准确地捕捉时间序列的最新走势,我们需要在建模前期判断历史数据中是否存在漂移的现象。全局漂移和周期性序列均值漂移,如下示例所示:
数据库指标受业务活动等复杂因素影响,很多数据会有非周期性的变化,而建模需要容忍这些变化。因此,区别于经典的变点检测问题,在异常检测场景下,我们只需要检测出历史上很平稳,之后出现数据漂移的情况。综合算法性能和实际表现,我们使用了基于中位数滤波的漂移检测方法,主要的流程包含以下几个环节:
中位数平滑
a.根据给定窗口的大小,提取窗口内的中位数来获取时序的趋势成分。
b.窗口需要足够大,以避免周期因素影响,并进行滤波延迟矫正。
c.使用中位数而非均值平滑的原因在于为了规避异常样本的影响。
判断平滑序列是否递增或是递减
a.中位数平滑后的序列数据,若每个点都大于(小于)前一个点,则序列为递增(递减)序列。
b.如果序列存在严格递增或是严格递减的性质,则指标明显存在长期趋势,此时可提前终止。
遍历平滑序列,利用如下两个规则来判断是否存在漂移的现象
a.当前样本点左边序列的最大值小于当前样本点右边序列的最小值,则存在突增漂移(上涨趋势)。
b.当前样本点左边序列的最小值大于当前样本点右边序列的最大值,则存在突降漂移(下跌趋势)。
对于一个时序指标,如果其在任意时刻,它的性质不随观测时间的变化而变化,我们认为这条时序是具备平稳性的。因此,对于具有长期趋势成分亦或是周期性成分的时间序列而言,它们都是不平稳的。具体示例如下图所示:
针对这种情况,我们可以通过单位根检验(Augmented Dickey-Fuller Test)[3]来判断给定的时间序列是否平稳。具体地说,对于一条给定时间范围指标的历史数据而言,我们认为在同时满足如下条件的情况下,时序是平稳的:
通过了解业界的一些知名公司在时序数据异常检测上公布的产品介绍,加上我们历史积累的经验,以及对部分线上实际指标的抽样分析,它们的概率密度函数符合如下情况的分布:
针对上述的分布,我们调研了一些常见的算法,并确定了箱形图、绝对中位差和极值理论作为最终异常检测算法。以下是对常见时序数据检测的算法对比表:
算法\场景 | 对称分布下适用性 | 偏态分布下适用性 | 正态性要求 | 异常容忍度 |
---|---|---|---|---|
3Sigma | 高 | 低 | 高 | 低 |
绝对中位差(MAD) | 高 | 低 | 高 | 高 |
箱形图(Boxplot) | 高 | 中 | 中 | 高 |
极值理论(EVT) | 中 | 高 | 低 | 低 |
我们没有选择3Sigma的主要原因是它对异常容忍度较低,而绝对中位差从理论上而言具有更好的异常容忍度,所以在数据呈现高对称分布时,通过绝对中位差(MAD)替代3Sigma进行检测。我们对不同数据的分布分别采用了不同的检测算法(关于不同算法的原理可以参考文末附录的部分,这里不做过多的阐述):
有了如上的分析,我们可以得出具体的根据样本输出模型的流程:
算法的整体建模流程如上图所示,主要涵盖以下几个分支环节:时序漂移检测、时序平稳性分析、时序周期性分析和偏度计算。下面分别进行介绍:
案例:给定一条时间序列ts={t0,t1,⋯,tn},假定其存在周期性且周期跨度为T,对于时间索引j而言,其中j∈{0,1,⋯,T−1},对其建模所需要的样本点由区间[tj−kT−m, tj−kT+m]构成,其中m为参数,代表窗口大小,k为整数,满足j−kT−m≥0, j−kT+m≤n。
举例来说,假设给定时序自2022/03/01 00:00:00至2022/03/08 00:00:00止,给定窗口大小为5,周期跨度为一天,那么对于时间索引30而言,对其建模所需要的样本点将来自于如下时间段:
[03/01 00:25:00, 03/01 00:35:00]
[03/02 00:25:00, 03/02 00:35:00]
…
[03/07 00:25:00, 03/07 00:35:00]
这里选取了一个案例,展示数据分析及建模过程,便于更清晰的理解上述过程。其中图(a)为原始序列,图(b)为按照天的跨度进行折叠的序列,图©为图(b)中某时间索引区间内的样本经过放大后的趋势表现,图(d)中黑色曲线为图©中时间索引所对应的下阈值。如下是针对某时序的历史样本进行建模的案例:
上图©区域内的样本分布直方图以及阈值(已剔除其中部分异常样本),可以看到,在该高偏分布的场景中,EVT算法计算的阈值更为合理。
为了实时检测规模庞大的秒级数据,我们以基于Flink进行实时流处理为出发点,设计了如下的技术方案:
以下是具体的离线训练和在线检测技术设计:
异常检测算法整体采用分治思想,在模型训练阶段,根据历史数据识别提取特征,选定合适的检测算法。这里分为离线训练和在线检测两部分,离线主要根据历史情况进行数据预处理、时序分类和时序建模。在线主要加载运用离线训练的模型进行在线实时异常检测。具体设计如下图所示:
为了提高优化迭代算法的效率,持续运营以提高精准率和召回率,我们借助Horae(Horae是美团内部可扩展的时序数据异常检测系统)的案例回溯能力,实现在线检测、案例保存、分析优化、结果评估、发布上线的闭环。
目前,异常检测算法指标如下:
目前,美团数据库异常监测能力已基本构建完成,后续我们将对产品继续进行优化和拓展,具体方向包括:
绝对中位差,即Median Absolute Deviation(MAD),是对单变量数值型数据的样本偏差的一种鲁棒性测量[6],通常由下式计算而得:
$$MAD=C \times \operatorname{median}\left|X_{i}-\operatorname{median}(X)\right|$$
$$Upper=median+k \times MAD$$
$$Lower=median-k \times MAD$$
其中在先验为正态分布的情况下,一般C选择1.4826,k选择3。MAD假定样本中间的50%区域均为正常样本,而异常样本落在两侧的50%区域内。当样本服从正态分布的情况下,MAD指标相较于标准差更能适应数据集中的异常值。对于标准差,使用的是数据到均值的距离平方,较大的偏差权重较大,异常值对结果影响不能忽视,而对MAD而言少量的异常值不会影响实验的结果,MAD算法对于数据的正态性有较高要求。
箱形图主要通过几个统计量来描述样本分布的离散程度以及对称性,包括:
将Q1与Q3之间的间距称为IQR,当样本偏离上四分位1.5倍的IQR(或是偏离下四分位数1.5倍的IQR)的情况下,将样本视为是一个离群点。不同于基于正态假设的三倍标准差,通常情况下,箱形图对于样本的潜在数据分布没有任何假定,能够描述出样本的离散情况,且对样本中包含的潜在异常样本有较高的容忍度。对于有偏数据,Boxplot进行校准后建模更加符合数据分布[7]。
真实世界的数据很难用一种已知的分布来概括,例如对于某些极端事件(异常),概率模型(例如高斯分布)往往会给出其概率为0。极值理论[8]是在不基于原始数据的任何分布假设下,通过推断我们可能会观察到的极端事件的分布,这就是极值分布(EVD)。其数学表达式如下(互补累积分布函数公式):
$$P(X-t>x \mid X>t) \sim\left(1+\frac{\gamma x}{\delta(t)}\right)^{-\frac{1}{\gamma}}$$
其中t代表样本的经验阈值,对于不同场景可以设置不同取值,$\gamma$,$\delta$分别是广义帕累托分布中的形状参数与尺度参数,在给定样本超过人为设定的经验阈值t的情况下,随机变量X-t是服从广义帕累托分布的。通过极大似然估计方法我们可以计算获得参数估计值$\hat{\gamma}$与$\hat{\delta}$ ,并且通过如下公式来求取模型阈值:
上述公式中q代表风险参数,n是所有样本数量,Nt是满足x-t>0的样本数量。由于通常情况下对于经验阈值t的估计没有先验的信息,因此可以使用样本经验分位数来替代数值t,这里经验分位数的取值可以根据实际情况来选择。
美团基础技术部/数据库研发中心/数据库平台研发组,负责为美团各个业务线提供高效便捷的数据库使用入口,帮助美团DBA稳定快捷地维护数据库,同时提供分析诊断平台,实现数据库自治。