The Good, the Bad, and the Differences
Authors:
Open Access
- 22 August 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 115-128
Abstract
In this paper, we propose a new approach to diagnosing problems in complex distributed systems. Our approach is based on the insight that many of the trickiest problems are anomalies. For instance, in a network, problems often affect only a small fraction of the traffic (e.g., perhaps a certain subnet), or they only manifest infrequently. Thus, it is quite common for the operator to have “examples” of both working and non-working traffic readily available – perhaps a packet that was misrouted, and a similar packet that was routed correctly. In this case, the cause of the problem is likely to be wherever the two packets were treated differently by the network. We present the design of a debugger that can leverage this information using a novel concept that we call differential provenance. Differential provenance tracks the causal connections between network states and state changes, just like classical provenance, but it can additionally perform root-cause analysis by reasoning about the differences between two provenance trees. We have built a diagnostic tool that is based on differential provenance, and we have used our tool to debug a number of complex, realistic problems in two scenarios: software-defined networks and MapReduce jobs. Our results show that differential provenance can be maintained at relatively low cost, and that it can deliver very precise diagnostic information; in many cases, it can even identify the precise root cause of the problem.Keywords
Funding Information
- NSF (CNS-1065130)
This publication has 22 references indexed in Scilit:
- Packet-Level Telemetry in Large Datacenter Networks2015
- Distributed time-aware provenanceProceedings of the VLDB Endowment, 2012
- SPADE: Support for Provenance Auditing in Distributed Environments2012
- Secure network provenance2011
- Debugging the data plane with anteater2011
- Declarative networkingCommunications of the ACM, 2009
- Toward an understanding of bug fix patternsEmpirical Software Engineering, 2008
- A survey on tree edit distance and related problemsTheoretical Computer Science, 2005
- The stable paths problem and interdomain routingIEEE/ACM Transactions on Networking, 2002
- Why and Where: A Characterization of Data Provenance2001