Android apache nginx centos Ubuntu linux shell Firefox 开源 Python java 程序员 google 微软 wordpress Windows HTML5 linux命令 mysql php

Etsy 的 Kale 系统 skyline 的过滤算法

监控大户 Etsy 最近有公布了一个全新的监控分析系统,叫 Kale,博客地址:http://codeascraft.com/2013/06/11/introducing-kale/

上一篇博客介绍了安装部署和数据导入的方法。但是对 skyline 组件的过滤原理没有做研究。今天花了点时间看 wiki 和源码,大概搞清楚了 skyline 的工作方式。很有趣,值得记录一下。

同样作为时间序列存储的 rrdtool 和 graphite,都偏重在预测算法,也就是说根据现有数据推测下一个数据应该是多少;而 skyline 则是根据现有数据统计最新数据是否异常。

目前,skyline 一共提供了 7 个异常检测算法,如果有 5 个以上认为是异常,那么 skyline就认为这个序列异常了。(当然,这都是可以修改的)

异常检测算法实际写在了 src/analyzer/algorithms.py 里,包括有:

first_hour_average

这是最简单的。先求本周期内最前面的第一个小时的平均值和标准差,然后和最新的三个值的平均值(tail_avg(),这是后面多数算法都通用的做法)做比较。如果 tail_avg 和 第一小时平均值的差距大于 3 倍的标准差,那么认定为异常。

simple_stddev_from_moving_average

把上面算法的范围扩大化,求的是整个周期内全部数据的平均值和标准差。

stddev_from_moving_average

在上面算法的基础上,采用指数加权移动平均值。对周期内采点数量较少的情况更好一些。

mean_subtraction_cumulation

做法是这样的:

  1. 排除最后一个值;
  2. 求剩余序列的平均值;
  3. 全序列减去上面这个平均值;
  4. 求剩余序列的标准差;
  5. 判断全序列最后一个值是否大于 3 倍的标准差

在代码中本来还计算了一次序列的指数加权移动平均值,但是算完了却没用,感觉怪怪的。

least_squares

采用最小二乘法拟近时间序列,然后用实际值减去拟近值得到新序列。然后判断新序列的最后三个值的平均值是否大于 3 倍的新序列标准差。

所谓最小二乘法,简单说就是对一个 [x, y] 序列,会有一对常数 [m, c],让 Y = mx + c 等式中的 Y 和 y 在全序列上最接近。

histogram_bins

将整个周期序列的数据按照直方图统计法归入 15 个直方中,然后看最后三个值的平均值属于这 15 个直方的具体哪个。如果这个直方中包含的数据小于 20 个,判断为异常。

从算法中可以知道,如果周期内数据量不够,很容易被判断为异常的。

grubbs

将整个周期序列的数据按照格拉布斯法求异常值。

标准的格拉布斯法是这样的:

  1. 从小到大排序;
  2. 求序列的平均值和标准差;
  3. 计算最小值和最大值与平均值的差距,更大的那个为可疑值;
  4. 可疑值减去平均值,再除以标准差,如果大于格拉布斯临界值,那么就是异常值;
  5. 排除异常值,对剩余序列循环做 1-5 步骤。

这里只用判断时间序列的最后是否异常,所以直接将最后三个值的平均值作为可疑值判断是否异常即可。

延伸阅读

评论