Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

The problem: a slow search, and nobody who could say why

A single Google search in 2010 fanned out from a front end to hundreds of services on thousands of machines: query rewriting, several index shards, spelling, ads, maps, and more, written by many teams in several languages. When a search was slow, every one of those teams could truthfully say their service was fine, because each saw only its own slice. The logs of one machine told you what that machine did, not which request it was doing it for or what else that request had been waiting on.

The authors wanted a view of one request across every process it touched, and they set two constraints that shaped everything: the instrumentation had to be ubiquitous, present in every service without each team opting in, and its overhead had to be low enough to leave on in production, all the time, because the slow requests you care about happen when you are not looking.

The idea: a tree of spans, stitched by an id that travels with the request

Dapper records a request as a trace: a tree of spans, where a span is one unit of work (a server handling an RPC, say) with a start time, an end time, a name, and the id of its parent span. A trace id and the current span id are attached to every RPC as it leaves a process and read back when it arrives, so the tree can be rebuilt later from records written by different machines that never spoke to each other. Any process can attach annotations, timestamped notes or key-value pairs, to its span.

How it works

The span data never travels with the request. Each process writes its spans to a local log file; a daemon on every machine sweeps the files up and stores them in a Bigtable with one row per trace. The paper reports a median delay of under fifteen seconds from a request finishing to its trace being queryable, which was fast enough for debugging and left the serving path untouched.

Overhead was tamed by sampling. Tracing one request in 1,024 cost nothing measurable, and for a high-volume service it still produced thousands of traces a minute, enough to see every common pattern and most rare ones; low-traffic services used adaptive rates so they were not under-sampled. The authors’ point is that you do not need every request to understand the system, you need a representative set, and sampling is what makes “always on” affordable.

The uses they found were broader than debugging. Traces revealed the real dependency graph between services, which no document had kept current. They attributed load on a shared service back to the front ends causing it, which settled arguments about capacity. And they found behaviour nobody had designed: a service that made the same call twice in a request, a cache being bypassed by a path everyone had forgotten.

What it changed

Dapper is the design under nearly every distributed tracing system. Twitter’s Zipkin (2012) and Uber’s Jaeger (2015) reimplemented it in the open; the OpenTracing and OpenCensus projects standardised its API, and merged into OpenTelemetry, which is now the industry’s shared instrumentation layer; the W3C traceparent header is Dapper’s trace context as a web standard. The paper also set the terms of the observability conversation: logs, metrics and traces as three complementary signals, with tracing the one that follows the request.

Where you meet it today

• OpenTelemetry, Jaeger, Zipkin, Tempo, Datadog APM, X-Ray. Spans, trace ids and parent ids, exactly as the paper defined them.
• The traceparent header on an HTTP request, propagating the trace through every hop.
• Sampling decisions. Head-based and tail-based sampling policies are the paper’s cost argument, revisited.
• Service maps. The dependency graph your observability tool draws is derived from traces, as Dapper’s was.