Build Your Own: Distributed Tracing System

FR1: A service can attach trace context to a request and have spans accepted without blocking the request.
FR2: Given a trace_id, return the full span tree within the retention window.
FR3: Every span carries structured status (OK / ERROR / TIMEOUT) plus a bounded set of key-value tags.
FR4: Sampling policy is configurable per service/tier, not one global rate.
FR5: Trace context survives async boundaries (queue/broker) via explicit propagation, not assumption.
FR6: Error traces and traces above a latency threshold are guaranteed to survive sampling, not left to chance.
FR7: Query access is exposed as an API to internal tools, not raw storage access. Why this shape: every FR here maps to a concrete downstream design decision later in this session (FR6 forces tail sampling in segment 2; FR5 forces explicit context-link handling in segment 8). An FR that doesn't constrain a later decision is usually filler.

Scope out: 100% full-fidelity capture of every span (cost-prohibitive at this scale by construction — segment 5 will show why); cross-vendor trace federation; and rebuilding log aggregation inside the tracing system. Why it matters: an unscoped system quietly grows toward "let's also capture everything, forever, and search it like logs" — at which point you've rebuilt a second, worse logging platform on top of a data model that was never designed for full-text search. The scope line is what stops a tracing system from mission-creeping into something it structurally can't do well.

Ingest throughput: 50k–100k spans/sec sustained, 3x burst. Added latency to the caller: <5ms p99 — must be fire-and-forget. Single-trace query latency: <500ms p95. Hot retention: 24–72h. Cold/compliance retention: 90 days minimum for regulated flows (allotment, redemption, disbursal). Consistency: eventual is fine for trace assembly (spans arrive out of order); durability of an accepted span is the real non-negotiable. Availability: the ingest path must degrade by dropping spans, never by slowing or blocking the caller. Why this framing: the single NFR that shapes everything else is the last one — tracing must never become the reason the real system is slow or down. Every later trade-off (tail sampling's memory cost, backpressure policy, agent design) gets judged against that one sentence.

Tail sampling. The decision happens after you've seen the outcome, so error and slow traces can be kept deterministically instead of hoping a random head-sample coin flip caught them. The cost: the collector must now buffer every span of every in-flight trace until it's judged complete, which makes the collector stateful and memory-bound — a structural cost head sampling never pays, because head sampling decides at request-start and immediately forgets whatever it didn't select. This single choice is why segments 3, 6, 7, and 9 all end up dealing with buffering, memory pressure, and instance-affinity — it isn't a side detail, it's the decision's direct shadow.

Only as a cost-control layer underneath tail sampling, never as the sole mechanism — e.g. coarsely head-filtering known-low-value background traffic before it ever reaches the tail-sampling buffer. Why not pure head sampling: a decision made before the outcome exists cannot, by construction, condition on that outcome. Pure head sampling and "guarantee errors survive" are logically incompatible — no amount of tuning the head-sample rate fixes that, it only changes the odds.

Buffering must stay entirely off the path the caller waits on (or the <5ms NFR breaks immediately). Memory pressure per instance now scales with in-flight trace volume, not just span volume. And "when is a trace complete" becomes a real design problem — too eager and you cut off a slow trace before its signal arrives; too patient and buffers grow unbounded. Why say this out loud in a review: tail sampling is usually the right call for a system with an FR6-shaped requirement, but pretending it's free is how a design review gets ambushed later by a memory incident nobody budgeted for.

Instrumented Service (SDK)
   | spans, async, non-blocking
   v
Local Agent / Sidecar          -- batches, local retry, backpressure
   |
   v
Ingestion Gateway               -- auth, validation, rate-limit (stateless)
   |
   v
Trace Assembler / Sampler       -- buffers per trace_id, tail decision (stateful)
   |                    \
   v                     v
Hot Storage           Cold / Archive Storage  <- async tiering (segment 7)
   |
   v
Query Service / API
   |
   v
Dashboards / Alerting / on-call tooling

Why this exact shape: every box exists because of a decision made earlier — the assembler exists because of segment 2's tail-sampling choice; the agent exists because of the <5ms caller-latency NFR; the split between hot and cold storage exists because of segment 1's retention numbers. A component diagram that isn't traceable back to a requirement is usually just habit.

They have opposite failure and scaling profiles. The assembler needs in-memory state (buffered spans, per-trace, waiting on a decision) and a latency-sensitive decision loop. The storage writer needs durability and scales cleanly by write volume once the decision is already made. What coupling them would actually break: a storage slowdown would backpressure the assembler's memory buffer directly, turning a durability problem into a memory-exhaustion problem. And a stuck decision loop (a sampler bug) would block writes for traces that had nothing to do with it. Separating them means each can degrade independently without dragging the other down.

Because tracing must never become a source of latency or failure for the real request. The agent absorbs batching, local retry, and backpressure so the SDK's call is a local, fire-and-forget write — not a network call whose failure the business request has to survive. Why this isn't over-engineering: without the agent, a slow or unavailable ingestion gateway directly threatens every traced service's own availability — the exact violation of the segment-1 NFR that tracing exists to observe, not cause.

Why the caller column matters more than it looks: three of these six endpoints are deliberately gated to a human/reviewed caller, not a service or autoscaler — sampling policy, retention policy, and trace purge. That's not caution for its own sake; it's the answer to Q11.

No — and this is a blast-radius question, not an ownership question. Ingest should be scoped narrowly to "can write spans for a given service identity" — high-volume, low-blast-radius-per-call, since a bad ingest call corrupts at most one trace. Sampling-policy and retention-policy need a small, audited operator scope, because one bad policy push can silently blind the entire tracing pipeline for every service at once. Why "blast radius" beats "ownership" as the scoping question: ownership-based thinking asks "who owns this API" and often lands both endpoints under the same "tracing team" scope. Blast-radius thinking asks "what's the worst outcome of a single misused credential" — and that answer is wildly different for these two endpoints even though the same team owns both.

Do the math before assuming yes. ~5k requests/sec platform-wide × ~20 spans/trace ≈ 100k spans/sec pre-sampling. After an effective ~8% keep rate (head sample + guaranteed error/slow retention), you're persisting roughly 8k spans/sec, each maybe 300–500 bytes — call it ~3–4 MB/sec sustained, ~250–350 GB/day before compression. Why this is not a big-data problem: that's a standard time-series / wide-column storage workload, well within what one reasonably-sized cluster handles — not a "we need a custom distributed database" problem. The mistake is sizing for 100% capture of unsampled volume instead of sizing for what actually gets persisted after sampling. Skipping this arithmetic is how teams over-provision storage by an order of magnitude before writing a line of code.

Because they need opposite operational treatment. Policy data is small, low-write, and must be strongly consistent across every instance — a stale policy on one instance means inconsistent decisions for spans of the same trace_id that happen to land differently. In-flight trace buffers are the opposite: large, high-churn, and fine to lose per-instance on crash (worst case: a handful of traces skip tail sampling once). What conflating them costs you: store both the same way and you either over-pay for durability on data that doesn't need it (replicating megabytes of in-flight span buffers), or under-protect the one piece of state that genuinely can't afford to be lost (policy). The right instinct is to ask "what does losing this cost me" separately for every piece of state, not to pick one storage strategy for the whole system.

struct TraceBuffer:
  trace_id, spans: list<Span>, first_seen: ts, root_seen: bool, decided: bool

buffer_map: ConcurrentMap<trace_id, TraceBuffer>   # sharded by hash(trace_id)

on_span_arrival(span):
  buf = buffer_map.get_or_create(span.trace_id)     # atomic
  lock(buf):
    buf.spans.append(span)
    if span.parent_span_id is null: buf.root_seen = true

  if buf.root_seen and span.parent_span_id is null and span.end_ts is set:
    trigger_decision(buf)
  elif now() - buf.first_seen > MAX_TRACE_WINDOW:
    trigger_decision(buf)                            # forced, incomplete trace

trigger_decision(buf):
  lock(buf):
    if buf.decided: return                            # idempotent guard
    buf.decided = true
    keep = evaluate_policy(buf.spans)                 # error? p95+? priority? random%?
    if keep: persist_async(buf.spans)
    buffer_map.remove(buf.trace_id)                   # free memory either way

on_buffer_full(new_trace_id):
  evict_oldest_incomplete_trace()   # forces an early decision — chosen default
  # explicit alternative: reject_new_span(), incrementing a dropped_backpressure counter
  # never: drop silently with no counter at all

Why the guard and the memory-free step are both non-negotiable: without buf.decided, the root-arrival path and the timeout-sweep path can race on the same trace and double-persist or double-apply policy — corrupting the "one coherent decision per trace" guarantee tail sampling exists to provide. And freeing the buffer immediately at decision time, regardless of keep/drop, is what keeps the assembler's memory bound only to undecided traces — anything else is waste sitting in the exact resource this whole design is trying to protect.

There's no free answer here — you have to pick one and make it observable. Silently dropping without a counter is the worst option, because it turns a capacity problem into an invisible data-quality problem nobody can diagnose later. Why forcing an early decision beats outright rejection: a slightly-early, partial-trace decision degrades gracefully — if the error/slow tag has already arrived, that signal is still captured even on a forced decision. Rejecting new spans outright instead creates a hole specifically in the newest traces, which is usually the worse failure mode for an on-call engineer debugging something that just happened.

every TIERING_INTERVAL (e.g. 15 min), per storage shard, independently:

  for trace in shard.traces_older_than(HOT_WINDOW):
    cold_days = retention_policy[trace.flow_tag].cold_days   # e.g. LAMF=90d, default=7d
    move_to_cold(trace)
    mark_purge_after(trace, cold_days)

  for trace in shard.traces_past_purge_date():
    hard_delete(trace)
    emit_audit_log(trace_id, reason="retention_expired")

Why per-flow, not global: retention is a compliance decision, not an infrastructure default — LAMF disbursal and IPO allotment carry real regulatory retention exposure that a blanket "delete after 7 days" would silently violate. A flow-tag lookup means the loop enforces what compliance actually decided, not what the loop's original author guessed was reasonable.

Distributed, per-node local loops. Tiering decisions are purely local — "does this shard have data past its own retention window" needs no cross-node coordination or global ordering at all. Why centralizing here would be a mistake: a central coordinator would just be a single point of failure and a scaling bottleneck for a job that's embarrassingly parallel by nature. Contrast this with sampling-policy distribution (segment 9), which genuinely does need centralized, consistent replication, because a stale policy split across instances actively corrupts decisions — tiering has no equivalent correctness risk from running independently per shard.

RECEIVED_AT_AGENT -> BATCHED -> INGESTED_AT_GATEWAY -> BUFFERED
   -> DECIDED(keep) -> PERSISTED(hot) -> TIERED(cold) -> PURGED
   -> DECIDED(drop) -> [discarded, buffer freed]

Every state has a bounded max-time-in-state.
BUFFERED specifically: forced exit via MAX_TRACE_WINDOW (segment 6),
even if the root span never closes.

Why every state needs this, not just BUFFERED: it's the obvious one to protect because it's stateful and memory-bound, but INGESTED_AT_GATEWAY and TIERED can stall too (a downstream queue backing up, a stuck tiering job) — a state machine is only as safe as its least-protected state, so the discipline has to be applied uniformly, not just where the failure mode is most visible.

BUFFERED. A trace whose root span is delayed, lost, or never sent — a common real failure, since the originating request itself may time out before its own span closes — would otherwise sit in the assembler's memory indefinitely, waiting for a root-close event that never arrives. Why MAX_TRACE_WINDOW is the only real answer: it's the one guarantee that doesn't depend on the failure resolving itself. Every state in a distributed system that can wait on an external event needs exactly this shape of guarantee — "exit after N seconds no matter what" — or a single stuck upstream becomes a slow, silent, unbounded memory leak that's invisible until it isn't.

At every transition that can be retried after a failure without the caller knowing whether it already happened: span ingestion (agent retry on a network blip — dedup on span_id), the DECIDED transition (the buf.decided guard), and the hot-to-cold tier move (a retried partial move must not double-write or leave a trace in two places). Why "everywhere" is too vague to be useful: naming the specific transitions forces you to check each one has an actual guard, rather than asserting idempotency as a general property of the system. A transition without a concrete dedup key or guard is a transition that will corrupt state under retry — in a distributed pipeline that's the normal operating condition, not a rare edge case.

Because the tail-sampling decision needs all of a trace's spans buffered in one place — if span A lands on instance 1 and span B on instance 2, neither instance alone has enough information to decide correctly. Why consistent hashing, not a lookup table: routing by hash(trace_id) mod N at the ingestion gateway guarantees this with zero coordination overhead per request. The real cost only shows up when N changes — a naive rehash on scale-out would instantly split in-flight traces across old and new instance assignments, so scale-out needs a controlled rebalance, not an instant reshuffle.

Assembler buffer memory utilization sustained above ~70% for several minutes, or the backpressure-eviction rate (segment 6's on_buffer_full path) going above zero and staying there. Why this maps to the <5ms NFR specifically: once buffer pressure forces the assembler to do extra work per span — forced evictions, early decisions — that latency budget is the first thing to slip, well before the more obvious CPU or raw throughput metrics move. Scaling on CPU alone would catch the problem too late for a system whose actual constraint is memory-bound state, not compute.

No — and treating them the same is the mistake. Why they need different scaling models: the policy store is small, low-write, and needs strong consistency across every instance (segment 5) — it scales by replication. The assembler scales by partitioning trace_id space across more instances. Conflate the two and a routine policy update ends up needing the same careful, staged rollout as a full instance-count change, when it should be a fast, simple, consistently-replicated push.

HOT / DATA PATH
SDK -> Agent -> Ingestion Gateway -> Assembler(hash(trace_id) routed)
     -> [DECIDED keep] -> Hot Storage -> (tiering loop) -> Cold Storage -> Purge
     -> [DECIDED drop] -> discarded
Hot Storage -> Query Service -> Dashboards / on-call tooling

CONTROL / CONFIG PATH
Operator -> POST /sampling-policy  \
Operator -> POST /retention-policy  >-- Policy Store (replicated, strongly consistent)
                                    /
Policy Store -> pushed/pulled by -> every Assembler instance
Agent -> POST /agent/heartbeat -> Platform Monitoring -> scale-out signal (segment 9)

Why these two paths are drawn separately but must both appear: the hot path is judged by the <5ms and throughput NFRs; the control path is judged by consistency and blast-radius (segment 4/11's authorization reasoning). A design that only ever draws the hot path is a design that's never actually reasoned about how a bad policy push gets safely rolled out — which is usually where the real incidents happen.