Routing Traces Through a Collector Pipeline by Trace ID

The front of a telemetry pipeline is stateless by design. A receiver accepts spans, batches them, and forwards them; any instance can handle any span, so a load balancer can spread connections evenly and an instance can be replaced without coordination. That property holds until a stage needs to see a whole trace at once. At that point the pipeline acquires state, and the routing of spans stops being a load-balancing problem and becomes a partitioning problem.

The stage that breaks the assumption

Tail-based sampling is the canonical stateful stage: it holds spans in memory until a trace is complete, then decides, as described in tail-based sampling. Other examples exist. A stage that computes a per-trace derived attribute, such as a critical-path annotation, needs every span of the trace. A stage that joins spans with resource metadata from a different source needs to accumulate before emitting. A stage that detects a missing span, by comparing the trace’s tree against the expected service topology, needs the complete set.

In all of these, the requirement is the same: all spans with the same trace identifier must reach the same worker instance. If they do not, each instance sees a fragment and produces a decision about a fragment. The failure is quiet, because each instance believes it has a complete trace and produces output that looks well-formed.

The routing rule that follows is a hash of the trace identifier, mapped onto the set of worker instances. Every receiver applies the same hash function to the same identifier and therefore reaches the same destination. This is the only property the router needs. It does not need to know anything about the span, the service, or the timestamp.

Why modulo arithmetic is the wrong mapping

The obvious mapping is the remainder of the hash modulo the instance count. It satisfies the routing requirement exactly and fails operationally.

Consider eight instances and a hash value h. The span goes to instance h mod 8. Now add a ninth instance. The modulus changes, and every span whose hash was previously mapped to instance i is now mapped to a different instance, for almost every value of h. In a stateless stage that would be a brief imbalance, corrected within one batching interval. In a stateful stage it is a mass eviction: every buffered partial trace becomes unreachable, because its remaining spans will now be routed elsewhere. The traces in flight at the moment of the change are lost, and if the change is a rolling deployment that happens instance by instance, the loss repeats.

The proportion of keys that move is n/(n+1) when the count goes from n to n+1. With eight instances that is eight ninths, so a single scale-up discards nearly all in-flight state.

Consistent hashing changes the mapping so that adding an instance moves only the keys that the new instance takes over, which is on average 1/(n+1) of the keyspace. The construction places both instances and keys on a circle by hashing, and a key belongs to the first instance encountered clockwise from it. Adding an instance inserts one more point on the circle and takes over the arc between it and its predecessor, leaving every other arc unchanged.

The improvement is not free. Uniform placement requires many virtual points per instance, because a single hash per instance gives arcs of random and highly unequal length. With a few dozen to a few hundred virtual nodes per instance the distribution is acceptably even, and the memory cost is trivial. The lookup cost is a binary search over the sorted ring, which is logarithmic in the total number of virtual points.

import bisect, hashlib

class Ring:
    def __init__(self, nodes, vnodes=128):
        self.vnodes = vnodes
        self._ring = []          # sorted (hash, node) pairs
        self._nodes = list(nodes)
        self._build()

    def _hash(self, s: str) -> int:
        return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")

    def _build(self):
        pts = []
        for n in self._nodes:
            for v in range(self.vnodes):
                pts.append((self._hash(f"{n}#{v}"), n))
        pts.sort()
        self._ring = pts
        self._keys = [p[0] for p in pts]

    def owner(self, trace_id: str) -> str:
        h = self._hash(trace_id)
        i = bisect.bisect_right(self._keys, h)
        return self._ring[i % len(self._ring)][1]   # wrap around the circle

The wrapping at the end is the part that is easy to omit. A key whose hash exceeds every point on the ring belongs to the first point, not to none, and an implementation that returns nothing for that case silently drops every span whose trace identifier hashes above the last point on the circle.

When the assignment must not move at all

Consistent hashing bounds the disruption from a membership change; it does not eliminate it. If the requirement is that no buffered trace is ever split, even during a deployment, the assignment must be stable across the change, and the only fully stable option is a static partition: each instance owns a fixed range of the hash space, declared in configuration, and membership changes are handled by draining rather than by rehashing.

Draining works because the router can distinguish a live destination from a departing one. When an instance is removed from the active set, the router keeps sending it the spans for traces it already owns until its buffer is flushed, while new traces go to the new owner. This requires the router to know which keys an instance owns, which is exactly what consistent hashing with virtual nodes makes expensive to enumerate. A range-based partition makes it trivial, since ownership is a numeric interval.

The trade is that a static partition cannot rebalance automatically. A hot tenant, or a service whose trace identifiers happen to hash into one range, overloads one instance. In practice the partitions are sized with headroom and the balance is checked rather than assumed, and the operational simplicity is judged worth the unevenness. Systems that need both use a two-level scheme: a static assignment of ranges to a small number of logical shards, and a dynamic assignment of shards to instances. A shard move is then a whole-shard handoff with a known set of buffered traces, and the number of shards is large enough that the load evens out.

The forwarding hop and its failure modes

The router is usually a separate component from the stateful worker, which introduces a second hop: the receiver hashes, then forwards to the owner. That hop has its own behaviour to specify.

If the owner is unreachable, the receiver has three choices: drop the span, buffer and retry, or fall back to a different owner. Dropping loses the span, which breaks the trace at the tail stage. Buffering and retrying risks unbounded memory in the receiver and reorders spans, which is tolerable since the tail stage groups by identifier rather than by arrival order. Falling back to a different owner guarantees the trace is split, which is the outcome the routing was meant to prevent, so it should not be a fallback. Retry with a bound is the usual choice, and the bound has to be short enough that a failed owner does not stall the receiver’s queue for everything else.

The second failure mode is a hash disagreement. If two receivers in the same pipeline compute the hash differently, whether from a different hash function, a different encoding of the identifier, or a different set of virtual nodes, spans for the same trace land on different owners and the trace is split with no error anywhere. The configuration of the ring must therefore be identical across receivers, and it must be versioned so that a partial rollout of a new ring is detectable rather than silently inconsistent. Including the ring version in the forwarding metadata lets the owner reject a span routed by a ring it does not know about, which converts a silent split into a visible error.

The third failure mode is the identifier itself. Routing assumes the trace identifier is stable across the trace, which is true for well-behaved instrumentation and false when a service starts a new trace mid-request. A new trace identifier is a new routing decision, and the new trace will be complete and correct, but it will be a separate trace. That is a propagation failure, and it looks like a routing failure from the pipeline’s point of view; propagating context across boundaries is where the causes live.

Cost and observability of the router

The router is a fan-out point and must be sized for the full span rate, not a sampled subset, unless head-based sampling happens before it. It does no parsing beyond extracting the trace identifier, so its cost is dominated by network and serialisation rather than computation. The memory cost of the ring is negligible; the memory cost of retry buffers is not, and it must be bounded per destination so that one failed owner cannot consume the receiver’s entire buffer.

The router’s own health is worth instrumenting as a first-class signal, because its failures are otherwise invisible. The metrics that matter are the distribution of spans per owner, which reveals an unbalanced ring or a skewed trace identifier space; the rate of retries and drops per destination, which reveals an unhealthy owner; and the rate of ring-version mismatches, which reveals a partial rollout. None of these are derivable from the traces themselves, since a split trace looks like two complete traces and a dropped span looks like a service that was not called. This is the general problem of instrumenting the instrumentation, and it is the reason a pipeline that adds stateful stages needs its own monitoring rather than relying on the data it carries.