Google Dapper: distributed tracing

01 · CONTEXT AND REQUIREMENTS

Why look inside a request

The technical report presents Dapper as the distributed-systems tracing infrastructure in production at Google. Understanding system behavior in that context requires observing related activities across many programs and machines.

The authors' example is a web search: a front end may distribute the query to many hundreds of query servers, each with its own part of the index. Someone looking only at total latency may know there is a problem, but cannot guess which service is the culprit or why it misbehaves.

Two fundamental requirements come out of this situation, ubiquitous deployment and continuous monitoring, and three design goals: low performance overhead, transparency to application code, and scalability.

02 · DATA MODEL

Tree, spans, and annotations

Dapper thinks of a trace as a tree of nested RPCs and models it with trees, spans, and annotations. The nodes of the tree are the spans, the basic units of work; each span has a human-readable name, an id, and a parent id, and a span created without a parent is a root span.

All spans of a given trace share a common trace id, and the ids serve to reconstruct the causal relationships among the spans of a distributed trace.

1. In the paper's example, the user request, the initiator, arrives at front end A.

2. The front end sends RPCs to servers B and C.

3. B can respond immediately, but C needs work from backends D and E before responding to A.

4. In a typical trace there is one span per RPC, and each additional layer of infrastructure adds a level of depth to the tree.

The authors describe two classes of solution for associating message records with an originating request. The table summarizes the contrast.

In Google's environment, since all applications use the same threading, control-flow, and RPC model, it was possible to restrict instrumentation to a few common libraries and get monitoring that is effectively transparent to developers.

03 · INSTRUMENTATION

Transparency in a few libraries

Dapper follows distributed control paths with almost no intervention from developers, because it relies almost only on instrumenting a few common libraries. A thread handling a traced path stores the trace context in thread-local storage, and callbacks store the context of whoever created them, so the ids follow asynchronous paths.

Almost all inter-process communication goes through a single RPC framework, and span and trace ids travel from client to server in traced RPCs.

Anyone who wants can enrich the trace with timestamped annotations, through a simple API. Each span has a configurable upper bound on annotation volume, and application annotations do not displace the span's structural or RPC information.

04 · COLLECTION

From the local log to the repository

Collection is a three-stage pipeline. First, span data is written to local log files; then Dapper daemons and the collection infrastructure pull it from the production hosts and, finally, write it to one of the regional Bigtable repositories. A trace takes up one row of the table, with one column per span.

1. Instrumented processes write span data to local log files.

2. Dapper daemons pull this data from the production hosts.

3. The collection infrastructure writes the data to one of the regional Bigtable repositories.

4. Analysis tools read the traces through the Depot API, which gives direct access to the regional repositories.

5. In real-time data mode, the interface talks directly to the daemons on each machine and the data is available within seconds.

The median latency for data to get from the instrumented binaries to the central repository is under 15 seconds.

Collection is done out of band, separate from the request tree. The authors give two reasons: sending trace data back in RPC response headers can affect the application's network dynamics, and in-band schemes assume all RPCs are perfectly nested.

Most usage happens in the interactive web interface. Those who consume traces programmatically use the Depot API, which offers access by trace id, bulk access with MapReduce, and indexed access. The index ended up composed of service name, machine, and timestamp, in that order.

05 · SAMPLING

How much to trace without getting in the way

The authors consider sampling necessary to keep the cost low. According to them, a sample of just one in thousands of requests gives enough information for many common uses of tracing data.

In the search cluster used as an example, trace sampling was necessary to avoid noticeable latency degradation. The latency and throughput penalties at rates below 1/16 were within experimental error, and there was still adequate data for high-volume services at rates as low as 1/1024.

The collection daemon, in a load test described as unrealistically heavy, never uses more than 0.3% of one core of a production machine.

1. The first sampling happens in the instrumented processes, to limit the cost inside the applications.

2. At collection there is a second sampling: the hash of the trace id decides whether collection keeps or discards the whole trace.

3. A single configuration parameter adjusts the global write rate to the repository.

The second sampling exists because the team also needs to control the total volume written to the central repositories, and because it is not feasible to quickly adjust the sampling configuration in all deployed binaries.

In high-volume services, a notable execution pattern that appears once will appear thousands of times. Lower-volume services can trace every request, and this motivated adaptive sampling, which also records the sampling probability used alongside the trace.

06 · LESSONS AND LIMITS

What Dapper became

Dapper started as a self-contained tracing tool and evolved into a monitoring platform, which enabled tools its designers had not foreseen. It does not aim to replace the other tools: system-wide data usually focuses the investigation so that other tools can be applied locally.

Tracing was off by default at first, until there was confidence in its stability and low cost. The changes in which service owners turned it off were reverted after measuring the real overhead, which was immaterial.

The authors also note that transparency is easier to achieve because the deployment environment has a certain degree of homogeneity.