Design a distributed tracing system

A span is one unit of work: a request handled, a database call made. It holds a 128-bit trace ID, shared by the whole tree, a 64-bit span ID, the span ID of its parent, the service, the operation name, a start time, a duration, a status and a few attributes. Cap the attributes at about 32 per span and each value at 256 characters, so no span grows without limit.

Propagation. A service passes the context, which is the trace ID, the parent span ID and a sampled flag, to every service it calls. For HTTP and RPC it goes in a request header, such as the W3C Trace Context header. For a message, it goes in the message's metadata. A consumer starts a new span linked to the producer's span. For a background job, store the context in the job record. In-process, keep it in async-local storage and wrap thread pools so it survives a thread switch. If a service drops the header, the trace splits in two, so put propagation in the shared client and server libraries, not in app code.

Clock skew. Hosts disagree about the time by milliseconds. A child span can seem to start before its parent. Use monotonic clocks for each span's duration, which are reliable, and use the parent-child links, not timestamps, for the structure. To place a child, centre it in the parent's window. If a client span lasts 120 ms and the server span inside it lasts 100 ms, the 20 ms of slack is network time, so start the child 10 ms after the parent starts, whatever its own clock says.

A cheap library. Creating a span costs about 2 microseconds. A service with 3 spans on a request adds 6 microseconds to a 20 ms request, which is 0.03%. Spans go into a bounded ring buffer, flushed every second to an agent on the same host, which compresses and forwards them. If the buffer fills, drop the oldest spans and count the drops. Tracing must never block a request, or fail one because the collector is down.

There are two ways.

• Head sampling. The first service flips a weighted coin, and passes the result in the sampled flag. Every service then keeps or drops its spans to match. It is cheap and needs no buffering. But the choice is made before anyone knows whether the request will fail or run slow. Errors are 1% of requests, or 17.3 million traces a day. A 3% head sample keeps about 518,000 of them, so 97% of the traces you most want are gone.
• Tail sampling. Collect every span, wait until the trace is complete, then decide with full knowledge. Keep all errors, keep slow traces, and keep a small random share.

Tail sampling needs all spans of a trace in one place. So key the stream by trace ID, and give each sampler instance a share of the IDs. The instance holds a map of trace ID to its spans and a first-seen time. After 30 seconds it applies the rules. It keeps the trace if any span has an error status, if the root span lasts more than 1 second, or if a hash of the trace ID falls in 1%. A hash makes the random share consistent: every instance makes the same choice for the same ID.

The memory. At the 800,000 spans a second peak, 30 seconds of spans is 24 million, at 500 bytes is 12 GB. Maps and per-trace data double that to about 24 GB, which is 1.5 GB per instance across 16 instances. The buffer is also why a trace appears in search about 30 seconds late.

Edge cases.

• Late spans. A span can arrive after the decision. Keep each decision for 5 minutes in a small cache and apply it to late arrivals. About 600 kept traces a second over 300 seconds is 180,000 IDs, a few megabytes.
• Giant traces. One trace with 100,000 spans would sit on a single instance. Cap spans per trace at 10,000 and mark the rest as truncated.
• Incidents. A failing service makes every trace an error trace. Give each service a cap on kept error traces a second, and above it keep 10% at random, so a storm cannot flood the store.
• Full buffers. If memory runs out, decide early on the oldest traces from what has arrived.

Service graph. Because the sampler sees every span, it also adds each one to counters per calling service, called service and operation, per minute. The service map then reflects all traffic, not only the 3% kept.

The columns, or entries, are the span IDs, each holding a compressed span. The sampler writes the whole trace in one write after its decision, so a fetch by ID is a single key read of about 10 KB, 20 spans of 500 bytes. The hash prefix spreads rows evenly, and sharding is by trace ID.

Search needs an index. An engineer rarely has the ID. They ask for checkout traces slower than 2 seconds with errors. So the sampler also writes index entries for each kept trace and each service in it. The key is the service, the operation, a 5-minute time bucket and the error flag, and entries sort by duration. The value is the trace ID and its start time. That is about 20 entries a trace. At 600 kept traces a second, that is 12,000 entries a second, at about 60 bytes each 720 KB/s, or 62 GB a day, far smaller than the traces. A search reads a few buckets and returns trace IDs.

Limit what is indexed. Each indexed attribute value multiplies the entries, and a field such as user ID has millions of values. Index a short allowlist: service, operation, status, error flag, duration bucket, region and a few tags a team asks for. Everything else stays in the trace, where it can be read once the trace is found.

Retention tiers. Keep kept traces and their index entries 7 days in the fast store, 3.6 TB. After that keep only the error traces, one third of the kept volume, in object storage as compressed files grouped by day. That is 173 GB a day for 23 days, about 4.0 TB. Cold traces are fetched by ID, usually from a log link, and a cold search scans a day's files and takes minutes.

Linking. Log lines carry the trace ID, so a log search can jump to the trace. Metric histograms keep one example trace ID per bucket, so a click on a latency spike lands on a slow trace.

Assembling the tree. The API groups spans by parent ID and links each child to its parent. A span whose parent never arrived is shown as an orphan under the root, not dropped. The critical path, the chain that set the total time, follows the child that finishes last at each level.