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.
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.
Non-functional requirements
- Keep-or-drop decision p99 < 5 ms inline at 500,000 events/sec.
- Dedup state bounded under 200 GB across the fleet for a 24-hour, ~40-billion-key window.
- With a probabilistic filter, the false-positive rate (a unique event wrongly dropped) stays under 0.1%.
- The design states its guarantee explicitly: exact within window, or bounded-approximate with no missed known duplicate.
- 99.9% availability; a shard restart recovers dedup state within 90 s without losing the active window.
- Sustain a 2x burst (1,000,000 events/sec) for 5 minutes with bounded, recoverable lag.
Topics
- System Design HLD
- Data Dedup
- Data Streaming
- Patterns Windowing
- Data Probabilistic