Critical Path Guided Decision Making with CALLIGATOR
Authors: Meghna Pancholi (Columbia University); Lee Baugh (OpenAI); Olaf Schnapauff, David Culler (Google); Kostis Kaffes (Columbia University); Yu Gan, Brent Stephens (Google)
Presenter: Haodong Chen (First-year Ph.D. student, SNG)
Introduction
Modern online applications consist of hundreds of microservices, and a single request may trigger many downstream RPCs that execute sequentially, in parallel, or asynchronously. Consequently, the effect of changing one service can propagate through a complex execution graph, making it difficult to determine whether a local optimization will improve end-to-end tail latency. Distributed tracing records parent-child RPC relationships and span timings, but it usually describes what happened rather than answering actionable counterfactual questions such as which component should be optimized or how much a 5 ms speedup would reduce request latency. Manual diagnosis does not scale; machine-learning approaches lack explicit execution semantics and can be brittle under unseen workloads; and code analysis is difficult across multiple languages, libraries, and containerized services. CALLIGATOR addresses this gap by recovering execution dependencies directly from production traces and using them for interpretable performance decisions.
Key idea and contribution
CALLIGATOR compares span interleavings across multiple traces to infer happens-before and asynchronous relationships, then constructs an explicit execution-dependency graph. It models each trace as a structural causal model over span timing variables and traverses the graph backward from request completion to identify the critical path. Unlike methods that rank spans only by duration or parent-child structure, CALLIGATOR distinguishes sequential, parallel, and asynchronous execution, so a long-running span is not automatically treated as a useful optimization target.
The system derives three interpretable metrics. Drag measures a span’s contribution to critical-path length. Exclusive Drag removes time spent waiting for child operations and isolates the span’s own marginal impact on end-to-end latency. Slack measures how much an off-critical-path span can be delayed without increasing request completion time.
CALLIGATOR then performs retiming: it changes a target span’s duration and propagates the resulting timing changes through the dependency constraints to predict the end-to-end effect. This deterministic process requires no learned model and makes each prediction traceable. The system aggregates these metrics for p99-oriented analysis and applies them to optimization prioritization, resource reallocation, request hedging, and production bottleneck diagnosis.
Evaluation
The authors first compare CALLIGATOR’s inferred dependency graphs with execution relationships obtained through manual code inspection. They then speed up the compose-review service by 6 ms and test whether each method can predict the resulting end-to-end latency change. CALLIGATOR tracks the measured outcome more closely because it captures repeated appearances of the same service and their sequential or parallel dependencies; overall, it improves latency-prediction accuracy by 81.7% over the state of the art. The system also tunes hedging policies, identifies true bottlenecks in production Google applications, and reallocates resources using Exclusive Drag together with utilization. On DeathStarBench, it reduces p99 latency by up to 94.7% with the same total resources. This result is significant because it shows that dependency-aware decisions can direct a fixed resource budget toward components that actually affect end-to-end tail latency, rather than toward services that merely look slow or highly utilized.
Q&A
Q1: Why not obtain execution dependencies directly through static or dynamic code analysis?
A1: Microservice deployments commonly combine multiple languages with numerous frameworks, third-party libraries, and container images. Code analysis would require access to application source code and language-specific tooling that also understands the dependency stack, making it expensive and difficult to scale in large production systems. CALLIGATOR therefore infers dependencies from language-agnostic distributed traces that operators already collect.
Q2: How does CALLIGATOR handle nondeterministic latency caused by factors such as co-located resource contention?
A2: The authors collect traces under real workloads and operating conditions that are representative of the target scenario, then apply hypothetical speedups or delays to those observed executions. Contention and latency variation already present in the traces therefore become part of the prediction baseline, and the method does not require identical or noise-free requests. However, the response did not claim a formal robustness guarantee under arbitrary workload shifts. If an intervention changes the dependency structure itself, or if the sampled traces do not represent future conditions, new measurements and validation are still needed.
Q3: If telemetry is missing or delayed, can the inferred dependencies and root-cause conclusions still be trusted?
A3: The authors explained that CALLIGATOR recovers dependencies from timing relationships that recur across many traces, so additional traces increase confidence. Their experiments used roughly a thousand traces, while complete dependency graphs for the benchmark applications could generally be recovered with fewer. The talk did not provide a precise tolerable missing-data rate, confidence interval, or formal guarantee. Severe span loss or insufficient coverage of rare branches can therefore hide dependencies, and conclusions should be interpreted together with telemetry completeness.
Personal thoughts
The paper’s main strength is that it turns distributed tracing from an observability mechanism into a decision tool. Exclusive Drag is especially useful because it separates a service’s own work from time spent waiting for downstream calls, making it more actionable than raw span duration or utilization. Retiming also keeps counterfactual predictions transparent and easy for operators to inspect.
The main limitation is that both dependency inference and counterfactual accuracy depend on trace coverage and on the execution structure remaining stable after an intervention. Rare paths, workload shifts, and missing telemetry may weaken the conclusions. Promising next steps include explicit confidence estimates for inferred edges, active tracing of poorly covered paths, and continuous online calibration of what-if predictions against observed outcomes.
Paper: ACM Digital Library
Code: google/calligator