1. Introduction

X-Trace [1] is a framework for tracing the execution of distributed systems. It provides a logging-like API for the programmer, allowing the recording of events during the execution. X-Trace records the causal relations among these events in a deterministic fashion, across threads, software layers, different machines, and potentially different network layers and administrative domains. X-Trace groups events, which we also call operations, to tasks. These are sets of causally related events with a definite start. Events in a task form a directed acyclic graph (DAG). Each task is given a unique task identifier, and each event within a task is given an identifier which is unique within the task.

X-Trace tracks the causal relation among events by propagating a constant-sized metadata along with the execution, both in messages exchanged by the different components and within the components themselves. The metadata contains the task identifier of the current task, and the last event recorded in the current execution sequence. Each event is reported to a separate reporting infrastructure, and each report records the identifier of the current event, as well as the identifier(s) of the event(s) that caused the current event. The reports contain other information in the form of key/value pairs. The format of these reports is described in the accompanying specification [2].

The X-Trace metadata has two mandatory components, and a set of optional ones, described in their own specifications. The first mandatory component is a Task Identifier, or TaskId, which uniquely identifies a task (in the context of a reporting infrastructure and during a finite window of time). The TaskId is the same across all operations comprising a task, and serves the purpose of identifying all such operations as belonging to the task. The second component is called the Operation Identifier, or OpID, and should be unique for each operation or event within the task. The OpID identifies the operation that generated the metadata, and is used by the subsequent operation(s) to record the causal relationship between the two operations by means of reporting.

There are also optional fields, which may or may not be present, and enhance the functionality of the X-Trace framework. At the time of this writing, there are three types of options defined, but more can be added in the future. They are the Destination option, for specifying where to send reports if not to a default location; the ChainId option, to explicitly indicate concurrent chains of events; and the Severity option, that indicates how important it is to record events related to a particular task.

This document specifies in detail the layout and meaning of the X-Trace Metadata how it is represented in binary and textual form, and how it is propagated in the same and between adjacent layers. It does not discuss reporting in detail, nor how to implement the propagation. It is also beyond the scope of this document how different protocols include X-Trace Metadata associated to their respective protocol data units.

2. X-Trace Metadata Binary Representation

The X-Trace Metadata (XTR-Md) is represented in a compact wire format by the following byte layout. This layout is used when the XTR-Md is encoded in binary protocols, as is the case of the encodings of XTR-Md in IP options and in TCP options. A hexadecimal textual representation of this binary layout is also used when XTR-Md is encoded in text-based protocols, as is the case of HTTP and SIP, for example.

Flags:	1 byte
TaskId:	4, 8, 12, or 20 bytes
OpId:	4 or 8 bytes
Options Block (optional):
OptionsLen:	1 byte
Options:	OptionsLen bytes

The only mandatory fields are flags, TaskId, and OpId. The other fields are optional.

3. X-Trace Metadata Text Representation

For text-based protocols (ASCII, Unicode), like HTTP, SIP, or email, for example, X-Trace Metadata is represented as a the hexadecimal string of the successive bytes in the binary representation. The characters A to F SHOULD be represented in CAPITAL LETTERS, but implementations SHOULD be tolerant to non-capital letters. Each byte MUST be 0-padded and thus represented by two characters each.

4. Propagation

For the propagation of the X-Trace metadata, a node implementation will generate a unique OpId and replace the OpId of the previous operation(s) that happened before the current one. The TaskId MUST remain the same. So that the graph remains connected, every time a new OpId replaces a preceeding one, this binding MUST be registered in a report.

How specific options are propagated will depend on the semantics of each option. How each option is propagated is part of the option's specification. However, if an implementation doesn't know how to propagate a specific option, it MUST copy the option to any new metadata it generates based on the current one.

Figure 1 below shows an example of a simple HTTP transaction through a proxy that propagates X-Trace Metadata across layers and operations of the task. In the figure, (a) represents an OpId, and <T,a> represents metadata with TaskId T and OpId a.

   +--------+                                      +--------+
(a)| HTTP   |           <T,a>                   (b)|  HTTP  |    <T,b>
   | Client | ...................................> | Proxy  | ............>
   +--------+                                      +--------+
       |                                            ^     |
       | <T,a>                               <T,d>  |     |     <T,b>
       \/                                           |     \/  (e)
    +--------+         <T,c>             (d)+--------+   +--------+ <T,e>
 (c)|  TCP   |.............................>|  TCP   |   |  TCP   |........>
    +--------+                              +--------+   +--------+
        |                                       ^           |
        |                                       |           |  <T,e>
        \/  (f)                (g)              |  (h)      \/   (i)
     +--------+  <T,f>   +--------+ <T,g>   +--------+    +--------+ <T,i>
     |  IP    | -------->|  IP    |-------->|  IP    |    |  IP    |------->
     +--------+          +--------+         +--------+    +--------+

                               Figure 1.

5. Author's Address

Citations

Appendix: Change Log

Changes marked with a '*' mean changes that have implementation implications. Otherwise changes just refer to the document (fixes and clarifications). The versioning reflects this: minor numbers will change with at least one '*' change, e.g., from 1.2.x to 1.3.0.

• 2.1.1 - minor changes and fixes

• 2.1.0 - * upgraded the Metadata version to 1, backwards compatible with version 0.

  This update introduces variable length OpId field (4 and 8 bytes).

• 2.0.0 - major revision of the X-Trace metadata format, simplifying the metadata contents and propagation.

• 1.3.1 - added change log. fixed section numbering

• 1.3.0 - ! added a length byte to the destination field

• 1.2.1 - fixed typo in the mask for the task id length of 20 bytes: was 0x0C, should be 0xC0

• 1.2.0

  • ! added invalid XTR id
  • updated the description example to have 4-byte tree info operation ids
  • Added sentence to cover propagation operations on metadata with no tree info.
  • fixed typo and clarified IdLen flags
  • added reference to NSDI paper