Skip to content

CONCEPT Cited by 2 sources

Idempotency token

An idempotency token is a per-operation identifier attached to a mutation so that a retried or hedged write is logically indistinguishable from the original — every copy the server sees carries the same token, and the server (or storage engine) deduplicates. Canonical Netflix shape:

message IdempotencyToken (
  Timestamp generation_time,
  String    token
)

where generation_time is a client-generated monotonic timestamp and token is a random nonce (128-bit UUID in Netflix KV).

Why it matters

At Netflix's scale, tail latency is managed with hedging and retries — the same write may be sent twice concurrently or re-sent after a timeout. On a last-write- wins store like Cassandra, two copies of a write with different server-assigned tokens can be merged incorrectly (two distinct "versions" that compete on clock) or produce duplicate effects on append-only keys. An idempotency token tied to the logical write gives the server a de-duplication key that survives hedging, retries, and network reordering.

"To ensure data integrity the PutItems and DeleteItems APIs use idempotency tokens, which uniquely identify each mutative operation and guarantee that operations are logically executed in order, even when hedged or retried for latency reasons. This is especially crucial in last-write-wins databases like Cassandra, where ensuring the correct order and de-duplication of requests is vital." (Source: sources/2024-09-19-netflix-netflixs-key-value-data-abstraction-layer)

Token generation strategies

Client-generated monotonic (Netflix KV default)

  • generation_time comes from the client's clock.
  • token is a 128-bit random UUID.
  • Rationale: "client-generated monotonic tokens are preferred due to their reliability, especially in environments where network delays could impact server-side token generation."

Safety depends on small clock skew. Netflix measured sub-millisecond drift on the EC2 Nitro Cassandra fleet, making monotonic client timestamps workable. KV rejects writes with tokens far in the past (which would be silently discarded by last-write-wins) or far in the future (which would create doomstones — immutable records blocking legitimate writes until wall-clock catches up).

Regionally-unique (Zookeeper-issued)

  • Use when stronger ordering guarantees than clock-based are needed.
  • A coordinator (Zookeeper) issues tokens within a region.

Globally-unique transaction ID

  • Piggyback on an existing cross-region transaction identifier.
  • Works when a higher-level transaction manager already exists.

The two failure modes the DAL explicitly guards against

KV servers reject writes with tokens that drift too far from "now":

  • Silent write discard — token generation_time too far in the past. Last-write-wins would quietly lose the write.
  • Immutable doomstone — token generation_time too far in the future. Stores sensitive to future timestamps would treat the record as un-overwriteable until real-time catches up.

Both are silent, catastrophic, and hard to detect in production; the DAL turns them into loud client-side errors.

Chunked-write atomicity

For large items, chunking splits a single logical write across multiple backing- store operations. One idempotency token binds all the chunk writes + main-table commit — the storage engine sees one logical write-group identified by the token, even though the physical I/O is multi-operation.

Other production uses (wiki cross-refs)

Netflix KV DAL is this wiki's canonical idempotency-token instance, but the primitive shows up elsewhere:

  • Stripe-style API keys — POST bodies carry an Idempotency-Key header; server stores (key → response) for a TTL.
  • Kafka exactly-once producers — per-producer sequence numbers + producer IDs act as a de-duplication token at the broker.
  • DynamoDB client request tokens — optional request token for idempotent transactions (see systems/dynamodb).

Trade-offs

  • Clock-skew dependency. Client-generated monotonic tokens are only safe where clock skew is small (Netflix's < 1 ms on EC2 Nitro is the anchor; teams outside that class must re-measure).
  • Token storage cost. The backing store has to remember tokens for a dedup window; this is extra state.
  • Token collision risk. 128-bit UUIDs make collisions astronomically unlikely, but a shorter nonce would be risky at scale.
  • Doesn't cover non-mutative endpoints — read APIs don't need it; only the PutItems / DeleteItems (and chunked-commit) paths.

Seen in

  • sources/2024-09-19-netflix-netflixs-key-value-data-abstraction-layer — canonical definition; three token-generation strategies (client-monotonic / Zookeeper-regional / globally-unique); two failure modes guarded against (silent-discard / doomstone); chunked-write atomicity binding.
  • sources/2024-11-13-netflix-netflixs-distributed-counter-abstraction — second canonical Netflix instance, with the same (event_time, nonce) shape applied to counter mutations. The composite (event_time, event_id, event_item_key) on each TimeSeries event naturally deduplicates retries + hedges: the same AddCount(+1) call retried produces the same row on second arrival. Writes are therefore safe to retry + hedge even on a Cassandra LWW store. Best-Effort counters explicitly lack this property — EVCache incr/decr has no native idempotency, which is why Netflix flags retry-unsafe as a Best-Effort trade-off.
Last updated · 319 distilled / 1,201 read