Design a Ten-Minute In-Memory Notification Deduplication Engine

Scenario

Financial platforms emit high volumes of trade alerts, market events, and compliance triggers. Due to retries, network glitches, and at-least-once message delivery from upstream publishers, identical notifications are frequently emitted in bursts.

Design an in-memory notification deduplication engine that receives incoming notification events and determines whether a notification has already been processed within the last 10 minutes.

Requirements

Functional Requirements

• Deduplication Check & Record: Given a unique deduplication key (e.g., derived from user ID, event type, and payload hash), the engine must return whether the event is NEW or a DUPLICATE.
• 10-Minute Window Policy: The deduplication window is 10 minutes. Clarify and support policies for:
  • Fixed window from first seen: The key expires strictly 10 minutes after initial observation.
  • Sliding refresh: Every incoming duplicate resets the 10-minute retention timer.
• Cleanup: Expired keys must be purged predictably without triggering memory exhaustion or latency spikes.

Non-Functional Requirements

• Latency: p99 latency under 2 ms.
• Throughput: Handle up to 100,000 notification checks per second at peak.
• Concurrency: Thread-safe operations without lock contention bottlenecks under multi-core environments.
• Memory Footprint: Predictable and bounded memory usage suitable for in-memory operation.
• Clock Handling: Resilient to wall-clock skew and NTP synchronization adjustments.

Scale Assumptions

• Peak ingestion rate: 100,000 events/second.
• Window duration: 10 minutes (600 seconds).
• Unique keys in memory at peak: Up to 60,000,000 active keys.
• Key size: 128-bit hash (16 bytes) or UUID representation.

Key Discussion Points

• Data Structure Selection: Trade-offs between concurrent hash maps with TTLs, segmented circular time-buckets, and linked hash maps.
• Cleanup Strategy: Proactive background eviction vs. passive eviction on read vs. atomic rotation of time-sliced buckets.
• Clock Source: Local monotonic clock (clock_gettime(CLOCK_MONOTONIC)) vs. event payload timestamps.
• Partitioning & Sharding: Key-based partitioning (consistent hashing) across CPU cores or instances to eliminate cross-thread lock contention.
• High Availability & Fault Tolerance: Trade-offs between pure volatile in-memory operation and append-only write-ahead logging (WAL) or standby replicas.