In-Memory Notification Deduplication Engine (10-Minute Window)

0) Problem Restatement

Goldman Sachs asked: design the in-memory component of a high-throughput notification service that detects repeated notification IDs. Rule: if a notification with the same UUID arrives again within 10 minutes, suppress it. After 10 minutes, the same ID may be sent again. The component handles hundreds of thousands of checks per second from many threads.

1) API

should_send(notification_id, now) -> bool
  True  = first time in the last 10 minutes (send it, and remember it)
  False = duplicate inside the window (suppress)

2) Design

• Hash map id → last_accepted_time for O(1) lookups.
• Expiry queue (FIFO of (time, id) in arrival order): since time only moves forward, the oldest entries are always at the front. Before each check, pop entries older than now − 600 s and delete them from the map (only if the map still holds that same time). This keeps memory bounded to the last 10 minutes of IDs.
• Amortized O(1): each ID is added once and removed once.

flowchart LR
    REQ["should_send(id, now)"] --> EXP["Pop expired from queue front, delete from map"]
    EXP --> CHK{"id in map?"}
    CHK -->|"yes"| NO["Return False - duplicate"]
    CHK -->|"no"| ADD["map[id] = now; queue.append((now, id))"]
    ADD --> YES["Return True - send"]

3) Code (Python)

import threading
from collections import deque

class DedupEngine:
    def __init__(self, window_s=600, shards=64):
        self.window = window_s
        self.shards = [({}, deque(), threading.Lock()) for _ in range(shards)]

    def should_send(self, nid, now):
        seen, order, lock = self.shards[hash(nid) % len(self.shards)]
        with lock:
            cutoff = now - self.window
            while order and order[0][0] <= cutoff:       # expire old entries
                t, old = order.popleft()
                if seen.get(old) == t:
                    del seen[old]
            if nid in seen:
                return False                             # duplicate within the window
            seen[nid] = now
            order.append((now, nid))
            return True

• Sharding: 64 independent (map, queue, lock) shards chosen by hash(id). Threads working on different IDs rarely block each other.
• Window rule: an ID seen at time t is a duplicate until t + 600 (exclusive here). State the boundary explicitly in the interview.

4) Memory Estimate

At 50K new IDs/sec × 600 s = 30M entries. At ~100 bytes each in Python, that's ~3 GB (in Java/C++ with compact structures, ~1–1.5 GB). Options if that's too much:

• Store a 64-bit hash of the UUID instead of the full string (a tiny false-duplicate risk).
• Use a time-bucketed Bloom filter (10 one-minute filters, rotated each minute): very small memory, no false negatives, a small tunable false-positive rate (it would occasionally suppress a real first-time notification). State whether that's acceptable.

5) Beyond One Machine

• Partition by ID: route each notification to the node that owns hash(id) (consistent hashing). Each node runs this engine locally.
• Or a shared store: Redis SET id 1 NX EX 600. Atomic "set if not exists with a 10-minute TTL" is exactly this rule, with one network round trip per check.
• Order of operations: if we mark "seen" and then the send fails, a retry would be suppressed. Either mark only after a successful send, or allow the sender's retry to bypass the check using the same attempt token. Choose based on whether duplicates or misses are worse.

6) Wrap-Up

Keep a hash map of ID → first-accepted time plus a FIFO expiry queue, so each check first drops entries older than 10 minutes and then accepts or suppresses the ID in amortized O(1). Shard the structures with separate locks for concurrency, bound memory (hashed IDs or rotating Bloom filters when needed), and scale out by partitioning IDs across nodes or using Redis SET NX EX 600.