Distributed Tracing Explained: Trace IDs, Spans and Sampling

A dashboard says the search page got slow. Five services touch every search request, each keeps its own logs, and none can tell you where the time went. Distributed tracing answers exactly that: for one request, which hop spent the time. This article covers the machinery that makes a trace exist, the ids in the headers and the collector that stitches spans together, and what happens when either breaks. How tracing fits next to metrics and logs is in observability explained.

The problem it solves

Each service sees only its own slice of a request. Matching slices by timestamp fails under real traffic: thousands of requests overlap every second, and server clocks disagree. You need a label that travels with the request, and a record of who called whom, so the slices form a tree rather than a pile.

The intuition

• A span is one timed piece of work: a name, a start, a duration, its own id, and the id of its parent span.
• A trace is every span sharing one trace id. The gateway mints it when the request arrives, and opens the root span.
• Propagation: every outbound call carries the trace id and the caller's span id in a header. The callee makes its span a child of that id and passes its own id on to its callees.
• The collector receives spans from every service, groups them by trace id and rebuilds the tree from parent ids.

As of October 2026, the usual header is the W3C Trace Context traceparent: a version, a 32-hex-digit trace id, the 16-hex-digit parent span id and a flags byte whose lowest bit means "sampled", with all-zero ids treated as invalid (from memory). OpenTelemetry implements it, and it is the default in many tracing setups.

Two consequences follow. A service that drops the header causes no error; it silently starts a new trace. And since every span costs money, almost everyone samples: head sampling decides at the root and passes the decision along in that flag; tail sampling decides after the trace ends.

Watch it run

The animation is a waterfall: a lane per service, columns in milliseconds. A dashboard says the search page got slow, p99 at 120 ms; a trace says which hop did. The gateway opens the root span and mints trace id 7f0a, and everything else hangs off this one box. The id rides along in the headers of every outbound call, now with the root as parent, and the search span starts, 40 ms wide. Search calls the store for 10 ms, and that span is a child of search, not of the gateway: depth three. Search finishes and the ranker starts, 30 ms; sequential, so the widths add up. The gateway makes one last store read, and the request comes back: five spans. Read as a tree, the gateway's direct children account for 80 ms of the root's 120. The missing 40 ms is the finding: queueing, serialization or a lock, time nobody put a span around. Then the bill. This picture only exists if the request was sampled, and head sampling decides at step two, keeping 1 in 100. Tail sampling keeps the slow ones instead, and pays by buffering every span until the trace ends.

The code

A toy model. First the header: build it, parse it, and reject one that is malformed or all zeros. The ids are the specification's own example values:

import random
import re

HEADER = re.compile(r"^([0-9a-f]{2})-([0-9a-f]{32})-([0-9a-f]{16})-([0-9a-f]{2})$")

def inject(trace_id, span_id, sampled):
    return {"traceparent": "00-%s-%s-%s" % (trace_id, span_id, "01" if sampled else "00")}

def extract(headers):
    """Trace id, parent span id and sampled flag, or None for a missing or invalid header."""
    m = HEADER.match(headers.get("traceparent", ""))
    if not m:
        return None
    version, trace_id, parent_id, flags = m.groups()
    if version == "ff" or set(trace_id) == {"0"} or set(parent_id) == {"0"}:
        return None
    return trace_id, parent_id, int(flags, 16) & 1 == 1

h = inject("4bf92f3577b34da6a3ce929d0e0e4736", "00f067aa0ba902b7", True)
print(h["traceparent"])     # 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
print(extract(h))           # ('4bf92f3577b34da6a3ce929d0e0e4736', '00f067aa0ba902b7', True)
print(extract({"traceparent": "00-" + "0" * 32 + "-00f067aa0ba902b7-01"}), extract({}))  # None None

Now services. Each one extracts the context from its incoming headers, records a span, and returns the headers its own calls must carry. No context means a new trace, and that is where head sampling rolls its dice. request replays the animation's timings; lost names a hop whose caller forgot the header:

class Tracer:
    def __init__(self, seed, one_in=1):
        self.rng, self.one_in, self.spans = random.Random(seed), one_in, []

    def span(self, service, headers, start, end):
        ctx = extract(headers)
        if ctx is None:                        # no context arrived: start a brand-new trace
            sampled = self.rng.randrange(self.one_in) == 0      # head sampling decides here
            ctx = ("%032x" % self.rng.getrandbits(128), None, sampled)
        trace_id, parent, sampled = ctx
        span_id = "%016x" % self.rng.getrandbits(64)
        self.spans.append({"trace": trace_id, "id": span_id, "parent": parent, "kept": sampled,
                           "service": service, "start": start, "end": end})
        return inject(trace_id, span_id, sampled)   # the headers for this span's own calls

def request(tracer, t0=0, slow=0, lost=()):
    """The animation's request: 120 ms at the gateway, four calls made inside it."""
    send = lambda callee, h: {} if callee in lost else h      # a hop that drops the header
    gw = tracer.span("gateway", {}, t0, t0 + 120 + slow)
    search = tracer.span("search", send("search", gw), t0 + 10, t0 + 50)
    tracer.span("store", send("store", search), t0 + 20, t0 + 30)
    tracer.span("ranker", send("ranker", gw), t0 + 50, t0 + 80)
    tracer.span("store", send("store", gw), t0 + 80, t0 + 90)

The collector groups by trace id, finds each root, rebuilds the tree, and reports the root time no child covers:

def uncovered(span, kids):
    """Root time that no child covers: time nobody put a span around."""
    covered, reach = 0, span["start"]
    for k in sorted(kids, key=lambda k: k["start"]):
        s, e = max(k["start"], reach), min(k["end"], span["end"])
        if e > s:
            covered, reach = covered + e - s, e
    return span["end"] - span["start"] - covered

def collect(spans, show=True):
    """Group spans by trace id and rebuild each tree from the parent ids."""
    traces = {}
    for s in spans:
        traces.setdefault(s["trace"], []).append(s)
    out = []
    for group in traces.values():
        ids = {s["id"] for s in group}
        kids = {s["id"]: [k for k in group if k["parent"] == s["id"]] for s in group}
        root = min((s for s in group if s["parent"] not in ids), key=lambda s: s["start"])
        out.append((root, kids, len(group)))
        def draw(s, depth):
            print("  " * depth + "%s %d-%d" % (s["service"], s["start"], s["end"]))
            for k in sorted(kids[s["id"]], key=lambda k: k["start"]):
                draw(k, depth + 1)
        if show:
            draw(root, 0)
            print("  uncovered: %d ms" % uncovered(root, kids[root["id"]]))
    return out

whole = Tracer(17)
request(whole)
collect(whole.spans)
# gateway 0-120
#   search 10-50
#     store 20-30
#   ranker 50-80
#   store 80-90
#   uncovered: 40 ms

broken = Tracer(17)
request(broken, lost={"ranker"})
collect(broken.spans)
# gateway 0-120
#   search 10-50
#     store 20-30
#   store 80-90
#   uncovered: 70 ms
# ranker 50-80
#   uncovered: 30 ms

The broken run is the dangerous one. Nothing failed: the ranker's 30 ms simply left the trace, so the gateway seems to have wasted 70 ms itself, and the investigation goes to the wrong service. Next, sampling over 20,000 requests, 0.5% of them slow. Head sampling at 1 in 100 keeps 2 of the 98 slow traces; a tail rule, "keep anything over 200 ms", keeps all 98. The price is memory: every span is held until its root ends, plus a wait for late spans:

rng = random.Random(7)
head, tail = Tracer(1, one_in=100), Tracer(1)
for i in range(20_000):
    slow = rng.choice([0] * 199 + [400])                # 0.5% of requests are slow
    request(head, t0=i * 5, slow=slow)
    request(tail, t0=i * 5, slow=slow)

def kept_slow(traces, keep):
    return sum(r["end"] - r["start"] > 200 and keep(r) for r, _, _ in traces)

head_traces, tail_traces = collect(head.spans, False), collect(tail.spans, False)
slow_total = kept_slow(tail_traces, lambda r: True)
print(slow_total, kept_slow(head_traces, lambda r: r["kept"]),
      kept_slow(tail_traces, lambda r: r["end"] - r["start"] > 200))     # 98 2 98

def peak_buffered(spans, wait_ms):
    """Tail sampling holds every span until its trace's root ends, plus a wait."""
    root_end = {s["trace"]: s["end"] for s in spans if s["parent"] is None}
    events = sorted([(s["start"], 1) for s in spans] +
                    [(root_end[s["trace"]] + wait_ms, -1) for s in spans])
    level = peak = 0
    for _, step in events:
        level += step
        peak = max(peak, level)
    return peak

print(peak_buffered(tail.spans, 0), peak_buffered(tail.spans, 10_000))   # 103 10103

The seeded check: 400 random call trees where one call in five loses its header. Traces must number one plus the lost hops, linked spans must point at their real caller, uncovered time must match a millisecond count, each trace must share one sampling decision, and headers must round-trip:

ok = True
for seed in range(400):
    r = random.Random(seed)
    tracer = Tracer(seed, one_in=r.choice([1, 2, 3]))
    calls, lost, made = [(None, "s0", 0, r.randint(5, 60))], set(), {}
    for caller, name, start, end in calls:              # the list grows while we walk it
        if caller is not None and r.random() < 0.2:
            lost.add(name)
        made[name] = tracer.span(name, {} if caller is None or name in lost else made[caller],
                                 start, end)
        for j in range(r.randint(0, 3) if len(calls) < 12 else 0):
            s = r.randint(start, end - 1)
            calls.append((name, "%s.%d" % (name, j), s, r.randint(s + 1, end)))
    spans = {s["service"]: s for s in tracer.spans}
    trees = collect(tracer.spans, show=False)
    ok &= len(trees) == 1 + len(lost)
    for caller, name, _, _ in calls[1:]:
        s, c = spans[name], spans[caller]
        ok &= (s["parent"] is None) if name in lost else (s["parent"] == c["id"] and s["trace"] == c["trace"])
    for root, kids, _ in trees:
        mine = kids[root["id"]]
        ok &= uncovered(root, mine) == sum(
            not any(k["start"] <= ms < k["end"] for k in mine) for ms in range(root["start"], root["end"]))
        ok &= len({s["kept"] for s in tracer.spans if s["trace"] == root["trace"]}) == 1
    tid, sid = "%032x" % r.getrandbits(128), "%016x" % r.getrandbits(64)
    ok &= extract(inject(tid, sid, seed % 2 == 0)) == (tid, sid, seed % 2 == 0)
print(ok)                                           # True

The complexity

• Per request: one span per instrumented operation, a few hundred bytes each, plus one small header per call.
• Collector, head sampling: work proportional to the kept fraction of traffic; the decision costs nothing.
• Collector, tail sampling: memory proportional to request rate × spans per trace × (trace duration + wait), as the 103 versus 10,103 spans above show.

Where it goes wrong

• A hop that drops the header. Async queues, thread pools and hand-written HTTP clients are the usual leaks; put the context in message metadata too.
• Trusting timestamps across hosts. Clock skew can draw a child starting before its parent.
• Head sampling for rare failures. It keeps 1 in 100 of the slow requests you wanted, too.
• Unbounded tail buffers. Cap the wait and the memory, and decide what happens to late spans.
• Missing spans around waits. Pool checkouts and queue time stay unexplained gaps until someone instruments them.

When it shows up in interviews

As "how would you debug a slow request across microservices?", and as a follow-up in any design with several services. Expect: how the trace id propagates, how spans form a tree, head versus tail sampling, and why a gap in the waterfall is itself a finding. The AWS flavour is in CloudWatch and X-Ray.

How to say it in an interview

"The gateway opens a root span and mints a trace id. Every outbound call carries the trace id and the caller's span id in a header, usually W3C traceparent; each service records spans with a parent id and ships them to a collector, which groups by trace id and rebuilds the tree. I read the waterfall for the widest span and for gaps no child covers, which are untracked waits. Head sampling is cheap but misses rare slow requests; tail sampling keeps errors and slow traces but buffers spans until each trace completes. And queues and async hops must propagate the context, because a lost header silently splits the trace."