System Design Case Study

Problem Statement

Multiple triggers can fire the same notification: producer retries after timeout, multiple event sources for the same business event, Kafka consumer rebalance replaying messages. How do you prevent sending the same notification twice to a user while maintaining at-least-once processing guarantees from the queue?

Functional Requirements

What the deduplication layer must do

Non-Functional Requirements

Quality constraints for the deduplication middleware

Scale Estimation

Sizing the dedup infrastructure for 5B notifications/day

APIs

Deduplication is internal middleware — not user-facing. Integrated into the send path.

{
  "user_id": "u_abc123",
  "template_id": "order_shipped",
  "params": { "order_id": "ORD-9876" },
  "channels": ["push", "email"],
  "dedup_key": "order_shipped:ORD-9876:u_abc123",   // explicit override
  // If dedup_key omitted, system generates: SHA256(user_id + template_id + sorted(params))
  "dedup_ttl_sec": 86400                             // optional: custom TTL (default 24h)
}

// Response when first send:
202 Accepted: { "notification_id": "n_001", "status": "queued", "dedup": "new" }

// Response when duplicate detected:
200 OK: { "notification_id": "n_001", "status": "already_sent", "dedup": "duplicate", "original_sent_at": "..." }

// Pseudocode — runs inside every worker before send
function checkDedup(notification):
    dedup_key = notification.dedup_key 
                || sha256(notification.user_id + notification.template_id + sortedHash(notification.params))
    
    // Atomic: SET if NOT EXISTS, with TTL
    result = redis.SET("dedup:" + dedup_key, notification.id, NX=true, EX=86400)
    
    if result == OK:
        return PROCEED      // first time seeing this key → send notification
    else:
        return SKIP         // key already exists → duplicate → skip silently
        log.info("Dedup suppressed", {dedup_key, original: redis.GET("dedup:" + dedup_key)})

function generateDedupKey(user_id, template_id, params):
    // Sort params for deterministic hashing (order-independent)
    sorted_params = JSON.stringify(sortKeys(params))
    
    // Concatenate with separator to avoid collisions
    input = user_id + "|" + template_id + "|" + sorted_params
    
    // SHA-256 truncated to 128 bits (sufficient for 5B daily notifications)
    hash = sha256(input).substring(0, 32)  // 32 hex chars = 128 bits
    
    return "dedup:" + hash
    
// Example:
// user_id: "u_abc123", template: "order_shipped", params: {"order_id": "ORD-9876"}
// → "dedup:a7f3b2c1d4e5f6a7b8c9d0e1f2a3b4c5"

Data Model

Minimal storage — just the dedup key and metadata

Redis: Dedup Keys (Primary Store)

// Each dedup key is a simple Redis key with TTL
// Key: dedup:{hash}
// Value: notification_id (for audit/debugging)
// TTL: 24 hours (86400 seconds)

SET dedup:a7f3b2c1d4e5f6a7b8c9d0e1f2a3b4c5 "n_001" NX EX 86400

// NX = Set only if Not eXists (atomic check-and-set)
// EX = Expire in seconds
// Returns OK if set (first time) or nil if already exists (duplicate)

// Memory per key:
//   Key: "dedup:" + 32 chars = 38 bytes
//   Value: notification_id ~20 bytes
//   Redis overhead: ~40 bytes (dict entry, expire entry)
//   Total: ~100 bytes per key

delivery_log (Cassandra — audit trail)

CREATE TABLE delivery_log (
  notification_id   UUID PRIMARY KEY,
  user_id           TEXT,
  template_id       TEXT,
  dedup_key         TEXT,            -- the hash used for dedup
  status            TEXT,            -- sent | dedup_suppressed
  attempts          INT,             -- how many times this dedup_key was seen
  first_seen_at     TIMESTAMP,
  last_seen_at      TIMESTAMP,
  sent_via          TEXT             -- channel that actually delivered
);

// Query: "How many duplicates were suppressed for notification N?"
// SELECT attempts FROM delivery_log WHERE notification_id = ?

Redis: Active Dedup Keys (SET for monitoring)

// Optional: track active dedup keys per user for debugging
// Sorted set: score = timestamp, member = dedup_key
ZADD active_dedup:u_abc123 1705312200 "a7f3b2c1d4e5f6a7b8c9d0e1f2a3b4c5"

// Cleanup: ZREMRANGEBYSCORE active_dedup:{user_id} 0 (now - 86400)
// Usage: "Show me all dedup keys for this user in last 24h"
// Useful for support debugging: "Why didn't my notification arrive?"

Dedup Key Composition

// The dedup key uniquely identifies "same notification to same user"
// Components:
//   1. user_id      → same user
//   2. template_id  → same notification type
//   3. params_hash  → same parameters (order_id, etc.)

// Examples of SAME dedup key (duplicates):
//   Send #1: user="u_abc", template="order_shipped", params={order: "ORD-9876"}
//   Send #2: user="u_abc", template="order_shipped", params={order: "ORD-9876"}  ← DUPLICATE

// Examples of DIFFERENT dedup keys (not duplicates):
//   user="u_abc", template="order_shipped", params={order: "ORD-9876"}
//   user="u_abc", template="order_shipped", params={order: "ORD-9877"}  ← different order
//   user="u_def", template="order_shipped", params={order: "ORD-9876"}  ← different user

Architecture Overview

Event → Generate dedup_key → Redis SETNX → If new: send → If exists: skip

Key Design Decisions

Tradeoffs for deduplication at scale

Resilience & Edge Cases

Edge cases specific to deduplication at scale

Interview Cheat Sheet

5 key points for notification deduplication design interviews