Critical Path Guided Decision Making with CALLIGATOR

Abstract

Modern web applications are typically implemented by many independent microservices. Seeing into such a distributed system and predicting how component changes propagate across the system is essential for informed decision-making. Unfortunately, existing tools provide only partial support for such analysis in microservice systems. Calligator is a toolkit that addresses this limitation by introducing a new approach to analyzing distributed systems that uses critical path analysis to make informed decisions about design, planning, and provisioning. This paper makes two key contributions. (Methodology) Calligator infers explicit execution dependencies from distributed traces and uses them to compute accurate critical paths and key metrics. Pairing this dependency graph with these metrics enables a retiming-based "what-if" predictor and tail-aware (e.g., p99) bottleneck analysis, improving latency prediction accuracy by 81.7% over the state of the art. (Applications) Using these techniques, Calligator tunes hedging policies, identifies true bottlenecks in production applications at Google, and allocates resources where they most reduce end-to-end latency, achieving up to 94.7% lower p99 latency at equal resources for DeathStarBench.