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

TL;DR: Hold a keyed state store of seen event ids with a 7-day TTL, and put an in-memory Bloom filter in front so most unique events avoid the costly state lookup. A watermark (7 days behind the latest event time) caps the state and drops expired keys, keeping memory flat no matter the stream volume. The Bloom filter yields false positives but never false negatives, so a "maybe seen" kicks off a confirming lookup; nothing unique is discarded.

How to approach it. Name the core tension: exact dedup has to remember every key, yet unbounded memory is the failure mode, so the design centers on bounding state (TTL + watermark) and cheapening the common path (probabilistic prefilter). Then walk through the tiers and how eviction works.

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.