CS PAPERS DEEP-READ · PAPER 26
Sigelman et al. · Google · Technical Report 2010
In 2010, Google published its internal tool Dapper. When you type a search or click "buy," hundreds or thousands of machines hand off work behind the scenes. Before Dapper, if that one request got slow or went wrong, nobody could say which machine, which step was the culprit. Dapper issues each request a "travel record" for its whole journey, stitching together every service it passed through and how long each stop took. Today every system that talks about "observability" or "distributed tracing" — Zipkin, Jaeger, OpenTelemetry — is built in Dapper's image.
A single request at a big company hasn't been "one server computes and returns" for a long time. You search a word, and the frontend fans it out at once to dozens of backends: one for web pages, one for images, one for ads, one for spelling correction… and each backend asks a whole chain of services beneath it. Spread out layer by layer, one request can touch thousands of machines. Here's the problem: the whole thing was 100 ms slow — who dragged it down? The engineer who owns the frontend can't see inside the backends; the person who owns some backend doesn't know who called them or where in the chain they sit. Everyone holds one small piece of the puzzle, and no single person can see the whole of one request — which is fatal when you're debugging an outage.
Dapper's idea: give every incoming request a unique ID, then make that ID travel with the request the whole way — wherever the request goes, the ID goes too. Each stop notes down "what time I received it, what time I finished, and who called me." Afterward you gather all the records sharing that same ID and reassemble a complete call tree: who called whom, how long each segment took, which branch was slow — all at a glance. Like slapping one unified tracking barcode on a form as it winds through a dozen departments.
Two clever moves make it work. First, engineers barely change their own code: every service at Google uses the same underlying communication libraries, so Dapper put its recording code inside those shared libraries — and every service got traced "for free." Second, don't record everything — sample: the request volume is enormous, so recording each one would slow the system and cost too much to store. Dapper keeps a full record only about once every thousand-plus requests — for high-traffic systems that tiny sample is plenty to see the patterns, at a cost small enough to ignore.
With a full travel record, things that used to be guesswork become directly visible: open the call tree of a slow request and you see whether some downstream service stalled or the network wait was long; want to know "which other services does mine actually depend on?" — aggregate a mass of records and the dependency map draws itself; chasing a bizarre bug across a dozen teams no longer means meeting each team to line up timelines — lay out one trace and it's clear which segment is to blame. It turns "the distributed system is a black box" into "something you can click open, layer by layer."
An honest note: sampling cuts both ways. It's great for massive traffic, but if the very thing you're chasing is a rare failure that shows up once in ten thousand times, that one occurrence probably wasn't sampled and left no record — later tracing systems added a "record everything first, then decide what to keep once something looks off" approach to patch this.
Give every request an ID that travels with it, automatically record each stop and its timing inside the shared communication libraries, and reassemble a call tree afterward — so with no code changes from engineers and near-zero overhead via sampling, you can see exactly which path one request took across thousands of machines and where it got slow. This "trace / span / context-propagation" model became the blueprint for every distributed-tracing and observability system today.
Want the call-tree diagram, the collection pipeline, and the overhead numbers? → switch to the deep read
Dapper is Google's internal distributed-tracing infrastructure: it assigns each request a global trace id that propagates along the call chain, records each unit of work as a span (with parent/child links and timestamps), and reassembles a full call tree afterward. Guided by three design principles — application-level transparency, low overhead, and company-wide scale (achieved by baking instrumentation into shared RPC/threading libraries plus sampled collection), it let engineers see a system spanning thousands of machines from the vantage of a single request for the first time — becoming the blueprint for Zipkin, Jaeger, OpenTelemetry, and the whole "observability" movement.
The authors include Benjamin Sigelman, Luiz André Barroso (a central figure in Google's infrastructure), and Mike Burrows (author of Chubby, Paper 20), published as a Google technical report in 2010. It builds on academic distributed-tracing work — especially X-Trace (2007), Magpie, and Pinpoint, which pioneered propagating request metadata along a call chain — but Dapper was the first to run it in a hyperscale company's production for years and to report the engineering trade-offs honestly. It spawned nearly every open-source tracing system in industry: Twitter's Zipkin, Uber's Jaeger, and the unifying standards OpenTracing / OpenTelemetry.
At Google, an ordinary web search can touch dozens of service types across hundreds or thousands of machines: the frontend fans out the query to backends for web indexing, images, ads, spelling correction, and each backend issues RPCs to services further down. The whole system is a mosaic of services built and deployed independently by many small teams, and no single engineer understands all the pieces.
So when a request is slow or wrong, debugging is a nightmare: the frontend engineer only knows "it took 300 ms total" but can't see inside any backend; a backend owner sees their own slowness but doesn't know which request chain they're on or who called them. Everyone holds one small puzzle piece, and no one can assemble a request's full causal chain. Traditional per-machine logs and performance counters are organized "by machine / by service" — missing exactly the crucial dimension: stitching work across all machines back together "by single request."
Two approaches existed. One is the black-box style: change no code, just statistically correlate services' message logs and infer who called whom — zero-intrusion but inaccurate and data-hungry. The other is annotation-based: explicitly mark traces in code and have the request carry an ID — precise causality, but you must change code. Dapper chose the annotation-based route, then used a trick to all but erase the "change code" cost (below).
Dapper compressed its goals into three hard constraints, and every design choice serves them: ① application-level transparency — engineers shouldn't touch their business code to get traced; ② low overhead — tracing itself must not slow production services, or no one will turn it on; ③ company-wide scale — it must cover thousands of machines and run for years. The hardest two are "transparency" and "low overhead," and they directly dictate the two key techniques below.
Dapper's data model is clean. All the work for one request is a trace, keyed by a globally unique trace id. Each unit of work on that tree (typically one RPC, e.g. "frontend calls the ads service") is a span. Every span records its own span id, the parent span's id, and its trace id — and from "whose parent is whom," the scattered spans reassemble into a call tree.
Inside a span are several annotations: one kind is automatic timestamps — the four standard ones are cs (client send, caller sends the request), sr (server receive, callee receives it), ss (server send, callee returns), cr (client receive, caller gets the result). With these four points Dapper computes network transit time (sr−cs, cr−ss) and server-side processing time (ss−sr), cleanly separating whether a slow segment was the "network" or the "other side doing work." The other kind is application annotations engineers add by hand (e.g. "query hit cache"), pulling app semantics into the trace.
How do engineers get traced without touching business code? Because all of Google shares the same underlying libraries — a unified threading model, async control-flow, and RPC framework. Dapper put its tracing code inside just those shared libraries: create a root span when a request arrives, auto-create a child span on each outgoing RPC and stuff the trace id into the RPC message header for the callee, who receives it and keeps passing it down. Within a machine the trace id flows with the thread via thread-local storage; across machines it hitches a ride on the RPC. Application engineers do nothing and get traced "for free" — that's the whole magic of "application transparency," and also why it blanketed Google in one shot yet is hard to transplant to heterogeneous environments where libraries aren't uniform.
Full tracing has two bills: the runtime cost of creating spans and writing annotations on the request path, and the collection cost of writing, shipping, and storing massive trace data. The latter dominates. Dapper crushes both to negligible with two moves:
One: sampling. Rather than tracing every request, trace with a low probability — production commonly used about 1/1024 (a full record kept once every thousand-plus requests). For high-traffic services that tiny sample already yields a stable latency distribution and call structure, while runtime cost drops to near zero. (In the paper, creating/destroying a span is a hundreds-of-nanoseconds operation; multiply by a one-in-a-thousand sample and the per-request cost is minuscule.)
Two: out-of-band, asynchronous collection. Traced data is not processed on the request's critical path: the application first writes spans to local log files, then a separate Dapper daemon asynchronously, after the fact scoops them up, collectors aggregate them, and one trace lands as a single row in BigTable (each span a column). Because collection happens after the request returns and over a separate channel, it doesn't slow live requests at all; the paper reports this collection consumes a tiny fraction of CPU and well under 1% of network. Engineers then retrieve and visualize traces through a query API (DAPI) and a web UI.
Dapper's most convincing "result" isn't an accuracy number but the fact that it actually ran in Google production and stayed useful for years. The paper reports: tracing covered nearly every system in the company, at enormous data scale; runtime overhead was negligible — a single span's creation and annotation is a hundreds-of-nanoseconds operation, and with sampling it barely dents production latency or throughput; the collection daemon uses minimal CPU and under 1% of network. The query API DAPI and trace visualizations built on top were used daily by many engineers for performance analysis (locating the critical path, finding services that inflate tail latency), inferring service dependencies, and cross-team debugging. Through a series of real usage stories the paper shows that a transparent, sampled, out-of-band tracing system is both viable at hyperscale and genuinely useful.
Dapper defined the standard paradigm for distributed tracing. Its trio of trace / span / context propagation was inherited almost verbatim by nearly every tracing system since: Twitter's open-source Zipkin was built directly on Dapper, as was Uber's Jaeger; then came OpenTracing to unify the vendors, converging into the CNCF's OpenTelemetry standard — the trace ids, spans, and cs/sr/ss/cr-style timestamps you see in any microservice architecture today all descend from this report. More broadly, together with "logs and metrics" it turned observability from a slogan into one of engineering's three pillars — the conceptual foundation of modern cloud-native and microservice operations.
1/1024 is fine for high-traffic services, but to chase a "one in ten thousand" anomaly or a low-traffic service, the crucial trace probably wasn't sampled at all. Dapper later added an "on-demand force-trace this request" mechanism; still-later systems (e.g. tail-based sampling) switched to "record everything first, then decide what to keep once something looks slow or wrong."① In one line: assign each request a global trace id that propagates along the call chain, record each unit of work as a parent/child-linked span, reassemble a call tree, and see a system spanning thousands of machines from a single request's vantage.
② Pain: a request fans out to hundreds or thousands of machines; per-machine logs are organized by machine, and no one can assemble a request's full causal chain — slow or wrong, you can't tell where it stalled.
③ Three principles: application transparency, low overhead, company-wide scale — every design choice serves these.
④ Data model: trace (one request) = a tree of spans; each span carries trace id / span id / parent id + cs/sr/ss/cr timestamps splitting cost into network transit vs server processing.
⑤ Transparency secret: instrument the company-wide shared RPC / threading / control-flow libraries; the trace id propagates automatically via thread-local storage + RPC headers, with zero changes to business code.
⑥ Low-overhead secret: sampling (~1/1024) crushes runtime cost + out-of-band async collection (local logs → daemon → BigTable, one trace per row) stays off the request's critical path.
⑦ Impact: defined the trace/span/context-propagation paradigm, directly spawning Zipkin, Jaeger, OpenTelemetry — the foundation of observability, one of engineering's three pillars.
⑧ Limits: sampling misses rare events; transparency needs homogeneous infra; the causal model favors RPC trees, blurring async/batch; aggregates drown outliers; tracing isn't automatic root-cause diagnosis.