ACT now: Aggregate Comparison of Traces for Incident Localization

To determine trends in incidents, we studied incident reports of 75+ severe incidents that occurred over three years (June 2017 - May 2020) at eBay. Severe incidents correspond to more than 85% of overall impact. Incident impact is measured in terms of loss of availability. Impact to availability of an incident is the duration of time that all or some fraction of users were unable to use the system i.e. availability of service. We make the following observations:

Component down: Components can fail for various reasons - a recent change made to the component, a dormant bug in a code path not used often - triggered by an increase in load or a change in user options. Component failure by itself is not an incident but the lack of a fallback mechanism or the critical nature of a component failure not being common knowledge can lead to an incident. Incidents corresponding to this category may arise due to component failures or decommissioning components that are in use.

Component A unable to call component B: A component (A) which was previously able to make RPC calls to a different component (B) that it depends on may no longer be able to do so due to link failures, changes in access control lists, firewall rules, and security fixes. This may further result in additional, unexpected component interactions.

Buggy failure recovery: When a component fails to respond within the configured timeout or crashes, the calling component may call a different component or perform a series of actions to recover. Since the recovery path is generally not exercised often, it may not work as expected resulting in overall request failure. In such a case, the fallback is inappropriate or incorrectly set up to recover from the failure. This is an important failure mode as failures in the recovery path continue to be reported [16, 17, 18] despite various efforts to address them.

From these observations, effective localization of incidents that arise from RPC failures between application-level components would produce the most significant reduction in user impact and therefore, we focus on these.

We describe a real incident that occurred at eBay which serves as our running example for the remainder of the section. Fig. 3 depicts the actions taken by SREs. The mitigation steps took SREs close to 3 hours and was dominated by time taken to arrive at the correct mitigating action (2.5 hours).

SREs first observed an increase in errors (a metric) for the Payments Service in one data center and immediately declared an incident. Metrics are used to monitor the overall health of the system. Business metrics such as number of transactions completed, number of canceled transactions and rate of incoming traffic are tracked in real-time since they are related to revenue. SREs attempted to mitigate the incident by restarting the service, but errors increased in all the data centers instead. In this instance, SREs could surmise from the metrics that something was wrong, but not what or why.

To understand what caused the increase in errors, SREs looked at the application logs and noticed that the local cache used for storing access tokens was empty and the service used for minting the tokens (Token Service) was unreachable. SREs found that Payments Service started calling Token Fallback Service instead of Token Service. However, all calls to Token Fallback Service were also failing. Further investigation using the logs revealed that the Token Fallback Service was inaccessible due to incorrect firewall rules. Once the firewall rules were corrected, the error rate returned to normal and Payments Service fully recovered.

The breakthrough in our running example came when one of the SREs observed from the logs that during the incident, requests were attempting to make a call to a service (Token Fallback Service). No such call was present in pre-incident execution traces. SREs had to trawl through logs to find the specific events and event interactions in the unsuccessful executions that contributed to its failure. These events indicated the presence of additional calls that were not present in executions before the incident. In this case, SREs needed to not only understand the absence of calls from the logs but also the presence of additional calls. This illustrates that effectively localizing incidents usually requires both aggregate (the presence of errors) and causal information (Payments Service trying to call Token Fallback Service) - in this instance provided by metrics and logs. SREs had to first determine which executions to consider based on the failure of requests and then compare the events and their relationships between successful and unsuccessful executions. The request path and system model were reconstructed from system logs for this incident. The crucial step in localizing the incident was differencing the request paths before and during the incident to see what was different about the request paths.

Although prior work localizing incidents in data centers [22, 23] is extensive, these are orthogonal to localizing application-level incidents since applications are designed to tolerate network failures such as link failures and packet drops. For example, a service usually has instances in multiple data centers such that if a network link in one data center goes out, requests will be sent to a different instance.

We will briefly describe each of the observability signals - metrics, logs, and traces - and the most relevant approaches that use them as inputs. With our running example as context, we discuss why they don’t effectively localize incidents. We also discuss the constraints of differential reasoning when using traces and how our approach addresses them.

Fa [24] detects and localizes incidents by vectorizing metrics to learn incident signatures. The localization points to the set of metrics (and underlying components) most relevant to the failure. During an incident, multiple metrics are affected and SREs would need to understand relationships amongst different components. Marianil et al. [25] use metrics to learn a baseline model and build out an undirected graph by correlating pairs of metrics. They further use graph centrality measures to identify the most severely affected metrics and thereby, a faulty service. For our example incident, the Payments Service has the most errors, and will most likely be identified as the faulty service. This does not give SREs any actionable insights and is therefore, not useful.

More recent approaches such as Grano [26] and Groot [27] assume that relationships amongst components are available either in the form of system architecture diagrams or global dependency graphs. They build machine learning models to identify the metrics correlated with a given incident which are then overlaid on the dependency graph for incident localization. Such follow-the-errors approaches do not work when multiple incidents co-occur, one or more metrics are not captured or incident localization involves identifying when a call between two components did not occur. Our example incident falls into this last category.

Logs capture a machine centric view of the system and provide additional context, but require sifting through large volumes of data to extract it. Aggarwal et al. [28] model logs from different components as multiple time series and correlate errors emitted by various services to localize the incident given a dependency graph (static topology or architecture diagram). Approaches that reconstruct individual user requests from logs involve control and data flow analysis [29, 30]. Yet others use unique identifiers to identify events corresponding to different requests [31] and custom log parsing to recognize identifiers [32]. Network communication and temporal order are used as heuristics to infer relationship amongst events. Causality inference using log analysis is brittle since it depends on the quality of user logging and is inapplicable either due to practical concerns (running control and data flow analysis for constantly evolving systems like microservices with continuously changing topologies is impractical) or because the timescales for incident localization are very stringent (as systems scale, application logs grow, increasing analysis time).

Distributed tracing provides a request-level view of the system and is used for debugging [33, 34, 35], profiling, and monitoring production applications. It has also been used to address correctness concerns [36], for capacity planning, and workload modeling [37]. Tracing is increasingly being adopted by industry and there is a push for standardization [38, 39, 40] as well. A trace captures events that occur in a given request as well as how they relate to each other i.e causality. The most general representation of a trace is a directed acyclic graph (DAG) where nodes and edges correspond to events and their interactions respectively.

Had traces been available, SREs would been able to compare the trace of a successful execution and that of an unsuccessful execution - which we call pairwise comparison - to determine the events that differentiate the two. Doing so would have highlighted the missing and additional events in executions during the incident and thereby enabled them to take effective action. Fig. 4 demonstrates an idealized result of pairwise comparison for our running example. In the unsuccessful execution, the call from Payments Service to Token Service service is missing, but an attempted call from Payments Service to Token Fallback Service is additional. Since the structure of a trace represents causality of event interactions, we use it to establish cause-and-effect relationships between events in the result - retaining only the causes.

Prior works that uses trace analysis employ a similar differential approach between pairs of traces with appropriate user inputs. For eg., ShiViz [33] and Jaeger [11] both support pairwise comparison of user selected traces. Such tools allow SREs to interactively validate hypotheses but are not suited to automated localization.

Inputs to ACT consist of two sets of traces - traces drawn during the most recent steady-state operation of the system ($t_{before}$) and traces drawn during the incident ($t_{incident}$). These are sampled based on the incident start time specified by SREs. We expect the sampled traces to satisfy two constraints. First, the number of traces sampled in each of the two sets must be large enough that a majority of events or event interactions, if captured in underlying traces, are present in the sampled traces. Many large-scale systems generate millions [43] of traces per day, but a much smaller sample size turns out to be sufficient for localization, as we will see in Section 4.1.

Second, traces are labeled as successful or unsuccessful based on an external success criterion. Examples of external criteria could include credit card charged in case of buying an item, the item displayed correctly when it is added to the product catalog, a HTTP status code of 200, an acknowledgement of data writes, etc. If a trace cannot be assigned a label, it is discarded (based on our data, less than 0.2% of traces).

Outputs from our system should localize the incident under consideration rather than return the entire difference between the set of traces before and during the incident. SREs can investigate along two axes - a) Why are specific calls missing during the incident? and/or b) Why are other calls present only during the incident? Based on what the investigation reveals, an appropriate mitigating action can be applied.

In ACT, we use aggregate information from witnessing a large set of traces and the causality of event interactions within individual requests to localize incidents. Fig. 7 shows the three techniques we use to localize an incident given sets of traces from before and during the incident.

The symmetric difference of $t_{before}$ and $t_{incident}$ is the set of ordered pairs that are in one of $\bigcup_{i=1}^{|t_{before}|}View(Trace_{i})$ or
$\bigcup_{j=1}^{|t_{incident}|}View(Trace_{j})$ but not both. If the changes produced by an incident are represented in $t_{incident}$ and at least one example of the correct interaction is in $t_{before}$, the symmetric difference will contain the site where the mitigation is to be applied. To obtain a precise result, we employ thresholding and reachability.

We use thresholding to answer the question: Which ordered pairs in the symmetric difference are statistically significant and must be retained? Since $t_{before}$ and $t_{incident}$ are randomly sampled, one or more of the sampled traces may correspond to a code path that is rarely exercised. If such traces occur in one or the other set of traces, some ordered pairs will be part of the symmetric difference as a result of sampling randomness. The use of thresholding allows us to discard these. Using a threshold also addresses trace quality issues in individual traces that arise due to the best-effort nature of tracing.

After computing symmetric difference and applying the threshold, the result may still contain some superfluous ordered pairs. To understand how this may occur, assume two ordered pairs (a, b) and (b, c) are in the result. The edges in a trace represent event interactions. For a given trace, let’s further assume that (a, b) and (b, c) correspond to edges ($e_{1},e_{2}$) and ($e_{2},e_{3}$) respectively. Reachability is the transitive closure of the edge relation of a graph. If we find that ($e_{2},e_{3}$) is reachable from ($e_{1},e_{2}$), we can discard the ordered pair (b, c) since its potential cause (a, b) is in the result. By establishing cause-and-effect relationships between edges corresponding to ordered pairs and eliminating the ordered pairs corresponding to effects, we use reachability to whittle down the result set for effective localization. Failure of a database call or third party vendor issues into which SREs have no visibility can be localized to a single leaf node or edge. For these, we expect to see effective localization even without the use of reachability.

The three techniques build on each other - symmetric difference produces the initial result set while thresholding and reachability prune the result set such that the incident is effectively localized.

We now walk through an example of a simulated incident from the eBay dataset which demonstrates how techniques in ACT apply end to end and highlights trade-offs SREs often need to make when an incident produces changes in a small number of traces. We simulate interruption in communication between PaymentService and OrderMgmtService. For users purchasing items, this call is required to validate the purchase. Interruption results in users being unable to place orders. Therefore, we want to highlight the missing call from PaymentService to OrderMgmtService. Assume that the probabilistic guarantee is 0.99 (if a call appears in more traces than the threshold, it is in the sampled traces with 99% probability) and $t_{before}$ and $t_{incident}$ each contain 2K traces.

ACT computes a set of results, the elements of which are ordered pairs. The symmetric difference produces a result set of size 21 but after applying thresholding, the result set is empty. This implies that the sampled traces do not contain evidence of the correct execution, the changes produced by the incident, or both. SREs can now take two actions:

The choice to trade-off time or number of results is situational - for example, if trading off number of results for time produces many false positives, SREs may pivot and sample more traces instead.

We discuss how we use ACT’s probabilistic guarantees to determine the initial sample size from underlying traces and frequency statistics. This serves as an input when sampling $t_{before}$ and $t_{incident}$ for localization.

A structural change to a trace consists of ordered pairs that are missing during an incident which would normally be present in traces during steady state operation or additional calls only occur during an incident. From our discussion of thresholding in Section 3.2.1, we provide a probabilistic guarantee that evidence of the correct interaction as well as structural changes to traces are represented in $t_{before}$ and $t_{incident}$ respectively if they appear in more traces than the threshold.

We can plot a Cumulative Distribution Function (CDF) of the percentage of ordered pairs probabilistically guaranteed to be represented for a given number of sampled traces. Fig. 8 depicts these for our three datasets. From the CDFs, we observe that although a very large number of traces would need to be sampled to identify every possible call (if it were missing), we find that a majority of calls can be identified with a sample that is orders of magnitude smaller. Accordingly, we sample 4K (of 20K) traces for DSB, 8K (of 60K) for HDFS and 20K (of 250K+) for eBay in our experiments.

To conduct a quantitative evaluation of ACT using data from real incidents, we would have needed to collect traces during steady-state operation and then again when incidents occur. Although a large number of incidents occur (anecdotally, three or four every day), we are only interested in those in one of the categories described. Identifying these and capturing traces while they are still retained remains a challenge.

From our incident study and observations of traces generated when we inject faults, we have a good grasp on how we expect the structure of traces to change for each incident category. Therefore, simulating incidents can serve as a good proxy. Simulation not only allows us to apply ACT to a wide range of scenarios but is also useful in testing its limits.

To simulate an incident, we randomly sample two sets of traces which we designate as $t_{before}$ and $t_{incident}$ respectively. For each incident category, Table 1 describes inputs, how traces are mutated and expected output. Some fraction of traces in $t_{incident}$ that satisfy the condition for mutation are mutated to represent traces that would have been generated during the incident being simulated, while traces in $t_{before}$ remain unmodified. All mutated traces represent unsuccessful executions. An unsuccessful execution is one for which we evaluate some external criteria and determine that the user request corresponding to the execution did not succeed. We choose simulations uniformly at random. $t_{before}$ and $t_{incident}$ serve as inputs to the different techniques.

We use three trace datasets in our evaluation. These consist of a production dataset from eBay and two open-source datasets - DeathStar Benchmark (DSB) [10], a micro-services benchmark and Hadoop Distributed File System (HDFS) [9] traces. eBay has about 4500-5000 services, the dataset captures user requests as they purchase items during a week in November 2019. User requests to start a session and complete a purchase account for nearly two thirds of the requests; the remaining third is distributed across twenty other request types that span different system functions. Examples include changing user address and payment modes as well as updating items or item quantities. The captured requests record 250+ unique services and databases and 850+ unique calls. Vertices and edges represent services and calls between services respectively. DSB traces were generated by deploying the benchmark on a single machine and capturing traces of different API types. HDFS traces were generated by deploying HDFS on a 9-node cluster and consists of traces obtained by reading and writing files of various sizes. The DSB and HDFS traces are in X-Trace [44] format and are captured at a lower level of abstraction where vertices represent execution of lines of code and edges represent the execution flow.

In prior work, graph analysis approaches [34, 45] transform graphs into vectors (by counting nodes or edges or converting them into strings) and compare pairs of graphs. The result returned is a pair of $\langle Successful,Unsuccessful\rangle$ traces such that they exercise the same execution path and are separated by the shortest distance. "Shortest" is precisely defined based on the distance metric and the representation used. NodeCount and EdgeCount represent traces as vectors containing the counts of components and calls between components respectively and use $L_{2}$ distance as the distance metric. Spectroscope [34] linearizes traces to produce an event string and uses string edit distance as its distance metric.

Since graph selection is not viable, we have adapted the different techniques to return the best result after comparing all pairs of traces. The inputs are vectors or string representations of traces in $t_{before}$ and $t_{incident}$. For the resultant pair of traces, we compute the symmetric difference of the view of traces and apply reachability. This final step focusses attention on only the relevant results and is not employed in prior work. We take this step to be able to compare the results from the baselines with ACT. A single experiment comparing linearized traces took multiple hours as compared to the few seconds taken by other techniques. Hence, we ran simulations comparing ACT with NodeCount and EdgeCount only.

Additionally, when NodeCount and EdgeCount produce the expected result (in 2.5% to 30% of the scenarios) depending on the technique and dataset, results include false positives. From our experiments, EdgeCount produces false positives in fewer scenarios than NodeCount. Fig. 9 shows the CDF of the number of results produced by NodeCount and EdgeCount.

We have integrated our approach with Jaeger [11] to enable online comparison of sets of traces. Jaeger is an open source, end-to-end distributed tracing tool that enables monitoring and troubleshooting complex distributed systems. It currently provides a feature that allows users to select and compare a pair of traces. The obvious drawback is that users need to know which traces to compare. We have extended the UI to compare sets of traces instead. Rather than requiring users to select traces as input, we accept as input the time since the incident started. This enables us to split the traces into before and after sets. For the purposes of our integration, we use HTTP status codes in the traces to mark them as successful or unsuccessful - a trace with any span returning a non-zero status code is considered unsuccessful. In general, SREs can use any criteria to label traces as successful or unsuccessful. With the two sets of traces and their labels as inputs, we extended Jaeger-UI to implement and visualize ACT.