Papers
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure
Benjamin H. Sigelman, Luiz André Barroso, Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, Chandan Shanbhag · Google Technical Report, 2010
The problem: one request, hundreds of services, zero visibility
At Google in the late 2000s, a single user request (for example, a search) could traverse dozens or hundreds of different services, written by different teams, running on thousands of machines spread across several datacenters. Each individual service had its own logs and metrics, but no one could answer a simple question: why did THIS specific request take 2 seconds, and in which of the intermediate services was the time spent? Looking at metrics aggregated per service did not reveal problems that only appeared in specific combinations of calls, and manually correlating logs across teams was infeasible in continuous production, where the system's topology is constantly changing. What was missing was a way to reconstruct, after the fact, the complete path a request took through the distributed system — who called whom, in what order, and how much time each step consumed. This is the gap that the Dapper paper describes as its central motivation: earlier systems such as Pinpoint, Magpie, and X-Trace had already explored similar ideas, but Google's challenge was to make this work transparently and cheaply at the scale of the entire production infrastructure, without requiring each development team to manually instrument its own code.
The core idea: trace trees, spans, and automatic context propagation
Dapper represents the path of a request as a causality tree called a trace, identified by a unique ID. Each node of this tree is a span: a unit of work with a human-readable name, its own identifier and the identifier of its parent span, so that the edges between spans reconstruct who called whom. A span records the time interval in which that work took place (for example, a specific RPC call) and can carry additional annotations that the application voluntarily inserts with business information. The crucial part of the design is how this context — which trace and which parent span a given piece of code belongs to — is propagated without the developer having to do anything: Dapper instruments a small number of common libraries (the RPC layer, threading, flow control) used by practically every Google service, and it is this shared instrumentation that carries the trace context across threads, asynchronous callbacks and network calls. As a result, most of a trace's tree is assembled automatically; manual annotations are an optional complement, not a requirement. The paper reports that most spans and the vast majority of collected traces contained at least one application-specific annotation, showing that teams used this voluntary mechanism when useful, even without being required to.
The central trade-off: aggressive sampling in exchange for very low overhead
Tracing every request in detail would have a CPU, memory and network cost too high to run continuously across all of Google's fleet — and one of the paper's three explicit design goals was precisely low overhead, alongside application-level transparency and ubiquitous deployment at very large scale. The solution was to sample: instead of recording every trace, Dapper decides, early in the request lifecycle, whether that entire trace will be kept or discarded, and this decision applies to the whole tree, not span by span, preserving the coherence of the sample. The first versions used a fixed rate (a small, constant fraction of requests); later versions moved to an adaptive scheme, parameterized by a desired rate of sampled traces per unit of time rather than a uniform probability, which avoids oversampling very high-traffic services and undersampling low-traffic ones. The paper's central argument for justifying this deliberate loss of completeness is that, in systems at Google's scale, a problematic execution pattern that occurs once tends to occur thousands of times — so it is not necessary to capture every occurrence to detect the problem. In return, Dapper guarantees writing to disk asynchronously and in batches, and the paper itself reports very low CPU and network bandwidth consumption even in the worst cases measured in production.
Legacy: the common ancestor of today's distributed tracers
Dapper was an internal Google technical report published in 2010, describing a system that had already been running in production for more than two years, and not a product open to the public — but its ideas spread quickly through the industry. A few years after its publication, Twitter released Zipkin as an open-source distributed tracer explicitly inspired by Dapper's model of traces and spans, and later Uber released Jaeger following the same conceptual lineage. These two systems, in turn, influenced the standardization effort that resulted first in OpenTracing and, later, in the merger that gave rise to OpenTelemetry, today a widely adopted standard for observability instrumentation in cloud systems. The vocabulary that practically every tracing tool uses today — trace ID, span, parent span, child span, annotations/tags, context propagation between services — comes directly from the model proposed by Dapper. Even the design decision to sample traces instead of capturing everything, originally motivated by Google's scale, became standard practice in modern tracing systems that handle high traffic volumes, although more sophisticated sampling strategies exist today than those described in the original article.
See the ideas at work
Practice the designs that use this paper in the System Design school.