A distributed trace is a tree of spans. Each span records one operation: service name, operation name, start time, duration, tags (key-value pairs), and parent span ID. Storing traces so that you can find “all traces for user 12345 that had errors in the payment service last hour” requires a storage design that supports multiple query patterns simultaneously on append-heavy write load.

The Write Pattern#

Spans arrive as a stream: millions per second in a large system (after sampling). Writes are append-only: spans are never updated. The write path must handle high throughput with low latency, since spans should be searchable within seconds of being created.

Columnar storage is the right fit. Spans have a fixed schema: trace_id, span_id, parent_span_id, service, operation, start_time, duration_ms, error, tags. A columnar store (Cassandra, ClickHouse, Apache Parquet on S3) compresses repeated values efficiently and supports aggregation queries without reading all columns.

Query Patterns#

Trace lookup by ID: “show me trace abc123.” Direct key lookup. O(1) in a column family keyed by trace_id.

Service error rate: “what fraction of spans from payment-service had errors in the last hour?” Aggregate query over the error and service columns filtered by time range. Efficient in a columnar store with time-partitioned data.

Dependency graph: “which services called payment-service in the last day?” Aggregate over (parent service, child service) extracted from parent_span_id joins. Requires either a precomputed dependency index updated from the span stream or a join-heavy query.

Latency distribution: “show me the p99 latency for checkout operations.” Aggregate over duration_ms filtered by operation name.

graph TD A[Span arrives: trace_id, service, duration, error] --> B[Write to columnar store, partitioned by time] B --> C[Trace index: trace_id to shard mapping] C --> D[Query 1: GET trace abc123 - key lookup] C --> E[Query 2: error rate by service - column scan + aggregate] C --> F[Query 3: p99 latency for checkout - column scan + percentile] D --> G[Result: full trace tree reconstructed] E --> H[Result: payment-service error rate = 0.4%] F --> I[Result: p99 = 340ms] style A fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style B fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style C fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style D fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style E fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style F fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style G fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style H fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff style I fill:#000000,stroke:#00ff00,stroke-width:2px,color:#fff

Tag Indexing#

Tags carry arbitrary key-value pairs: user_id=12345, order_id=abc, region=us-east. Querying “all traces for user 12345” requires an index on tag values. Full inversion of all tags is expensive: a span with 20 tags would create 20 index entries.

Selective indexing: index only high-cardinality tags that are commonly queried (user_id, order_id, request_id). Low-cardinality tags (region, environment) can be filtered post-scan. Jaeger uses this pattern with Elasticsearch for tag indexing.

Retention and Tiering#

Traces are most valuable in the first hour (debugging active incidents). Less valuable after a day. Near-useless after a week (except for audit purposes). Tier storage accordingly: hot storage (fast SSD) for the last 24 hours, warm storage for 7 days, cold storage (S3) for 30 days. Drop after 30 days unless sampled for long-term retention.

At Salesforce#

Salesforce’s distributed tracing infrastructure stored spans in Cassandra, partitioned by (service, date). Lookup by trace ID required a secondary index that mapped trace IDs to the service and date needed to find the partition. This worked but the secondary index became a hot partition for high-volume services. We moved trace ID indexing to a separate Redis layer with 48-hour TTL, routing trace lookups through Redis before hitting Cassandra. Lookup latency dropped from 800ms to 12ms.

What I’m Learning#

Trace storage is a time-series-adjacent problem with an additional requirement: reconstructing the tree structure from individual span records. Columnar storage handles the aggregation queries; a separate index handles the trace-by-ID lookup. Getting both right with acceptable write throughput is the design challenge.

What trace storage backend have you used in production, and where did it break down at scale?