Notification System — Push to Followers on New Post

Onsite SD round. Design a push-notification service: when a user creates a new post, every follower receives a notification. The interviewer treats it as a product-flavored design (not pure infra), so weighting is on data model + fanout strategy + delivery guarantees rather than on cluster topology. Requirements Functional: A user creates a post → every follower of that user gets a notification. Notifications must be deliverable to multiple device types (mobile push via APNs / FCM, web push, in-app inbox). Support read / unread state, mark-as-read, and delete from inbox. Tolerate offline followers — notifications queue until the device reconnects. Scale (rough working numbers for the discussion): 100M users, average 300 followers, peak post rate ~10K/s. Latency target: p50 < 5s, p99 < 30s for normal authors (first-batch delivery should feel real-time); availability 99.9%+; durability is the hard requirement — a lost post event is unrecoverable. Decision points the interviewer probes: Fanout-on-write vs fanout-on-read — when does each break down (celebrity users with millions of followers)? Hybrid fanout: write for normal users, read for celebrities. Where do you draw the line? Idempotency and deduplication when a worker retries. Backpressure when a downstream provider (APNs) throttles. Notes The round is in-person on a laptop — type your reasoning into the shared doc rather than relying on a whiteboard photo. The product-design angle matters: define the notification payload schema, the inbox API, and how it interacts with feed ranking. Cover the celebrity problem explicitly. Pure fanout-on-write with a 50M-follower account writes 50M rows per post; degrade to fanout-on-read for that segment and merge at fetch time. Discuss exactly-once vs at-least-once delivery — push providers are at-least-once; the inbox layer must dedupe by (post_id, user_id). Mention metrics: delivery latency p50/p99, fanout queue depth, provider throttle rate. The standard hybrid threshold in production designs is on the order of ~10K followers: under it, fan-out-on-write into a per-user precomputed-feed table (≈200 recent posts × ~2KB per row); over it, store the post once and merge at read time. Celebrities are flagged in the Follow table so the post-create worker can skip their write-fanout. Two different thresholds are in play: the fan-out-on-write-vs-read line (~10K) above, and a separate paced-campaign trigger for true hot authors — below ~100K opted-in followers enqueue all shards at high priority; above it, create a campaign that splits followers into ~50K-follower shards and paces shard dispatch so provider quotas are respected and progress is checkpointed (never scan all of a celebrity's followers in one query). Use a pub/sub bus (Kafka / Redis pub-sub) keyed on user_id for the delivery side: each post-create publishes a fanout job, sharded workers consume and route to the per-device WebSocket or push provider. This is the same shape WhatsApp-style designs use to scale a single chat-server farm — any worker can serve any user because routing is decoupled from connection ownership. Track delivery per (user_id, client_id) not per user_id — a user with phone + tablet + web has three rows in the Inbox table and three independent ack states. Behind the fanout bus, a bounded queue is doing two jobs that often get conflated: (1) decoupling post-create latency from delivery latency, and (2) backpressure when APNs/FCM throttle — the queue absorbs the slowdown without spilling 429s back to the author. Surface both in the design. Cache hot-key reads (viral post inbox entries) in a non-sharded Redis replica set to avoid a single shard's CPU melting. Provider failures & token hygiene: retry temporary provider errors with exponential backoff + jitter; on a permanent error mark the device token invalid and stop sending, emitting an invalid-token event back to the Device service for cleanup. Cap retry age so a stale "new post" push is never delivered hours late, and batch sends by provider + platform. Provider acceptance ≠ user-visible delivery — an APNs/FCM success only means the message was accepted, not seen. Multi-region: run stateless API / orchestration / dispatch workers in several regions with region-local, mirrored-failover queues; the follower graph and notification store tolerate eventual consistency across regions — only the initial post write needs strong consistency, so keep it off the cross-region synchronous path. Canonical data model & write-path details Transactional outbox between POST /posts and the post_created event: write the post row and an outbox row in the same transaction, then a relay publishes to the bus. Publishing separately is the classic lost-notification bug — the post commits but the trigger is dropped if the process crashes. Model the follower edge as (author_id, shard_id, follower_id) so a celebrity never collapses to one hot partition; carry per-edge notify_on_post / muted / blocked on the edge, but keep user-global quiet_hours + timezone in a separate preference row so a timezone change does not rewrite every follow edge. Split the record in two: a follower-level Notification (canonical, with a UNIQUE dedupe_key on (post_id, follower_id, channel)) and per-device NotificationAttempt rows. The parent status aggregates from children — dispatched = ≥1 device accepted, opened = any device opened, exhausted = all devices permanently failed or retry budget spent. The full Notification.status lifecycle is scheduled → delayed → queued → dispatched → opened, with terminal suppressed (filtered out before send), expired, and exhausted. Quiet hours = defer, not drop. Create the notification, compute the next valid send time in the user's timezone, set scheduled_for, and release it from a delayed queue later. Filter as late as possible (during shard expansion / just before dispatch), not at event-creation time — otherwise a user who mutes or unfollows seconds after the post still gets pushed. Working capacity numbers for the estimate: ~30M DAU, ~15M posts/day, ~200 opted-in followers/post → ~3B candidate notifications/day (~35K/s avg, 350K/s peak), celebrity fanout up to ~20M recipients per post; store ~250 bytes of compact metadata per recipient (template id, actor, post id, state) and render the provider payload at dispatch time. At ~250 bytes × ~3B/day that is ~750 GB/day of hot notification state, ~5.25 TB at 7-day retention before replication. Preparation Pre-write a 10-minute whiteboard skeleton: post-write API → fanout queue (Kafka) → per-shard worker pool → device-router (APNs / FCM / web) → device. Be able to draw the hybrid fanout decision tree and pick a follower-count threshold (e.g. 10K). Practice the read-path: an inbox service backed by per-user Redis sorted set or a sharded Cassandra table keyed on (user_id, ts). Cross-train with the standard "design Twitter / News Feed" interview — most of the building blocks transfer.