Deduplicate events exactly-once over a sliding 7-day window in a high-throughput stream without running out of memory.

TL;DR: Keep a keyed state store of seen event ids with a 7-day TTL, fronted by an in-memory Bloom filter so most unique events skip the expensive state lookup. A watermark (7 days behind the latest event time) bounds the state and evicts expired keys, so memory stays flat regardless of stream volume. The Bloom filter can false-positive but never false-negative, so a "maybe seen" triggers a confirming lookup; nothing unique is dropped.

How to approach it. State the core tension: exact dedup needs to remember every key, but unbounded memory is the failure mode, so the design is about bounding state (TTL + watermark) and cheapening the common path (probabilistic prefilter). Then lay out the tiers and the eviction mechanism.

A strong answer. The naive approach (a hash set of all seen ids) grows without bound and eventually OOMs on a high-throughput stream. Bound it and make the hot path cheap with a tiered design:

incoming event (key + event_time)
   |
   v
[in-memory Bloom filter]  -- "definitely new"? --> process + insert into Bloom + state
   |  "maybe seen" (could be a false positive)
   v
[durable keyed state store (RocksDB/Delta), TTL = 7 days]
   |  found? --> duplicate, drop
   |  not found? --> process + insert into Bloom + state

• Bloom filter (probabilistic prefilter). A space-efficient set membership structure with no false negatives: if it says "not present," the key is definitely new and you skip the costly state lookup, which handles the majority of unique traffic cheaply. If it says "maybe present," you fall through to the authoritative state store to confirm (Bloom false positives are the only cost, and they are rare and tunable). Every processed key is inserted into both the Bloom filter and the state store, so a repeat of that key can never read as "definitely new".
• Durable keyed state with TTL. The source of truth: event ids with a 7-day time-to-live. A confirmed hit is a duplicate (drop); a miss is unique (process and insert). RocksDB-backed state (as in Flink/Spark Structured Streaming) spills to disk so state larger than RAM still works.
• Watermark for eviction. Process on event time and maintain a watermark 7 days behind the latest seen event. The engine uses it to (a) evict state older than the window, keeping memory bounded, and (b) drop or side-output events arriving later than the watermark, so late data does not silently reopen a closed window. This is what makes memory flat regardless of total volume: you only ever hold ~7 days of keys.

So exactly-once dedup at scale = cheap probabilistic prefilter + authoritative TTL'd state + watermark-driven eviction. The Bloom filter buys throughput; the TTL and watermark buy bounded memory.

Each tier owns one job, and conflating them is where designs fail:

Key takeaways

• Exact dedup needs to remember every key in the window; the whole design is about bounding that set (TTL plus watermark) and cheapening the hot path (Bloom prefilter).
• The Bloom filter is an optimization, never the source of truth: a "maybe seen" must fall through to a confirming state lookup, since false positives are tolerable but dropping unique events is not.
• Process on event time, not wall clock; the watermark is what keeps memory flat regardless of total stream volume.
• Size the watermark delay from the observed lateness distribution: too tight drops valid late events, too loose holds more state.

What interviewers probe next.

• "Why a Bloom filter if you still have the state store?" It avoids a state lookup for the common case (new keys), cutting IO/CPU dramatically at high QPS; it is an optimization, not the source of truth.
• "Bloom false positives, are they dangerous?" No: a false positive just triggers an unnecessary confirming lookup (correctness preserved); false negatives would be dangerous, and Bloom filters have none. Size it for an acceptable false-positive rate.
• "How do you pick the watermark delay?" From the observed lateness distribution: too tight drops valid late events, too loose holds more state and delays results.
• "Partition/scale it?" Key-partition the stream so each worker owns a disjoint key range with its own Bloom + state; watch for hot keys/skew.

Common mistakes.

• An unbounded hash set of all seen ids, which OOMs.
• Processing on wall-clock time instead of event time, so late/out-of-order events break dedup.
• No watermark, so state never evicts and memory grows forever.
• Treating the Bloom filter as authoritative (acting on "maybe seen" without confirming), dropping unique events.