metric-anomaly-detection

How it is built

Architecture overview

A metric anomaly detector turns "this number is too high" from a hand-set threshold into a learned expected band per time series. Every series (a metric name plus labels, such as latency_p99{service="checkout"}) has a baseline made of a level, a trend and a seasonal shape, because most operational metrics follow daily and weekly cycles. Each new point is compared with its forecast; the gap, divided by a robust estimate of how much the series normally wobbles, is the anomaly score. A decision layer turns scores into alerts only when the deviation is large, lasts, and is not one of ten thousand coincidences.

The one idea that makes it work is that the baseline must be fitted on data that may itself contain anomalies, so every stage is built to be robust: medians and median absolute deviations instead of means and standard deviations, a seasonal decomposition that gives outliers low weight, and a persistence requirement before alerting. Hochenbaum et al. (2017) describe exactly this recipe, seasonal decomposition followed by median and MAD, for cloud metrics, and Datadog's anomaly monitors document three algorithms of rising sophistication: a rolling quantile, a robust variant of SARIMA, and a seasonal-trend decomposition. The detector reads series that a Metrics system collects and hands its alerts to Alerting.

Parts:

• Series store and windowing — keeps recent history per series and cuts it into aligned windows — Gorilla XOR compression, Columnar storage, Windowed stream aggregation, quantile-sketches (no page yet)
• Baseline model — expected value and normal spread per series and time of day — Exponential smoothing, STL decomposition, arima (no page yet)
• Scoring — turns the gap between observed and expected into one comparable number — Robust statistics, Isolation forest for several signals at once
• Shift detection — separates a spike from a new normal — change-point-detection (no page yet)
• Decision — persistence, error-rate control across many series, grouping — Hypothesis testing, Count-min sketch for rare event types
• Feedback and evaluation — operator labels, retraining and backtests — Time-series cross-validation, Model monitoring, Canary analysis

 collectors ─► metrics store ──► windowing / rollups ──► per-series state
 (scrape/push)  (TSDB)             (aligned buckets)        (level, trend, season, spread)
                                                               │
                      new point ──► forecast ──► residual ─► robust score ──► persistence check
                                                                   │                │
                                                         shift detector ──► multi-series control
                                                                                    │
                                                          grouping/dedup ──► alert + context ──► on-call
                              operator feedback ─► labels ─► retrain / tune thresholds ◄────────────┘

How the parts fit together

Series store and windowing

The detector reads series from the metrics store and keeps its own small state per series. The store holds history in compressed form: Gorilla XOR compression stores timestamps as deltas of deltas and values as the XOR of consecutive float bit patterns, which is why weeks of history for millions of series fit in memory (Pelkonen et al., VLDB 2015). Training and backtesting read long ranges of one or a few series at a time, the access pattern Columnar storage is built for.

Points must be aligned to a fixed step (for example one minute) before modelling, because decomposition and exponential smoothing assume regularly spaced samples. Windowed stream aggregation does this on the live path: group events by event-time window, keep one partial aggregate per window, and emit a window when the watermark passes its end. The contract: the model sees one value per series per step, a missing step is marked missing rather than zero (a gap is not a drop to zero), and late data either revises the window within an allowed lateness or is ignored. For latency metrics the aggregate per window must be mergeable; a percentile cannot be averaged across hosts, so quantile-sketches (no page yet) keep a sketch per window that merges across hosts, and the detector watches the merged percentile.

Baseline model

The baseline answers "what should this value be right now?". Three families cover most needs:

• Rolling statistics (no seasonality): the median and a robust spread over the last window. Cheap, adapts in minutes, blind to daily cycles. This is the idea of Datadog's "basic" algorithm, a lagging rolling quantile (Datadog anomaly monitor docs).
• Exponential smoothing (Holt-Winters): keeps a level, a trend and a seasonal profile, each updated by a fraction of the forecast error. It needs O(1) memory per series, so one process can hold millions of series, and a new point updates the state in constant time. The weakness is that a long anomaly leaks into the state: the model learns the outage as normal. The usual fix is to update with a clipped residual (the point capped at the band edge) so a spike barely moves the state.
• STL decomposition: splits a series into trend, seasonal and remainder with loess smoothing and bisquare robustness weights, so an outlier lands in the remainder rather than bending the seasonal shape. It is a batch method, re-run on a window (for example nightly) and used to project the next period, which keeps it stable through long anomalies at the cost of reacting slowly to intended level shifts. Datadog describes its "robust" algorithm as a seasonal-trend decomposition with exactly this property, and its "agile" algorithm as a robust variant of SARIMA that updates quickly after level shifts at the price of being less robust to long-lasting anomalies (Datadog docs).

arima (no page yet) is the third classical choice, with differencing and autoregressive terms; it fits dynamics that smoothing cannot, but needs order selection and a fit per series, so it suits high-value series rather than a million-series default. Exponential smoothing and STL come first because they have few parameters, fit by recursion, and fail in predictable ways.

Seasonality must be declared or detected: the period is a property of the business (24 hours, 7 days), not something to hunt for in noise. Series shorter than two periods fall back to rolling statistics until they have enough history.

Scoring

The residual is observed minus expected. To compare series of different scale, divide by a spread estimate. The ordinary standard deviation is inflated by the very outliers being sought, so use Robust statistics: the median absolute deviation (MAD) scaled by 1.4826 estimates sigma for normal data and has a 50 % breakdown point, while the standard deviation has none. The score is a robust z: (observed − forecast) / (1.4826 · MAD of recent residuals). A cut around 3 to 4 is a common starting point; the real value is set by the cost of false alarms.

For several signals that matter jointly (CPU, latency, error rate of one service), per-series scores miss the combination. Isolation forest scores a feature vector, one row per time step, by how few random axis-aligned splits isolate it; anomalies are few and different, so they isolate early. With 100 trees of 256 samples (the scikit-learn defaults, as listed on the block page) the model is small and scoring is cheap enough for the live path. The price is interpretability: the score says "unusual", not which metric moved, so keep per-series scores beside it for the explanation.

Shift detection

A step change is not a spike. After a deploy, traffic may settle at a new level; a detector that keeps calling it anomalous is useless, while one that adapts too fast hides a real regression. change-point-detection (no page yet) separates the cases with methods such as CUSUM, which accumulates small deviations until their sum crosses a bound, or PELT, which finds the best segmentation of a series. The policy: a short excursion is an anomaly; a sustained shift raises one "level shift" event and then re-baselines the series. Record deploy times as annotations so a shift can be attributed.

Decision

Raw scores are not alerts. Three filters sit between them:

1. Persistence. Require the score to stay over the threshold for several consecutive steps. Prometheus alerting rules use the same idea with the for clause: an element must stay active at every evaluation for the whole duration before the alert fires (Prometheus alerting-rules docs).
2. Error-rate control across series. With 100,000 series tested every minute, even a one-in-a-thousand false-positive rate gives about 100 false alerts per step. Hypothesis testing supplies the frame: convert scores to tail probabilities under the "no anomaly" model and control the false discovery rate (the Benjamini-Hochberg procedure covered on that page) instead of testing each series alone. In practice many systems set the threshold per series from its own history and alert on the count of series that agree.
3. Grouping. Anomalies on the same service, host or deploy within a window become one alert, grouped by labels, with the top contributing series as context.

For event streams with high-cardinality keys (error messages, URL paths), a Count-min sketch counts each key per window in fixed memory; a jump in a key's estimated count, or a new heavy key, feeds the same scoring. Count-min only overestimates, so thresholds on the estimate err toward false positives, which persistence then filters.

Feedback and evaluation

A detector without feedback decays. Operators mark alerts useful or noise; those labels tune per-series thresholds and choose the algorithm per series. Evaluate offline by backtesting: replay the stream in time order and never score a point with a model that saw its future (Time-series cross-validation is the rolling-origin scheme), and report precision and recall with a tolerance window, since an alert a few minutes late is still a hit. The Numenta Anomaly Benchmark is an open corpus of labelled streams for comparing streaming detectors. Model monitoring applies the same machinery to ML inputs and outputs, and Canary analysis compares against a control group instead of against history.

Data and control flow

A new point arrives:

1. The sample reaches the store; the windowing stage aligns it to the step and marks gaps.
2. The detector loads the series state (level, trend, seasonal profile, residual spread), forecasts the step and computes the residual.
3. It divides by the robust spread to get the score and compares it with the series' threshold.
4. It updates the state with the clipped residual, so the baseline adapts but not to the anomaly.
5. If the score stays over the threshold for the required steps, it emits a candidate; the shift detector decides whether it is a spike or a new level.
6. The decision layer applies error-rate control and grouping, attaches context (series, band, recent deploys) and sends one alert to the alerting system.

A nightly retrain: for each series, STL or a Holt-Winters refit runs on the last several weeks, excluding steps already flagged; the new parameters are backtested against the last week and replace the old ones only if they score no worse.

A feedback loop: an operator marks an alert as noise; the label raises that series' threshold or switches it to a more tolerant algorithm; the next backtest includes the label.

Scaling

In the order the limits appear:

1. Number of series. Keep per-series state O(1) (smoothing state, a few numbers) in memory, shard series by key hash, and use cheaper models for rarely queried series. Score only series that received a point.
2. Cold start. New series have no history; use rolling statistics at first, borrow a seasonal profile from a similar series (same metric, other host) and mark the output low confidence.
3. Training cost. STL and ARIMA refits are batch work: run them nightly, only on series with enough history and recent traffic, and start from the last fit.
4. False alert volume. Grows with the number of series, not with traffic: control it with persistence, FDR control and grouping before adding detection power.
5. Storage and read cost. Backtests read long ranges: keep columnar copies of rollups so a backtest reads only the columns it needs.

Failure modes

Real implementations

Sources

• Datadog, Anomaly monitor: the basic, agile and robust algorithms, seasonality options, time-zone note. docs.datadoghq.com/monitors/types/anomaly
• J. Hochenbaum, O. Vallis, A. Kejariwal, Automatic Anomaly Detection in the Cloud Via Statistical Learning, 2017: seasonal decomposition, then median and MAD. arxiv.org/abs/1704.07706
• R. Hyndman and G. Athanasopoulos, Forecasting: Principles and Practice, 3rd ed.: STL decomposition and exponential smoothing. otexts.com/fpp3
• F. T. Liu, K. M. Ting, Z.-H. Zhou, Isolation Forest, ICDM 2008. doi.org/10.1109/ICDM.2008.17
• T. Pelkonen et al., Gorilla: A Fast, Scalable, In-Memory Time Series Database, VLDB 2015. doi.org/10.14778/2824032.2824078
• Prometheus, Alerting rules (the for clause) and Query functions (predict_linear). alerting rules, functions