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

做法是这样的：

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

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

least_squares

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

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

histogram_bins

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

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

grubbs

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

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

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

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

相关内容