Engineering Atlas › System Design Interviews

Design a distributed tracing system

19 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional

Non-functional

Out of scope: metrics and logging pipelines (we only link to them by trace id), profiling, and the UI.

Back-of-envelope

Assume 50,000 user requests per second at the edge at peak, each touching about 40 spans across services. The average is half the peak.

API

Applications never call the backend directly. They use an SDK that exports over OTLP, and the collector speaks the same protocol (OTLP spec).

# Propagation (HTTP header, W3C): version-traceid-parentid-flags
traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
tracestate:  vendor1=opaque,othervendor=value

# Export (OTLP/gRPC, batched)
rpc Export(ExportTraceServiceRequest) returns (ExportTraceServiceResponse)
  resource_spans[] -> scope_spans[] -> spans[]
    { trace_id(16B), span_id(8B), parent_span_id, name, kind,
      start_time_unix_nano, end_time_unix_nano, attributes[], events[], status }
  response.partial_success { rejected_spans, error_message }

# Query
GET /api/traces/{trace_id}
POST /api/search
  { "q": "{ resource.service.name = \"checkout\" && status = error && duration > 2s }",
    "start": "2026-10-17T10:00:00Z", "end": "2026-10-17T11:00:00Z", "limit": 20 }
  -> [ { trace_id, root_service, root_name, start, duration_ms, span_count } ]

Data model

A span is immutable once it ends, so storage is append-only.

High-level design

flowchart LR
  A["Service + SDK"] -->|"OTLP, batched"| AG["Agent / sidecar"]
  AG --> LB["Stateless collectors (route by trace id)"]
  LB -->|"consistent hash"| TS["Tail-sampling collectors (buffer 30 s)"]
  TS -->|"kept traces"| Q[("Queue (Kafka)")]
  LB -.->|"RED metrics, edges"| M[("Metrics store")]
  Q --> W["Block writers"]
  W --> OS[("Object storage: blocks + index")]
  U["Query UI / API"] --> QF["Query frontend"]
  QF --> QR["Queriers"]
  QR --> OS
  QR --> RC["Recent-data cache"]
  W --> RC

Write path.

  1. The SDK creates a root span, makes the head decision (usually "record everything and mark sampled" or a low-rate probability), and injects traceparent into outgoing calls.
  2. On span end, the SDK hands the span to a batch processor with a bounded queue. A background thread exports batches to a local agent. A full queue drops spans and increments a counter.
  3. The first-tier collectors are stateless. They validate, enrich with resource attributes, compute RED metrics, and forward spans using a load-balancing exporter that hashes the trace id.
  4. The tail tier buffers every span of a trace until it is "done", then applies policies: any error, duration over a threshold, a rate limit per service, then a probabilistic baseline.
  5. Kept traces go to a queue, and block writers cut sorted, compressed blocks to object storage.

Read path.

  1. By id: the query frontend looks in the recent-data cache, then asks storage nodes. Each block's Bloom filter rules out most blocks without reading them. Matches are read by range from object storage.
  2. By attributes: the frontend splits the time range into jobs, queriers scan only the needed columns in parallel, and results are merged and limited.

Deep dives

1. Head versus tail sampling

Head sampling decides when the root span starts, from the trace id or a fixed rate. It is nearly free and the decision travels in the sampled flag, so every service agrees. Its flaw is that it cannot know the outcome: an error that appears in the fifth span of a 1% sampled trace is lost 99% of the time, and OpenTelemetry's own guide says tail sampling is the answer when you must keep every error (OpenTelemetry sampling).

Tail sampling decides after the trace is complete. It sees errors, latency and the whole shape, but each trace must be held in memory until the last span arrives, and "last" is unknowable. A decision_wait timer (default 30 seconds in the OpenTelemetry processor) is the guess. A late span either finds the decision already made or arrives after a trace was dropped.

Choice: both. Head-sample generously, for example record everything when the cost allows, or at 10 to 25% when it does not, and tail-sample for the keep decision. Drop most healthy, fast traces; keep all errors and slow traces. Make the baseline deterministic from the trace id: compare a hash of the id to a threshold. Every collector that sees the same id then agrees, and raising the rate only adds traces. OpenTelemetry's probability-sampling work encodes that threshold in tracestate so downstream components know the effective rate and can weight counts (spec).

2. Making the tail sampler scale

The tail sampler is stateful, and the documentation is blunt: all spans for a trace must reach the same collector instance (README). Two tiers solve this. A stateless tier receives spans from anywhere and uses a consistent hash on trace_id to choose a tail node. Consistent hashing matters because when a tail node joins or dies, only about 1/N of traces move. The traces in flight during the change get split across two nodes and make bad decisions, and you accept that and measure it.

Memory is the limit. The buffer holds num_traces traces, evicts the oldest when full, and every eviction is a trace decided too early. Alert on evictions, because they silently degrade the "keep every error" promise. Keep a small cache of recent decisions so late spans of an already-kept trace are forwarded and late spans of a dropped trace are discarded cheaply.

Alternatives: keep the buffer out of process by writing every span to a log keyed by trace id and deciding at read or compaction time. That costs 40 TB/day of writes, which is the cost we are avoiding.

3. Storage and query

Two queries with opposite shapes. By trace id is a point lookup, so blocks are sorted by trace id and carry a Bloom filter. A 1% false-positive filter for 100 million ids needs about 120 MB, small enough to cache. By attributes is a search, and the temptation is an inverted index on every tag. At 2 attributes × 40 spans × 25,000 traces per second that index would be larger and busier than the data, and attribute cardinality is unbounded (user ids, URLs).

The alternative is a columnar block format: each attribute is a column, with dictionary encoding and a min/max per row group, so a query on status = error AND service = checkout reads two columns and skips row groups by statistics. Cost scales with time range, not with trace count, and parallelism comes from splitting a range into many row-group jobs. This is the design Tempo uses; Jaeger's older Elasticsearch and Cassandra backends instead index chosen tags, which gives faster narrow queries but a heavy write and storage bill (Jaeger architecture).

To keep the last minute searchable, writers also keep recent spans in memory or a local WAL, and queriers merge that with object storage.

Down the stack

Layer 1The contract

  • Propagation: traceparent is version-traceid-parentid-flags, 55 characters for version 00: a 32 hex trace id, a 16 hex parent id, and 2 hex flags. All-zero ids and version ff are invalid, and uppercase hex is not allowed (W3C Trace Context). A service that cannot parse the header starts a new trace.
  • The sampled flag is the least significant bit of the flags byte. It means the caller may have recorded data, and a component that defers its decision should propagate it unchanged.
  • Delivery: spans are best effort. We promise that kept traces are complete to within the decision window, not that every span is stored. Missing spans appear as gaps, and the UI marks an orphan whose parent never arrived.
  • Freshness: a kept trace is searchable within about 60 seconds: 30 for the decision wait plus block cut time.

Layer 2The mechanism

  • SDK: a TracerProvider holds a sampler and a span processor. The BatchSpanProcessor has a bounded queue, a batch size and a scheduled delay, and it exports from its own thread (OpenTelemetry SDK spec). The sampler runs at span start, so a non-recording span costs almost nothing.
  • Collector: receivers, processors and exporters wired into pipelines. A memory limiter processor refuses data when the process nears its limit, and the refusal turns into back-pressure to the sender (Collector architecture).
  • Tail sampler policies: status_code, latency (duration from the earliest start to the latest end), rate_limiting and probabilistic, combined with OR logic. A trace is kept if any policy keeps it.
  • Writers: sort by trace id, build row groups, write the footer, Bloom filter and index, then upload with a single multi-part put. Compaction merges small blocks and removes duplicates, because retried exports can deliver the same span twice and (trace_id, span_id) identifies it.

Layer 3The machine

  • Hot path: starting and ending a span is a few allocations, two clock reads (about 20 to 50 ns each with the vDSO) and a lock-free enqueue, well under a microsecond. Dapper measured the cost of tracing every request as 16.3% added latency in a web search cluster, but rates below 1 in 16 were within experimental error (Dapper paper). Modern SDKs are cheaper, yet the lesson holds: a recorded span is much costlier than an unrecorded one.
  • Wire: a batch of 512 spans at 500 B is 256 KB, which fits in one gRPC message and amortises TCP and TLS cost. gzip or zstd shrinks span data about 5 to 10 times because names and attribute keys repeat.
  • Collector memory: Go-based collectors allocate heavily and the GC runs concurrently, so the heap needs headroom, often 2x the live set, and a memory limit set below the container limit to avoid OOM kills.
  • Object storage: a GET has a first-byte latency of tens of milliseconds, so reading a trace means a few ranged GETs (footer, index, row group), around 100 to 300 ms with caching of footers and Bloom filters.

Why it's built this way

  1. Tracing every request is too expensive for the application and the budget, so we sample.
  2. Head sampling cannot see failures that happen later, so the valuable decision moves to the tail.
  3. The tail decision needs a whole trace in one place, so spans are routed by trace id into a memory buffer.
  4. Memory and wait time are bounded, so decisions are approximate, late spans are handled with a cache and evictions are monitored.
  5. Kept data is immutable and queried by time, so it fits large sorted columnar blocks in object storage rather than a database with secondary indexes.

Failure modes

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Head sampling onlyNo buffering, constant cost, consistent across servicesMisses rare errors and slow outliersVery high volume, cost matters more than completeness
Tail samplingKeeps every error and slow traceStateful, memory heavy, needs trace-id routing, approximate under churnFailures must always be debuggable
Tag-indexed store (Elasticsearch, Cassandra)Fast narrow queries on chosen tagsLarge write amplification, cardinality limitsSmall volume or a fixed set of search tags
Columnar blocks on object storageCheap, any attribute searchable, scales with parallel scansSearch is a scan, slower for a very selective queryLarge volume with free-form attribute search
Spans to a queue, decide at writeAbsorbs bursts, replayablePays to ship and store all spans firstModerate volume with bursty load
Generate metrics from all spansAccurate RED metrics despite samplingExtra CPU at the collectorDashboards and alerts depend on span data

Leadership lens

Check yourself

  1. A service's error rate is 0.2%, and you head-sample at 1%. What fraction of failing requests produce a stored trace, and what changes with tail sampling?

    Show answer

    About 1% of them, because the decision is independent of the outcome, so 99% of errors are invisible. Tail sampling keeps all of them, at the cost of buffering every trace until it finishes.

  2. Why must the tail-sampling tier be fed by a router that hashes on trace id?

    Show answer

    A policy such as "keep if any span has an error" is only right if one node sees every span of the trace. Without trace-id routing, each node sees a fragment and makes inconsistent decisions, so kept traces are incomplete.

  3. Why store traces in Bloom-filtered blocks sorted by trace id rather than indexing every attribute?

    Show answer

    Fetching by id needs only a point lookup, which the sort order and Bloom filters give cheaply. A tag index would cost more to write than the data itself, and attribute cardinality is unbounded, so attribute search uses column scans.

  4. At 1M spans per second and 500 bytes per span, how much do you ingest per day, and how much do you store with 2.5% kept and 4:1 compression?

    Show answer

    1M × 500 B × 86,400 = about 43 TB/day ingested. Keeping 2.5% gives about 1.1 TB, and compression gives about 270 GB/day.

Sources and further study

Primary

Systems docs

Books

Free resources

Open in the interactive app: practice, quiz, mock interview →