One request hits your API gateway, which calls auth, which calls the user service, which calls three downstream services, two of which hit a cache and a database, one of which enqueues a job that a worker picks up 40ms later. That single user-facing click fanned out into 30 service calls across 12 machines, and it was slow - 1.2 seconds when it should be 200ms. Which hop ate the second? Logs won’t tell you: they are 30 disconnected lines in 12 different files with no thread that ties them together. Metrics won’t tell you: they say “p99 latency is up” but not which call in which request. The thing that ties them together - the single most valuable artifact in a microservice debugging session - is the trace: the full call tree of one request, every span timed and parented, so you can see exactly where the 1.2 seconds went.

That is distributed tracing, and Google’s Dapper paper plus Jaeger/Zipkin are the canonical designs. The interview version cranks the scale: hundreds of microservices, ~1M spans/sec, reconstruct the complete call tree per request with a per-hop latency breakdown, and - because you cannot afford to store every span of every request - sample only what’s needed. Three hard problems fall out of that sentence. First, context propagation: how does service D know it is part of the same request that started at the gateway, across process boundaries, threads, and message queues? Second, trace assembly: spans for one request arrive independently, out of order, from a dozen machines at different times - how do you stitch them back into one tree? Third, sampling: at 1M spans/sec you drown if you keep everything, but if you sample blindly you throw away the one slow, erroring trace you actually needed. Get sampling wrong and the whole system is either bankrupt or useless.

Let me do it properly.

Functional Requirements (FR)

In scope:

  • Capture spans across hundreds of services. A span is one unit of work - a single service handling one call - with a start time, duration, an operation name, a set of tags/attributes (HTTP status, DB statement, error flag), and structured logs/events. Every service, in every language, emits spans for the work it does. This is instrumentation via a client library (OpenTelemetry SDK) plus auto-instrumentation of common frameworks.
  • Propagate trace context across boundaries. Every span carries a trace_id (shared by all spans in one request), a span_id, and its parent_span_id. When service A calls service B, A must inject the trace context into the outgoing request (HTTP headers, gRPC metadata, message-queue headers) so B continues the same trace instead of starting a new one. This is what makes 30 spans on 12 machines one tree.
  • Assemble the full call tree per request. Given a trace_id, return every span for that request, correctly parented, so a UI can render the tree/flamegraph: who called whom, in what order, and how long each took. This includes async hops (a span parented across a queue).
  • Latency breakdown. Per trace, show the critical path and per-span self-time vs total-time, so an engineer can point at the exact span that consumed the request’s latency. Aggregate across many traces to answer “what is the p99 latency of the checkout endpoint and which downstream call drives it.”
  • Search traces. Find traces by service, operation, tag (http.status=500, error=true), duration range (>1s), and time window. “Show me slow, erroring checkout traces from the last hour.”
  • Sample intelligently. Keep interesting traces (errors, slow, rare) and a representative fraction of the boring ones; drop the rest before they cost storage. Support both head-based (decide at trace start) and tail-based (decide after seeing the whole trace) sampling.
  • Service dependency graph. Derive, from trace data, the live map of which service calls which and with what error rate/latency - a byproduct of having every call tree.

Explicitly out of scope (own the scope):

  • Metrics and logs pipelines. Tracing is the third telemetry pillar with its own access pattern (trace-id lookup, span trees). Metrics-over-ranges and log-search are separate systems; we note where a trace_id on a log line links the two and move on.
  • Alerting and anomaly detection. Consumers of the trace/latency data, not part of this design. We produce the spans and aggregates and hand off.
  • The instrumentation SDK internals. How the OpenTelemetry SDK hooks a framework to start/stop a span is assumed. We design from “the SDK produced a span” onward, though context propagation (the wire format) is in scope because it is the crux.
  • Profiling (continuous CPU/heap profiles). Related but a different artifact; a span is request-scoped work, a profile is code-scoped resource use. Out.
  • Exactly-once span delivery. A dropped or duplicated span among billions is tolerable; we design for at-least-once and best-effort, and lean on it in the sampling and assembly design.

The one decision that drives everything: this is a write-heavy fan-in-and-reassemble problem where the payload is a graph, not a row, and the only way to survive 1M spans/sec is to never store most of it - so context propagation must be cheap and universal, assembly must tolerate spans arriving independently and late, and sampling (especially tail-based) is the load-bearing wall that decides what you can afford to keep. The architecture follows: a thin per-process tracer, a local agent, a collector fleet that groups spans by trace, a sampling decision plane, and a trace store keyed by trace_id.

Non-Functional Requirements (NFR)

  • Scale: hundreds of services, tens of thousands of hosts, ~1M spans/sec sustained ingest (a single user request commonly produces 20-100 spans, so this is on the order of 10K-50K traced requests/sec after sampling upstream). Incident spikes push span volume to ~2-3M/sec (errors generate more spans and trigger retries). A trace has anywhere from 3 to a few thousand spans; assume an average of ~30.
  • Latency: span emission must be near-zero cost to the traced application - the tracer buffers in memory and ships asynchronously, adding microseconds, never blocking the request. Trace availability for lookup: a completed trace should be queryable within seconds of the request finishing (this is a debugging tool; freshness matters during an incident). Trace-by-id lookup under ~1s; trace search under ~2-5s for a scoped query.
  • Availability: the collection path targets 99.9%+; if it drops during an incident you lose the forensics. But tracing must fail open - if the tracing backend is down, the traced application keeps serving traffic normally, just without traces. Tracing must never be able to take down production.
  • Consistency: eventually consistent, at-least-once, best-effort. A trace may be missing a span (its emitter crashed before flush), or have a duplicate; both are acceptable - a 29-of-30-span trace is still enormously useful. We explicitly do not need every span of every trace.
  • Durability: moderate, and only for what we choose to keep. Sampled-in traces must survive to the retention window (say 7-15 days for full traces; aggregates/service-graph longer). The vast majority of spans are dropped by design and never stored at all - that is the point.
  • Overhead budget is a first-class NFR. Tracing instruments every service; its CPU, memory, and network cost is paid by production. The end-to-end overhead (context propagation + span buffering + shipping) must stay in the low single-digit percent, and sampling is the primary knob that keeps stored volume - and therefore cost - bounded.

Back-of-the-Envelope Estimation (BoE)

Ground it in numbers.

Traffic:

Services:                       hundreds
Hosts:                          ~50,000
Spans/sec (sustained):          1,000,000     (1M)
Avg spans per trace:            ~30
=> Traced requests/sec:         ~33,000/sec    (post upstream head-sampling)
Incident spike (~2-3x):         2-3M spans/sec  (size ingest for this)

The 1M/sec is after whatever head-sampling the tracer already applied. If you head-sample 10% of requests and each request is ~30 spans, then the un-sampled request rate is ~330K req/sec - the raw traffic is 10x larger, which is exactly why sampling happens as early as possible.

Read vs write:

Writes: 1M spans/sec sustained, ~3M/sec peak. Overwhelmingly write-dominated.
Reads:
  - Trace-by-id lookup:  low hundreds/sec (an engineer opens a trace). Point read.
  - Trace search:        low tens/sec, but each scans a time+tag slice. Spiky.
  - Service graph / aggregate reads: continuous but served from pre-computed rollups.

Writes dominate by four to five orders of magnitude. Reads are rare (humans debugging), but a trace-by-id read must be fast and a search must be tractable. This is a firehose-ingest system with a light, latency-sensitive read side.

Span size and storage (the number that decides sampling):

Avg span on wire (proto, tags + a few logs):  ~500 bytes - 1 KB. Use ~700B.
Raw span volume:  1M/sec * 700B  = 700 MB/sec = ~60 TB/day RAW ingested.
Compression (~5-8x on repetitive span protos): ~9-12 TB/day compressed.

IF WE KEPT EVERYTHING:
  ~10 TB/day compressed * 15d retention = ~150 TB.  Large but not the killer -
  the killer is that MOST traces are boring and identical, so we'd be paying to
  store millions of copies of "the happy path took 200ms."

WITH TAIL-BASED SAMPLING keeping ~1-5% of traces (all errors/slow + a sample):
  effective stored volume drops ~20-100x -> single-digit TB/day, tens of TB total.

Two facts fall out. The ingest firehose (1M spans/sec) is unavoidable because tail-based sampling must see the whole trace before deciding, so you pay to receive and buffer everything even if you store almost none of it. And storage is a sampling decision, not a compression decision - the difference between 150 TB and 15 TB is not a better codec, it is throwing away the 95% of traces that all look the same and keeping the 5% that are errors, slow, or a fair random sample. That is why sampling is the central deep dive.

Bandwidth:

Ingest: 700 MB/sec raw -> ~100-140 MB/sec compressed on the wire, spread
   across a per-host agent + a collector fleet. ~1 Gbps aggregate inbound.
Intra-cluster (tail sampling): spans for one trace must converge on one
   decision point -> a shuffle by trace_id. This is the sneaky bandwidth cost.
Query responses: a trace is KB-MB; searches return trace summaries. Low volume.

The scarce resources are sustained span ingest throughput, the buffer memory to hold in-flight traces for the tail-sampling decision window, and the trace_id shuffle bandwidth to route all spans of a trace to one place. Size for those; the read side is cheap.

High-Level Design (HLD)

A thin in-process tracer buffers spans and ships to a per-host agent; the agent forwards to a stateless collector fleet; collectors route spans by trace_id to a tail-sampling decision layer that buffers spans per trace for a short window, decides keep/drop on the completed (or timed-out) trace, and writes kept traces to a trace store keyed by trace_id with secondary indexes; a query layer serves trace-by-id, search, and a derived service-dependency graph.

   HUNDREDS OF SERVICES / ~50,000 HOSTS
   ┌──────────────────────────────────────────────────────────────────────────┐
   │  [request in]                                                              │
   │    SDK/TRACER (in-process, per language - OpenTelemetry)                   │
   │      - start/stop spans, record tags + events                             │
   │      - INJECT context (trace_id, span_id, sampled) into outbound calls     │
   │      - EXTRACT context from inbound calls -> continue same trace           │
   │      - head-sampling gate; async in-memory span buffer -> flush batches    │
   └───────────────────────────────┬────────────────────────────────────────────┘
                                    │ batched spans (OTLP/gRPC, non-blocking)
                            ┌───────▼────────┐
                            │  HOST AGENT     │ (sidecar/daemon per host)
                            │  - local buffer │  (absorb SDK bursts, retry)
                            │  - batch/compress
                            └───────┬────────┘
                                    │ compressed span batches
                          ┌─────────▼──────────┐
                          │  COLLECTOR FLEET    │ (stateless, LB'd, autoscaled)
                          │  - validate/decode  │
                          │  - relabel/scrub    │  (drop hi-card/PII tags)
                          │  - ROUTE by trace_id│  (consistent hash / Kafka key)
                          └─────────┬──────────┘
                                    │ partition by hash(trace_id) -> all spans
                                    │ of one trace land on ONE decision node
                     ┌──────────────▼───────────────────────────────┐
                     │  KAFKA (durable buffer, keyed by trace_id)     │ absorbs
                     │  partitioned, replicated x3, short retention   │ 3M/sec
                     └──────────────┬───────────────────────────────┘ spikes
                     ┌──────────────▼───────────────────────────────┐
                     │  TAIL-SAMPLING / TRACE-ASSEMBLY LAYER          │
                     │   - buffer spans per trace_id (decision window)│
                     │   - on trace complete OR timeout:              │
                     │       evaluate policies (error? slow? rate?)   │
                     │       KEEP -> write ; DROP -> discard          │
                     │   - emit span-level metrics + service-graph edges
                     └───────┬───────────────────────────┬──────────┘
                    kept traces                     span metrics / edges
             ┌──────────────▼──────────┐        ┌────────▼──────────────┐
             │  TRACE STORE             │        │  AGGREGATE STORE       │
             │  primary: trace_id -> spans│      │  - service dep graph    │
             │  (columnar/wide-column)  │        │  - RED metrics per edge │
             │  secondary indexes:      │        │  - latency histograms   │
             │   service,op,tag,duration│        └────────┬───────────────┘
             │  7-15d retention         │                 │
             └──────────────┬───────────┘                 │
                    ┌────────▼─────────────────────────────▼─────────┐
                    │              QUERY LAYER                        │
                    │  - GET trace by id  (point read of span set)    │
                    │  - search by service/op/tag/duration/time       │
                    │  - service graph + latency breakdown (rollups)  │
                    └───────────────────────┬─────────────────────────┘
                                      ┌──────▼──────┐
                                      │  Trace UI   │ (flamegraph/waterfall)
                                      └─────────────┘

Write path - one request’s spans:

  1. A request arrives at the gateway. The tracer extracts trace context from the inbound headers; if none exists, this is a root - it mints a new trace_id and applies the head-sampling gate (e.g. keep 100% for now and let tail sampling decide later, or drop obvious noise). It starts a span, and on every outbound call injects traceparent headers so the callee continues the same trace.
  2. Each service records its span (operation, duration, tags, error, events) into an in-memory buffer and returns immediately - the request path never blocks on tracing. A background flusher batches spans and ships them over OTLP/gRPC to the host agent.
  3. The host agent (a per-host daemon/sidecar) buffers, batches, and compresses spans from all local processes, then forwards to the collector fleet. It shields the SDK from backend hiccups and gives one network egress point per host.
  4. Collectors (stateless, autoscaled behind an LB) decode and validate spans, scrub PII / drop high-cardinality tags, and - critically - route each span by hash(trace_id) into Kafka, keyed by trace_id. This guarantees every span of a given trace lands on the same partition and thus the same downstream decision node. Ack after the durable append.
  5. The tail-sampling/assembly layer consumes a partition, buffering spans grouped by trace_id in memory. It holds each trace for a decision window (e.g. wait until it sees a root span finish, or a timeout of ~10-30s). When the trace is complete (or the timeout fires), it evaluates sampling policies against the whole trace: keep if any span errored, keep if total duration exceeds a threshold, keep a probabilistic sample of the rest, always keep rare operations. Keep -> serialize the span set and write to the trace store, plus emit edges/metrics to the aggregate store. Drop -> discard the buffered spans; they never touch disk.
  6. The trace store persists kept traces keyed by trace_id, with secondary indexes on service, operation, tags, duration, and time for search.

Read path:

  1. Trace by id: the query layer does a point read of the store by trace_id, returns the full span set, and the UI builds the tree from parent_span_id links, rendering a waterfall/flamegraph with per-span timing.
  2. Search: resolve tag/service/duration/time predicates against the secondary indexes to a candidate trace-id set, fetch summaries, return ranked results. Opening one drills into the full trace.
  3. Service graph and latency breakdown: served from the pre-computed aggregate store (edges and RED - rate/errors/duration - metrics the assembly layer emitted per trace), never by scanning raw traces.

The key insight: context propagation makes independent spans one logical trace; routing every span by trace_id funnels a trace to one place so it can be assembled and tail-sampled as a unit; and tail sampling - deciding after seeing the whole trace - is what lets you receive 1M spans/sec but store only the interesting 1-5%. Everything else is plumbing around those three moves.

Component Deep Dive

Three hard parts, each walked from naive to scalable: (1) context propagation across process/thread/queue boundaries, (2) trace assembly from independently-arriving spans, and (3) sampling - the head-vs-tail decision that makes the economics work.

1. Context Propagation: Making 30 Spans One Trace

If service D does not know it is part of the same request as the gateway, you have 30 unrelated spans and no tree. Propagation is the mechanism that carries the shared identity across every boundary.

Approach A: Correlate after the fact by timestamp and service (naive)

Don’t propagate anything. Each service emits spans independently; a backend later tries to stitch them into traces by matching timestamps (“gateway called something at 10:00:00.123, user-service started at 10:00:00.124, probably the same request”).

Where it breaks: immediately and catastrophically. At 33K requests/sec, thousands of requests are in flight in any millisecond, all hitting the same services with overlapping timing - timestamp correlation cannot tell which gateway call caused which user-service call. Clock skew across 50K hosts (even a few ms) makes ordering ambiguous. Fan-out and retries create ambiguous many-to-many matches. There is no way to reconstruct a deterministic parent-child tree from timing alone. Post-hoc correlation is fundamentally guesswork and produces garbage trees. The identity must travel with the request.

Approach B: Explicit context injection/extraction with W3C trace-context

Propagate a small, standard context on every hop:

  • The IDs. Each trace has a globally unique trace_id (128-bit) minted at the root. Each span has a span_id (64-bit) and records its parent_span_id. Together these form the tree: a span’s parent is whoever called it. A sampled flag rides along so the decision propagates (more in deep dive 3).
  • The wire format. Use the W3C Trace Context standard: a traceparent header 00-<trace_id>-<span_id>-<flags> plus a tracestate for vendor data. Standardizing the format is what lets a Go service, a Java service, and a Python service in the same request all speak the same trace - propagation is a cross-language contract, and a non-standard format silently breaks the tree at any service that doesn’t understand it.
  • Inject on outbound, extract on inbound. The tracer extracts context from the inbound carrier (HTTP headers, gRPC metadata) when a request arrives, making the incoming span_id the parent of the span it is about to create. On every outbound call it injects the current span’s context into the carrier, so the callee’s extract picks up the right parent. Auto-instrumentation of the HTTP/gRPC clients and servers does this transparently so app developers don’t hand-thread it.
  • In-process propagation across threads/async. Within a process the “current span” lives in a context object carried on the execution (thread-local, or an explicit context in async/coroutine runtimes). The hard cases - thread pools, callbacks, async continuations - must copy the context onto the new execution unit, or the child span detaches and parents to nothing. This is the single most common instrumentation bug; frameworks provide context-aware executors to handle it.
  • Across message queues. For async hops (A enqueues, worker W dequeues later), inject the context into the message headers. W extracts it and creates a span parented to A’s producing span - even though W runs seconds later on another host. This is how a trace spans a queue and why “async work is invisible” is a solved problem when you propagate through the broker.
inbound at service B:
   ctx = extract(request.headers["traceparent"])     # trace_id + parent span_id
   span = start_span(op="B.handle", parent=ctx.span_id, trace_id=ctx.trace_id)
   ...do work, set tags, record error if any...
   for each outbound call to C:
        inject(ctx_of(span), call.headers)             # C continues same trace
   span.finish()                                        # duration recorded
   buffer.add(span)                                     # async ship, non-blocking

The mindset: the request carries its own identity across every boundary - HTTP, gRPC, threads, and queues - via a standardized context, so parent-child links are recorded deterministically at emit time, not guessed later. Propagation is cheap (a few headers), universal (every service, every language), and the foundation the whole tree stands on.

2. Trace Assembly: Stitching Independently-Arriving Spans

Spans for one trace are emitted by a dozen services, buffered for different durations, and shipped independently - they arrive at the backend out of order, on different partitions if you’re not careful, and at different times (the leaf span may arrive before or after the root). Reassembling them into one tree, and knowing when the trace is done, is the second hard problem.

Approach A: Assemble lazily at read time from a flat span table (naive)

Store every span as a row in a big table indexed by trace_id. When someone requests a trace, SELECT * WHERE trace_id = X, then build the tree from parent_span_id in the query layer.

Where it breaks: two ways. First, this design forces you to store every span to be able to assemble later - which defeats tail sampling entirely, because you can’t decide to drop a trace after you’ve already written all its spans. The whole economic argument (store 1-5%) requires assembling before the storage decision, in memory. Second, even ignoring cost, “when is the trace complete?” has no answer in a flat table - a read at time T might see 25 of 30 spans because 5 are still buffered in a slow service, and you’d render an incomplete tree with no way to know it’s incomplete. Read-time assembly with no completion signal gives you truncated traces and blocks tail sampling. Assembly has to happen in-flight, in a buffered decision layer.

Approach B: In-memory per-trace buffering with a completion heuristic, before the store

Assemble each trace in memory as its spans stream in, decide when it’s “done,” then persist as a unit:

  • Route all spans of a trace to one assembler. As established in the HLD, collectors key Kafka by hash(trace_id), so every span of trace X lands on the same partition and the same assembler consumes them together. Without this, a trace’s spans scatter across nodes and can never be buffered as one - this routing is the precondition for both assembly and tail sampling.
  • Buffer spans grouped by trace_id. The assembler maintains an in-memory map trace_id -> [spans seen so far], plus the arrival time of the first span. Spans arrive out of order; that’s fine, the tree is built from parent_span_id, not arrival order. The map is the working set of in-flight traces.
  • Deciding completeness - the root-span + timeout heuristic. You cannot know for certain a trace is complete (a straggler span could always arrive). Two practical signals: (a) the root span finishing is a strong hint the request is done - the root’s duration bounds the whole trace, so once you’ve seen the root span and a short settle time for stragglers, close it; (b) a hard timeout (e.g. 10-30s from first span) closes traces whose root never arrived (the root emitter crashed, or it’s a async/streaming trace). On close, you emit the assembled trace to the sampling policy. Late spans arriving after close are either attached to an already-kept trace (a cheap append) or dropped for an already-dropped trace.
  • Bounded memory and spill. The in-flight map is the system’s most precious and most dangerous resource: at 33K traces/sec with a 30s window, that’s ~1M traces * 30 spans = ~30M spans buffered per assembler cluster. Bound it: cap per-trace span count (a pathological 10,000-span trace is truncated with a flag, not allowed to OOM the node), cap total memory and evict oldest-decided first, and shard assemblers so each holds a slice of the trace-id space. This is why the decision window is short - every extra second of window is linear memory.
  • Partial traces are fine. If a span never arrives (its emitter crashed before flush), the trace is assembled without it - a 29-of-30 tree, flagged as possibly-incomplete. Per the NFRs this is acceptable; a mostly-complete trace is still hugely valuable, and chasing exactly-complete assembly would cost far more than it’s worth.
assembler, per consumed partition (spans keyed by trace_id):
   on span s:
        t = inflight[s.trace_id] or new_trace(first_seen=now)
        t.spans.add(s)
        if s.is_root: t.root_seen = true; t.deadline = now + settle_time
        if t.spans.count > MAX_SPANS: t.truncated = true
   periodically / on deadline:
        for t in inflight where (t.root_seen and now>t.deadline) or now>t.hard_timeout:
             tree = build_tree(t.spans by parent_span_id)   # assemble
             decision = sampling_policy(tree)                # deep dive 3
             if decision.keep: store(tree)  else: discard(t)
             evict(t.trace_id)

The principle: assemble each trace in memory as spans stream in, use a root-span-plus-timeout heuristic to decide it’s done, and make the keep/drop decision on the whole tree before anything is written - because tail sampling only works if assembly happens before storage, and because a flat write-everything table would both cost 20-100x more and never know when a trace is complete.

3. Sampling: The Wall That Makes It Affordable

At 1M spans/sec, keeping everything is either ruinously expensive or forces useless retention. But naive sampling (“keep 1% at random”) throws away the rare error trace you desperately need. Sampling is where this system is won or lost.

Approach A: Uniform head-based sampling only (naive)

At the root, flip a coin: with probability p (say 1%), mark the trace sampled=true and propagate that flag; every service in the trace honors it and emits (or doesn’t). Simple, and it bounds volume beautifully - you only ever emit ~1% of spans.

Where it breaks: it is blind to what the trace turns out to be. The decision is made at the root before anything has happened, so a rare error deep in the call tree, or a request that turns out to take 5 seconds, has a 99% chance of having been dropped at the very start - and those are the only traces anyone ever wants. You end up with a statistically representative sample of the boring happy path and almost none of the pathological traces that justify having tracing at all. Uniform head sampling optimizes cost and destroys utility. You cannot decide what’s interesting before you’ve seen it.

Approach B: Head-sampling for volume + tail-sampling for what matters

Use two stages, each doing what it’s good at:

  • Head sampling to cheaply shed obvious volume. At the root, apply cheap, coarse rules that don’t need the whole trace: always trace requests that already arrive with sampled=true (respect upstream), always trace a small guaranteed baseline (e.g. 1% probabilistic so you have unbiased data), rate-limit per endpoint so one hot endpoint can’t dominate, and drop obvious noise (health checks). The head decision propagates via the sampled flag so a trace is consistently traced or not across all services - you never get half a trace. Head sampling’s job is to bound the ingest firehose somewhat, not to make the smart keep/drop call.
  • Tail sampling for the smart decision. The assembly layer already buffers the whole trace (deep dive 2). Once assembled, evaluate policies on the complete tree and keep if any is satisfied: error policy (any span has error=true or a 5xx status -> always keep), latency policy (total duration > threshold, or an unusual per-service latency -> keep), rare-operation policy (an operation seen infrequently -> keep for coverage), and a probabilistic policy (keep p% of the remaining boring traces as an unbiased baseline). Composite/OR of policies means “keep all errors, all slow ones, all rare ones, plus 1% of normal.” This is what makes stored data dense with signal: nearly every stored trace is one someone would want.
  • Why you still ingest everything. Tail sampling’s cost is that the decision needs the whole trace, so you must receive, route, and buffer all spans up to the decision - you pay full ingest and buffer cost, then drop 95-99% at the write. That’s the deliberate trade: spend on transient ingest/buffer to save massively on durable storage and to keep exactly the traces that matter. Head sampling reduces the ingest bill partially; tail sampling makes the storage bill small and the stored content useful.
  • Consistency of the decision across a distributed assembler. All spans of a trace route to one assembler (via hash(trace_id)), so the tail decision is made in one place with the full trace - no need to coordinate a decision across nodes. This is the second reason the trace-id routing matters (the first was assembly).
  • Adaptive rates. Under a spike, tune head rate-limits and the probabilistic tail rate down automatically to hold storage/throughput budgets, while never touching the error/latency policies - you shed boring volume, never the incident’s own traces. Sampling gets more selective exactly when load is highest, which is the correct behavior since that’s when the interesting traces are densest.
HEAD (at root, cheap, no full trace):
   if inbound.sampled: sampled=true                     # respect upstream
   elif is_health_check: sampled=false
   elif rate_limiter[endpoint].allow(): sampled = coin(1%) or force-keep-baseline
   propagate sampled flag to all children               # whole trace consistent

TAIL (in assembler, on completed trace):
   keep = trace.has_error
       or trace.duration > latency_threshold(service, op)
       or is_rare(trace.root_operation)
       or coin(baseline_p)                              # unbiased sample
   if keep: store(trace) else: discard(trace)
DimensionHead sampling (only)Head + tail sampling
Decision timingAt trace start, blindAfter full trace assembled
Keeps errors/slow?Only by luck (~p)Always (policy)
Ingest costLow (drop early)Full (must see whole trace)
Storage costLowLow (drop 95-99% at write)
Stored data qualityRepresentative, low-signalDense with errors/slow/rare
ComplexityTrivialNeeds buffering + assembly

The trade is explicit: tail sampling costs you full ingest and a memory buffer for every in-flight trace, and in exchange it keeps almost every error and slow trace while storing only 1-5% of volume - so the stored corpus is small and useful. Head sampling stays as a cheap first-stage volume cap and a way to respect upstream decisions. Pure head sampling is what you fall back to only if you can’t afford to buffer the firehose; for a system that exists to debug the pathological request, tail sampling is worth its cost.

API Design & Data Schema

Ingest API (write plane - tracer/agent to collector)

POST /v1/traces        (OTLP - OpenTelemetry Protocol over gRPC/HTTP)
  Content-Type: application/x-protobuf   (batched spans, gzip/zstd)
  body: ExportTraceServiceRequest {
    resource_spans: [
      { resource: { service.name:"checkout", host.name:"h-9f2",
                    region:"ap-south-1" },
        scope_spans: [ { spans: [
          { trace_id:"4bf92f...", span_id:"00f0...", parent_span_id:"a3c1...",
            name:"POST /charge", kind:SERVER,
            start_unix_nano:..., end_unix_nano:...,
            attributes:{ http.status_code:500, error:true, db.system:"postgres" },
            events:[ { time:..., name:"exception", attrs:{...} } ],
            status:{ code:ERROR } },
          ...
        ] } ] }
    ]
  }
  200 OK (partial success allowed: {rejected_spans:N, error:"..."})
Notes:
  - Non-blocking on the app: SDK buffers, background flush, drops on buffer-full
    (increments a dropped_spans counter it reports about itself).
  - Fail-open: if the collector is unreachable, the app keeps serving; spans lost.
  - Context is on the WIRE of the traced calls (traceparent header), NOT here -
    here we ship the already-linked spans.

Query API (read plane)

# Trace by id - the point read that renders the flamegraph
GET /v1/traces/{trace_id}
  200 OK { trace_id, spans:[ {span_id,parent_span_id,service,op,
             start,duration,tags,events,status} ... ],
           warnings:[ "possibly_incomplete", "truncated_at_10000_spans" ] }

# Search traces - by service/op/tag/duration/time
GET /v1/traces?service=checkout&operation=POST%20/charge
    &tags=error:true&minDuration=1s&start=...&end=...&limit=20
  200 OK { traces:[ { trace_id, root_service, root_op, duration,
             span_count, error:true, start } ... ] }   # summaries; drill in for full

# Service dependency graph (from pre-computed aggregates)
GET /v1/dependencies?start=...&end=...
  200 OK { edges:[ { parent:"checkout", child:"payments",
             call_count, error_rate:0.02, p99_latency_ms:180 } ... ] }

# Per-operation latency breakdown (RED metrics from rollups)
GET /v1/metrics/latency?service=checkout&operation=POST%20/charge&start=..&end=..
  200 OK { p50, p90, p99, error_rate, call_rate, by_downstream:[ {service,p99} ] }

Data model: trace store + aggregate store

Trace store - trace_id as primary key, wide-column / columnar NoSQL:

Primary (point lookup by trace_id):
  trace_id (partition key)  ->  set of spans (serialized), or:
  (trace_id, span_id) rows in a wide-column store (Cassandra/Bigtable-style):
     trace_id | span_id | parent_span_id | service | operation
              | start_ts | duration | tags(map) | events | status
  A trace = all rows sharing trace_id, colocated on one partition -> single-seek read.

Secondary indexes (for search):
  service_operation_index: (service, operation, bucket_hour) -> [trace_id...]
  tag_index:               (tag_key, tag_value, bucket_hour) -> [trace_id...]
  duration_index:          (service, bucket_hour, duration)  -> [trace_id...]
  (indexes hold trace-id + summary only; the full trace is fetched by id)

Retention: 7-15 days for full traces; drop by time bucket (immutable partitions).

Aggregate store - service graph + RED metrics (TSDB / rollup store):

edge:   (parent_service, child_service, bucket) -> call_count, error_count,
                                                    latency_histogram
op_red: (service, operation, bucket) -> rate, error_rate, latency histogram
Emitted by the assembly layer per assembled trace (kept OR dropped - aggregates
should reflect ALL traffic, so compute RED/graph BEFORE the sampling drop, from
the full assembled trace, not just the stored sample). Retention: longer (weeks).

Durable buffer (Kafka), keyed by trace_id:

topic: spans ; PARTITION KEY = hash(trace_id) ; replicated x3 ;
short retention (hours) as shock-absorber + to colocate a trace's spans on one
partition -> one assembler. Consumers track offsets; failure replays -> at-least-once.

Why this split and these stores. The dominant read is trace-by-id, a point lookup, so a wide-column store partitioned by trace_id (Cassandra/Bigtable/ScyllaDB, as Jaeger uses) gives a single-partition seek for the whole trace and scales writes horizontally by trace-id hash - exactly the access pattern. Search needs secondary indexes on the few dimensions people filter by (service, op, tag, duration), holding only trace-ids so the index stays small; Elasticsearch is a common backend for this flexible-tag search side. A relational DB is wrong: a trace is a variable-shape set of spans with arbitrary tags (schema-flexible), the write rate (1M spans/sec) exceeds what a single relational primary can take, and you never need joins across traces - you need “give me this one trace, fast.” The service graph and RED metrics are numeric rollups, so a TSDB/rollup store serves them cheaply and, importantly, they’re computed over all assembled traffic (before the sampling drop) so aggregates stay accurate even though stored traces are a sample. Right tool per read pattern; unified only at the collection pipeline and the query API.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix:

1. Storing every span (the number-one killer). At 1M spans/sec, keeping everything is ~150 TB of mostly-identical happy-path traces - expensive and low-signal. Fix: tail-based sampling. Assemble each trace in memory, keep all errors/slow/rare traces plus a small probabilistic baseline, drop 95-99% before the write. Storage becomes single-digit TB and dense with signal. Head sampling caps ingest partially as a cheap first stage.

2. Ingest write throughput (1-3M spans/sec). No single node accepts it, and synchronous span shipping would block production apps. Fix: async in-memory SDK buffers + per-host agents + a stateless, autoscaled collector fleet + a partitioned durable buffer (Kafka) decoupling ingest from assembly. Add collectors and partitions to add capacity. The app path never blocks - fail open.

3. The trace_id shuffle / assembly memory. Tail sampling needs all of a trace’s spans in one place, and buffering millions of in-flight traces is memory-heavy. Fix: key Kafka by hash(trace_id) so a trace’s spans converge on one assembler (no cross-node decision coordination), shard assemblers across the trace-id space, keep the decision window short (memory is linear in window length), and bound per-trace span count and total memory with oldest-decided eviction. A pathological giant trace is truncated with a flag, never allowed to OOM.

4. Hot service / hot endpoint flooding the pipeline. One extremely chatty service or a retry storm dominates span volume. Fix: per-endpoint head rate-limiting at the root, adaptive sampling that tightens the probabilistic rate under load (never the error/latency policies), and relabeling/scrubbing at collectors to drop high-cardinality or PII tags. Shed boring volume, keep the incident’s traces.

5. Context propagation gaps (broken trees). Async hops, thread pools, and non-standard header formats silently detach spans, producing orphan spans and truncated trees. Fix: W3C Trace Context as the universal wire format, auto-instrumentation of HTTP/gRPC clients+servers and message brokers, context-aware executors for thread pools/async, and orphan detection at assembly (spans whose parent never arrives are attached to a synthetic root and flagged). Standardize the contract so every language/service interoperates.

6. Trace-by-id read latency / search fan-out. A trace must open fast; a broad search must stay tractable. Fix: partition the trace store by trace_id so a full trace is a single-partition seek; secondary indexes on service/op/tag/duration holding only trace-ids keep search scoped; time bucketing prunes the range. Reads are rare (humans debugging), so the read side is cheap once the point-read and index shapes are right.

7. Aggregate accuracy under sampling. If RED metrics and the service graph are computed only from stored (sampled) traces, they undercount by the sampling rate and lie about real traffic. Fix: compute aggregates in the assembly layer from every assembled trace, before the sampling drop - the service graph and latency histograms reflect 100% of traffic even though only 1-5% of full traces are stored. Aggregates and stored traces are decoupled on purpose.

8. Duplicate / missing spans under at-least-once. Kafka replay on consumer restart double-delivers spans; a crashed emitter never ships its span. Fix: dedupe by span_id within the assembler’s per-trace buffer (a re-delivered span is idempotent), and accept partial traces - a missing span yields a 29-of-30 tree flagged possibly-incomplete. Exactly-once isn’t worth its cost for a debugging tool; robustness to dup/loss is.

9. Tracing taking down production (the cardinal sin). If the tracing backend’s slowness or outage propagates back into the traced app, monitoring causes the outage. Fix: fail open everywhere - SDK buffers are bounded and drop on overflow (counting drops), shipping is fully async and never on the request path, and agents/collectors absorb backend hiccups. If tracing is down, apps serve traffic normally with zero traces. Overhead stays in low single-digit percent.

10. Clock skew across 50K hosts distorting the waterfall. Spans timed on different machines with skewed clocks render a tree where a child appears to start before its parent. Fix: trust durations over absolute timestamps (a span’s own start/end are from one clock, so its duration is accurate), reconstruct ordering primarily from parent_span_id links, and apply skew-correction heuristics at render (clamp a child’s start within its parent’s window). The tree topology comes from IDs, not timestamps - which is exactly why propagation, not timing, defines the structure.

Wrap-Up

The trade-offs that define this design:

  • Tail sampling over head-only sampling. We pay full ingest and a memory buffer for every in-flight trace so we can decide keep/drop after seeing the whole trace - keeping nearly all errors/slow/rare traces while storing only 1-5% of volume. The stored corpus is small and dense with the traces someone actually wants, which pure head sampling can never deliver.
  • Assemble before you store. Trace assembly happens in memory in a buffered decision layer, gated by a root-span-plus-timeout completion heuristic - because tail sampling only works if the drop decision precedes the write, and because a flat write-everything table would cost 20-100x more and never know when a trace is complete.
  • Identity on the wire, not guessed later. W3C Trace Context propagated across HTTP, gRPC, threads, and queues makes 30 independent spans one deterministic tree; timestamp correlation is guesswork that collapses at concurrency. The tree topology comes from parent_span_id, which also immunizes it against clock skew.
  • Route by trace_id to funnel a trace to one place. Keying the buffer by hash(trace_id) colocates every span of a trace on one assembler, which is the single precondition for both in-memory assembly and a coordination-free tail-sampling decision.
  • Fail open and best-effort over exactly-once. Tracing must never take down production, so shipping is async and bounded-drop; and a partial or slightly-duplicated trace among billions is fine, so we spend that relaxation on cost and availability - approximate-but-safe beats exact-but-fragile for a tool whose entire job is to be there when production is on fire.

One-line summary: thin async tracers propagate W3C trace context so spans self-link into a tree, a per-host agent and stateless collector fleet route every span by hash(trace_id) into a durable buffer, an in-memory assembly layer stitches each trace and applies tail-based sampling to keep only the 1-5% that matter, and a trace_id-partitioned wide-column store plus tag indexes serve trace-by-id and search - trading full-firehose ingest and exactly-once for a system that captures 1M spans/sec across hundreds of services and reconstructs the exact call tree and latency breakdown of any request you care about.