Problem statement
Design a sliding-window deduplication service that sits inline on a high-volume event stream and drops duplicate events — the same idempotency key seen within a recent time window — before they reach downstream processors, all under a bounded memory budget.
Operating context. An event stream runs at ~500,000 events/sec, and upstream producers resend on retry, so at-least-once duplicates are common. Every event carries an idempotency key, and a duplicate is any key already observed within the last window (say 24 hours). The service must make a keep-or-drop decision inline with very low latency, cannot remember every key forever, and may trade a small, well-understood inaccuracy for a large memory saving. The precise guarantee it offers is a first-class design choice.
Out of scope. The upstream producers, downstream processing logic, exactly-once writes at the final sink, and how idempotency keys are generated.
What to produce. A high-level architecture covering: partitioning the stream by key so a key's occurrences co-locate, the windowed seen-key store (an exact set versus a probabilistic structure such as a rolling Bloom or Cuckoo filter), how the window slides and expires keys to bound memory, the inline keep-or-drop decision path and its latency, the accuracy guarantee and which error direction it tolerates, and durability / recovery of the window state after a crash. Sketch the components and flow; we will probe specifics at checkpoints.
Must do 5
Functional requirements
- Partition the stream by idempotency key so all occurrences of a key hit the same dedup shard.
- Decide keep-or-drop per event by testing membership in the recent-window seen-key set.
- Record a newly seen key so later duplicates within the window are dropped.
- Expire keys as the window slides so memory stays bounded and old keys become admissible again.
- Expose the effective window size and allow it to be configured per stream.