System Design Interview: How Would You Design a Distributed Tracing Platform?

Prompt and Scope

Design a multi-tenant distributed tracing platform used by backend and reliability teams to follow one request or asynchronous workflow across services. The interview assumptions are 500,000 new root workflows per second, 15 spans per workflow on average, and 700 bytes per encoded span before storage compression. A kept trace must become searchable within 30 seconds at p99. Exact lookup by tenant and trace ID must finish within 2 seconds at p99; common searches by service, operation, error, duration, and time window should finish within 3 seconds at p95. Instrumentation must not synchronously wait for the central platform, and losing one availability zone must not stop applications from emitting telemetry.

The platform creates or receives spans, propagates W3C trace context over supported transports, assembles spans that arrive late or out of order, samples whole traces under explicit budgets, stores trace detail, and supports a dependency graph derived from kept traces. Building every language SDK, a complete APM UI, log storage, metric storage, and anomaly detection are outside scope. Logs and metrics may carry trace IDs or exemplars, but they remain separate systems.

Three independent 2026 interview-preparation pages present distributed tracing as a system-design exercise covering spans, context propagation, trace assembly, sampling, and query storage. That establishes current representativeness without proving any company attribution, so the article makes none. The technical model comes from the W3C Trace Context recommendation, the OpenTelemetry specification and Collector implementation, and Google's Dapper paper.

What the Interviewer Is Evaluating

The first signal is whether the candidate preserves causality across process boundaries. A trace_id is not enough. Each operation needs a span_id, parent relation or explicit links, timing, status, resource identity, and carefully bounded attributes. The W3C format defines interoperable traceparent and optional vendor state in tracestate; it does not make an untrusted incoming trace ID an authorization credential. A strong answer validates incoming context, separates tenants at ingestion, and defines behavior at trust boundaries.

The second signal is an honest sampling model. Head sampling decides before the whole trace is known and can reduce SDK, network, and ingest work. It cannot promise to retain every later error. Tail sampling can select a trace after seeing most spans, but it must first receive and hold those spans. It reduces downstream storage, not upstream collection cost. If a 2% head sampler already dropped a trace, no later tail sampler can recover its error spans.

The third signal is trace assembly rather than a generic event pipeline. Spans are duplicated, delayed, and unordered; asynchronous fan-out or batch work can form a directed acyclic graph rather than a neat tree. A tail sampler needs all spans for one trace routed to the same decision owner, a bounded completion rule, memory protection, and explicit late-span behavior. This stateful boundary decides whether the design produces useful evidence or silent sampling bias.

The final signal is operability. A good answer quantifies raw and kept volume, limits arbitrary attribute indexes, isolates noisy tenants, measures missing propagation and dropped spans, and keeps the telemetry path from becoming an application dependency. A diagram ending at “write spans to a database” leaves the cost, correctness, and failure questions unanswered.

Questions to Clarify Before Answering

• Which workflows require tail decisions? Full tail sampling requires central receipt of all candidate

spans. This design uses source head sampling for ordinary traffic and sends a controlled set of critical routes at 100% to a tail pool. If every route needs error-aware retention, the entire raw stream must fit the central network and state budget.

• What does “complete trace” mean? There is no universal end marker across queues and detached work.

For synchronous requests, a finished root span plus a grace interval is useful. Long-running workflows need a longer policy or explicit workflow completion. The platform must still publish an incomplete flag instead of claiming certainty.

• Which searches are contractual? Exact trace-ID lookup and bounded filters over service, operation,

status, duration bucket, and time are in scope. Arbitrary full-text predicates over every attribute would multiply index cost and create high-cardinality abuse, so non-allowlisted attributes remain available only after a trace is fetched.

• How long is data retained? The assumed policy is seven days of indexed hot data and another 23 days

of compressed object data. Longer hot retention changes storage and index sizing; legal deletion rules also determine whether object keys and encryption domains must be tenant-specific.

• Are cross-tenant traces allowed? The default is no. Gateways bind authenticated credentials to a

tenant and overwrite any tenant field supplied in a span. Approved cross-domain workflows use explicit links or separately authorized correlation, never a client-selected tenant identifier.

• How should asynchronous causality be represented? A single parent works for one causal predecessor.

Batch consumers and fan-in can depend on multiple producers, so they need span links. Forcing one parent loses information; copying one span under multiple parents corrupts trace accounting.

• What may the application lose during overload? Business traffic must continue. A bounded local queue

may drop telemetry after exhausting memory and disk budgets, but the loss is counted by service, tenant, reason, and sampling class. If zero telemetry loss is required, tracing becomes a business-path dependency and the availability contract must change.

30-Second Answer Framework

“I would separate context propagation, collection, trace decisions, and query storage. Instrumented libraries create spans and propagate validated W3C context. A local agent batches them asynchronously and uses a bounded spool, so the central platform never blocks the request path. Regional gateways authenticate the tenant, enforce schema and quotas, and append spans to a durable stream partitioned by trace ID.

“Ordinary routes use consistent head sampling to reduce upstream cost. Critical routes enter a full tail pool; all spans for one trace reach one assembler, which waits for the root plus a grace window, applies error, latency, and baseline budgets, and records whether the trace is incomplete. Kept traces go to an object store for canonical detail and to an allowlisted hot index for trace-ID and bounded filters. I would size both the pre-sampling state and kept storage, degrade by dropping low-priority normal traces first, and verify propagation, late spans, biased sampling, tenant isolation, and zone recovery with canary traces.”

Step-by-Step Deep Dive

Step 1: Define the span contract and query API.

A span record contains at least:

Span {
  tenant_id, trace_id, span_id, parent_span_id?, links[],
  service, operation, kind, start_time, end_time, status,
  resource_attributes, span_attributes, events[],
  observed_at, schema_version, trace_flags, tracestate?
}

The gateway derives tenant_id from authentication. It validates identifier lengths and formats, rejects oversized records, normalizes approved semantic fields, and limits attribute count, value length, event count, link count, and total bytes. It stores both event time and observed_at: service clocks help render a timeline, while collector time exposes delay and clock-skew problems. SDKs should measure a local span's duration with a monotonic clock even though cross-host ordering still needs wall time and causal edges.

The main query contracts are:

GetTrace(tenant_id, trace_id)
SearchTraces(tenant_id, start, end, service?, operation?, status?,
             min_duration?, max_duration?, cursor?, limit?)

GetTrace returns spans, links, the sampling policy and version, firstobservedat, lastobservedat, and completeness warnings. SearchTraces requires a bounded time range and returns a cursor rather than an unbounded offset. Detail retrieval and secondary search are different access paths; one wide trace record should not be duplicated into every secondary index.

Step 2: Propagate context without turning it into trust.

For HTTP, the SDK extracts and injects W3C traceparent, carrying version, trace ID, parent ID, and flags; tracestate carries optional vendor-specific state. Message producers put the same propagation fields in message metadata. Receivers validate the format before joining the trace. Invalid context starts a new trace and increments a propagation error counter rather than poisoning an existing key space.

At an Internet-facing or cross-tenant boundary, the service can deliberately start a new trace and attach a link to an approved upstream context. This preserves correlation without letting an external caller choose an internal parent or sampling control. Baggage is a separate propagated key-value mechanism. It must be allowlisted, size-bounded, and stripped of secrets or personal data because it fans out to every downstream hop.

Auto-instrument common HTTP, RPC, database, and queue libraries first. Dapper demonstrated why common library instrumentation improves coverage with lower application effort. Custom spans remain useful for business boundaries, but the platform measures services and routes that lack expected server or client spans. Trace quality is only as complete as instrumentation and retained samples.

Step 3: Keep collection off the application request path.

Finished spans enter an in-process bounded buffer and are flushed in compressed batches to a node agent or sidecar. The agent has a bounded disk spool for brief collector outages, exponential retry with jitter, and per-priority queues. It never waits synchronously for a central acknowledgement before the application can finish its response. Once the local budget is exhausted, it drops low-priority normal telemetry first and exports counters describing exactly what was lost.

Regional stateless gateways authenticate the agent, bind the tenant, enforce byte and span quotas, validate schema, and append accepted batches to a replicated durable stream. Acknowledgement means the regional stream has durably accepted the batch, not that search already contains it. Consumers are idempotent by (tenantid, traceid, span_id) plus a record version; duplicate delivery updates observation metadata but does not duplicate a span.

The stream partitions by a stable hash of (tenantid, traceid). That gives one trace an ordered decision owner without requiring global span order. For tail sampling at larger scale, a first collector layer can load-balance by trace ID into a second stateful layer. The OpenTelemetry Collector documents the same invariant: all spans for one trace must reach the same tail-sampling instance.

Step 4: Make every capacity boundary recomputable.

Before sampling, the workload generates:

500,000 workflows/s × 15 spans/workflow = 7,500,000 spans/s
7,500,000 spans/s × 700 bytes/span = 5.25 GB/s
5.25 GB/s × 86,400 s = 453.6 TB/day raw

These are workload assumptions, not measured compression claims. A platform that sends all raw spans to a central tail sampler must provision the 5.25 GB/s ingest path before accounting for replication, protocol overhead, retries, skew, and failover headroom.

Assume ordinary routes produce 90% of spans and use 2% consistent head sampling. Critical routes produce 10% and enter the tail pool at 100%:

ordinary: 7.5M × 90% × 2% = 135,000 spans/s
tail pool input: 7.5M × 10% = 750,000 spans/s
collector input: 885,000 spans/s × 700 bytes = 619.5 MB/s

If the tail policy retains 10% of its candidate spans on average, hot storage receives 135,000 + 75,000 = 210,000 spans/s, or 147 MB/s and 12.7008 TB/day before compression, replication, indexes, and object metadata. Seven raw-equivalent hot days are 88.9056 TB. Benchmarks with production attribute distributions determine compression and node count; the arithmetic only establishes the lower bound and shows which sampling boundary pays which cost.

Step 5: Treat tail sampling as the decisive stateful bottleneck.

The assembler stores partial state keyed by tenant and trace ID: unique spans, earliest start, latest end, root-finished state, error state, current duration, byte count, and last arrival. A synchronous trace becomes eligible for decision after its root ends and a grace interval passes. It is also forced to decision at a maximum age, span count, or byte count. Long workflows use a separate policy; otherwise one trace can pin memory indefinitely.

The decision order reserves capacity for explicit critical flows, errors, and high-latency traces, then uses a consistent probabilistic baseline within per-service and per-tenant budgets. A global “keep every error” rule is not a bounded policy during an incident, when errors may approach 100%. Token buckets and hard byte ceilings cap each class; the response to exhaustion is a visible degraded policy, not an out-of- memory crash.

The sampler records a decision cache for late spans. A late span for a kept trace is appended and marks the trace updated. A late span for a dropped trace is discarded consistently. A span arriving after the cache expires is counted as orphaned; it must not create a misleading one-span trace. Every stored trace carries complete, decision_reason, and late-span counters. Increasing the grace interval improves completeness but increases memory, decision latency, and the number of traces exposed to a sampler failure.

The critical trap is a hybrid pipeline. Tail logic can choose only among traces that reached it. If a 2% head sampler discarded a normal trace before an error occurred downstream, the tail stage cannot recover it. Therefore, routes requiring guaranteed error-aware decisions must enter the tail pool without an upstream dropping decision, or use a separate trigger and accept that it will not reconstruct the past.

Step 6: Store canonical detail separately from bounded indexes.

Kept spans are compacted into immutable, compressed objects partitioned by tenant and time, with a manifest for each trace revision. The trace-ID directory maps (tenantid, traceid) to object locations and the latest revision. This path serves exact lookup. Recent trace objects may be cached, but the object layer is the rebuild source for derived indexes.

The hot search index stores one summary row per trace: tenant, trace ID, root service and operation, start bucket, duration, status, selected service set or fingerprints, sampling reason, completeness, and object pointer. Only allowlisted fields receive secondary indexes. Arbitrary user IDs, SQL text, URLs, and baggage values remain in protected detail or are redacted; indexing them by default creates unbounded cardinality, privacy exposure, and write amplification.

Service dependency and latency views are streaming aggregates over kept traces and must be labeled as sampled estimates. Sampling weights can support some unbiased count estimates when the probability is known, but error- and latency-biased tail samples do not automatically represent traffic proportions. Metrics remain the source for exact fleet-level rates; traces explain individual causal paths.

Step 7: Isolate tenants and define failure behavior.

Gateways enforce per-tenant bytes per second, spans per second, concurrent partial traces, query concurrency, and retained bytes. Partition keys include tenant identity, encryption policies can separate regulated tenants, and query authorization is checked before any index lookup. One tenant with a huge trace or a high-cardinality attribute must not evict another tenant's sampler state.

If a gateway or availability zone fails, agents retry another regional endpoint and use their bounded spool. If the durable stream is slow, admission control lowers ordinary sampling and rejects excess bytes before stateful assembly. If an assembler dies, the stream replays its partition; checkpoints speed recovery, while idempotent span keys absorb duplicates. During an index outage, canonical objects continue to land and an index backlog grows. Exact recently written queries may report “accepted, indexing” instead of returning a false not-found.

If the tail pool is overloaded, progressively reduce the probabilistic baseline, cap large traces, and then fall back to a deterministic head policy for affected routes. Preserve control-plane canary traces and some bounded error capacity. Monitor accepted, dropped, retried, too-early-evicted, late, orphaned, and indexed spans by tenant, service, zone, and policy.

Step 8: Verify truthfulness, not just throughput.

Propagation tests cover valid, missing, malformed, and future-version headers; cross-tenant and Internet boundaries; baggage limits; queues; retries; fan-out; fan-in; and batch links. Assembly tests inject duplicate, out-of-order, missing-parent, late, oversized, and never-finishing traces. Sampling tests prove whole-trace consistency, budget ceilings, deterministic probability decisions, error and latency policies, and the fact that upstream head drops remain unrecoverable.

Load tests preserve production-shaped trace sizes and tenant skew. They measure SDK overhead, agent loss, gateway admission, stream lag, active trace memory, decision latency, kept bytes, index lag, trace lookup, and filtered search. Fault tests remove a zone, restart an assembler during a hot partition, pause object storage, exhaust a tenant quota, and rebuild the hot index from canonical objects.

Continuously emit synthetic canary workflows with a known graph through every region. Alert if expected spans disappear, parentage changes, search freshness breaches 30 seconds, or trace-ID lookup breaches its SLO. A healthy collector process does not prove that traces are complete or searchable.

Strong Sample Answer

“I would first state that a trace is a causal graph of spans, not a bag of log lines. Each span has a tenant- bound trace ID, span ID, parent or links, timing, status, resource, bounded attributes, events, and observed time. Services propagate validated W3C context over HTTP or message metadata. At an untrusted boundary I would start a new internal trace and link it, because trace context is correlation data, not authorization.

“Spans leave the request path through a bounded in-process buffer and local agent. The agent batches, compresses, briefly spools to disk, and drops measured low-priority data rather than blocking business traffic. Regional gateways authenticate tenants, enforce schema and quotas, and write to a replicated stream. Partitioning by tenant and trace ID sends every trace to one assembler and makes retries idempotent by span ID.

“The raw workload is 7.5 million spans per second and 5.25 GB/s. I would not send all of that to a tail sampler by accident. Ordinary routes use 2% consistent head sampling. The controlled 10% critical-route pool enters tail sampling at 100%, so collector input is 885,000 spans/s, or 619.5 MB/s. If the tail pool keeps 10%, storage gets 210,000 spans/s, about 12.7 TB/day raw before indexes and replicas. Those boundaries are benchmark inputs, not promised compression results.

“The assembler is the hard part. It holds partial traces, waits for a finished root plus a grace window, and forces decisions at age, span, and byte limits. It reserves bounded capacity for critical, error, and slow traces, then fills per-service budgets with a consistent baseline. It caches decisions for late spans and labels incomplete traces. A 2% upstream head drop cannot be recovered later, so any route that truly needs error-aware retention must enter the tail pool unsampled.

“Kept trace detail goes to compressed object storage with a trace-ID directory. A separate hot index stores one trace summary and only allowlisted service, operation, status, duration, and time fields. That controls cardinality and lets the index be rebuilt. During failures, agents use bounded spools, stream partitions replay, object writes continue if search is down, and overload sheds the normal baseline before protected classes. I would verify context boundaries, duplicate and late spans, sampling bias and ceilings, noisy- tenant isolation, zone loss, rebuilds, and end-to-end canary traces.”

Common Mistakes

• Say “sample 2%, then keep every error in the tail” → the first stage already erased 98% of candidate

traces, including later errors → send protected routes unsampled to the tail pool or weaken the guarantee.

• Hash spans across collectors without the trace ID → one tail sampler sees only fragments and makes a

biased decision → route every span for (tenant, trace_id) to the same decision owner.

• Wait forever for a complete trace → asynchronous work has no universal end marker, so state grows

without bound → use root-plus-grace, maximum age/size, explicit workflow policies, and an incomplete flag.

• Treat traceparent as identity or authorization → an external caller can choose correlation fields →

authenticate the tenant independently and start a new linked trace at trust boundaries.

• Put baggage or arbitrary attributes into every index → cardinality, write amplification, and sensitive

data exposure become unbounded → allowlist indexed fields and bound or redact propagated values.

• Send spans synchronously to the central collector → telemetry failure raises application latency or

availability risk → batch asynchronously through bounded local queues and expose measured loss.

• Store each span but omit a trace summary → service, duration, and error searches scan huge detail data →

keep canonical detail plus one bounded, rebuildable summary row per trace.

• Call a biased tail sample an exact traffic distribution → error and latency rules intentionally

overrepresent unusual traces → publish sampling metadata and use metrics for exact aggregate rates.

• Test only collector uptime → context breaks, missing spans, and index lag can remain invisible →

run known-graph canaries and assert completeness, sampling, freshness, and query SLOs.

Follow-up Questions and Responses

Follow-up 1: Product now requires every error trace while keeping the same central ingest budget. What changes?

The two requirements may conflict. An error is often known only after downstream spans execute, so a source head sampler cannot guarantee retention. Quantify the maximum raw span rate and central tail capacity. If the budget cannot receive all candidate routes, narrow the guarantee to a bounded critical-route set, increase capacity, or add application error triggers that start future high-rate sampling while admitting that past dropped spans cannot be reconstructed. “Always errors” must also have a byte cap because an incident can turn nearly all traffic into errors.

Follow-up 2: A message consumes events from 10 producer traces. Which parent should the consumer span use?

No single parent represents ten independent causes. Create a consumer or batch-processing span in the appropriate workflow and attach links to the ten producer contexts, subject to a link-count limit. If the batch itself has one delivery context, that can be the parent while individual inputs remain links. Query and visualization code must support a DAG and show truncated-link metadata; copying the consumer span into ten trees distorts duration and storage.

Follow-up 3: The tail sampler is evicting partial traces before its decision window. How do you debug it?

Compare active trace count and bytes, trace-size distribution, arrival lateness, hot partitions, decision age, early-eviction counters, and per-tenant skew. Increasing the wait window can worsen memory pressure. First cap oversized traces, isolate noisy tenants, split partitions without breaking trace affinity, and reduce the normal baseline. Then add capacity or shorten the window based on observed late-span value. Run a shadow policy to measure how the proposed change alters retained errors, slow traces, and completeness.

Follow-up 4: Search is down for two hours, but ingestion and object storage are healthy. What does the API return?

Continue writing canonical trace objects and the durable index-change backlog. GetTrace can use the trace- ID directory if that path remains available; secondary search reports stale as_of data or an explicit temporary-unavailable state. It must not report that a newly accepted trace does not exist merely because its summary is not indexed. After recovery, replay idempotently, compare counts and lag, and rebuild the index from objects if the backlog is corrupt.

Follow-up 5: How do you prove that sampling has not hidden one low-volume service entirely?

Maintain a per-service or per-operation minimum baseline budget before sharing the remaining global budget. Track the probability and decision reason with each kept trace, and alert on services with traffic but no retained traces. Synthetic canaries verify the full path independent of probability. Compare trace-derived coverage with metric request counts; if a service receives requests but yields no spans, distinguish missing instrumentation, propagation failure, quota drops, head decisions, tail decisions, and index loss.