美团数据库平台研发组,面临日益急切的数据库异样发现需要,为了更加疾速、智能地发现、定位和止损,咱们开发了基于 AI 算法的数据库异样检测服务。本文从特征分析、算法选型、模型训练与实时检测等维度介绍了咱们的一些实际和思考,心愿为从事相干工作的同学带来一些启发或者帮忙。
1. 背景
数据库被宽泛用于美团的外围业务场景上,对稳定性要求较高,对异样容忍度非常低。因而,疾速的数据库异样发现、定位和止损就变得越来越重要。针对异样监测的问题,传统的固定阈值告警形式,须要依赖专家教训进行规定配置,不能依据不同业务场景灵便动静调整阈值,容易让小问题演变成大故障。
而基于 AI 的数据库异样发现能力,能够基于数据库历史体现状况,对要害指标进行 7 * 24 小时巡检,可能在异样萌芽状态就发现危险,更早地将异样裸露,辅助研发人员在问题好转前进行定位和止损。基于以上这些因素的考量,美团数据库平台研发组决定开发一套数据库异样检测服务零碎。接下来,本文将会从特征分析、算法选型、模型训练与实时检测等几个维度论述咱们的一些思考和实际。
2. 特征分析
2.1 找出数据的变化规律
在具体进行开发编码前,有一项十分重要的工作,就是从已有的历史监控指标中,发现时序数据的变化规律,从而依据数据分布的特点选取适合的算法。以下是咱们从历史数据中选取的一些具备代表性的指标分布图:
从上图咱们能够看出,数据的法则次要出现三种状态:周期、漂移和安稳[1]。因而,咱们后期能够针对这些广泛特色的样本进行建模,即可笼罩大部分场景。接下来,咱们别离从周期性、漂移性和平稳性这三个角度进行剖析,并探讨算法设计的过程。
2.1.1 周期性变动
- 提取趋势成分,拆散出残差序列。应用挪动平均法提取出长期趋势项,跟原序列作差失去残差序列(此处周期性剖析与趋势无关,若不拆散趋势成分,自相干将显著受到影响,难以辨认周期)。
- 计算残差的循环自相干(Rolling Correlation)序列。通过循环挪动残差序列后,与残差序列进行向量点乘运算来计算自相干序列(循环自相干能够防止提早衰减)。
- 依据自相干序列的峰值坐标来确定周期 T。提取自相干序列的一系列部分最高峰,取横坐标的距离为周期(如果该周期点对应的自相干值小于给定阈值,则认为无显著周期性)。
具体过程如下:
2.1.2 漂移性变动
对于待建模的序列,通常要求它不存在显著的长期趋势或是存在全局漂移的景象,否则生成的模型通常无奈很好地适应指标的最新走势[2]。咱们将工夫序列随着工夫的变动呈现均值的显著变动或是存在全局渐变点的状况,统称为漂移的场景。为了可能精确地捕获工夫序列的最新走势,咱们须要在建模后期判断历史数据中是否存在漂移的景象。全局漂移和周期性序列均值漂移,如下示例所示:
数据库指标受业务流动等简单因素影响,很多数据会有非周期性的变动,而建模须要容忍这些变动。因而,区别于经典的变点检测问题,在异样检测场景下,咱们只须要检测出历史上很安稳,之后呈现数据漂移的状况。综合算法性能和理论体现,咱们应用了基于中位数滤波的漂移检测办法,次要的流程蕴含以下几个环节:
-
中位数平滑
a. 依据给定窗口的大小,提取窗口内的中位数来获取时序的趋势成分。
b. 窗口须要足够大,以防止周期因素影响,并进行滤波提早改正。
c. 应用中位数而非均值平滑的起因在于为了躲避异样样本的影响。
-
判断平滑序列是否递增或是递加
a. 中位数平滑后的序列数据,若每个点都大于(小于)前一个点,则序列为递增(递加)序列。
b. 如果序列存在严格递增或是严格递加的性质,则指标显著存在长期趋势,此时可提前终止。
-
遍历平滑序列,利用如下两个规定来判断是否存在漂移的景象
a. 以后样本点右边序列的最大值小于以后样本点左边序列的最小值,则存在突增漂移(上涨趋势)。
b. 以后样本点右边序列的最小值大于以后样本点左边序列的最大值,则存在突降漂移(上涨趋势)。
2.1.3 平稳性变动
对于一个时序指标,如果其在任意时刻,它的性质不随观测工夫的变动而变动,咱们认为这条时序是具备平稳性的。因而,对于具备长期趋势成分亦或是周期性成分的工夫序列而言,它们都是不安稳的。具体示例如下图所示:
针对这种状况,咱们能够通过单位根测验(Augmented Dickey-Fuller Test)[3]来判断给定的工夫序列是否安稳。具体地说,对于一条给定工夫范畴指标的历史数据而言,咱们认为在同时满足如下条件的状况下,时序是安稳的:
- 最近 1 天的时序数据通过 adfuller 测验取得的 p 值小于 0.05。
- 最近 7 天的时序数据通过 adfuller 测验取得的 p 值小于 0.05。
3. 算法选型
3.1 散布法则与算法抉择
通过理解业界的一些出名公司在时序数据异样检测上颁布的产品介绍,加上咱们历史积攒的教训,以及对局部线上理论指标的抽样剖析,它们的概率密度函数合乎如下状况的散布:
针对上述的散布,咱们调研了一些常见的算法,并确定了箱形图、相对中位差和极值实践作为最终异样检测算法。以下是对常见时序数据检测的算法比照表:
算法 \ 场景 | 对称散布下适用性 | 偏态散布下适用性 | 正态性要求 | 异样容忍度 |
---|---|---|---|---|
3Sigma | 高 | 低 | 高 | 低 |
相对中位差(MAD) | 高 | 低 | 高 | 高 |
箱形图(Boxplot) | 高 | 中 | 中 | 高 |
极值实践(EVT) | 中 | 高 | 低 | 低 |
咱们没有抉择 3Sigma 的次要起因是它对异样容忍度较低,而相对中位差从实践上而言具备更好的异样容忍度,所以在数据出现高对称散布时,通过相对中位差(MAD)代替 3Sigma 进行检测。咱们对不同数据的散布别离采纳了不同的检测算法(对于不同算法的原理能够参考文末附录的局部,这里不做过多的论述):
- 低偏态高对称散布:相对中位差(MAD)
- 中等偏态散布:箱形图(Boxplot)
- 高偏态散布:极值实践(EVT)
有了如上的剖析,咱们能够得出具体的依据样本输入模型的流程:
算法的整体建模流程如上图所示,次要涵盖以下几个分支环节:时序漂移检测、时序平稳性剖析、时序周期性剖析和偏度计算。上面别离进行介绍:
举例来说,假如给定时序自 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]
- 偏度计算。时序指标转化为概率分布图,计算散布的偏度,若偏度的绝对值超过阈值,则通过极值实践进行建模输入阈值。若偏度的绝对值小于阈值,则通过箱形图或是相对中位差的形式进行建模输入阈值。
3.2 案例样本建模
这里选取了一个案例,展现数据分析及建模过程,便于更清晰的了解上述过程。其中图 (a) 为原始序列,图 (b) 为依照天的跨度进行折叠的序列,图 (c) 为图 (b) 中某工夫索引区间内的样本通过放大后的趋势体现,图 (d) 中彩色曲线为图 (c) 中工夫索引所对应的下阈值。如下是针对某时序的历史样本进行建模的案例:
上图 (c) 区域内的样本分布直方图以及阈值(已剔除其中局部异样样本),能够看到,在该高偏散布的场景中,EVT 算法计算的阈值更为正当。
4. 模型训练与实时检测
4.1 数据流转过程
为了实时检测规模宏大的秒级数据,咱们以基于 Flink 进行实时流解决为出发点,设计了如下的技术计划:
- 实时检测局部:基于 Flink 实时流解决,生产 Mafka(美团外部的音讯队列组件)音讯进行在线检测,后果存储于 Elasticsearch(以下简称 ES)中,并产生异样记录。
- 离线训练局部:以 Squirrel(美团外部的 KV 数据库)作为工作队列,从 MOD(美团外部运维数据仓库)读取训练数据,从配置表读取参数,训练模型,保留于 ES,反对主动和手动触发训练,通过定时读取模型库的形式,进行模型加载和更新。
以下是具体的离线训练和在线检测技术设计:
4.2 异样检测过程
异样检测算法整体采纳分治思维,在模型训练阶段,依据历史数据辨认提取特色,选定适合的检测算法。这里分为离线训练和在线检测两局部,离线次要依据历史状况进行数据预处理、时序分类和时序建模。在线次要加载使用离线训练的模型进行在线实时异样检测。具体设计如下图所示:
5. 产品经营
为了进步优化迭代算法的效率,继续经营以进步精准率和召回率,咱们借助 Horae(Horae 是美团外部可扩大的时序数据异样检测零碎)的案例回溯能力,实现在线检测、案例保留、剖析优化、后果评估、公布上线的闭环。
目前,异样检测算法指标如下:
- 精准率:随机抉择一部分检测出异样的案例,人工校验其中的确是异样的比例,为 81%。
- 召回率:依据故障、告警等起源,审查对应实例各指标异常情况,对照监测后果计算召回率,为 82%。
- F1-score:精准率和召回率的和谐平均数,为 81%。
6. 将来瞻望
目前,美团数据库异样监测能力已根本构建实现,后续咱们将对产品持续进行优化和拓展,具体方向包含:
- 具备异样类型辨认能力。能够检测出异样的类型,如均值变动、稳定变动、尖刺等,反对按异样类型进行告警订阅,并作为特色输出后续诊断系统,欠缺数据库自治生态[4]。
- 构建 Human-in-Loop 环境。反对依据反馈标注主动学习,保障模型继续优化[5]。
- 多种数据库场景的反对。异样检测能力平台化以反对更多数据库场景,如 DB 端到端报错、节点网络监测等。
7. 附录
7.1 相对中位差
相对中位差,即 Median Absolute Deviation(MAD),是对单变量数值型数据的样本偏差的一种鲁棒性测量[6],通常由下式计算而得:
其中在先验为正态分布的状况下,个别 C 抉择 1.4826,k 抉择 3。MAD 假设样本两头的 50% 区域均为失常样本,而异样样本落在两侧的 50% 区域内。当样本遵从正态分布的状况下,MAD 指标相较于标准差更能适应数据集中的异样值。对于标准差,应用的是数据到均值的间隔平方,较大的偏差权重较大,异样值对后果影响不能漠视,而对 MAD 而言大量的异样值不会影响试验的后果,MAD 算法对于数据的正态性有较高要求。
7.2 箱形图
箱形图次要通过几个统计量来形容样本分布的离散水平以及对称性,包含:
- Q0:最小值(Minimum)
- Q1:下四分位数(Lower Quartile)
- Q2:中位数(Median)
- Q3:上四分位数(Upper Quartile)
- Q4:最大值(Maximum)
将 Q 1与 Q 3之间的间距称为 IQR,当样本偏离上四分位 1.5 倍的 IQR(或是偏离下四分位数 1.5 倍的 IQR)的状况下,将样本视为是一个离群点。不同于基于正态假如的三倍标准差,通常状况下,箱形图对于样本的潜在数据分布没有任何假设,可能形容出样本的离散状况,且对样本中蕴含的潜在异样样本有较高的容忍度。对于有偏数据,Boxplot 进行校准后建模更加合乎数据分布[7]。
7.3 极值实践
真实世界的数据很难用一种已知的散布来概括,例如对于某些极其事件(异样),概率模型(例如高斯分布)往往会给出其概率为 0。极值实践 [8] 是在不基于原始数据的任何散布假如下,通过推断咱们可能会察看到的极其事件的散布,这就是极值散布(EVD)。其数学表达式如下(互补累积散布函数公式):
其中 t 代表样本的教训阈值,对于不同场景能够设置不同取值,$\gamma$,$\delta$ 别离是狭义帕累托散布中的形态参数与尺度参数,在给定样本超过人为设定的教训阈值 t 的状况下,随机变量 X - t 是遵从狭义帕累托散布的。通过极大似然预计办法咱们能够计算取得参数估计值 $\hat{\gamma}$ 与 $\hat{\delta}$,并且通过如下公式来求取模型阈值:
上述公式中 q 代表危险参数,n 是所有样本数量,Nt 是满足 x -t>0 的样本数量。因为通常状况下对于教训阈值 t 的预计没有先验的信息,因而能够应用样本教训分位数来代替数值 t,这里教训分位数的取值能够依据理论状况来抉择。
8. 参考资料
- [1] Ren, H., Xu, B., Wang, Y., Yi, C., Huang, C., Kou, X., … & Zhang, Q. (2019, July). Time-series anomaly detection service at microsoft. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining (pp. 3009-3017).
- [2] Lu, J., Liu, A., Dong, F., Gu, F., Gama, J., & Zhang, G. (2018). Learning under concept drift: A review. IEEE Transactions on Knowledge and Data Engineering, 31(12), 2346-2363.
- [3] Mushtaq, R. (2011). Augmented dickey fuller test.
- [4] Ma, M., Yin, Z., Zhang, S., Wang, S., Zheng, C., Jiang, X., … & Pei, D. (2020). Diagnosing root causes of intermittent slow queries in cloud databases. Proceedings of the VLDB Endowment, 13(8), 1176-1189.
- [5] Holzinger, A. (2016). Interactive machine learning for health informatics: when do we need the human-in-the-loop?. Brain Informatics, 3(2), 119-131.
- [6] Leys, C., Ley, C., Klein, O., Bernard, P., & Licata, L. (2013). Detecting outliers: Do not use standard deviation around the mean, use absolute deviation around the median. Journal of experimental social psychology, 49(4), 764-766.
- [7] Hubert, M., & Vandervieren, E. (2008). An adjusted boxplot for skewed distributions. Computational statistics & data analysis, 52(12), 5186-5201.
- [8] Siffer, A., Fouque, P. A., Termier, A., & Largouet, C. (2017, August). Anomaly detection in streams with extreme value theory. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1067-1075).
对于团队
美团根底技术部 / 数据库研发核心 / 数据库平台研发组,负责为美团各个业务线提供高效便捷的数据库应用入口,帮忙美团 DBA 稳固快捷地保护数据库,同时提供剖析诊断平台,实现数据库自治。
浏览美团技术团队更多技术文章合集
前端 | 算法 | 后端 | 数据 | 平安 | 运维 | iOS | Android | 测试
| 在公众号菜单栏对话框回复【2021 年货】、【2020 年货】、【2019 年货】、【2018 年货】、【2017 年货】等关键词,可查看美团技术团队历年技术文章合集。
| 本文系美团技术团队出品,著作权归属美团。欢送出于分享和交换等非商业目标转载或应用本文内容,敬请注明“内容转载自美团技术团队”。本文未经许可,不得进行商业性转载或者应用。任何商用行为,请发送邮件至 tech@meituan.com 申请受权。