Idempotency Key Generation Strategies

Part of: Idempotency Fundamentals & API Guarantees

Problem Framing

Every duplicate request that bypasses deduplication is a potential phantom charge, double inventory reservation, or corrupted ledger entry. The root cause is almost always a mismatch between how the key was generated and what the deduplication store expects: keys that are too short collide, keys that are purely random fragment B-tree indexes, and keys that are client-determined without a server-side validation step allow adversarial replay. This page covers the full lifecycle — algorithm selection, atomic registration, response caching, retry propagation, and TTL expiration — for backend engineers who need a deterministic guarantee, not a probabilistic one.

The deduplication guarantee only holds when key generation is treated as part of the broader idempotency contract, not as an afterthought bolted onto an existing endpoint.

---

Guarantee Model

Correctly generated and registered idempotency keys provide exactly-once execution within a bounded TTL window: N identical requests carrying the same key produce exactly one state transition and N identical responses. Outside that window the guarantee lapses — a key that expires before a delayed retry will trigger a second execution.

The guarantee breaks under two conditions:

1. Clock skew across regions: If the TTL is set on a primary node and a cross-region replica lags by more than the network partition window, a retry routed to the replica may not find the key and will re-execute the operation. Synchronous replication within an availability zone eliminates this; cross-region replication must document an explicit consistency window (typically 200–500 ms for Redis Cluster with async replication).

2. Partial commit: The business transaction commits but the response cache write fails. The next retry will query the committed state from the database, reconstruct the response, and return it — provided the key record still exists. If the key record was also lost (e.g., a Redis eviction mid-write), the operation executes twice. The remedy is to write the key record before beginning the business transaction and to use a status field (pending → complete) rather than a simple boolean.

---

Core Algorithm: Atomic Check-and-Set with Status Transitions

The registration protocol follows a strict state machine regardless of which generation algorithm is used for the key value itself.

Step-by-step registration protocol:

1. Validate that the Idempotency-Key header is present and well-formed (128-bit minimum entropy; reject keys shorter than 22 characters).
2. Execute SET key '{"status":"pending","ts":<epoch_ms>}' NX EX 86400 in Redis (or an equivalent INSERT ... ON CONFLICT DO NOTHING in PostgreSQL).
3. If the key already exists, read its current status:
   • pending → return 409 Conflict with Retry-After: 2 to signal in-flight execution.
   • complete → deserialise the cached response and replay it verbatim (status code, headers, body).
4. If the key was newly inserted (NX succeeded), execute the business logic inside a database transaction.
5. On successful commit, update the key record to {"status":"complete","response":{...}} using SET key <value> XX EX 86400.
6. Return the response to the client.
7. On application crash between steps 4 and 5, the key remains pending. Expose a background sweep that promotes orphaned pending keys older than the maximum expected execution time (e.g., 30 seconds) to expired, allowing the client to safely resubmit.

---

Implementation Variants

Variant 1 — UUIDv7 (Recommended for Relational Databases)

UUIDv7 embeds a 48-bit millisecond timestamp into the first 48 bits of a 128-bit UUID, followed by 74 bits of cryptographic randomness. The time-ordered prefix keeps B-tree index inserts sequential, reducing write amplification to approximately 1.1× vs. 3–4× for fully random UUIDv4.

// Go — requires github.com/google/uuid v1.6+
import "github.com/google/uuid"

func NewIdempotencyKey() string {
    id, err := uuid.NewV7()
    if err != nil {
        panic(err) // entropy failure — hard stop, do not silently degrade
    }
    return id.String() // e.g. "019018a2-1b3c-7d4e-9f0a-1b2c3d4e5f60"
}

# Python 3.12+ — uuid7 in stdlib
import uuid

def new_idempotency_key() -> str:
    return str(uuid.uuid7())  # time-ordered, 74-bit random suffix

Variant 2 — ULID (Sortable, URL-Safe)

ULID (Universally Unique Lexicographically Sortable Identifier) encodes a 48-bit timestamp and 80 bits of randomness into a 26-character Crockford base-32 string. It is human-readable, URL-safe without encoding, and maintains monotonic ordering within a millisecond via a per-process counter.

// Go — github.com/oklog/ulid/v2
import (
    "math/rand"
    "time"
    "github.com/oklog/ulid/v2"
)

func NewIdempotencyKey() string {
    entropy := ulid.Monotonic(rand.New(rand.NewSource(time.Now().UnixNano())), 0)
    return ulid.MustNew(ulid.Timestamp(time.Now()), entropy).String()
    // e.g. "01HXYZ3ABCDEFGHJKMNPQRSTVW"
}

// Java — com.github.f4b6a3:ulid-creator
import com.github.f4b6a3.ulid.UlidCreator;

String key = UlidCreator.getMonotonicUlid().toString();

Variant 3 — HMAC-SHA256 Deterministic (Client-Driven)

When the client has a stable, unique set of inputs for a logical operation (e.g., order_id + customer_id + amount + currency + timestamp_truncated_to_minute), it can derive the idempotency key deterministically using HMAC-SHA256 with a server-issued signing secret. This eliminates key storage on the client side and guarantees that the same operation always produces the same key across client restarts.

import hmac, hashlib, os

SIGNING_SECRET = os.environ["IDEMPOTENCY_SIGNING_SECRET"]  # 256-bit secret

def deterministic_key(order_id: str, customer_id: str, amount_cents: int,
                       currency: str, minute_epoch: int) -> str:
    """Derives a 64-hex-char key; identical inputs → identical key."""
    payload = f"{order_id}:{customer_id}:{amount_cents}:{currency}:{minute_epoch}"
    return hmac.new(
        SIGNING_SECRET.encode(),
        payload.encode(),
        hashlib.sha256
    ).hexdigest()

Security requirement: The signing secret must rotate on a schedule aligned with the key TTL. A compromised secret allows an attacker to predict future keys and replay requests within the TTL window.

Variant 4 — UUIDv4 (LSM-Tree Stores)

For Cassandra, DynamoDB, or RocksDB, random distribution across partitions is desirable: sequential keys create hot-partition write skew. UUIDv4 provides 122 bits of cryptographic randomness with zero temporal ordering.

# Shell / quick test generation
python3 -c "import uuid; print(uuid.uuid4())"
# Node.js
node -e "const {randomUUID}=require('crypto'); console.log(randomUUID());"

Variant Comparison

---

Edge Cases & Failure Scenarios

---

Operational Concerns

TTL Management

Set hot-tier TTL to 86400 seconds (24 hours) in Redis using the EX argument on every write — both the initial SET NX EX and the SET XX EX update on completion. Do not extend the TTL on read; only extend on a legitimate new execution. Archive key hashes (SHA-256 of the key value, never the payload) to cold object storage (S3, R2) with a 90-day retention for PCI-DSS and SOC 2 audit trails.

Implement a two-phase expiry: at T+24h the key moves from complete to expired in-memory; at T+90d the archived hash record is purged. This prevents the deduplication store from growing unboundedly while satisfying compliance requirements.

For idempotency key storage and TTL management at the database layer — including partitioning strategies and compaction tuning — see the dedicated storage patterns section.

Index Strategy

• PostgreSQL / MySQL (B-tree): Use UUIDv7 or ULID to maintain semi-sequential inserts. Add a partial index on (key, status) where status = 'pending' to accelerate orphan-sweep queries. Partition the deduplication table by created_at (monthly partitions) to allow instant cold-partition drops.
• Redis: Store keys under a consistent hash slot prefix ({tenant_id}:idem:) to co-locate related keys on the same shard, reducing cross-slot operations. Use SCAN with MATCH {tenant_id}:idem:* for TTL audits rather than KEYS.
• DynamoDB: Set key as the partition key and created_at (epoch seconds) as the sort key. Enable TTL on the expires_at attribute. Use a GSI on (status, created_at) for the orphan-sweep job.

Memory and Storage Budgeting

A 24-hour Redis cache holding 50 million active keys at ~512 bytes per entry (key + status + cached response body) requires approximately 25 GB of hot memory. Budget an additional 20% headroom for key metadata and Redis overhead. For systems where response bodies exceed 4 KB, store only the response reference (e.g., a DynamoDB item ID or S3 object key) in Redis and retrieve the full body from the primary store on replay.

SRE Alert Thresholds

Emit the following metrics from every service that issues or validates idempotency keys:

• idempotency_key_hit_ratio — ratio of complete cache hits to total requests bearing the header. Alert if < 0.90 over a 5-minute window (indicates expired keys being retried past TTL).
• idempotency_key_collision_total — counter of DB unique constraint violations. Alert on any non-zero value.
• idempotency_pending_promotion_lag_seconds — time from pending creation to complete promotion. Alert if p99 > 30 s.
• idempotency_response_replay_latency_ms — latency of serving a cached replay. Alert if p99 > 5 ms (indicates cache eviction under memory pressure).
• idempotency_orphan_pending_count — gauge of pending keys older than 60 s. Alert if > 0 for more than 60 s.

---

Related

• How to Generate Cryptographically Secure Idempotency Keys — runtime-specific runbooks (Go, Python, Node.js, Java) with copy-pasteable CSPRNG code, container entropy configuration, and test harnesses for verifying collision resistance.
• Retry Logic & Backoff Fundamentals — how to propagate the same key across exponential backoff with jitter retry loops without triggering duplicate executions.
• Redis Cache-Based Deduplication — atomic SET NX patterns, shard-key design, and eviction policy configuration for using Redis SETNX for distributed request deduplication.
• Idempotency Key Storage & TTL Management — PostgreSQL partition strategies, DynamoDB TTL configuration, and tiered archival for long-term compliance.
• HTTP Method Semantics & Safety — which HTTP verbs require explicit idempotency keys vs. those that are safe by design, and how If-Match conditional headers interact with key-based deduplication.
• Idempotency Fundamentals & API Guarantees — parent section covering the end-to-end exactly-once contract, failure boundary map, and trade-off matrix across storage backends.