Introduction

In a microservice architecture, interactions between services are complex, often with deeply nested, asynchronous downstream service calls—especially at Uber’s scale. When a request fails at its originating service, it can be difficult to determine which downstream dependencies contributed to the failure. It’s also impractical to assume that ‌service owners can keep track of all the dependencies, especially the indirect dependencies, of their service and their interactions, due to their dynamic and complex nature. The lack of insight into a service’s dependencies and how ‌failures might impact the service are a deterrent to making engineering systems at Uber reliable.

Understanding how failures in dependencies of critical services impact the requests to these services and shape the user experience can help in making high-ROI and focused investments. For example:

• Improve TTD (Time to Detection) by implementing dependency-aware alerting that explicitly models hard dependencies and their impact on critical service endpoints
• Improve TTM by identifying the root cause faster 
• Reduce on-call burden with a few pageable alerts
• Identify high-leverage call path optimization opportunities that yield the greatest return on investment in terms of availability and reliability for core user journeys

Background

Every service API has downstream dependencies. Dependencies for an API are represented as call trees. A dependency (interchangeably called a node) can be a <service, endpoint> tuple or a datastore.

Figure 1: Fail-close and fail-open dependencies. 

A dependency can be called fail-close or as a hard dependency for a caller node, if its failure can consistently cause the caller node to fail. It also means that an error in a fail-close dependency can cause all its ancestors, up to the root node in the call path, to error out. Otherwise, the dependency can be treated as a fail-open or as a soft dependency for the caller node.

Figure 2: Multiple node failures in a distributed trace.

In the example shown in Figure 2: 

• Nodes E and C are a fail-close dependency of root node A
• Node D is a fail-open dependency of root node A
• Nodes B and F are unknown dependencies of root node A, as they don’t have any errors to correlate

The dependency classification of a path can be derived from the classifications of its edges, where an edge links two nodes in the call graph. 

So in the example above, path A->C->E is fail-close because both edges A->C and C->E are fail-close. This means any error at E will cause C to fail, and any error at C will cause A to fail, similarly. Path A->B->D is fail-open because B->D is fail-open. That is, any failure at node D won’t cause node B to fail, stopping the propagation of any error in node D back to node A.

Correlation and Causation

The intuition of this problem lies in the problem definition. A fail-close dependency requires the caller node to fail when the callee node fails, a simple causation. To establish causation, however, we first need to correlate these failures.

When examining the distributed trace for a request, it’s easy to see how failures propagate across the call graph. A node deep in the call chain might return an error that’s sent to its caller node, who then propagates it to its own caller, and so forth until it reaches the root node, which then errors out because of it. This is a clear correlation.

For example, if we observe 10 identical failures, we have clear causation: whenever node E in the call chain A->B->C->D->E fails, the root node A fails too. So, all we need is 10 such failure samples to establish causation. How hard could it be? Turns out, very.

At Uber’s scale, it’s not prudent to sample every request passing through our service mesh. The cost of such large-scale distributed trace processing would be prohibitively high to justify the ROI, especially since over 99.9% of requests are served without errors and within acceptable latency bounds for our customers.

So instead, we sample our distributed traces. But how do we determine, before sampling a user request, whether it’ll error out? While we could tail-sample the request, like if the request fails somewhere then decide to sample it, it isn’t trivial to do so and the infrastructure costs are prohibitive, so we don’t.

Let’s say the distributed sampling rate is 0.01% of requests, and the overall availability of an API is 99.9%. This means that 1 in 10,000 requests is sampled, and 1 in 1,000 requests returns an error. So, the probability of sampling an erroneous request is 1 in 10 million. For an API that serves 500 requests per second, it’d take 5 hours, 33 minutes, and 20 seconds to sample a single failed request.

Each API (or root node) will have hundreds of dependencies, like a call graph with hundreds of nodes as its (grand)children. Assuming each node in the call graph has an equal probability of failure (the same availability).

To observe 10 such failures, we’d need 2 days, 7 hours, 55 minutes, and 31 seconds. This is too slow; someone could have updated the call path multiple times in the meanwhile to achieve different behavior.

We needed something with faster feedback, so we started identifying dependencies through logging.

Observing Every Failure

While distributed tracing offers a visually rich experience, it limits how quickly we can catalog dependencies across our service mesh. What if we could solve it with metrics instead? We’d trade off visibility into individual failures for rapid convergence, but gain it by observing every failure in production. 

Uber uses an on-host proxy, Muttley, to route requests between services. A service (caller) calls this on-host proxy, which in turn calls the downstream service (callee). The on-host proxy is responsible for rerouting and telemetry (emitting success/failure call metrics). The on-host proxy has no context of the incoming endpoint at the caller service; it only knows about the caller service and the callee node (service and procedure).

This means that any effort to correlate failures across caller node (service and endpoint) and callee node (service and endpoint) would be low-fidelity. The caller service could call the callee node (service and endpoint) for 10 of the 11 endpoints it serves. So, any correlation between the caller service and the callee node is an aggregate across the 10 endpoints served by the caller service, not for the single endpoint we’re interested in. At an aggregate level, the callee node may behave differently for the caller service than for the caller node (service and endpoint).

Figure 3: Request execution flow in Uber’s service mesh.

Figure 4: Request routing and telemetry through the Muttley sidecar in Uber’s service mesh.

The yarpc middleware allows inspecting and altering the incoming request to the service and the outgoing request from the service. They also have access to the response returned by the downstream in the outbound middleware, as well as the response returned by the application to its caller in the inbound middleware.

The method signature of the inbound middleware is:

Figure 5: Inbound middleware method signature. 

And the outbound middleware is:

Figure 6: Outbound middleware.

Where the *transport.Request(Ref) struct provides access to all request attributes, such as the caller, procedure, and headers. And the *transport.Response(Ref) struct similarly provides access to all response attributes,  such as status, error, and headers. The Handle(...)(Ref) method of the inbound middleware returns an error that can be used to check if the application intends to return an error to its caller. Similarly, the Call(...)(Ref) method of the outbound middleware returns an error that can be used to check if the callee returned an error to the service.

Both middlewares expect the context.Context object as the first parameter, respecting the golang paradigm. This allows us to connect the otherwise disjointed inbound and outbound middlewares of yarpc in the context of a single request. When the request arrives at our service, we overload the context object in our inbound middleware to assign it a unique ID using an in-memory atomic counter, like ctx = context.WithValue(ctx, "request-id", 1) and then pass this overloaded context into the application. The application does its processing. When it needs to call a downstream service for data, it passes the same context object to the client, which then calls our outbound middleware, where we retrieve the request ID with requestID:= ctx.Value("request-id"), allowing the outbound middleware to precisely link each outbound request to a specific triggering incoming request.

With both middlewares aware of the unique incoming request Identifier, we can, via shared memory between them, backpropagate context. This is the intuition that allows us to correlate outbound failures with inbound failures, and also kill retry storms at Uber.

Figure 7: Correlation of Inbound and outbound failures on application with middlewares using shared memory.

Figure 8: Ingress and egress log representation for a request. 

When a request reaches the service, the Inbound Middleware first intercepts it before any application logic executes. At this stage, the middleware generates a requestID and creates an entry in a shared in-memory store called RequestTracker, using this ID as the key.

The value stored is an IngressLog, initialized with a Service field that captures the current service and the endpoint handling the request. This is represented as a Node object, which stores the service name and procedure (endpoint).

The middleware then injects the generated request ID into the request’s context and forwards the enriched context to the application layer. As the application processes the request, it propagates the same context when making downstream calls.

When a downstream call is initiated, the request passes through the Outbound Middleware. The middleware extracts the request ID from the context, looks up the corresponding IngressLog from RequestTracker, and appends an EgressLog entry. This entry records the downstream service, the target endpoint, and whether the call failed.

By the end of the request life cycle, the IngressLog contains a complete view of the inbound request and all outbound calls made as part of handling it.

Figure 9: Egress request handling and telemetry for recording request errors.

Once the application has done all of the processing by calling its downstreams and executing its logic, it sends a response back to yarpc, which passes through our Inbound middleware. At this point, we know that application processing is complete and that the response and any errors are ready.

Figure 10: Telemetry for correlating all outbound errors to the inbound error. 

The Inbound middleware iterates over the log of each outbound request. It emits a metric that captures details of the service, the endpoint it received the request on, whether it returned an error, the outbound service and endpoint it called, and whether that returned an error. This happens for every request served by this service.

Figure 11: Complete request flow for mapping inbound and outbound failures.

The Probability Model

Finally, we aggregate the metric to figure out whether a particular downstream dependency of a node is fail-close using the following formula:

The probability of an edge being fail closed, Pc , is the ratio of requests in which the callee node N of the edge P failed and the caller node R of the edge failed too, divided by the total number of requests in which the callee node failed, irrespective of whether the caller node failed.

Occurrences of the edge where the callee node of the edge failed, and the caller node failed.

Occurrences of the edge where the callee node of the edge failed, but the caller node succeeded.

A Note About Retries

Our implementation completely ignores retries originating before the outbound middleware. We enforce no retries within the application layer and use another chained outbound middleware that sits after the Dependency Analysis outbound middleware to perform retries. In other words, when the Dependency Analysis middleware sees the status of an outbound request, all retry attempts have already occurred.

Figure 12: Complete request flow with retries.

Conclusion

This initiative helped us catalog dependencies of all critical APIs at Uber, ushering in a wave of reliability initiatives focused on improving the resilience standards of our critical services. For example, this engineering effort successfully indexed most fail-close anomalies across the service mesh, cementing essential regression safety guardrails for Uber's Failover Architecture 2.0 (Table 6). As a result, our services are now better equipped to handle failures and maintain stability during high-traffic periods.

Acknowledgments

Cover Photo Attribution: Generated with ChatGPT by OpenAI; no external images, logos, or third-party assets used.

Stay up to date with the latest from Uber Engineering—follow us on LinkedIn for our newest blog posts and insights.