Designing a Distributed Tracing System: Span Collection, Sampling Strategies, and Trace Storage at Scale

Most teams consume distributed tracing through a vendor dashboard and never think about what happens below that surface. But if you are building an observability platform, running a multi-tenant SaaS that needs per-customer trace isolation, or operating at a scale where off-the-shelf pricing becomes painful, you need to understand how tracing infrastructure actually works.

This article is about designing the system itself. Not how to add spans to your application code, but how to build the pipeline that collects, samples, and stores billions of spans per day while keeping query latency under two seconds.

The Span Data Model

A trace is a directed acyclic graph of spans. Every span represents a unit of work: an HTTP handler, a database query, a cache lookup. The graph structure is encoded in the span itself rather than computed at write time.

Here is the canonical span structure:

interface Span {
  traceId: string;       // 128-bit identifier, hex-encoded (e.g., "4bf92f3577b34da6a3ce929d0e0e4736")
  spanId: string;        // 64-bit identifier (e.g., "00f067aa0ba902b7")
  parentSpanId?: string; // absent on root spans
  operationName: string; // "http.server", "db.query", "cache.get"
  serviceName: string;
  startTimeUnixNano: bigint;
  durationNano: bigint;
  status: "ok" | "error" | "unset";
  attributes: Record<string, string | number | boolean | string[]>;
  events: SpanEvent[];   // timestamped annotations within the span
  links: SpanLink[];     // references to other traces (fan-in patterns)
  resource: Resource;    // host, k8s pod, deployment env
}

interface SpanEvent {
  name: string;
  timeUnixNano: bigint;
  attributes: Record<string, string | number | boolean>;
}

interface SpanLink {
  traceId: string;
  spanId: string;
  attributes: Record<string, string | number | boolean>;
}

interface Resource {
  attributes: Record<string, string>;
  // e.g., "service.name", "host.name", "k8s.pod.name", "deployment.environment"
}

A few design decisions embedded in this model are worth calling out. The traceId is 128 bits rather than 64 to reduce collision probability at scale. A 64-bit ID space has a 1% collision risk at around 600 million traces; 128 bits pushes that boundary far past any realistic volume. The parentSpanId is optional and absent on root spans, which means the tree can be reconstructed at read time by grouping all spans that share a traceId and then building the parent-child relationships. The resource block is separated from span-level attributes because resource attributes (host, pod, service version) are stable across all spans from a given process, so they can be deduplicated during compression.

Context Propagation Internals

For a trace to be coherent across service boundaries, every outbound call must carry the current trace context. The W3C Trace Context specification defines two HTTP headers for this: traceparent and tracestate.

The traceparent header encodes four fields in a fixed format:

traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
             ^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^
             version  traceId (32 hex chars)     spanId (16 hex)  flags

The flags byte currently has one meaningful bit: the sampled flag (bit 0). When this bit is set, the downstream service knows the trace is being recorded. When it is clear, the downstream service knows it can skip instrumentation overhead. This is load-bearing for head-based sampling.

Building your own propagator in TypeScript looks like this:

const TRACEPARENT_HEADER = "traceparent";
const VERSION = "00";

function injectContext(span: Span, headers: Record<string, string>, sampled: boolean): void {
  const flags = sampled ? "01" : "00";
  headers[TRACEPARENT_HEADER] =
    `${VERSION}-${span.traceId}-${span.spanId}-${flags}`;
}

function extractContext(headers: Record<string, string>): TraceContext | null {
  const header = headers[TRACEPARENT_HEADER];
  if (!header) return null;

  const parts = header.split("-");
  if (parts.length < 4) return null;

  const [version, traceId, spanId, flags] = parts;
  if (version !== VERSION) return null;
  if (traceId.length !== 32 || spanId.length !== 16) return null;

  return {
    traceId,
    parentSpanId: spanId,
    sampled: (parseInt(flags, 16) & 0x01) === 1,
  };
}

interface TraceContext {
  traceId: string;
  parentSpanId: string;
  sampled: boolean;
}

The critical invariant: every child span must carry the same traceId as its parent. If a service fails to propagate context (async queues are a common failure point), the trace breaks into disconnected fragments. Message queue payloads need to embed trace context in message headers or metadata, not just in HTTP headers.

Sampling Strategies

At 10,000 requests per second, storing every span is expensive. A trace with 50 spans at 2KB average size generates 1GB per second of raw data. You need to shed load without making traces useless for debugging. Two primary strategies exist, and they have fundamentally different tradeoffs.

Head-Based Sampling

The sampling decision is made at the root span, before downstream spans are created. The decision propagates via the sampled flag in traceparent. If a trace is not sampled, no spans in the entire call graph are collected.

interface HeadSampler {
  shouldSample(traceId: string, operationName: string): boolean;
}

class RateLimitedSampler implements HeadSampler {
  private readonly maxPerSecond: number;
  private count = 0;
  private windowStart = Date.now();

  constructor(maxPerSecond: number) {
    this.maxPerSecond = maxPerSecond;
  }

  shouldSample(traceId: string, operationName: string): boolean {
    const now = Date.now();
    if (now - this.windowStart >= 1000) {
      this.count = 0;
      this.windowStart = now;
    }
    if (this.count >= this.maxPerSecond) return false;
    this.count++;
    return true;
  }
}

class ProbabilisticSampler implements HeadSampler {
  constructor(private readonly rate: number) {}

  shouldSample(traceId: string): boolean {
    // Use the traceId itself as the random source for consistency
    // across services: same traceId always makes the same decision
    const value = parseInt(traceId.slice(0, 8), 16) / 0xffffffff;
    return value < this.rate;
  }
}

Head-based sampling is simple and low-overhead because unsampled traces generate zero spans. The problem: you make the decision before you know whether the trace is interesting. A 1% sample rate means 99% of all 5xx errors, slow queries, and edge cases are discarded.

Tail-Based Sampling

The sampling decision is deferred until the trace is complete. You buffer all spans in memory, wait for the root span to close (signaling trace completion), then decide whether to keep or drop the entire trace based on what actually happened.

interface TailSamplingPolicy {
  evaluate(spans: Span[]): "keep" | "drop";
}

class ErrorOrSlowPolicy implements TailSamplingPolicy {
  constructor(
    private readonly slowThresholdMs: number,
    private readonly errorSampleRate: number
  ) {}

  evaluate(spans: Span[]): "keep" | "drop" {
    const hasError = spans.some((s) => s.status === "error");
    const rootSpan = spans.find((s) => !s.parentSpanId);
    const durationMs = rootSpan
      ? Number(rootSpan.durationNano) / 1_000_000
      : 0;

    if (hasError) {
      // Sample errors at a configurable rate to avoid error storms flooding storage
      return Math.random() < this.errorSampleRate ? "keep" : "drop";
    }

    if (durationMs > this.slowThresholdMs) return "keep";

    // Drop fast, successful traces at a high rate
    return Math.random() < 0.01 ? "keep" : "drop";
  }
}

class TraceBuffer {
  private readonly spans = new Map<string, Span[]>();
  private readonly timers = new Map<string, ReturnType<typeof setTimeout>>();
  private readonly policy: TailSamplingPolicy;
  private readonly ttlMs: number;

  constructor(policy: TailSamplingPolicy, ttlMs = 30_000) {
    this.policy = policy;
    this.ttlMs = ttlMs;
  }

  ingest(span: Span, onFlush: (spans: Span[]) => void): void {
    const existing = this.spans.get(span.traceId) ?? [];
    existing.push(span);
    this.spans.set(span.traceId, existing);

    // Reset TTL on each span arrival
    const existing_timer = this.timers.get(span.traceId);
    if (existing_timer) clearTimeout(existing_timer);

    const timer = setTimeout(() => {
      this.flush(span.traceId, onFlush);
    }, this.ttlMs);

    this.timers.set(span.traceId, timer);
  }

  private flush(traceId: string, onFlush: (spans: Span[]) => void): void {
    const spans = this.spans.get(traceId) ?? [];
    this.spans.delete(traceId);
    this.timers.delete(traceId);

    const decision = this.policy.evaluate(spans);
    if (decision === "keep") onFlush(spans);
  }
}

Tail-based sampling requires buffering all spans until the trace is complete. This creates real memory pressure. A 30-second buffer TTL for traces that involve long-running background jobs means your collector nodes need significant heap. The standard architecture uses a consistent hash on traceId to route all spans of a given trace to the same collector node, so the buffer is local and never needs to be distributed.

The tradeoff is latency: you cannot query a trace until it has been flushed from the buffer.

Tradeoffs: Head vs. Tail Sampling

Dimension	Head-Based	Tail-Based
Decision latency	Immediate	After trace completion (seconds)
Memory footprint	Minimal	High (all in-flight spans buffered)
Error capture rate	Proportional to sample rate	Near 100% with correct policy
Collector complexity	Stateless	Stateful, requires consistent routing
Implementation risk	Low	High (buffer management, TTL tuning)
Cost	Low	Medium-High (collector fleet must handle peak load)

Many production systems combine both: apply a high head-based rate (keep 10% of all traces) and then apply tail-based policies on top of that subset to guarantee error and latency coverage. This bounds memory at the cost of some tail-sampling fidelity.

Trace Storage Backends

Once spans are sampled, they need to be stored in a way that supports two very different query patterns: trace lookup by ID (point query) and trace search (aggregation across millions of spans).

Columnar Storage for Span Search

Searching for “all traces from service X where duration > 500ms and status = error in the last hour” is a scan over a large dataset with high-selectivity filters. This maps naturally to a columnar storage format like Apache Parquet or a columnar database.

In a columnar store, each attribute is stored as a separate column. Queries that filter on service.name and status only read those two columns, skipping the rest of the row data. Predicate pushdown and dictionary encoding (replacing repeated string values like service names with integer codes) reduce I/O dramatically.

The schema design challenge is that span attributes are arbitrary key-value pairs. You cannot pre-define a column for every possible attribute key. The standard approach is a two-tier schema: fixed columns for the high-cardinality fields that every span has (traceId, spanId, serviceName, durationNano, status, startTime), and a serialized blob column for the full attribute map.

interface SpanRow {
  // Fixed columns - directly queryable
  traceId: string;
  spanId: string;
  parentSpanId: string | null;
  serviceName: string;
  operationName: string;
  startTimeUnixNano: bigint;
  durationNano: bigint;
  statusCode: 0 | 1 | 2; // unset, ok, error
  httpStatusCode: number | null;
  dbSystem: string | null;
  // ... other promoted attributes

  // Serialized blob - requires full scan of this column to filter
  attributes: Uint8Array; // protobuf or msgpack encoded
}

Promoted attributes (those extracted into dedicated columns) must be chosen carefully. Every attribute you promote increases storage width and write amplification. Choose based on actual query patterns. HTTP status code, database system, and peer service name are good candidates. Custom business attributes are not.

Time-Series Storage for Trace Lookup

Point lookups by traceId need a different index. A common pattern is to store a (traceId, startTime) -> storageKey mapping in a fast key-value store (Cassandra, DynamoDB, or a dedicated index). The storageKey points to the object storage location where the full trace is serialized.

The time dimension in the index key allows efficient range scans: “all traces starting in the last hour” becomes a range scan on the partition rather than a full table scan.

Primary index: (traceId) -> (objectStorageKey, startTime)
Time index:    (serviceName, startTimeHour) -> [traceId, ...]
Error index:   (serviceName, startTimeHour, status=error) -> [traceId, ...]

These secondary indexes are written asynchronously from the main span ingestion path to avoid adding write latency. The tradeoff is eventual consistency: a trace may not appear in the search index for a few seconds after ingestion.

Query Patterns and Their Implementation

Trace queries fall into three categories:

Trace-by-ID: Direct lookup using the primary index. Retrieve the serialized trace blob from object storage. Under 100ms is achievable with a warm cache layer in front of object storage.

Filtered search: “Show me traces from payment-service where duration > 1s in the last 30 minutes.” This requires a scan of the columnar store against the promoted columns. Partitioning data by time (hourly or daily) bounds the scan to a small number of files. A query planner can prune partitions outside the time range before reading any span data.

Dependency graphs: “What services did this trace touch?” Reconstruct from the spans collected under a single traceId. This is a local join within the columnar store after fetching all rows for a given traceId.

The hardest query is the cross-service fanout search: “Find all traces that touched service A and then called service B and resulted in an error at service C.” This requires joining spans within a trace, which is expensive in a pure columnar format. Precomputed trace summaries (one row per trace, with arrays of service names touched, max duration, error flag) are written at flush time to answer this class of query without loading full span data.

Production Considerations

Backpressure on the collector. Your application instrumentation should use a non-blocking span exporter. If the collector is slow or unavailable, spans should be dropped rather than blocking the application thread. A bounded in-process queue with a drop policy on overflow is the correct default.

class BoundedSpanQueue {
  private readonly queue: Span[] = [];
  private readonly maxSize: number;
  private dropped = 0;

  constructor(maxSize = 10_000) {
    this.maxSize = maxSize;
  }

  enqueue(span: Span): boolean {
    if (this.queue.length >= this.maxSize) {
      this.dropped++;
      return false;
    }
    this.queue.push(span);
    return true;
  }

  drainBatch(size: number): Span[] {
    return this.queue.splice(0, size);
  }

  get droppedCount(): number {
    return this.dropped;
  }
}

Expose droppedCount as a metric. A spike in drop rate is an early signal that your collector fleet is undersized.

Clock skew between services. Spans from different hosts have timestamps that may differ by milliseconds. Never reconstruct parent-child ordering based on start time alone. Always use parentSpanId. When rendering a trace waterfall, use relative offsets from the root span’s start time, not wall-clock times.

Cardinality explosion in attribute keys. Dynamic attribute keys (user IDs embedded in attribute names, URL templates with path params) will destroy the columnar storage schema. Enforce a schema validation step in the collector that rejects or sanitizes spans with high-cardinality keys. The span attribute http.url should store /users/{id}, not /users/12345678.

TTL and retention tiers. Recent traces (last 24-48 hours) need fast query access. Older traces are rarely accessed. A two-tier architecture with hot storage (columnar database in SSD-backed nodes) and cold storage (compressed Parquet files in object storage) reduces cost by 70-80% at the expense of slower cold queries. Implement an automatic migration job that moves traces older than 48 hours to the cold tier.

Putting It Together

The complete pipeline looks like this. Application SDK generates spans and enqueues them in a bounded local buffer. A background exporter flushes batches over gRPC to a collector fleet. The collector runs tail-based sampling, routing spans by traceId via consistent hash. After the trace TTL expires, the collector evaluates the sampling policy, serializes the kept spans, and writes them to three places: the columnar span store (for search), the object store (for trace-by-ID retrieval), and the secondary indexes (for service-level aggregations). A query tier sits in front of these stores, routing requests to the appropriate backend based on query type.

The system works because each layer does one thing well. The SDK is stateless and non-blocking. The collector is stateful only for buffering in-flight traces. The storage layer is optimized for its specific access pattern. The query tier is the only place that has a view across all backends.

The hardest part of operating this at scale is not the data path. It is schema evolution: adding a new promoted attribute column means backfilling historical data or accepting a split schema where old queries return incomplete results. Define your promoted column schema conservatively and treat additions as a schema migration, not a config change.

Tracing infrastructure is one of those systems where the first version is fast to build and the production version takes months to harden. The data model is simple. The operational challenges around cardinality, memory pressure during traffic spikes, and query performance at billion-span scale are where the real engineering lives.