Storing Traces: Two Access Patterns That Cannot Share One Index

A trace store is asked two questions that pull its design in opposite directions. The first is “show me this trace”, issued with a 32-character identifier copied out of a log line, and it must return within a second or two. The second is “show me the slowest requests to the payments service in the last hour”, issued with a time range, a service name, and a duration threshold, and it must scan a large amount of data without returning everything. A schema built for one answers the other badly, and the interesting engineering is in how the two are reconciled.

Point lookup: the traces-first layout

The first access pattern is the one that makes tracing different from a log store. Logs are queried by time range and content; traces are queried by identifier. A user arrives at a trace from a log line, an alert, or a metric exemplar, holding one identifier and expecting the whole trace.

The layout that serves this well writes all the spans of a trace together, physically adjacent, keyed by the trace identifier. A write path that buffers spans per trace and flushes a complete trace as one unit makes the read a single sequential range scan. The identifier is the primary key, so the lookup is a point query regardless of how many spans the trace contains.

The complication is that spans arrive over time and out of order, as described in the span model. A trace’s spans are written by many hosts, each with its own clock, and they arrive at the store over a period that may be seconds for a synchronous request and hours for a queue-backed workflow. Writing them contiguously requires either waiting for the trace to complete, which delays availability by the size of the collection window, or writing incrementally and merging later, which costs a rewrite.

The usual compromise is to batch on a time window rather than on trace completion. Spans are accumulated for a few seconds, grouped by trace identifier within the batch, and written as runs. A trace spanning several batch windows is stored as several runs, and a read must merge them. The merge is cheap because the runs are few and the identifier is known, and the cost is that a point lookup touches several small ranges instead of one large one. This is the same trade a log-structured merge store makes between write amplification and read amplification, and it can be tuned by the same knobs: a larger batch reduces the number of runs and increases the write latency.

Range search: the spans-first layout

The second access pattern filters on span attributes: service name, operation name, duration, status, and a small set of user-selected tags. This is a scan with predicates, and the layout that serves it is columnar, storing each attribute in its own column so that a query touching three attributes reads three columns rather than the whole record.

Columnar layout also makes compression effective. Duration values in a column are numerically similar, so delta or frame-of-reference encoding compresses them well. Service names are drawn from a small set, so dictionary encoding reduces them to small integers. Trace identifiers are high-entropy, compress poorly, and are the reason a columnar trace store is usually larger than a metrics store with comparable row counts.

The predicate that dominates is the time range, because almost every query is scoped to one. Partitioning by time is therefore automatic in every implementation: a directory per hour or per day, or a partition key in a distributed table. Within a partition, the ordering that helps most depends on the query mix. Sorting by service and then by start time turns a service-scoped query into a contiguous scan. Sorting by duration turns a percentile query into a scan of the tail, since the longest spans are at one end. Neither ordering can be primary, which is why real systems maintain several sort orders or several projections of the same data, and pay the write amplification.

The duration index has a property worth noting because it is often misunderstood. A trace’s duration is not the duration of any of its spans for a query that asks for slow traces: the trace’s total latency is the root span’s duration. Filtering on the maximum span duration instead of the root duration finds traces that contain one slow internal call, which is a different and also useful question. Storing the root duration as a denormalised field on every span, so that a scan of any partition can filter on it without assembling the trace, is the standard solution.

Joining the two

The gap between the two layouts is bridged by a secondary index. A point lookup needs to find, given a trace identifier, which time partitions contain its spans. The index is a mapping from identifier to partition, either a global structure or a per-partition bloom filter over the identifiers present.

Bloom filters are attractive because they are small and can be kept per column chunk rather than per partition. A query for a specific identifier checks the filter for each candidate partition and skips the ones that certainly do not contain it. The false positive rate is a function of the number of bits per key; at ten bits per key it is around one percent, and the resulting wasted reads are acceptable. The gain is that a lookup touches only the partitions that can contain the trace, instead of scanning every partition in the retention window.

The index does not have to be exact, and this is the key insight that keeps it cheap. A false positive costs a read that finds nothing. Only a false negative, which would hide a span that is actually present, is a correctness problem, and a Bloom filter cannot produce one. Since the identifier is high-entropy and the number of distinct identifiers per partition is large, the filter’s size scales with span count rather than with identifier count, and the bits per key is the only tunable.

Retention and the cost cliff

Traces are voluminous and their value decays. The retention policy is therefore a cost decision with a functional consequence, and the consequences are worth being explicit about.

Deleting by age is the standard policy, and it is the one that interacts worst with the point lookup. A trace whose spans straddle a retention boundary has part of its data deleted while the rest survives, producing a trace that is stored, retrievable, and structurally incomplete. The reader has no way to distinguish “this span was never recorded” from “this span was deleted”, which is the same ambiguity that sampling decisions create when the flag is not propagated. Retention should be applied at trace granularity, not span granularity, which means the retention boundary is approximated by the start time of the trace and the deletion is per-partition, and the tail of a partition is retained slightly longer than its nominal age.

A second policy is sampling by age: keep everything for a short window and a small sample beyond it. This reduces cost while preserving the ability to answer aggregate questions over older data, at the price of the same inverse-probability correction that any sampled store needs. The sampling probability must be stored per trace, as with head-based sampling, or the older data cannot be reweighted.

The third is tiering. Recent data lives in a store that supports the range queries described above, and older data moves to object storage in a columnar format. Object storage is cheap and slow, with the extra latency of a request per object and no index beyond what the writer produced. A trace in the cold tier is retrievable by identifier if the writer produced an index mapping identifiers to object keys, which is exactly the Bloom-filter-per-chunk structure described earlier, materialised as a file. Without that index, a cold trace is only reachable by listing and scanning, which is impractical at any real volume. The migration itself is the same problem a log-structured file system solves by writing new segments rather than modifying existing ones: rewriting a partition in place to compact or tier it is far more expensive than writing a new representation and dropping the old.

What the schema cannot avoid

Two properties of tracing defeat any attempt at a compact schema.

The first is that span counts are heavy-tailed. A trace of an HTTP request has a few dozen spans; a trace of a batch job has millions. A store that allocates per-trace metadata in proportion to the average trace size underestimates the large ones badly, and a store that allocates for the worst case wastes space on everything else. Chunked storage with per-chunk metadata and a limit on chunk size is the pragmatic answer, and it makes a very large trace a sequence of chunks rather than one oversized record.

The second is that attribute keys and values are user-controlled. A schema that indexes every attribute value pays for the ones nobody queries, and a schema that indexes none cannot answer the queries users actually have. The common arrangement is a fixed set of indexed keys, chosen from the attribute conventions, plus an opt-in mechanism for specific keys, with everything else stored and only filterable after retrieval. The size of that set is the direct cost: indexing ten keys rather than one multiplies the index a query must read, and none of the ten helps unless the query filters on it. The list of indexed keys then becomes a piece of operational configuration that has to be planned against the query mix and changed rarely, because rebuilding the index is a full pass over the data.

Neither limitation is fatal, and both indicate the same thing: a trace store is a specialised database whose schema is a compromise between two access patterns that will not unify. The measurements that decide the compromise are the ratio of point lookups to range queries and the distribution of trace sizes, both of which change as the organisation’s usage changes. Revisiting the layout when those numbers move is the maintenance a trace store actually requires, and it is cheaper than either extreme: an identifier-keyed store that cannot answer aggregate queries, or a span-indexed store that cannot return one trace promptly.