Efficient Unsupervised Latency Culprit Ranking in Distributed Traces with GNN and Critical Path Analysis

Problem and motivation

Latency-culprit methods for microservices often require labeled anomalies or make assumptions about propagation paths that do not hold across requests. The paper seeks request-level culprit ranking without a labeled training set.

Method and contribution

Historical service-span latency vectors are normalized and grouped by computed critical path. Each critical-path cluster stores service latency distributions. A two-layer GraphSAGE encoder/decoder reconstructs node features on a directed acyclic service-invocation graph; MSE above 0.1 marks an anomalous request. For each candidate service, a sampled latency from its historical distribution replaces the observed value; candidates whose replacement makes the request normal are retained and ranked by distributional deviation. A static graph plus periodic updates and neighborhood sampling is used for efficiency.

Findings and evidence

On FIRM preprocessed traces for social-network, hotel-reservation, media-service, and ticket-booking benchmarks, ACC is 87%, 95.4%, 86.4%, and 96%; Top-1 is 83%, 94.7%, 85%, and 94.3%; Top-3 is 86.2%, 95.4%, 86.4%, and 96%; Top-5 is 87%, 95.4%, 86.4%, and 96%, respectively. The paper reports roughly 3-8% accuracy improvement and training-time reduction to more than one-fifth of a comparable method; the critical-path version reduces test culprit-identification time from 1.5-13 s to 0.8-8.3 s, reported as a 58.33% average improvement.

Limitations and future directions

Limitations: Static service graphs require updates; a computed critical path can overshadow the actual culprit in sparse systems or when the culprit has a narrow latency distribution. The evaluation uses aggregated, preprocessed FIRM data rather than arbitrary raw tracing backends, and the paper does not establish production transfer.

Future work: Broaden experiments, improve detection, handle evolving dependencies, and test larger or more varied service graphs and deployment conditions.

Resources

• Code
• Data

Sources and identifiers

• Published version published
• Public ACM PDF · PDF public_full_text

When to cite this paper

Cite this paper when your work uses or compares an unsupervised GraphSAGE encoder/decoder that detects request-level latency anomalies from service-span vectors.

• an unsupervised GraphSAGE encoder/decoder that detects request-level latency anomalies from service-span vectors.
• critical-path clustering plus service latency distributions as a label-free culprit-ranking strategy.
• the FIRM benchmark ACC/Top-k table or the v1/v2 timing comparison when evaluating efficient distributed-trace culprit localization.
• with the static-graph and preprocessed-data caveat when discussing production generalization.

Citation

@inproceedings{ezzatiJivan2024efficientunsupervised,
  author = {Mahsa Panahandeh and Naser Ezzati-Jivan and Abdelwahab Hamou-Lhadj and James Miller},
  title = {Efficient Unsupervised Latency Culprit Ranking in Distributed Traces with GNN and Critical Path Analysis},
  year = {2024},
  booktitle = {ACM/SPEC International Conference on Performance Engineering (ICPE) Companion},
  pages = {62-66},
  publisher = {ACM},
  doi = {10.1145/3629527.3651841},
  url = {https://doi.org/10.1145/3629527.3651841}
}

Panahandeh, M., Ezzati-Jivan, N., Hamou-Lhadj, A., & Miller, J. (2024). Efficient Unsupervised Latency Culprit Ranking in Distributed Traces with GNN and Critical Path Analysis. In ACM/SPEC International Conference on Performance Engineering (ICPE) Companion (pp. 62-66). https://doi.org/10.1145/3629527.3651841

M. Panahandeh, N. Ezzati-Jivan, A. Hamou-Lhadj, and J. Miller, "Efficient Unsupervised Latency Culprit Ranking in Distributed Traces with GNN and Critical Path Analysis," in ACM/SPEC International Conference on Performance Engineering (ICPE) Companion, pp. 62-66, 2024, doi: 10.1145/3629527.3651841