TraceDiag: Adaptive, Interpretable, and Efficient Root Cause Analysis on Large-Scale Microservice Systems

Ruomeng Ding, Chaoyun Zhang, Lu Wang, Yong Xu, Minghua Ma, Xiaomin Wu, Meng Zhang, Qingjun Chen, Xin Gao, Xuedong Gao, Hao Fan, Saravan Rajmohan, Qingwei Lin, Dongmei Zhang

Introduction

In modern cloud architectures, the complexity of microservice ecosystems has reached a point where manual troubleshooting is increasingly untenable. A single user request can traverse hundreds or even thousands of interconnected services. When performance degradation occurs—such as a sudden spike in email delivery latency—on-call engineers are tasked with identifying the "needle in a haystack" among a massive volume of trace data.

Current Root Cause Analysis (RCA) tools face two primary hurdles: scale and the distinction between correlation and causation. Large-scale traces often contain significant noise, where healthy components appear in the dependency graph, slowing down analysis. Furthermore, simple correlation-based tools often misidentify root causes because a healthy service may appear slow simply because it is waiting on a downstream dependency. TraceDiag addresses these challenges through a novel two-stage framework that combines Reinforcement Learning (RL) for graph pruning with causal inference for precise diagnosis.

The TraceDiag Framework

TraceDiag operates in two distinct stages: adaptive graph pruning and causal root cause analysis.

1. Adaptive Graph Pruning via Reinforcement Learning

To manage the sheer volume of data, TraceDiag employs a Policy Learner based on Proximal Policy Optimization (PPO). Unlike traditional methods that rely on static, human-defined thresholds (e.g., filtering out any service with less than 10ms latency), TraceDiag learns an optimal pruning strategy dynamically.

The RL agent constructs a "Filtering Tree" of pruning actions. These actions include:

  • Latency-based filters: Removing nodes based on timing thresholds.
  • Anomaly-score filters: Utilizing metrics from TraceArk to identify statistical outliers.
  • Correlation filters: Evaluating the relationship between local service metrics and global request latency.

The agent’s reward function is designed to balance efficiency and accuracy. It is rewarded for minimizing the size of the final pruned graph while ensuring that the actual root cause remains within the set of retained nodes. This approach typically reduces a graph of over 500 nodes down to approximately 11 high-probability candidates.

2. Causal Root Cause Analysis

Once the graph is pruned, TraceDiag applies a CausalRCA method. This stage uses Bayesian models to represent the causal mechanisms of each remaining node. To quantify the contribution of each microservice to the observed anomaly, TraceDiag utilizes Shapley values—a concept derived from cooperative game theory. By calculating the marginal contribution of each service to the system-wide latency, the framework can distinguish between a service that is inherently slow and one that is merely a victim of downstream delays.

Empirical Evaluation

The efficacy of TraceDiag was evaluated using extensive real-world data from the Microsoft Exchange microservice system. The dataset spanned 345 days and covered more than 8,400 microservices across 11 "forests" (large-scale infrastructure clusters).

The study focused on 12 high-impact historical incidents with human-verified root causes. The RL pruning policy was trained on 3 cases and rigorously tested on the remaining 9.

Key Insights and Results

The research yielded several critical insights into the nature of microservice failures:

  • The Necessity of Pruning: Empirical analysis showed that in a trace involving 500+ nodes, typically only about 16 are actually affected by the root cause. This high level of redundancy makes pruning a requirement for both speed and accuracy.
  • Exclusive Latency (ExL): The study highlights that Exclusive Latency—the time a service spends on its own internal logic—is a far more robust indicator of a service's "guilt" than Inclusive Latency, which includes wait times for downstream calls.
  • RL vs. Human Heuristics: The RL-learned policy outperformed human-designed rules. While both methods reduced the graph to a similar size (~11 nodes), the RL policy retained the true root cause in 92.9% of cases, compared to 83.3% for human heuristics.

In terms of performance, TraceDiag demonstrated a 72.3% improvement in PR@Avg (Precision at Average) over state-of-the-art methods like BackTrace and GrootRank. The end-to-end analysis is remarkably efficient, taking approximately 40 seconds from raw trace ingestion to root cause identification.

Production Impact and Limitations

Since its integration into the Microsoft 365 environment, TraceDiag has achieved a precision rate of 82.1% in live production settings. For complex cases that previously required hours of manual investigation, the framework has reduced the diagnosis time by 96.5%.

Despite these successes, some limitations remain. TraceDiag is dependent on the quality of intermediate metrics provided by anomaly detectors like TraceArk. Furthermore, the RL agent requires a "cold start" period involving a few labeled historical incidents to learn an effective policy for a new environment. Future work will focus on improving generalization across different cloud ecosystems and open-telemetry standards.

Conclusion

TraceDiag represents a significant step forward in automated system observability. By combining the adaptive decision-making of Reinforcement Learning with the mathematical rigor of causal inference, it provides a scalable and interpretable solution for the "needle in a haystack" problem in modern microservices.

Summary updated

BibTeX
@inproceedings{ding2023tracediag,
  author = {Ruomeng Ding and Chaoyun Zhang and Lu Wang and Yong Xu and Minghua Ma and Xiaomin Wu and Meng Zhang and Qingjun Chen and Xin Gao and Xuedong Gao and Hao Fan and Saravan Rajmohan and Qingwei Lin and Dongmei Zhang},
  title = {{TraceDiag: Adaptive, Interpretable, and Efficient Root Cause Analysis on Large-Scale Microservice Systems}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2023},
  doi = {10.1145/3611643.3613864},
}
Figure