Distributed Tracing for Deduplication

Part of: Observability & Operations for Idempotent Systems

A dashboard can tell you that your idempotency hit rate dropped from 99.2% to 94.7% last night. It cannot tell you why a specific customer was double-charged for order ord_8841. Answering that question requires reconstructing the exact causal chain of spans across every service the request touched — and that reconstruction is only possible if the dedup decision itself is a first-class citizen inside your traces, not a side effect buried in application logs. This page defines the OpenTelemetry span model for idempotency decisions, shows how a single retry produces two independently sampled traces that must be correlated after the fact, and covers the sampling and cardinality trade-offs that determine whether the trace you need still exists when you go looking for it.

---

Why Traces, Not Just Metrics

Metrics and traces answer fundamentally different questions. A counter like idempotency.hit_total tells you the dedup layer is working in aggregate. It cannot tell you:

• Which specific request hit a stale fencing token instead of a clean cache hit.
• What the causal ordering was between the original request’s commit and the retry’s read — was the retry 40 ms behind the commit, or 4000 ms?
• Which downstream call actually executed twice, if the dedup check itself passed but a non-idempotent side effect fired regardless.
• Whether the retry arrived on a different node than the original, and whether that node had a stale view of the idempotency store.

Every one of these questions requires per-request causal data: a directed graph of spans with precise start/end timestamps, parent-child relationships, and the attributes attached at each hop. That graph is a trace. When a payments engineer opens an incident ticket for order ord_8841, the debugging workflow is: look up the idempotency key used for that order, find every trace whose span carries that key’s hash, and lay the traces side by side. Metrics cannot do this; only tracing can.

The corollary is that if the dedup decision is not represented as a span with the right attributes, this workflow is impossible — you are left grepping application logs across however many services the request fanned out to, hoping the timestamps are close enough in each service’s local clock to reconstruct ordering. Structured tracing removes the guesswork.

---

The Span Model for a Dedup Decision

Represent every dedup check as its own child span, not as an attribute bag hung off the parent HTTP span. This gives the decision its own start/end timestamps (how long did the lookup + lock acquisition take?) and lets it carry a small, fixed set of attributes without polluting the parent span’s cardinality.

Use three attributes, consistently, on every dedup span:

# Python: OTel SDK manual span around a dedup check
from opentelemetry import trace
import hashlib

tracer = trace.get_tracer("dedup.service")

def check_idempotency(raw_key: str, store):
    key_hash = hashlib.sha256(raw_key.encode()).hexdigest()[:16]
    with tracer.start_as_current_span("dedup.check") as span:
        span.set_attribute("idempotency.key_hash", key_hash)
        record = store.get(raw_key)
        if record is None:
            span.set_attribute("dedup.result", "miss")
            return None
        if record.fencing_token < store.current_token(raw_key):
            span.set_attribute("dedup.result", "conflict")
            span.set_attribute("lock.fencing_token", record.fencing_token)
            raise StaleFencingTokenError(raw_key)
        span.set_attribute("dedup.result", "hit")
        span.set_attribute("lock.fencing_token", record.fencing_token)
        return record.cached_response

Never place the raw idempotency key on a span. If the key is derived from a customer identifier, order number, or payment instrument, the hashed form is the only form that should ever leave the process boundary into a tracing backend — see Operational Concerns below.

---

Trace Diagram: One Retry, Two Traces, One Key

The critical mental model for debugging duplicates: a client retry after a timeout is a new HTTP request, and OpenTelemetry mints a brand-new trace_id for every new root span. The original attempt and the retry are therefore two entirely separate traces in your backend — they do not share a trace_id, a span_id, or a parent-child relationship. The only thing they share is the idempotency.key_hash attribute value on their respective dedup.check spans. That shared attribute is the sole correlation key an engineer has when reconstructing what happened.

The tinted dedup.check boxes in both traces mark the spans that share the same idempotency.key_hash. Note the asymmetry: Trace A spends 360 ms inside process_payment because it is the request that actually executes the mutation; Trace B never enters that span at all — the hit result short-circuits the entire downstream call. If your tracing backend cannot answer “show me every trace where idempotency.key_hash = f8d2e1” in one query, you cannot reconstruct this picture during an incident, no matter how good your metrics dashboards are.

---

W3C Trace Context vs the Idempotency Key

These are two different identifiers with two different lifetimes, and conflating them is a common instrumentation mistake:

Both are necessary and neither substitutes for the other. traceparent lets you follow one request through every service it touches; the idempotency key lets you find every attempt — potentially many independent traces — that represent the same logical operation. A common failure is trying to make the idempotency key do double duty by stuffing it into the tracestate header or, worse, hand-rolling a fake trace-id derived from it. Both approaches break interoperability with any W3C-compliant vendor or collector that assumes trace-id is opaque, random, and 128 bits — never derived from business data. Keep them separate: propagate traceparent for causal graph reconstruction, and carry the idempotency key as a span attribute plus (for cross-service correlation before the dedup decision is made) OpenTelemetry baggage.

---

Implementation Variants

Variant 1 — OTel SDK Manual Spans

You explicitly start a span around the dedup check and set attributes by hand, as shown in the span model section above. This gives full control over attribute names and cardinality but requires every service that performs a dedup check to import the OTel SDK and wire the span correctly.

// Node.js: manual span with dedup attributes
const { trace } = require('@opentelemetry/api');
const tracer = trace.getTracer('dedup-service');

async function checkIdempotency(rawKey, store) {
  const keyHash = require('crypto')
    .createHash('sha256').update(rawKey).digest('hex').slice(0, 16);

  return tracer.startActiveSpan('dedup.check', async (span) => {
    span.setAttribute('idempotency.key_hash', keyHash);
    const record = await store.get(rawKey);
    if (!record) {
      span.setAttribute('dedup.result', 'miss');
      span.end();
      return null;
    }
    span.setAttribute('dedup.result', record.staleToken ? 'conflict' : 'hit');
    span.setAttribute('lock.fencing_token', record.fencingToken);
    span.end();
    return record.staleToken ? null : record.cachedResponse;
  });
}

Variant 2 — Auto-Instrumentation with a Custom Processor

Framework auto-instrumentation (opentelemetry-instrument for Python, @opentelemetry/auto-instrumentations-node for Node.js) automatically wraps HTTP handlers, database calls, and Redis commands with spans — but it has no idea what a “dedup decision” is. You get spans for the underlying GET/SETNX calls to your idempotency store automatically, but not the idempotency.key_hash or dedup.result attributes. Bridge the gap with a lightweight SpanProcessor that inspects specific span names (e.g. the Redis command span) and enriches them:

# Python: enrich auto-instrumented Redis spans with dedup attributes
from opentelemetry.sdk.trace import SpanProcessor

class DedupEnrichmentProcessor(SpanProcessor):
    def on_start(self, span, parent_context):
        if span.name == "SETNX" and span.attributes.get("db.redis.key", "").startswith("idem:"):
            span.set_attribute("dedup.instrumented_via", "auto+enrichment")

This variant is fast to deploy across many services but fragile: it depends on span-naming conventions from the auto-instrumentation library, which can change across versions.

Variant 3 — Vendor APM Agents

Datadog, New Relic, and similar agents auto-instrument at the bytecode or process level and require no code changes to get basic HTTP/DB spans. Adding dedup-specific attributes still requires a call into the vendor’s tagging API at the point of the dedup decision:

// Java: Datadog APM custom tag on the active span
import datadog.trace.api.DDTags;
import datadog.trace.api.GlobalTracer;

public CachedResponse checkIdempotency(String rawKey, IdempotencyStore store) {
    String keyHash = Hashing.sha256().hashString(rawKey, StandardCharsets.UTF_8)
                             .toString().substring(0, 16);
    GlobalTracer.get().activeSpan().setTag("idempotency.key_hash", keyHash);
    Record record = store.get(rawKey);
    String result = record == null ? "miss" : (record.isStale() ? "conflict" : "hit");
    GlobalTracer.get().activeSpan().setTag("dedup.result", result);
    return record == null ? null : record.cachedResponse();
}

Vendor agents give you turnkey infrastructure spans and a polished UI, but the attribute names and span model are proprietary — migrating to a different backend later means re-tagging every call site.

Comparison Summary

Two focused runbooks operationalize Variant 1 end-to-end: Instrumenting Idempotency Flows with OpenTelemetry walks through adding spans in Python and Node.js and exporting to a collector, and Propagating Idempotency Keys Through Trace Context covers carrying the key across service hops in Go and Java via baggage.

---

Edge Cases and Failure Scenarios

---

Operational Concerns

Sampling Strategy That Keeps Duplicates

Standard head-based sampling makes the keep/drop decision at the root span, before any dedup outcome is known — which means it samples independently of whether the trace is actually interesting. Configure your collector for tail-based sampling so the decision is deferred until the full trace (or a batching window) is available, and write an explicit policy that always retains:

# OTel Collector: tail_sampling processor config
processors:
  tail_sampling:
    decision_wait: 10s
    policies:
      - name: keep-non-hit-dedup
        type: string_attribute
        string_attribute:
          key: dedup.result
          values: ["miss", "conflict"]
      - name: keep-fencing-mismatch
        type: string_attribute
        string_attribute:
          key: lock.fencing_token
          values: ["stale"]
      - name: baseline-sample
        type: probabilistic
        probabilistic:
          sampling_percentage: 1

This guarantees every conflict and every miss (i.e. every trace where a mutation actually happened, or where a fencing check failed) is retained at 100%, while clean cache hit traces — the overwhelming majority in a healthy system — are sampled down to a manageable 1% baseline.

Attribute Cardinality

idempotency.key_hash is, by construction, unique per logical operation — that is exactly the property that makes it useful for correlation, and exactly the property that makes it dangerous as an index if your tracing backend is not built for high-cardinality attributes. Truncate the hash to 16 hex characters (64 bits of entropy is more than sufficient to avoid collisions at any realistic request volume) rather than storing the full 256-bit digest, and confirm your backend indexes attributes used for search (Tempo’s TraceQL, Jaeger’s tag search) rather than relying on full-text scan — full digests bloat storage and slow every query that filters on the attribute.

PII: Hash Keys, Never Store Raw

If your idempotency key is derived from or contains a customer email, account number, or payment instrument token, the raw key must never reach the tracing backend — tracing data typically has weaker access controls and longer retention than your primary datastore. Hash with SHA-256 at the point of span creation, before the value leaves process memory, and confirm no upstream proxy or logging middleware captures the raw Idempotency-Key HTTP header into span attributes automatically (auto-instrumentation libraries sometimes capture all request headers by default — explicitly exclude Idempotency-Key from any such capture list).

---

Related

• Observability & Operations for Idempotent Systems — parent section covering metrics dashboards, alerting SLOs, and chaos engineering for the dedup layer
• Instrumenting Idempotency Flows with OpenTelemetry — runbook for adding dedup spans in Python and Node.js and exporting to a collector
• Propagating Idempotency Keys Through Trace Context — runbook for carrying the key across service hops in Go and Java via OTel baggage
• Monitoring Idempotency Metrics and Dashboards — the aggregate hit-rate and latency metrics that trigger the trace-level investigation described here
• Lock Timeout & Lease Management — the fencing token mechanism whose value is surfaced as the lock.fencing_token span attribute
• Using Redis SET NX for Distributed Request Deduplication — the storage layer whose calls are the natural target for auto-instrumentation enrichment