Abstract
Modern cloud-native applications rely on complex microservice interactions, making end-to-end latency prediction critical for proactive resource scaling. FastPERT addresses the limitations of existing models—which are either too simple to capture dependencies or too computationally heavy for real-time use—by leveraging the structural properties of microservice execution traces. Modeled as PERT networks, these traces allow FastPERT to achieve high accuracy with extreme efficiency, running entirely on standard CPUs.
The Challenge of Microservice Latency Prediction
In cloud-native architectures, a single user request triggers a cascade of internal calls across dozens of microservices. Predicting the total "end-to-end latency" of these chains is essential for maintaining service level agreements (SLAs). However, engineers face a "Goldilocks" problem: simple models like Gradient Boosted Trees (GBTs) often fail to capture complex service dependencies, while accurate Graph Neural Networks (GNNs) require expensive GPU resources and are too slow for real-time production environments. FastPERT aims to bridge this gap by being both accurate and lightweight.
Methodology: Leveraging Structural Inductive Bias
FastPERT bridges the gap between speed and accuracy through a two-stage workflow grounded in the "structural inductive bias" of Directed Acyclic Graphs (DAGs).
1. Trace-PERT Graph Representation
The system first models execution traces as Trace-PERT Graphs. As shown in Figure 2, individual service calls and their dependencies are mapped from a linear trace into a DAG structure that represents the concurrent and sequential nature of the request execution.
2. Node-level Estimation and Path-Averaging
The prediction process involves two main steps:
- Node-level Delay Estimation: FastPERT predicts the delay of each individual task (node) using a shared GBT model. This keeps the model lightweight and efficient.
- Path-Averaging Aggregation: To calculate total latency, FastPERT uses a unique aggregation method. Instead of identifying a single "critical path" (the longest path), which can be sensitive to measurement noise, FastPERT calculates the average latency across all possible paths from the start to the end of the trace.
This averaging acts as a built-in ensemble, making the system robust to noise in individual service measurements. Mathematically, this is achieved using a precomputed reachability matrix, allowing the average to be calculated via a single, fast vector operation rather than an exponential path search.
Experimental Evaluation
FastPERT was evaluated using two massive real-world datasets from Alibaba: Ali-2021 (20 million traces) and Ali-2022 (detailed runtime metrics for 1,084 API calls).
Key Results
- Speed: FastPERT processed 1.5 million traces in under 10 seconds on a standard CPU. In contrast, the state-of-the-art PERT-GNN required over 10 minutes on an Nvidia RTX 3090 GPU. Training time was similarly reduced from 11 hours to just 7 minutes.
- Accuracy: On the Ali-2022 dataset, FastPERT achieved a Mean Absolute Percentage Error (MAPE) of 11.36%, outperforming both PERT-GNN (12.84%) and standard GBTs (17.29%).
Discussion and Insights
The success of FastPERT highlights that complex GNNs may not be necessary when the underlying system rules—such as the DAG structure of microservice traces—are already known. By treating these structures as a "cheat code" or inductive bias, the authors moved the computational workload from GPUs to CPUs without sacrificing performance.
Limitations and Future Work
Currently, FastPERT focuses on predicting average expected latency. Future work aims to address tail latency (e.g., p99 lag), which is critical for high-stakes systems where rare, slow requests can significantly impact user experience. Additionally, the model currently relies on the frequency of observed graph structures to handle cases where the exact trace graph isn't known in advance.
Summary updated