2

I'd need some feedback on how to approach the design of a function that highlights parts of a time series chart. The chart shows the response time of an application, in particular the 90th percentile, over time. Each bar on the chart is one minute. I want to see anomalies, determined based on thresholds I define.

I expect I will be able to obtain a threshold, maybe based on historical data, of what's the expected value of the 90th percentile (as in, "what's normal"). Same goes for another threshold for the extreme values of the 90th percentile, also based on historical data. Let's call these thresholds T1 and T2, respectively.

What I want to do: I want to be able to enhance the chart in such a way that I can see "unusual deviations" of the 90th percentile. This will be in particular useful to find issues we saw after releasing a new software version of the application - check if there are extreme, prolonged spikes, if there are consistent, but not extreme, degradation of performance, etc.

Now, to the key point, what is unusual?

  1. Consecutively exceeding the lower threshold T1. The 90th percentile has been above the lower threshold, for say X=10 minutes in a row.
  2. a) Extreme peaks, exceeding higher threshold T2. The 90th percentile has been exceeding the extreme values for say X=5 minutes in a row. b) I think to make the extreme values measure more useful, there needs to be a notion of "close to threshold T2", since I expect T2 to be probably twice as high as the lower threshold T1. So, exceeding threshold T2 might be already too late/extreme.
  3. To make these measures somewhat robust, we should ignore intermittent dips, so the sequence of values extreme, extreme, normal, extreme would still be considered a single series of extreme values.
  4. After a deviation is over, the highlighting, presumably based on a running score, needs to return back to normal quickly. I don't want to see highlighted data points for an issue that happened 1 hour ago. Think of exponential drop-off.

Let's look at a made-up response time chart:

enter image description here

W1 would be an example of scenario 1. and W2 would be an example of scenario W2. Note that we don't care if the values are below the T1 threshold, or if there are single, extreme values. At least for now.

What I'd like to get out after my model colors the graph:

enter image description here

Based on the second chart, I'd know that I need to look at the two red timeranges and have a closer look what happened there.

I don't expect someone to provide me the finished code, but I could use a few pointers:

  • Examples of existing implementations. I found fancy machine learning anomaly detections, but I'm not interested in that. What I'm looking for is a basic model with tunable parameters such as thresholds and timeframe length. The model should not be too involved and easily explainable, such that I can implement it myself based on basic stats functions.
  • Many examples I found are based on normally distributed data. The percentile distributions I work with are for sure not normally distributed. They maybe follow loosely a power law distribution, but I'd like to avoid assuming a certain distribution - is that doable?
  • Any other input you have if you worked on a system like this before.

I'm OK with the basics of math and some stats.

3
  • I’m not sure how you’ll define the difference between “normal” and “extreme” without assuming some kind of distribution. Don’t you need an assumed distribution to define what constitutes an outlier? May 22 at 18:24
  • You have already described an approach that is close to an implementable algorithm, but it doesn't seem to match your graphics. For example, you've marked t=12 despite being under T1, and not marked T=38 despite being over T1. I wouldn't worry about normal distributions since a lot of statistics can still be done in a non-parametric manner. Percentiles are a robust metric that can be used without assuming any distribution.
    – amon
    May 22 at 22:25
  • @amon, fair enough, in W1, t=12/13 should NOT have been marked. For W2 I think that would be OK to color t=38 maybe in orange or so, as a kind of "in between". What I'm struggling with a bit is for example the "drop off" part, so that I can gloss over drops of 1 or 2 mins but still return back to normal state as soon as the situation steadily normalizes (values are below threshold.)
    – Max
    May 23 at 11:26
3

I work in a completely different domain, but we have a similar requirement where our system must take action when a measured physical signal is outside a predefined band long enough to be considered significant. The main difference to your algorithm is that we must act as soon as the conditions are fulfilled, rather than marking past values as requiring further human analysis.

If I were to apply our algorithm to your situation, it would look something like this:

  1. Define 2 thresholds, a detect threshold and an undetect threshold, and a minimum number of samples
  2. Iterate over the relevant portion of the response time measurements (the data for the 1-minute bars in the graph)
  3. At each 1-minute interval, check if the value is above the defined detect threshold
    1. If it is increment a counter
    2. If it is not, but it is above the undetect threshold, increment the counter as well
    3. If it is below the undetect threshold, reset the counter to 0
    4. If the counter exceeds the minimum number of samples, indicate that the past <counter> samples need to be marked as needing investigation

If there are two alerting levels, each with their own levels and time, then you just run two instances of the algorithm.

The idea with the separate detect/undetect thresholds is to create a hysteresis band during which the state of the detection algorithm doesn't change.

4
  • Thanks for the input, a few questions. 1. Interesting idea with two thresholds. That is to make the system less sensitive to intermittent drop-offs in response times? 2. Do you use a linear 1/0 approach to define if sth is above or below the threshold? I was thinking about implementing "close to", to get more granular scoring. Example: if threshold is 10, then if the current value is 11, then it's not as "bad" as if the current value would be 35. Not sure how to implement that yet though. 3. How did you determine your thresholds/bands?
    – Max
    May 23 at 11:35
  • 1
    @Max, 1) The hysteresis between the thresholds is indeed to make the system less sensitive to response times that fluctuate slightly around the threshold. 2) We indeed use a binary yes/no to tell if the signal is above the threshold. We find that to be entirely sufficient. 3) Our thresholds are in part based on experience and in part on experimentation. We know what kind of situations our system must react to and we can set up experiments in a lab to simulate or create those situations. You probably need to go on experience and make the thresholds tunable. May 23 at 17:39
  • Nice input, much appreciated for sharing your experiences. I think I have some idea now how to continue.
    – Max
    May 23 at 18:17
  • Just as a feedback: I implemented this algorithm with good success in my application. Where I'm somewhat unsure: "Point 2. If it is not, but it is above the undetect threshold, increment the counter as well" -> My intuition is that we could make false positives a bit less likely if the values need to be AT LEAST 1 TIME above the detect threshold. Only after this happens once, going above the undetect threshold also counts as violation. But I haven't tested that yet, because it makes the impl. somewhat more complicated.
    – Max
    Jul 11 at 7:19
1

Have a look at HdrHistogram.

There are implementations for all kinds of languages.

What it effectively is, is a history of latency distributions. So you could have a latency distribution per second and if you run a benchmark for 60 seconds, you have a 60 latency distribution of 1 second. With HdrHistogram you can calculate the percentiles and other statistics per time window. And then you can add logic to detect if there are anomalies in whatever kind of statistic. E.g. if you easily detect if there are 10 consecutive windows with a too high p99. You could also aggregate the histograms and create latency distributions per minute/hour/day/week etc. So you don't need to deal with large quantities of tiny histograms.

The nice thing is that you make a final latency distribution and determine e.g. your percentiles; or remove e.g. warmup and cooldown. But you can also zoom into a particular region, e.g. there is a compaction causing problem at a particular moment, then you can zoom into exactly that section.

There are some other nice properties: because you have the full latency distribution, you can merge the latency distributions of multiple load generators. The common approach I see is that engineers average the percentiles of the 2 load generators, but that is mathematically incorrect.

If you are doing a latency test, make sure you also deal correctly with coordinated omission. If you don't deal with it correctly, the worst latencies in your benchmark are omitted and you will falsely assume your system is behaving better than it actually is. You can find some presentations of Gil Tene (author of HdrHistogram) on YouTube on this topic.

3
  • That's super interesting input. I will need to do some reading, never heard this before, but it this looks very practical. Thank you!
    – Max
    Jul 11 at 7:12
  • You are welcome. And you could use a sliding window approach. So you calculate the 1 minute average of 1-61s, from 2-62, 3-63 etc by merging the latency distributions for those periods. And you could just set an alert e.g if the p99 of the 1 minute sliding window is above a certain level.
    – pveentjer
    Jul 11 at 7:24
  • And it is up you to decide the lowest granularity a histogram-period. Perhaps you don't care for 1 second granularity but perhaps 1h granularity is good enough to start with.
    – pveentjer
    Jul 11 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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