Jump-Starting Multivariate Time Series Anomaly Detection for Online Service Systems

Minghua Ma, Shenglin Zhang, Junjie Chen, Jim Xu, Haozhe Li, Yongliang Lin, Xiaohui Nie, Bo Zhou, Yong Wang, Dan Pei

TL;DR

This paper introduces JumpStarter, a novel approach for anomaly detection in multivariate time series data from online service systems. It addresses the critical issue of long initialization times for existing learning-based methods by leveraging Compressed Sensing, achieving high accuracy with significantly reduced setup time.

What Problem Does This Paper Address?

Online service systems, like those powering cloud applications, generate vast amounts of multivariate time series data (e.g., CPU utilization, response times, requests per second) that are crucial for monitoring system reliability. Detecting anomalies in this data is vital to ensure service quality. However, current state-of-the-art anomaly detection methods, primarily based on deep learning, suffer from prohibitively long initialization periods – often taking tens to hundreds of days to train sufficiently. This makes them impractical for rapidly evolving online service environments where deployments and configurations change frequently, leading to concept drift and invalidating trained models. The paper aims to bridge this gap by developing an anomaly detection system that is both accurate and can be quickly deployed.

Methods

The core of JumpStarter is the application of Compressed Sensing (CS) for anomaly detection. Unlike traditional learning-based methods that explicitly learn the "normal" behavior of time series, CS reconstructs a signal from a subset of measurements, implicitly capturing normal patterns. Anomalies are detected by identifying significant deviations between the original and reconstructed time series.

To handle the challenges of large-scale systems with numerous time series, JumpStarter employs two key novel techniques:

  • Shape-Based Clustering: Univariate time series are grouped based on their shape similarity using a hierarchical clustering approach. This allows for efficient reconstruction of related time series together, reducing computational burden without losing temporal relationships.
  • Outlier-Resistant Sampling: To avoid sampling from anomalous segments that can degrade detection performance, a novel sampling algorithm is introduced. This algorithm assigns lower sampling confidence to data points likely to be outliers, ensuring that the reconstruction is primarily based on normal data patterns.

The anomaly score is calculated using the harmonic mean of the differences between original and reconstructed time series across clusters, and an Extreme Value Theory (EVT) approach is used to dynamically set an anomaly threshold.

Datasets

The authors evaluated JumpStarter on three real-world datasets:

  • D1: A five-week-long dataset from a large Internet company (Company A), collected from 28 online service systems, sampled once per minute.
  • D2 & D3: Two datasets from a top-tier global content platform (Company B), each spanning seven weeks and collected from 30 online service systems, sampled every five minutes. These datasets represent services used by over 800 million users.

The ground truth for anomalies in all datasets was manually labeled by operators based on performance issues and incident reports.

Key Insights and Ideas

  • Initialization Time is a Major Bottleneck: The empirical study clearly demonstrates that existing learning-based anomaly detection methods require an impractically long time to initialize, rendering them unsuitable for dynamic online service environments.
  • Compressed Sensing Offers a Promising Alternative: CS provides a mechanism for anomaly detection that bypasses the need for extensive training data, significantly reducing initialization time.
  • Shape Matters for Clustering: Grouping time series by their shape is crucial for efficient and effective reconstruction in multivariate settings, especially when dealing with a large number of metrics.
  • Robust Sampling is Key to Accuracy: Simply sampling randomly can lead to false positives/negatives when anomalies are present. An outlier-resistant sampling strategy is essential for accurate anomaly detection with CS.
  • Component Contributions are Significant: Both shape-based clustering and outlier-resistant sampling individually contribute to JumpStarter's improved performance, and their combination yields the best results.

Key Results

  • High Accuracy: JumpStarter achieved an average F1 score of 94.12% across the three datasets, significantly outperforming state-of-the-art approaches like OmniAnomaly (86.51%), MSCRED (59.64%), LESINN (82.5%), and RRCF (36.01%).
  • Rapid Initialization: JumpStarter has an initialization time of only twenty minutes, a stark contrast to the tens to hundreds of days required by learning-based methods.
  • Robustness to Concept Drift: JumpStarter demonstrated superior performance in reacting to software changes, exhibiting a significantly lower False Positive Rate (FPR) compared to other methods after such events.
  • Efficiency: The shape-based clustering step takes at most 500ms, and the detection time per multivariate time series is approximately 127.13 ms.

Limitations and Future Work

  • Anomaly Labeling Noise: The authors acknowledge that manual anomaly labeling by operators can introduce noise (false positives/negatives), though they argue that contiguous anomaly segment evaluation mitigates this.
  • Granularity: While the algorithm is not expected to be affected by granularity, experiments were conducted on minute-level data.
  • Alert System Integration: JumpStarter is presented as a component for anomaly detection. Future work will focus on building a more comprehensive intelligent alert system that integrates domain knowledge, handles anomalies not visible in monitored time series (e.g., from logs/traces), and provides better root cause diagnosis.
  • Preference for Precision/Recall: Different services have varying needs for precision and recall. Future work aims to provide an interface for users to choose their preferred balance.
  • Severe Faults: The paper notes that severe faults are rare, while performance issues are common, and aims to reduce mean time to restore for severe faults in future work.

Summary updated

BibTeX
@inproceedings{ma2021jump,
  author = {Minghua Ma and Shenglin Zhang and Junjie Chen and Jim Xu and Haozhe Li and Yongliang Lin and Xiaohui Nie and Bo Zhou and Yong Wang and Dan Pei},
  title = {{Jump-Starting Multivariate Time Series Anomaly Detection for Online Service Systems}},
  booktitle = {USENIX ATC},
  year = {2021},
}
Figure