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).

  • This seems to have been useful to people, so I will leave the title as-is, but I think "spike" is misleading. What we were actually looking for is an inflection point or a relative increase. – dbenton Dec 22 '17 at 17:27
up vote 36 down vote accepted

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:

Error Graph

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:

Error Histogram

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.

Time Differences

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

  • Thanks for the thorough and educational answer. We ended up writing a stored procedure to record each error to a database and return the number of errors in the last X (we settled on 5) minutes. If that number was over our threshold, Y, a warning email was sent. We adjusted the threshold by experimentation until we were happy with it. If I were doing it over, I would incorporate your suggestion of counting time between errors for greater granularity. – dbenton Apr 22 '13 at 16:11
  • 4
    Hall of fame answer, applause. Joined this community solely to upvote this. – wesanyer Jan 28 '16 at 17:19
  • Indeed an excellent answer! Thank you! – mkaran Feb 23 '17 at 14:04

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

  • I searched for online detection algorithms, and mostly found academic articles that are over my head. They may hold the answer, but don't pass my personal "simple" test. Correct me if I'm wrong, but I don't think I'm looking for a peak detection algorithm. Once the errors have peaked, it seems that by definition I've missed my opportunity to ameliorate the worst of the issue. Apologies if my use of "spike" was confusing. I guess I need to predict a continued increase in errors or identify a large step up. – dbenton Oct 25 '12 at 15:26

+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

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.).

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.