Simple way to algorithmically identify a spike in recorded errors

Question

We need an early warning system. I am dealing with a server that is known to have performance issues under load. Errors are recorded in a database along with a timestamp. There are some manual intervention steps that can be taken to decrease the server load, but only if someone is aware of the issue...

Given a set of times that errors occurred, how can I identify the beginning of a spike in errors (in real time)? We can calculate periodically or on each error occurrence.

We are unconcerned about occasional errors, but don't have a specific threshold. I could just notify someone any time we get, say, three errors in five minutes, but I'm sure there's a better way...

I'd like to be able to adjust the sensitivity of the algorithm based on feedback from the sysadmins. For now, they'd like it to be fairly sensitive, even though we know we can expect some false positives.

I am not a statistician, which I'm sure is obvious, and implementing this needs to be relatively simple with our existing tools: SQL Server and old-school ASP JScript. I'm not looking for an answer in code, but if it requires additional software, it probably won't work for us (though I welcome impractical but ideal solutions as a comment, for my own curiosity).

Answer 1

It has been 5 months since you asked this question, and hopefully you figured something out. I'm going to make a few different suggestions here, hoping that you find some use for them in other scenarios.

For your use-case I don't think you need to look at spike-detection algorithms.

So here goes: Let's start with a picture of the errors occurring on a timeline:

What you want is a numerical indicator, a "measure" of how fast the errors are coming. And this measure should be amenable to thresholding - your sysadmins should be able to set limits which control with what sensitivity errors turn into warnings.

Measure 1

You mentioned "spikes", the easiest way to get a spike is to draw a histogram over every 20-minute interval:

Your sysadmins would set the sensitivity based on the heights of the bars i.e. the most errors tolerable in a 20-minute interval.

(At this point you may be wondering if that 20-minute window length can't be adjusted. It can, and you can think of the window length as defining the word together in the phrase errors appearing together.)

What's the problem with this method for your particular scenario? Well, your variable is an integer, probably less than 3. You wouldn't set your threshold to 1, since that just means "every error is a warning" which doesn't require an algorithm. So your choices for the threshold are going to be 2 and 3. This doesn't give your sysadmins a whole lot of fine-grained control.

Measure 2

Instead of counting errors in a time window, keep track of the number of minutes between the current and last errors. When this value gets too small, it means your errors are getting too frequent and you need to raise a warning.

Your sysadmins will probably set the limit at 10 (i.e. if errors are happening less than 10 minutes apart, it's a problem) or 20 minutes. Maybe 30 minutes for a less mission-critical system.

This measure provides more flexibility. Unlike Measure 1, for which there was a small set of values you could work with, now you have a measure which provides a good 20-30 values. Your sysadmins will therefore have more scope for fine-tuning.

Friendly Advice

There is another way to approach this problem. Rather than looking at the error frequencies, it may be possible to predict the errors before they occur.

You mentioned that this behavior was occurring on a single server, which is known to have performance issues. You could monitor certain Key Performance Indicators on that machine, and have them tell you when an error is going to happen. Specifically, you would look at CPU usage, Memory usage, and KPIs relating to Disk I/O. If your CPU usage crosses 80%, the system's going to slow down.

(I know you said you didn't want to install any software, and it's true that you could do this using PerfMon. But there are free tools out there which will do this for you, like Nagios and Zenoss.)

And for people who came here hoping to find something about spike detection in a time-series:

Spike Detection in a Time-Series

The simplest thing you should start by doing is to compute a moving average of your input values. If your series is $x_1, x_2,...$, then you would compute a moving average after each observation as:

$M_k = (1 - \alpha) M_{k-1} + \alpha x_k$

where the $\alpha$ would determine how much weight give the latest value of $x_k$.

If your new value has moved too far away from the moving average, for example

$\frac{x_k - M_k}{M_k} > 20\%$

then you raise a warning.

Moving averages are nice when working with real-time data. But suppose you already have a bunch of data in a table, and you just want to run SQL queries against it to find the spikes.

I would suggest:

1. Compute the mean value of your time-series
2. Compute the standard deviation $\sigma$
3. Isolate those values which are more than $2\sigma$ above the mean (you may need to adjust that factor of "2")

More fun stuff about time series

1. Many real-world time-series exhibit cyclic behavior. There is a model called ARIMA which helps you extract these cycles from your time-series.

2. Moving averages which take into account cyclic behavior: Holt and Winters

Answer 2

+1 for Statistical process control, there's some useful information here on Step Detection.

For SPC it's not too hard to write an implementation of either the Western Electric Rules or the Nelson Rules.

Just make a USP in SQL server that will iterate through a data set and ping each point against the rules using its neighbouring points. Maybe sum up the number of errors by hour (depending on your needs).

---

This kind of relates to a question I posted on Stack Overflow a while back (have just penned a quick answer if it helps): Statistical Process Control Charts in SQL Server 2008 R2

Answer 3

A search for Online detection algorithms would be a start.

More information located on stackoverflow: Peak Dection of measured signal

A python implementation of a naive peak detection routine is to be found at github

Answer 4

You may want to look at statistical process control. Or time series monitoring. There are tons of work in this direction, and the optimal answer probably depends a lot on what exactly you are doing (do you need to filter out yearly or weekly seasonalities in load before detecting anomalies etc.).