X-Trace: A Pervasive Network Tracing Framework

This paper shows how a minimal amount of extra data in protocol messages can be used to trace execution of distributed systems and deterministically infer causality between events. The basic idea of X-Trace is that each event logged will include the ID of its parent, which is passed as a header in protocol messages. This allows both extending the tracing into systems that originally didn't have it or are owned by different administrative domains, and going down into lower layers of the networking stack. One nice aspect of X-Trace is that once the events are logged, they can be collected any time after the fact, or even sampled for traces that are particularly interesting; thus X-Trace can be used by mutually untrusted parties to debug problems without revealing all of their internal network events to eachother. Another nice thing is that log events don't have to be sent over the network, only small event IDs. Thus log events can contain many key-value pairs of interesting information, while event IDs are just a few bytes of overhead.

X-Trace has actually changed since this paper was written to produce a DAG rather than a tree. This makes it easier to understand what is going on in the trace by placing edges "up" from lower layers into higher ones.

The paper is also very good at listing the limitations of X-Trace, which is something we don't often see in papers. The main limitation is that X-Trace requires modifications to the application. It would be nice if some kind of program analysis could add these automatically! In practice, modifying just RPC and threading libraries may also be beneficial, especially in more limited programming languages such as Erlang.