状态窗口和状态仓库

简介

在最近面对的一个网管系统中，要求实现基于时间窗的阈值告警。 最终我设计了状态窗口和状态仓库的概念来实现了算法，成功运用在这个项目中。本文对概念和算法进行简单介绍,以被遗忘，并和大家交流。

摘要

对状态窗口的概念进行介绍。并且设计了状态窗口工具类。在数据网管系统中，可以使用这里设计的工具类，实现基于时间窗的阈值告警。

概念

网管系统中，对一个KPI指标(比如一个主机的CPU利用率)的监控:按照一定的采集周期(比如5妙)，采集数据并检测。每次阈值检测后，可能产生两个结果：超过阈值/低于阈值。基于时间窗的告警，就是对一个时间区间内的结果进行统计，如果超过阈值的时间过高，就产生告警。这个时间区间是固定长度，并且随着时间的变化而向前滑动，称为时间窗。当前时间窗的右边界就是最新一次采集点的时间。

参考下面的图，时间轴上的时间窗口

虚线的框表示时间窗，时间窗在时间轴上滑动，每一个时刻，可以统计出，时间窗口内超过阈值的采集点的个数或超过阈值的时间长度。

职责

为了实现基于时间窗的阈值检测，抽象出状态窗口的概念StateWindow，并最终使用JAVA语言实现。这个对象有下面的职责：

1. 内部保存当前时间窗内的所有检测结果。因为每次检测结果有两个值，可使用Boolean类型的变量保存。

2. 当往状态窗口中添加新的检查结果时，时间窗向前滑动，记录新的结果，并且删除超过时间窗的旧的结果。

3. 统计当前时间窗的结果，报告窗内状态的统计情况。

接口

1. void changeSize(int size) 设置时间窗的大小,参数size，以”秒”为单位或者以采集时间点个数为单位。

2. void reset(state) 重新初始化时间窗,把所有时间点的值设置成state。

3. int size() 返回状态窗口的大小

4. void move(boolean newState,int steps = 1) 添加新的检测结果，并移动窗口。参数newState是新的检测结果。参数steps 是窗口移动的距离，也是上一检测点到现在的时间。这个距离的量度单位必须和时间窗大小的单位相同。调用这个方法通知StateWindow在最新的steps长度的时间内，状态一直为newState。如果没有指定steps，默认steps=1。

5. int statTrueTime() 统计结果：状态为Ture的时间的长度， 单位和时间窗大小的单位相同。

实现

实现的关键是数据结构。要保存一段时间内的状态变化情况，有两种方法：

1. 第一种方法，SimpleWindow，保存一个size长度的数组。数组中的元素为boolean类型state。记录每个时间点的状态。这种方法实现简单，但占用内存较大。当size较小的时候。可以使用。size的大小，主要决定于时间窗的单位，如果采集周期固定不变，适应采集点的个数（或周期的个数）作为单位，这种情况下，size较小。如果采集的周期不固定，应该以“秒”为时间单位，这种情况下size会很大，应该用下面的方法。

2. 第二种方法，CompressWindow，压缩存储。保存状态的数组长度是不固定的，数组第每个元素为(duration， state)对。表示状态为state，长度为duration的一断时间。这种方法，只记录每次状态变化，在size很大时可以节省空间，并且可以自动适应采集周期的变化，但实现较复杂。

SimpleWindow的数据结构

数据结构	说明
int m_num_true	保存状态为true的时间，在窗口滑动过程中更新。避免每次遍历状态列表计算，提高效率。
LinkedList m_state_list	保存每个时间点(或等长时间段)的状态，因为插入删除操作频繁并且没有随机访问动作。选用链表。
boolean m_default_state	默认状态，在初始化时或链表长度增加的时候，用这个状态来填充链表。

构造函数：protected SimpleWindow(int size, boolean default_state)

CompressWindow的数据结构

内部类型用来保存一段持续的状态

private class StateDuration {

public boolean state; //状态

public int duration; //这个状态的持续时间

... ...

}

数据结构	说明
int m_num_true	保存状态为true的时间，在窗口滑动过程中更新。避免每次遍历状态链表计算，提高效率。
boolean m_default_state	默认状态，在初始化时或链表长度增加的时候，用这个状态来填充链表
LinkedList m_state_list	保存各个时间段状态的链表，连续的状态压缩在同一个时间断保存
int m_size	因为时间窗的大小不能通过链表长度直接得到，在时间窗滑动过程中保持这个值的更新

构造函数：CompressWindow(int size, boolean default_state)

状态仓库

摘要

对状态窗口的概念进行介绍。设计并实现状态窗口工具类。

概念

在数据网管系统的应用中，需要动态的创建大量的状态窗口。为了简化状态窗口的创建和使用。开发状态仓库类。一个状态仓库内部维护大量的状态窗口，这些状态窗口可以使用，自定义key访问。

职责

状态仓库，利用状态窗口类，有下面的职责。

1. 提供按KEY创建和访问状态窗口的机制。创建和并且保存状态窗口。

2. 为每个状态窗口自动补全缺失的状态更新。有了这个功能，在数据网管系统的应用中，为了提高效率，当检测一个KPI不超过阀值的时候，不必更新状态窗口状态，这种情况下也不产生告警。当KPI超过阈值，客户更新窗口状态，状态仓库自动判断并补全丢失的状态更新。请参考下面的实现 。

3. 统一的设置和维护所有状态窗口的时间单位。外部通过Interval更新状态，状态仓库根据状态窗口的时间单位滑动状态窗口，当采集的Interval发生变化的时候，状态窗口可以不失效。外部使用统一的单位size访问时间窗口。

4. 自动清理过期的状态窗，释放占用的内存。

接口

唯一的状态访问接口：UpdateAlertState，更新告警状态，返回当前时间窗内告警的总时间。为了方便，这个函数提供了不同参数的多个版本

int updateAlertState(Sring name,int iterval, int windowSize, int timestamp)

int updateAlertState(Sring name,int iterval, int windowSize)

int updateAlertState(Sring name,int iterval)

更新告警状态，返回指定时间窗内，告警时间的长度。状态第一次更新的时候，会自动为这个名字创建一个状态窗口。

参数：

name - 状态的名字

iterval - 告警持续的时间，单位为秒。

timestamp - 当前时间的时间错，精度为秒，如果没有指定，使用当前时间。

size - 状态窗口的大小，如果指定的大小和当前的窗口不同，将修改状态窗口的大小，如果没有指定，使用Iterval作为窗口大小。

单位为秒

返回：

这个状态对应的状态窗口中，告警状态的总时间。用户把这个值除以Iterval，可以得到指定时间窗内告警的次数。单位为秒

实现

内部数据结构

内部类

class State{

public int ts; //记住状态窗口的最后更新时间

public StateWindow win; //状态窗口

... ...

}

数据结构	说明
int m_unit	时间窗口的单位。为了最大可能的节省内存，应该设置成所有采集周期的最大公约数。默认为60妙，以分钟为单位。
int m_clean_interval	自动清理周期。定期清理过期的时间窗，以节省内存。
HashMap m_state_base	使用HashMap保存所有的状态，提高查找的效率

构造函数

public StateDepot(int unit, int autoCleanTime)

public StateDepot(int unit)

public StateDepot()

参数unit为时间窗口的单位。默认为60,表示60秒，单位为分钟。

参数autoCleanTime为自动清理过期状态窗口的周期，默认为3600,表示3600妙，半小时。

关键算法：updateAlertState的实现

参考下面的流程图