Design a Ten-Minute In-Memory Notification Deduplication Engine

Question

Design a high-throughput in-memory deduplication engine that filters out duplicate notifications received within a ten-minute window based on their unique notification IDs.

Codemia · Accepted Answer

The deduplication engine must filter out duplicate notifications based on their `notification_id` within a 10-minute window. It needs to handle approximately 10,000 notifications per second and operate within strict memory constraints on a single instance.

The architecture consists of the following components:
1. **Input Queue**: Receives incoming notifications.
2. **Deduplication Module**: Checks for duplicates against a time-based sliding window.
3. **Storage**: Utilizes a data structure to store recent notification IDs and their timestamps, such as a hash map combined with a linked list for efficient access and removal.
4. **Output Queue**: Sends non-duplicate notifications for further processing.

To implement the deduplication logic, I would use a hash map where the key is the `notification_id` and the value is the timestamp of when it was last seen. Each time a notification is processed:
- Check if the `notification_id` exists in the hash map.
- If it exists, compare the stored timestamp with the current time. If the difference is less than 10 minutes, discard the notification.
- If it does not exist or is older than 10 minutes, add it to the hash map and update the timestamp.

Using a hash map allows for O(1) average time complexity for insertions and lookups, which is efficient for high throughput. However, memory usage can be a concern as the number of unique `notification_id`s increases. To mitigate this, I would implement a cleanup mechanism that periodically removes entries older than 10 minutes. This can be done using a background thread that iterates through the hash map to remove stale entries.

Consider scenarios such as:
- **High Volume Spikes**: Implement rate limiting or backpressure mechanisms to handle sudden surges in notifications.
- **Memory Constraints**: If nearing memory limits, prioritize the removal of the oldest entries more aggressively. Additionally, consider using more memory-efficient data structures or offloading some data to disk if necessary.

Design a Ten-Minute In-Memory Notification Deduplication Engine

Goldman Sachs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Goldman Sachs Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search