Design distributed tracing for a microservice fleet

01The design, in the six-step framework

1. Requirements

Functional.

• Every request entering the fleet gets a trace id; each service records a span (start, end, parent, attributes) for the work it did and propagates the context to services it calls.
• Engineers look up a trace by id, or search for traces by service, latency, error and attribute, and see the tree of spans with timings.
• Aggregates per service and endpoint: latency percentiles, error rates, dependency graph, derived from traces.
• Out of scope: logs and metrics as systems of record; profiling.

Non-functional.

• Fleet of 200 services, 2 million requests per second at the edge, averaging 30 spans per request.
• Overhead on the application under 1 percent of CPU and under 1 ms per request.
• A trace is viewable within 30 seconds of completing.
• Retention: sampled traces for 7 days; aggregates for 13 months.

2. Core entities

• Trace: trace_id (128-bit), root service, start, duration, status, sampled_by (head, tail-error, tail-slow).
• Span: span_id, trace_id, parent_span_id, service, operation, start, duration, status, attributes, events.
• Context: trace_id, span_id, sampling flags; carried in request headers between services.
• Service dependency edge: caller, callee, operation, count, latency percentiles per minute.
• Sampling policy: service or endpoint pattern, head rate, tail rules.

3. API

• Propagation: the traceparent request header (W3C) carrying trace id, parent span id and flags; every client library and gateway forwards it.
• Agent → collector: POST /spans batches from the on-host agent every second.
• GET /traces/{trace_id} → the span tree. The lookup every engineer uses first, pasted from a log line.
• GET /traces?service=&op=&min_duration=&status=error&from=&to=&attr=key:value → matching trace summaries, paged.
• GET /services/{name}/stats?from=&to= → percentiles, error rate, top callers and callees.

4. High-level design

One request through the fleet:

1. The edge gateway creates a trace id and decides head sampling (1 percent, in the flags). Every service's SDK starts a span when a request arrives, records attributes, and injects the context into outgoing calls.
2. Spans are written to a local in-memory buffer and flushed by the host agent to a collector in batches; the application never waits on the network.
3. Collectors validate and append spans to the stream, partitioned by trace id, so all spans of one trace reach the same tail sampler.
4. The tail sampler buffers a trace for about 30 seconds after its last span, then keeps it if it was head-sampled, had an error, or exceeded the endpoint's slow threshold; kept traces are written to the trace store and their attributes to the index.
5. Aggregators consume every span (not only sampled ones) and maintain per-minute service statistics and the dependency graph; the UI serves traces by id, searches by attribute, and shows the stats.

5. Deep dives

Which traces do we keep, and why head and tail sampling together?

Head sampling decides at the start, so every service in the trace agrees and the per-request cost is bounded; but it is blind, and the one trace you need (the 2-second request that errored) is 99 percent likely to have been dropped. Tail sampling decides after seeing the whole trace, which is what makes "keep every error and every slow request" possible, at the price of buffering every span for 30 seconds somewhere. The combination is standard: head sample a small uniform fraction for an unbiased view of normal traffic, tail sample the interesting ones, and record which rule kept each trace so that aggregates computed from sampled traces can be corrected for bias. Partitioning the stream by trace id is what makes tail sampling possible at 60 million spans per second: each sampler sees complete traces without any cross-node coordination.

How do service-level statistics stay exact when traces are sampled?

By computing them from all spans before sampling. The aggregators consume the full stream and maintain, per (service, operation, minute), a count, an error count and a latency histogram; that is a streaming aggregation with small state, cheap even at the full rate because it never stores spans. The dependency graph is the same computation keyed by (caller, callee). Only the example traces are sampled; the numbers are not. Candidates who compute percentiles from sampled traces get told their p99 is wrong, because tail sampling keeps slow traces preferentially.

How do we make the timings trustworthy across 200 machines with different clocks?

Spans record wall-clock start times from their own host, and hosts disagree by milliseconds even with NTP. Within one span, duration is measured with a monotonic clock, so each span's length is accurate; only the alignment between parent and child can be off. The UI shows a child that starts before its parent began as a clock-skew artefact, and the processing layer can correct small skews by shifting a child so it fits inside its parent when the overlap is smaller than the measured host offset. Causal ordering comes from parent ids, not timestamps; never sort siblings by wall clock alone. This is the question an interviewer asks to see whether the candidate knows clocks are not synchronised.

How does the overhead stay under 1 percent?

The SDK does three cheap things per span: read the incoming context, record two timestamps and a few attributes into a pre-allocated struct, and push it to a lock-free ring buffer; the flush happens on a background thread. Attributes are capped in count and size; high-cardinality values like full URLs are truncated or hashed. Head sampling keeps the recorded span count low on hosts that do not need everything, but note that tail sampling requires all spans to be sent, which is the real cost: about 300 bytes per span over the host's network, a few megabytes per second on a busy host. If that is too much, a hybrid keeps full spans at a higher head rate for traces already flagged and sends only minimal spans (ids and timings, no attributes) for the rest, enough for tail decisions and stats.

6. What a strong answer sounds like

• Start from spans per second and show that storing everything is a petabyte and a half a day; sampling is forced, so design it deliberately.
• Explain head versus tail sampling, why both, and why partitioning by trace id is the trick that makes tail sampling scale.
• Keep statistics exact by aggregating before sampling.
• Mention clock skew and monotonic durations; it signals real experience.
• Expected follow-ups: propagating context across queues and async work (the context rides in the message); traces that cross organisational boundaries (trust and attribute scrubbing); linking traces to logs by trace id.
• Common mistake: designing a central span database that every service writes to synchronously, which both overloads the store and adds latency to every request.

02Where this question was reported

• interviewkickstart.com · Q15