Design a Notification System: Queues, Preferences, Idempotency

"Design a notification system" sounds like plumbing: something happens, send a message. The interview is really about three failures that plumbing ignores: a burst that arrives faster than providers accept it, a provider that stops answering, and a retry that sends the same message twice. Get those three right and the boxes on the diagram mostly draw themselves.

The problem it solves

One event, such as "your order shipped" or "a storm warning for your area", has to become the right messages on the right channels: push, email and SMS. Each user chooses which channels they want and may have quiet hours. The lesson's working assumptions are 5 million users and bursts of 200,000 notifications a minute after something big happens.

That burst is about 3,300 notifications a second, and the rest of the week may be far quieter. So the system must accept work at the burst rate, but it only needs to send at whatever rate the channel providers and your budget allow. The design is about decoupling those two rates.

Functional requirements to agree on up front:

• Services publish events; the notification system decides who gets what, on which channel.
• Users control channels and quiet hours; urgent messages may override quiet hours.
• Every notification is delivered once from the user's point of view, or visibly parked as failed.

The intuition

Split the path into stages and put a queue between the fast part and the slow part:

• Ingest. Accept the event, validate it, write it to a durable queue and answer immediately. The caller never waits for an email provider.
• Fan-out and preferences. Workers read events, expand them into one job per user and channel, and drop the channels a user has turned off. A job that falls in quiet hours is scheduled for later unless it is urgent.
• Send. Channel workers hand each job to its provider and record the result.

The queue is the reason bursts and outages stop being emergencies. A burst becomes queue depth, which you can watch and drain by adding workers. A provider outage becomes jobs that retry with exponential backoff and, after a limit, move to a dead-letter queue for a human, instead of retrying forever.

The price is at-least-once delivery. When a worker sends a message but crashes, or its acknowledgement is lost, before the queue records success, the job is delivered to a worker again. So every job carries an idempotency key built from stable facts, the event ID, the user and the channel, and a worker checks the key before sending.

Watch it run

The animation follows one event through the pipeline. Ingest writes it to the queue and answers in milliseconds; a burst piles up as visible depth, and nothing is dropped. A job looks up the user's preferences, push and email but not SMS, and the idempotency key is checked before anything is sent. Then the email provider stops answering: that one job retries with backoff and is parked, while push goes out normally.

The code

A toy model, not a production service: fan-out with preferences and quiet hours, and idempotency keys that stay the same across retries:

PREFS = {
    "u1": {"channels": ["push", "email"], "quiet": (22, 7)},
    "u2": {"channels": ["sms"], "quiet": None},
}

def in_quiet_hours(hour, quiet):
    if quiet is None:
        return False
    start, end = quiet
    if start > end:                                      # wraps past midnight
        return hour >= start or hour < end
    return start <= hour < end

def plan(event, hour):
    """Expand one event into (idempotency_key, user, channel, when) jobs."""
    jobs = []
    for user in event["users"]:
        pref = PREFS[user]
        when = "later" if in_quiet_hours(hour, pref["quiet"]) and not event["urgent"] else "now"
        for channel in pref["channels"]:
            key = f'{event["id"]}:{user}:{channel}'     # stable across retries
            jobs.append((key, user, channel, when))
    return jobs

event = {"id": "evt-7", "users": ["u1", "u2"], "urgent": False}
for job in plan(event, hour=23):
    print(job)
# ('evt-7:u1:push', 'u1', 'push', 'later')
# ('evt-7:u1:email', 'u1', 'email', 'later')
# ('evt-7:u2:sms', 'u2', 'sms', 'now')

Retries wait longer each time, up to a cap, so a struggling provider is not hammered. A worker skips any key it has already sent and parks a job after too many failures:

def backoff(attempt, base=1.0, cap=60.0):
    return min(cap, base * 2 ** attempt)                # seconds before a retry

print([backoff(a) for a in range(8)])
# [1.0, 2.0, 4.0, 8.0, 16.0, 32.0, 60.0, 60.0]

class Worker:
    def __init__(self, provider, max_attempts=5):
        self.sent = set()               # keys already handed to a provider
        self.log = []                   # what users actually received
        self.parked = []                # gave up: dead-letter for a human
        self.provider = provider
        self.max_attempts = max_attempts

    def handle(self, job, attempt=0):
        key = job[0]
        if key in self.sent:
            return "duplicate skipped"
        if not self.provider(job):
            if attempt + 1 >= self.max_attempts:
                self.parked.append(key)
                return "parked"
            return "retry"
        self.sent.add(key)
        self.log.append(key)
        return "sent"

w = Worker(provider=lambda job: True)
job = plan(event, hour=12)[0]
print(w.handle(job), w.handle(job))                     # sent duplicate skipped

The guarantees, checked over 500 random runs where 30% of provider calls fail, retries arrive in random order, and 20% of successful sends are redelivered as if the acknowledgement were lost. With keys, nobody receives a message twice and every job ends up sent or parked; without the key store, duplicates appear. The quiet-hours rule is checked against walking the clock hour by hour:

import random

def run(jobs, dedupe, seed):
    rng = random.Random(seed)
    w = Worker(provider=lambda job: rng.random() > 0.3)   # 30% of calls fail
    queue = [(job, 0) for job in jobs]
    while queue:
        job, attempt = queue.pop(rng.randrange(len(queue)))
        if not dedupe:
            w.sent.clear()                              # no idempotency store
        result = w.handle(job, attempt)
        if result == "retry":
            queue.append((job, attempt + 1))
        elif result == "sent" and rng.random() < 0.2:   # at-least-once: the
            queue.append((job, attempt))                # ack was lost, redeliver
    return w

ok = True
dupes_without_keys = 0
for seed in range(500):
    users = [f"u{i}" for i in range(1, 3)]
    jobs = plan({"id": f"e{seed}", "users": users, "urgent": True}, hour=12)
    w = run(jobs, dedupe=True, seed=seed)
    keys = [j[0] for j in jobs]
    ok &= len(w.log) == len(set(w.log))                 # nobody got it twice
    ok &= sorted(w.log + w.parked) == sorted(keys)      # every job accounted for
    loose = run(jobs, dedupe=False, seed=seed)
    dupes_without_keys += len(loose.log) > len(set(loose.log))

for start in range(24):
    for end in range(24):
        quiet_set = set()                               # walk the clock by hand
        h = start
        while h != end:
            quiet_set.add(h)
            h = (h + 1) % 24
        ok &= all(in_quiet_hours(x, (start, end)) == (x in quiet_set) for x in range(24))
print(ok, dupes_without_keys > 0)                       # True True

The complexity

The costs here are throughput and storage, not asymptotics:

• Fan-out multiplies work. One event to u users with c channels each is u × c jobs. A broadcast to all 5 million users is millions of jobs, so fan-out itself runs in parallel workers reading from the queue, not in the request handler.
• The idempotency store grows with every send. Keys only need to live as long as a redelivery is possible, so they can expire after a retention window instead of forever.
• Send rate is set by the slowest dependency. Workers scale out, but each provider has its own throughput limits and its own price per message. Batching or digesting low-priority notifications cuts both.

Where it goes wrong

• Sending inline from the request. A slow provider then slows every caller, and a burst turns into timeouts and dropped events.
• Keys that change on retry. A key built from a timestamp or a random ID is different on the second attempt, so it protects nothing.
• Believing in exactly-once. A worker can send and then crash before recording the key, and the retry sends again. Keys make duplicates rare, not impossible; if a provider accepts an idempotency key of its own, pass yours through.
• Retrying forever. Without a cap and a dead-letter queue, one bad address or a dead provider becomes permanent load.

How to say it in an interview

"I'd split it into ingest, fan-out and send, with a durable queue between them. Ingest just validates and enqueues, so bursts become queue depth, which I can drain by scaling workers. Fan-out applies each user's channel preferences and quiet hours, with an urgent override. Sends retry with exponential backoff and a cap, then go to a dead-letter queue. Because the queue is at-least-once, each job has an idempotency key from event, user and channel, checked before sending. That makes duplicates rare, not impossible, and I'd say so."

The fan-out half of this design shows up again in design a news feed, and the queue choices behind it are compared in SQS vs SNS vs EventBridge.