Idempotency, Deduplication, and Delivery Semantics

What's being tested

Candidates must demonstrate practical mastery of idempotency, deduplication, and delivery semantics in distributed systems: how to prevent duplicate effects, how to detect and discard duplicate events, and how to reason about at-most-once / at-least-once / exactly-once tradeoffs. Interviewers look for clear scoping questions, pragmatic designs that tolerate partial failures, measurable bounds (memory, latency), and concrete choices for sequencing, finality, and late-arriving data.

Core knowledge

• Delivery semantics: know definitions and tradeoffs: at-most-once (no retries), at-least-once (retries, duplicates possible), exactly-once (strongest, expensive). Exactly-once often implemented via idempotent handlers plus dedupe, or via transactional sinks (2PC) — cost vs complexity tradeoff.

• Idempotency key: a unique client- or producer-supplied token (e.g., request UUID) persisted for TTL to make handlers safe to retry; store it with outcome (success/failure) to return same result for replays.

• Deduplication window and state: dedupe requires state mapping (key -> processed-timestamp/outcome). In-memory maps handle ~1–10M keys per node; beyond that use sharded persistent store (Postgres, Redis, Cassandra) with TTLs or compaction to bound growth.

• Hash vs explicit id: do not dedupe by payload hash alone unless content-addressable semantics are intended — hash collisions and semantically-equivalent-but-distinct events can mislead. Prefer monotonic sequence numbers or explicit event IDs.

• Ordering vs partitioning: deterministic ordering requires a partition key and sequence numbers per partition. Global ordering across partitions implies single leader or global sequencer (scales poorly). Use Kafka partitions for per-key order guarantees.

• Event time vs processing time: for windows and finality, use event time with watermarks and allowed-lateness; processing-time-only designs mis-handle late arrivals leading to retractions/updates.

• Late arrivals & finality: define “final” (e.g., watermark + allowed lateness). Use tombstones or compensating events rather than trying to retroactively reorder already-acknowledged delivers.

• Probabilistic dedupe: Bloom filters or approximate set caches reduce memory but have false positives; acceptable when occasional dropped duplicate is tolerable. Always quantify false positive rate: $p \approx (1 - e^{-kn/m})^k$.

• Concurrency and uniqueness: for “one claim per user” use a unique DB constraint (e.g., unique(user_id, deal_id)) or atomic INSERT IF NOT EXISTS / UPSERT with conditional WHERE for optimistic concurrency. Relying solely on application-level locks is risky under failures.

• State compaction & GC: persist dedupe keys with TTL; implement compaction via background jobs or log compaction (e.g., Kafka log compaction), and garbage-collect stale state once finality is reached.

• Exactly-once streaming: frameworks like Flink/Kafka Streams implement “exactly-once” by combining checkpointed operator state with transactional sinks; but they trade latency for consistent snapshots and increased operational complexity.

• Dead-letter queues and poison messages: on repeated retries, move problematic messages to a DLQ and record diagnostic context; do not block foreground processing on a few stuck events.

• Instrumentation & SLAs: measure duplicate-rate, delivery-latency, p99 retry amplification, dedupe store size. Set TTLs and window sizes based on expected throughput and acceptable memory (e.g., TTL = expected max delivery delay + margin).

Worked example: Design a Personalized Weekly Deals Service

First 30s framing: ask traffic volume, deal claim semantics (one claim per user-deal), latency requirements for personalization, expected sources and correction patterns, and whether eventual corrections are acceptable. Skeleton pillars: (1) ingestion + deduplication for multi-source feeds, (2) active-window selection and ranking with stable pagination, (3) claim-handling with idempotency and concurrency controls, (4) expiration/garbage collection and metrics. For ingestion dedupe, accept canonical event ID or compute stable event key; persist dedupe keys in a sharded Redis with TTL equal to correction window. For claim handling, prefer a unique DB constraint on (user_id, deal_id) and perform INSERT with explicit idempotency key; if synchronous confirmation is needed, combine with conditional update (WHERE status IS NULL) to avoid races. One tradeoff to call out: synchronous strong consistency for claims (simple correctness) vs higher availability and throughput using async processing plus compensation (complexity in refunds/rollbacks). Close: “If I had more time I’d prototype DB schema, quantify dedupe cache sizing for peak QPS, and sketch metrics and backfill/repair paths.”

A second angle: Design at-least-once notification delivery

Same primitives apply but constraints differ: delivery is per-recipient, often low-latency and retry-heavy. Use idempotency keys per notification per device and store outcome per (recipient, notif_id). Implement exponential backoff and a DLQ for persistent failures. Ordering is often relaxed — prefer per-recipient FIFO queues if recipient order matters, otherwise parallelize. For push (APNs/FCM) vs email/SMS, dedupe window and retry strategy change; for push, de-duplicating identical payloads can reduce cost, while for email dedupe must avoid sending multiple emails. For scaling, partition per recipient and shard dedupe state; for extremely high fanout, offload idempotency checks to the client where possible (e.g., include message-id and client dedupe) to reduce server state.

Common pitfalls

Pitfall: Treating payload-equality as a correct dedupe key. Payloads may be semantically different or reordered; dedupe must use an authoritative ID or sequence, not just content hash.

Pitfall: Proposing “exactly-once” as an off-the-shelf property without explaining costs. Exactly-once requires transactional sinks or coordinated checkpoints; the practical alternative is idempotent processing plus dedupe.

Pitfall: Not bounding dedupe state. Failing to set TTLs or compaction leads to unbounded memory growth; always quantify expected keys and choose LRU/Bloom or persistent sharding with GC.

Connections

Interviewers may pivot to stream processing (e.g., Flink state backends, checkpointing), event sourcing and log compaction strategies (Kafka), or database concurrency controls (unique constraints, serializable isolation) to probe deeper consistency tradeoffs.

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann — excellent chapters on messaging, deduplication, and consistency tradeoffs.

• Exactly-once delivery semantics in Kafka Streams — Confluent blog — practical explanation of transactional producers and sink semantics.