Design a notification and fan-out system

"Design a notification system: push, email, SMS and in-app, across 200 million users, with per-user preferences and no duplicates."

Step 1: clarify (4 minutes)

What triggers a notification? Three sources with different characteristics, and lumping them together is the first mistake:

Transactional   "Your order shipped."  1:1, low volume, HIGH urgency,
                must not be lost, must not be delayed.
Social          "Alice commented on your post."  1:N where N can be
                millions, moderate urgency, individually droppable.
Campaign        "Weekend sale."  1:200M, no urgency, scheduled,
                and it is the source of every capacity problem.

Assume all three, and design so they cannot interfere with each other. That separation is a large part of the answer.

Is there a fan-out ceiling? A celebrity with 50 million followers posting once produces 50 million notifications. Assume yes, and assume this is the hard case.

What are the delivery guarantees? Assume at-least-once with idempotent deduplication, which is the only honestly achievable combination, and say so as in the job scheduler design.

How rich are preferences? Assume: per channel, per notification type, quiet hours in the user's timezone, frequency caps, and a global unsubscribe. Preference evaluation is the highest-QPS component in the system and candidates routinely treat it as a lookup.

What about compliance? Global unsubscribe and marketing consent are legal obligations (CASL in Canada, GDPR in the EU, CAN-SPAM in the US), not preferences. They are evaluated differently and they cannot be overridden by any retry or bug.

Step 2: capacity math (4 minutes)

Users            200M
Notifications    ~500M/day average
Peak             A campaign to 200M users, targeted at 09:00 local time
                 across timezones -> 24 waves of ~8M each, but a global
                 campaign is 200M in one hour = ~55,000/sec

Fan-out spike    A celebrity post to 50M followers.
                 If done synchronously: 50M writes in one request. No.
                 If done at 100k/sec: 500 seconds. Acceptable for social,
                 unacceptable for transactional if they share a queue.

Preference checks
  Every notification needs a preference evaluation BEFORE it is worth
  building a payload. At 55,000/sec that is 55,000 preference reads/sec
  minimum, and more if fan-out is evaluated per recipient.
  A celebrity fan-out at 100k/sec = 100k preference reads/sec.
  -> Preferences must be in a cache, not a database, and they must be
     small enough to hold: 200M users x 200 bytes = 40 GB.
     Sharded Redis, or a local cache with CDC invalidation.

Dedupe state
  500M/day x 7 day window x 32 bytes of key = 112 GB.
  Too big for memory as exact keys. Options: a shorter window,
  Redis with TTL and sharding, or a probabilistic filter with an
  exact backstop for high-stakes channels.

Device tokens    200M users x ~1.6 devices = 320M tokens.
                 Token churn is ~2%/month, so invalid-token cleanup
                 is a permanent background job, not a one-off.

The two numbers that shape the design: 100,000 preference reads per second during a fan-out, and a 112 GB exact dedupe window. Both push work out of the database and into caches, and both are where naive designs fall over.

Step 3: architecture

  producers (order service, social service, campaign tool)
        │
        ▼
  ┌──────────────────┐
  │  INGEST API      │  validate, assign notification_id,
  │                  │  classify priority, dedupe on request key
  └────────┬─────────┘
           ▼
  ┌──────────────────────────────────────────────┐
  │  PRIORITY QUEUES (separate topics, not one)  │
  │   transactional │ social │ campaign          │
  └────────┬─────────────────────────────────────┘
           ▼
  ┌──────────────────┐
  │  FAN-OUT WORKERS │  audience -> recipients, chunked
  └────────┬─────────┘
           ▼
  ┌──────────────────┐
  │  PREFERENCE +    │  channels, quiet hours, caps, consent
  │  ELIGIBILITY     │  <- highest QPS component
  └────────┬─────────┘
           ▼
  ┌──────────────────┐
  │  DEDUPE          │  idempotency key -> already sent?
  └────────┬─────────┘
           ▼
  ┌──────────────────┐
  │  RENDER          │  template + locale + personalisation
  └────────┬─────────┘
           ▼
  ┌───────┬────────┬────────┬────────┐
  │ APNs  │  FCM   │ email  │  SMS   │  per-channel senders,
  │       │        │ (SES)  │(Twilio)│  each with its own rate
  └───────┴────────┴────────┴────────┘  limits and retry policy
           │
           ▼
  ┌──────────────────┐
  │  FEEDBACK        │  delivered, opened, bounced, unsubscribed,
  │                  │  invalid token -> back into preferences
  └──────────────────┘

Separate topics per priority class is the single most important structural decision. One queue means a 200-million campaign delays a password reset by twenty minutes, and that is the most common real-world failure of these systems. Separate topics, separate consumer groups, separate autoscaling, and the transactional consumers are never starved.

Step 4: fan-out, and the celebrity problem

# WRONG: one message carrying 50 million recipient ids.
{"post_id": "p1", "recipients": [50 million ids]}
#   - exceeds any message size limit
#   - not retryable: a failure at recipient 30M redoes 30M
#   - no progress visibility

# RIGHT: a fan-out job that expands in bounded chunks, resumably.
{"job_id": "fx-9912", "post_id": "p1", "audience": "followers:u_taylor",
 "cursor": null, "chunk_size": 10000}

def expand(job) -> None:
    cursor = job.cursor
    while True:
        # Cursor pagination over the audience, not offset, so the
        # scan cost stays flat and concurrent follower changes do
        # not shift the window.
        batch, cursor = audience_store.scan(job.audience, cursor, 10_000)
        if not batch:
            break

        # Bulk preference filtering: ONE multi-get for 10,000 users,
        # not 10,000 round trips. This is the difference between
        # 100k/sec and 3k/sec.
        eligible = preference_cache.filter_bulk(batch, job.notification_type)

        enqueue_delivery_batch(job.job_id, eligible, job.payload_ref)

        # Checkpoint after every chunk. A crash resumes here, and a
        # duplicate chunk is harmless because delivery is deduped.
        checkpoint(job.job_id, cursor)

        if rate_limiter.should_pause(job.priority):
            requeue(job, cursor)      # yield to higher-priority work
            return

Four properties worth naming. Cursor pagination so scan cost stays flat and a concurrent follower change does not shift the window. Bulk preference filtering, which is the difference between 100,000 per second and 3,000. Checkpointing so a crash at recipient 30 million resumes rather than restarts. And voluntary yielding, so a celebrity fan-out cannot monopolise the workers while transactional work waits.

The payload is stored once and referenced, not copied into 50 million messages. Fifty million copies of a 2 KB payload is 100 GB of queue traffic for one post.

When not to fan out at all

The push/pull decision from the news feed design applies here too. For a user with 50 million followers, writing 50 million notification rows may be the wrong model entirely: notify the 1 percent with high affinity eagerly, and let everyone else discover the post through the feed. Whether a notification is worth sending is a product question, and the system should make it cheap to answer "no" for most recipients.

Step 5: preferences, the highest-QPS component

# The full evaluation, in the order that is cheapest-to-most-expensive,
# because most notifications are rejected and rejecting early is free.
def is_eligible(user_id: str, notif_type: str, channel: str,
                now: datetime) -> tuple[bool, str]:
    prefs = preference_cache.get(user_id)          # one hit, ~40 GB total

    # 1. Legal first. This is not a preference and cannot be overridden.
    if channel == "email" and prefs.email_consent_withdrawn:
        return False, "consent_withdrawn"
    if prefs.global_unsubscribe and notif_type not in TRANSACTIONAL_TYPES:
        return False, "global_unsubscribe"

    # 2. Explicit user choice.
    if not prefs.channels.get(channel, {}).get(notif_type, True):
        return False, "type_disabled"

    # 3. Quiet hours, in the USER's timezone. Getting this wrong
    #    wakes people at 3am and is the fastest route to an uninstall.
    local = now.astimezone(ZoneInfo(prefs.timezone))
    if prefs.quiet_start <= local.time() < prefs.quiet_end:
        if notif_type in TRANSACTIONAL_TYPES:
            pass                    # transactional overrides quiet hours
        else:
            return False, "quiet_hours"     # defer, do not drop

    # 4. Frequency cap. A sliding window per channel.
    if freq_counter.count(user_id, channel, window="24h") >= prefs.daily_cap:
        return False, "frequency_cap"

    return True, "ok"

Four properties to defend:

Legal before preference before quiet hours before caps, because the checks get more expensive in that order and most rejections happen at the cheap end.

Quiet hours defer rather than drop, for anything worth sending at all. Dropping means the user simply never learns about it; deferring to the start of their next active window is nearly always the intended behaviour and it is what people forget to build.

Transactional overrides quiet hours and preferences, within limits. A password reset at 3am is correct. A marketing message is not. That distinction has to be in the type taxonomy rather than in the sending code.

Frequency caps are per channel, not global. Three pushes and one email is different from four pushes.

The cache invalidation path matters: a user turning off notifications must take effect in seconds, not at the next cache refresh. CDC from the preference database into a cache-invalidation topic, and each cache node subscribes. A stale preference cache is a compliance problem, not a performance one.

Step 6: deduplication

Duplicates come from four places, and only naming all four demonstrates you have run one of these systems.

1. Producer retries       (the order service sends twice)
2. Queue redelivery       (at-least-once semantics, by design)
3. Fan-out chunk replay   (a worker crashed and resumed)
4. Genuine duplicate events (two services both notice the same thing)

The mechanism is one derived idempotency key, checked once:

# Derived from what makes the notification unique, NOT random.
# Same event + same user + same channel = same key, always.
dedupe_key = sha256(f"{event_id}:{user_id}:{channel}".encode()).hexdigest()[:16]

def send_once(dedupe_key: str, ttl_seconds: int = 86_400 * 7) -> bool:
    # SET NX is atomic: exactly one caller gets True.
    return bool(r.set(f"dd:{dedupe_key}", "1", nx=True, ex=ttl_seconds))

Sizing the window is the real decision, and the arithmetic is the answer. 500 million per day over 7 days at 32 bytes is 112 GB, which is a large Redis fleet purely for dedupe. Three options, and I would take a mixture:

Short window (24h)   500M keys x 32 B = 16 GB. Sharded Redis, easy.
                     Covers retries and redelivery, which is 95% of it.

Long window,         A Bloom or Cuckoo filter at ~10 bits/key for 3.5B
probabilistic        keys is ~4 GB. False positives mean a notification
                     is silently NOT sent, which is only acceptable for
                     campaign traffic.

Exact for            Transactional traffic is a small fraction of volume,
transactional        so keep it exact with a 30-day window. It is the
                     traffic where a missed send actually costs something.

Stating the false-positive consequence is what makes the probabilistic answer credible: a Bloom filter false positive silently drops a notification, which is fine for a sale announcement and unacceptable for a shipping confirmation, so the channel determines the mechanism.

Step 7: the channel senders, and their real constraints

Each channel is its own system with its own limits, and treating them uniformly is a design error.

APNs (iOS)
  HTTP/2 multiplexed, keep connections warm (handshake is expensive).
  BadDeviceToken / Unregistered -> delete the token immediately.
  Collapse ID: replaces an undelivered notification with a newer one,
  which is how you avoid a user seeing 40 stale alerts after being
  offline.

FCM (Android)
  Batch send up to 500 tokens per request. Per-project quotas.
  UNREGISTERED / INVALID_ARGUMENT -> delete the token.

Email (SES / SendGrid)
  Reputation is the constraint, not throughput. Bounce rate above ~5%
  and complaint rate above ~0.1% risk suspension, so bounce handling
  is a correctness requirement rather than hygiene.
  Warm up new sending IPs over weeks.
  Dedicated IP pools per traffic class, so a campaign's complaints
  cannot damage transactional deliverability. This is the email
  equivalent of separate queues, and it is the same idea.

SMS (Twilio)
  Most expensive per message by an order of magnitude, so cost caps
  belong in the system. Carrier rate limits per sending number.
  Regulatory: A2P 10DLC registration in the US, sender ID rules
  elsewhere. Not optional and not fast to obtain.

In-app
  Just a write to a per-user inbox. Cheapest, most reliable, and the
  right fallback when every other channel is disabled.

Bounce and invalid-token feedback loops back into preferences and this is not optional: an unhandled hard bounce repeated daily destroys sender reputation, and an invalid device token retried forever wastes a permanent fraction of capacity.

Step 8: failure modes and degradation

APNs / FCM outage
  -> Do not drain the retry queue against a dead provider; circuit-break.
     Queue with a TTL matched to the notification's usefulness: a
     "someone liked your post" is worthless after 6 hours, so expire it
     rather than delivering a confusing burst on recovery.

Campaign floods the system
  -> Separate topics already prevent starvation. Add a global cost
     and volume budget per campaign, enforced at ingest, because the
     cheapest place to stop a bad campaign is before fan-out.

Preference cache down
  -> FAIL CLOSED for marketing (do not send), fail open for
     transactional (send). Sending marketing to someone who opted out
     is a legal problem; delaying it is not.

Duplicate storm from a producer bug
  -> Dedupe absorbs it, and the dedupe rejection RATE is an alert,
     because a sudden spike in dedupe hits means an upstream bug.

Template render failure
  -> Never send a partially-rendered notification. Fail the message
     into a dead-letter queue, alert, and keep the rest flowing.

Timezone data staleness
  -> Quiet hours depend on tzdata. An out-of-date tzdata after a DST
     rule change sends notifications an hour off for a whole region.
     Pin and update it deliberately.

The degradation ladder: drop campaign traffic first, then social, and never transactional. Because the queues are already separate, this is a consumer-scaling decision rather than an architectural change, which is the payoff for the step-3 structure.

Step 9: what changes at ten times the scale

At 2 billion users and 5 billion notifications a day:

Preferences stop fitting in one cache tier. 2 billion users at 200 bytes is 400 GB. The move is a local in-process cache of hot users (the active few percent) backed by a sharded remote cache, with CDC invalidation reaching both. Fan-out then does a bulk fetch of cold users, which is a different access pattern from the transactional path and worth separating.

Fan-out becomes a stream-processing problem. Chunked workers over a queue give way to a Flink or Spark Streaming job over the follower graph, with the audience materialised as a partitioned table and expansion parallelised by partition rather than by cursor.

Dedupe goes fully probabilistic for non-critical channels, with a per-partition Cuckoo filter (which supports deletion, unlike a Bloom filter) and an exact store only for transactional.

Cost becomes a first-class design constraint. At 5 billion messages a day, SMS at even a fraction of a cent dominates every other cost in the system, and the design gains a channel-selection optimiser: choose the cheapest channel that meets the required delivery confidence, rather than sending on every enabled channel.

Production evidence

Uber's published notification platform work describes exactly the priority-separation and per-channel-adapter structure, including handling provider outages without draining retries against a dead endpoint.

LinkedIn's "Air Traffic Controller" is the reference for the frequency-capping and relevance-filtering layer sitting between generation and delivery: their stated framing is that deciding not to send is the system's most valuable function, which is the argument for putting preference evaluation before payload construction.

Apple's APNs documentation specifies the HTTP/2 connection model, the apns-collapse-id header and the token-invalidation responses that make feedback handling mandatory rather than optional.

Amazon SES's published reputation thresholds (bounce rate under 5 percent, complaint rate under 0.1 percent) are why bounce handling is a correctness requirement, and dedicated IP pools are the documented mechanism for isolating traffic classes.

Twilio's A2P 10DLC documentation covers the US registration requirement for application-to-person SMS, which is a lead-time constraint that surprises teams late in a project.

Kleppmann's Designing Data-Intensive Applications chapter 11 covers the at-least-once plus idempotency framing that the dedupe design rests on.

The debate

The case for one unified pipeline: simpler to operate, one set of code paths, and priority can be a message attribute rather than a topic. Fewer moving parts is a real virtue.

The case for separate pipelines per priority class: a 200-million-recipient campaign and a password reset have nothing in common except the word "notification". Sharing a queue means the campaign delays the reset, and priority-within-a-queue does not save you because the consumers are still busy processing campaign messages.

The case for pushing preferences to the producer: let each service decide whether to notify, avoiding a central bottleneck. Fast, and it means consent logic is duplicated in twelve services and wrong in three of them.

My position: separate topics per priority class, centralised preference and consent evaluation, and derived idempotency keys with a channel-dependent dedupe window.

The separation is the decision I hold most firmly, because the failure it prevents is the one that actually happens: transactional notifications delayed behind a marketing campaign. It costs almost nothing (three topics instead of one) and no amount of in-queue prioritisation substitutes for it, since the consumers are still occupied.

Centralised preferences are non-negotiable for a different reason: consent is a legal obligation and it must have exactly one implementation. A service that forgets to check the unsubscribe flag is a regulatory incident, not a bug, and the only structural defence is that services cannot send directly.

On dedupe I would deliberately be inconsistent across channels, and say so: exact keys with a long window for transactional, a probabilistic filter for campaign traffic. A Bloom filter false positive silently drops a message, which is acceptable for a sale announcement and not for a shipping confirmation. Using one mechanism for both means either overpaying by an order of magnitude or accepting silent drops where they matter.

Where I would push back on the requirement itself: the most valuable thing this system does is decide not to send. Frequency caps, relevance filtering and quiet hours look like features and they are the retention mechanism, because notification fatigue produces uninstalls, and an uninstall is permanent in a way that a missed notification is not.

Follow-up Q&A

"A celebrity with 50 million followers posts. What happens?" A fan-out job, not a message. One message carrying 50 million recipient ids exceeds every size limit and is not retryable, because a failure at recipient 30 million redoes 30 million. Instead a job that expands the audience in 10,000-recipient chunks using cursor pagination, checkpointing after each chunk so a crash resumes, bulk-filtering preferences with one multi-get per chunk rather than 10,000 round trips, and yielding voluntarily when higher priority work is queued. The payload is stored once and referenced, because 50 million copies of a 2 KB payload is 100 GB of queue traffic for one post.

"Why separate topics rather than a priority field?" Because a priority field does not help when the consumers are already busy. If one consumer group is processing a 200-million campaign, a high-priority password reset sits behind whatever those consumers are doing regardless of its priority. Separate topics mean separate consumer groups with separate autoscaling, so transactional throughput is independent of campaign volume. It costs three topics instead of one, and it prevents the failure these systems actually have.

"Where do duplicates come from?" Four places: producer retries, queue redelivery which is by design in an at-least-once system, fan-out chunk replay after a worker crash, and two services genuinely noticing the same event. One derived idempotency key covers all four, hashed from event id, user id and channel, so the same event to the same user on the same channel always produces the same key. SET NX with a TTL is the check, and exactly one caller gets true.

"How big is the dedupe window and can you afford it?" 500 million a day over seven days at 32 bytes is 112 GB, which is a substantial Redis fleet for dedupe alone. So I would split it: a 24-hour exact window covers retries and redelivery, which is most of it, at 16 GB. Transactional traffic keeps an exact 30-day window because it is a small share of volume and it is the traffic where a missed send costs something. Campaign traffic goes to a Cuckoo filter at about 10 bits per key, and I would state the consequence out loud, which is that a false positive silently drops a message.

"What does the preference check actually evaluate, and in what order?" Legal first: withdrawn consent and global unsubscribe, which are obligations rather than preferences and cannot be overridden. Then explicit per-channel, per-type choices. Then quiet hours in the user's own timezone, where transactional overrides and everything else defers rather than drops. Then frequency caps per channel. The order is cheapest to most expensive, because most notifications are rejected and rejecting early is free.

"Quiet hours: drop or defer?" Defer, for anything worth sending at all. Dropping means the user never learns about it, which is almost never the intent; deferring to the start of their next active window is. The one exception is time-sensitive content that is worthless later, like a live-event alert, and that should carry an explicit expiry rather than being handled by the quiet-hours logic.

"The preference cache goes down. What do you do?" Fail closed for marketing and open for transactional. Sending marketing to someone who opted out is a regulatory incident; delaying it costs nothing. Not sending a password reset is a support incident. Those asymmetries are different so the failure behaviour should be different, and encoding that in one place is part of why preference evaluation is centralised.

"Why does bounce handling matter so much for email?" Because reputation is the throughput constraint, not bandwidth. SES suspends sending above roughly a 5 percent bounce rate or 0.1 percent complaint rate, so an unhandled hard bounce repeated daily does not just waste a send, it degrades deliverability for everything including transactional mail. Which is also why campaign and transactional traffic use separate dedicated IP pools: it is the email equivalent of separate queues, for the same reason.

"What's the most valuable thing this system does?" Decide not to send. Frequency caps, relevance filtering and quiet hours look like features and they are the retention mechanism, because notification fatigue causes uninstalls and an uninstall is permanent in a way a missed notification is not. LinkedIn's framing of their own system is that filtering is its primary function, and I would design the preference layer as the centre of the system rather than as a check before the interesting part.

Common misconceptions

"Fan-out is a message with many recipients." It is a resumable job with checkpoints. The message form is not retryable and does not fit.

"Priority is a field on the message." It is a topic. A field does not help when the consumers are already saturated.

"Preferences are a lookup." They are the highest-QPS component and they include legal obligations that must have exactly one implementation.

"Quiet hours mean don't send." They mean defer. Dropping silently loses information the user wanted.

"Email throughput is about bandwidth." It is about reputation. Bounce and complaint rates are the actual limit.

Interview delivery note

Split the traffic classes in the first minute, because everything follows from it: "Before designing anything I'd split this into three traffic classes: transactional, social fan-out, and campaign. They have completely different urgency, volume and failure tolerance, and the most common real failure of these systems is a password reset sitting behind a two-hundred-million-recipient campaign. So separate topics and separate consumer groups, not a priority field, because a field doesn't help when the consumers are already busy."

Then the fan-out mechanics, concretely: "A celebrity post is a job, not a message. One message with fifty million recipient ids exceeds every size limit and isn't retryable, because failing at recipient thirty million redoes thirty million. So: cursor pagination in ten-thousand chunks, checkpoint after each one, bulk preference filtering with a single multi-get per chunk, and voluntary yielding so it can't monopolise the workers."

Do the dedupe arithmetic out loud, because it forces a real decision: "Five hundred million a day over a seven-day window at thirty-two bytes is a hundred and twelve gigabytes, which is a lot of Redis for dedupe. So I'd split it by channel: exact keys with a long window for transactional, a Cuckoo filter for campaign, and I'd say the consequence plainly, which is that a false positive silently drops a message. That's fine for a sale announcement and not for a shipping confirmation."

Close on the reframe, which is the strongest thing to say here: "and the most valuable thing this system does is decide not to send. Frequency caps and quiet hours look like features and they're the retention mechanism, because notification fatigue causes uninstalls, and an uninstall is permanent in a way a missed notification isn't."

The Staff & Team Lead Interview Reference