News Feed System — System Design Interview

Phase 1: Clarify, Scope & Constraints

Interviewer: "Design a news feed system like Twitter's home timeline or Facebook's feed. Users follow other users; when they open the app, they see a ranked list of recent posts from people they follow. Where do you start?"

Candidate: "Let me clarify the key user journeys and then identify what makes this system hard:

Core user journeys:

1. Post: A user creates a post (text, image, or video link). It should appear in their followers' feeds.
2. Read Feed: A user opens the app and sees recent posts from people they follow, ordered by recency or relevance score.
3. Follow/Unfollow: A user follows or unfollows another user. This changes whose posts appear in their feed.

A few clarifying questions: Is the feed sorted by recency only, or is there a ranking algorithm? Is this a closed social graph (both users must follow each other, like Facebook friends) or a directed follow graph (like Twitter, where I can follow you without you following me)?"

Interviewer: "Directed follow graph, like Twitter. Recency sort for V1 — we can add ranking later. What's the core complexity?"

Candidate: "The core complexity is the fan-out problem on writes. When a user with 50 million followers posts, we need to update 50 million users' feeds. That's the defining challenge.

There are two opposing approaches:

• Fan-out on write (push model): When a post is created, immediately push it to all followers' feed caches. Feed reads are instant — it's pre-computed. But posting becomes an O(followers) operation.
• Fan-out on read (pull model): When a user opens their feed, we pull recent posts from all users they follow and merge them. No fan-out at write time. But reads become expensive — O(followees × recent posts).

Neither pure approach works at scale. The optimal answer is a hybrid: fan-out on write for most users, fan-out on read for celebrities (users with millions of followers).

WHY: Fan-out on write is O(followers) per post. For a user with 50M followers, that's 50M write operations for one post — unacceptable if synchronous, and still generates enormous Kafka lag if async. Fan-out on read for celebrity accounts is O(1) at write time; the read-time cost is bounded because a user follows a small number of celebrities (say, <10).

Non-goals for V1:

• Ranked/algorithmic feed — just recency
• Comments, likes, shares — the post creation and feed display are in scope; interaction counts are not
• Media hosting — assume posts reference media URLs already uploaded elsewhere
• Search or hashtag feeds

Non-functional requirements:

• Read latency: Feed P99 < 200ms
• Write latency: Post creation P99 < 500ms (the fan-out is async — user sees success immediately)
• Availability: 99.99% — feed unavailability is highly visible
• Consistency: Eventual. New posts can take up to 30 seconds to appear in all followers' feeds. This is acceptable for a social feed.
• Feed freshness SLA: 99% of posts appear in follower feeds within 60 seconds of posting

Back-of-envelope math:

Assumptions:

• 150M DAU, 500M total users
• Average user follows 500 accounts
• Average user posts once every 5 days = 0.2 posts/day
• Average user reads feed 10 times/day, fetching 20 posts per read
• 20% of users are 'celebrities' (>10K followers), 0.1% have >1M followers

Post QPS (write): $150M \times 0.2 = 30M \text{ posts/day}$ $30M \div 86{,}400 \approx 347 \text{ posts/s average}$ $\text{Peak posts} = 347 \times 5 = 1{,}735 \text{ posts/s}$

Feed read QPS: $150M \times 10 = 1.5B \text{ reads/day}$ $1.5B \div 86{,}400 \approx 17{,}361 \text{ reads/s average}$ $\text{Peak reads} = 17{,}361 \times 3 = 52{,}083 \text{ reads/s}$

Fan-out events (write amplification):

• Average follower count: 500M users × 500 avg follows / 500M users = 500 average followers
• Fan-out events/s: $1{,}735 \text{ posts/s} \times 500 \text{ avg followers} = 867{,}500 \text{ feed inserts/s}$

WHY: 867K feed insert events/s is substantial but achievable with a distributed queue and multiple consumer workers. This number validates the need for async fan-out — synchronous fan-out would add 500+ database writes to every post operation.

Feed storage (Redis sorted sets):

• Cache 1000 most recent feed items per user
• Each feed item: 8 bytes (post_id) + 8 bytes (score/timestamp) = 16 bytes
• Per user: 1000 × 16 = 16 KB
• For 500M users: $500M \times 16\text{KB} = 8\text{ TB}$

WHY: 8 TB is too large for a single Redis instance but fine for a Redis Cluster (sharding by user_id). We only cache for active users — caching feeds for 150M DAU is: $150M \times 16\text{KB} = 2.4\text{ TB}$, manageable.

Interviewer: "Your fan-out number is 867K events/s. That seems very high. How do you make sure that doesn't overwhelm your system?"

Candidate: "The key insight is that 867K is the aggregate across all consumers — it's not a single database write load. We distribute this across a Kafka cluster with many partitions, consumed by many Feed Worker instances in parallel. Each worker handles a fraction of the fan-out. Kafka with a 3-node cluster easily handles millions of messages/second. The bottleneck isn't the queue — it's the downstream cache writes. At 16 bytes per operation, 867K writes/s to Redis is ~14 MB/s — very manageable."

Phase 2: High-Level Architecture

Interviewer: "What does your API look like?"

Candidate: "REST API with two primary endpoints:

POST /api/v1/posts
  Request:  { "content": "Hello world!", "media_urls": [] }
  Response: { "post_id": "1234567890", "created_at": "...", "author_id": "..." }
  Status:   201 Created

GET /api/v1/feed?limit=20&cursor=<timestamp_or_id>
  Response: {
    "posts": [
      {
        "post_id": "...",
        "author_id": "...",
        "author_username": "...",
        "content": "...",
        "created_at": "...",
        "media_urls": []
      }
    ],
    "next_cursor": "...",   // null if no more posts
    "has_more": true
  }
  Status: 200 OK

I'll use cursor-based pagination over offset pagination for feed reads. A cursor (e.g., the created_at timestamp of the last post) allows efficient range queries and handles concurrent inserts correctly.

WHY: Offset pagination (?page=3) is broken for feeds — by the time you request page 3, new posts have shifted items, causing duplicates or gaps. Cursor-based pagination is stable.

Data model:

Copy
-- Posts table (PostgreSQL — authoritative post data)
CREATE TABLE posts (
    post_id     BIGINT PRIMARY KEY,       -- Snowflake ID
    user_id     BIGINT NOT NULL,
    content     TEXT NOT NULL,
    media_urls  JSONB,
    created_at  TIMESTAMPTZ DEFAULT NOW(),
    is_deleted  BOOLEAN DEFAULT FALSE
);
CREATE INDEX idx_posts_user_id ON posts(user_id, created_at DESC);

-- Follows table (PostgreSQL — social graph)
CREATE TABLE follows (
    follower_id BIGINT NOT NULL,
    followee_id BIGINT NOT NULL,
    created_at  TIMESTAMPTZ DEFAULT NOW(),
    PRIMARY KEY (follower_id, followee_id)
);
CREATE INDEX idx_follows_followee ON follows(followee_id);  -- "who follows me?"

Redis feed cache:

# Sorted set per user: key = feed:{user_id}
# Score = post timestamp (unix ms) for recency ordering
# Value = post_id (8 bytes)
ZADD feed:12345 1705320000000 "post_id_abc"
ZADD feed:12345 1705319900000 "post_id_xyz"
ZREVRANGE feed:12345 0 19 WITHSCORES  # Get 20 most recent posts

WHY: Redis sorted sets are perfect for time-ordered feeds. ZADD is O(log N); ZREVRANGE is O(log N + M) where M is items returned. The score is the post timestamp, giving natural recency ordering.

Let me draw the core architecture:"

-+ResetFullscreen

Candidate: "Walk through the paths:

Write path (user posts):

1. Client POSTs to Post Service
2. Post Service generates Snowflake ID, INSERTs into PostgreSQL
3. Publishes post_created event to Kafka (async) — returns 201 to user immediately
4. Feed Worker consumes from Kafka, queries PostgreSQL for the author's follower list
5. For each follower, ZADD feed:{follower_id} {timestamp} {post_id} in Redis
6. Trims the sorted set to 1000 entries (removes old entries beyond limit)

Read path (user reads feed):

1. Client GETs feed from Feed Service
2. Feed Service does ZREVRANGE feed:{user_id} 0 19 — gets 20 post IDs from Redis
3. Batch-fetches post content: SELECT * FROM posts WHERE id IN (pid1, pid2, ...)
4. Assembles and returns the feed"

Interviewer: "What if the user's feed cache is empty — they're a new user or haven't opened the app in a week?"

Candidate: "Good catch — this is the 'cold feed' problem. If the sorted set doesn't exist or is stale:

1. Feed Service detects empty/missing cache
2. Falls back to a pull-based rebuild: query the follows table for the user's followee list, then query posts for each followee (limited to last 7 days), merge by timestamp, populate the Redis sorted set
3. Serve from the just-populated cache

This is expensive (N followees × 1 query each), so we batch the queries: SELECT * FROM posts WHERE user_id IN (followee1, followee2, ...) ORDER BY created_at DESC LIMIT 20.

We also pre-warm caches: when a user logs in after a long absence, trigger a background job to rebuild their cache before they scroll to the bottom."

Phase 3: Deep Dive & Evolution

Interviewer: "The celebrity problem. Walk me through what happens when Elon Musk posts a tweet and he has 100M followers."

Candidate: "With our current pure fan-out-on-write design:

1. Feed Worker queries follows table for Elon's follower list — 100M rows. This query itself takes seconds.
2. It needs to do ZADD on 100M Redis sorted sets — at 500K Redis ops/s, that takes ~200 seconds.
3. During those 200 seconds, the post event is stuck in Kafka. Other posts are delayed because our Feed Workers are busy with Elon's fan-out.

This is unacceptable. We need the hybrid fan-out approach.

Hybrid Fan-out strategy:

Define a threshold: users with > 1M followers are 'celebrities'.

• Regular users (< 1M followers): Fan-out on write — post is pushed to all followers' Redis caches at post time
• Celebrity users (≥ 1M followers): Fan-out on read — their posts are NOT pushed to follower caches at write time. Instead, when a user reads their feed, we pull celebrity posts dynamically and merge with the cached regular posts.

Read path for hybrid feed:

1. Get cached regular posts: ZREVRANGE feed:{user_id} 0 99  → [post_ids + scores]
2. Get followed celebrities for this user:
   SELECT followee_id FROM follows WHERE follower_id = {user_id} AND is_celebrity = TRUE
3. For each celebrity (usually <10), fetch their recent posts:
   ZREVRANGE celebrity_posts:{celebrity_id} 0 19  → [post_ids + scores]
4. Merge all post lists by score (timestamp) → take top 20
5. Batch fetch post content for the merged list

Celebrity posts are stored in their own sorted set (celebrity_posts:{user_id}) that all followers share — O(1) write regardless of follower count.

WHY: A user follows at most ~5-10 celebrities, so the merge at read time adds ~10 Redis reads. That's negligible. The alternative — fanning out to 100M Redis caches on every Elon tweet — is not viable.

How to determine 'celebrity' status:

• A background job runs hourly, recalculating follower counts
• Users crossing the 1M threshold are promoted to celebrity status; their future posts use the pull model
• Historical posts don't need backfilling — the threshold applies going forward

Handling follow/unfollow for feed consistency:

When User A unfollows User B:

• Remove B's recent posts from A's feed sorted set: ZREM feed:{A_id} {post_ids_by_B}
• But we can't easily identify which post_ids in the sorted set belong to B without extra metadata

Solution: Instead of storing bare post_id, store user_id:post_id as the sorted set value. Unfollow triggers a background job to scan A's feed and remove entries where user_id matches B. This is an eventually consistent operation — it's fine if B's posts persist briefly after unfollow.

Here's the evolved architecture:"

-+ResetFullscreen

Changes from core design:

1. Hybrid fan-out routing: Kafka router detects celebrity posts and directs to Celebrity Fan-out Worker
2. Celebrity sorted sets: Celebrity posts in shared celebrity_posts:{id} sets — all followers read from same key
3. Feed Service merges regular + celebrity feeds at read time
4. Celebrity followees cached: follows:{user_id}:celebrity set in Redis to avoid DB lookup on every feed read

Phase 4: Robustness & Operations

Interviewer: "What happens if the Redis cluster goes down?"

Candidate: "Feed reads fall back to the pull model — Feed Service queries PostgreSQL for the user's followee list and fetches recent posts directly. At 52K peak read QPS, each DB query might return 20 posts from 500 followees — that's too expensive for every read.

A tiered fallback:

1. Redis available (normal): instant feed from sorted set
2. Redis degraded (some nodes down): serve feed from available shards; degrade gracefully for affected users (show fewer posts)
3. Redis completely down: fall back to DB pull, but rate-limited — serve only users who explicitly request feed (not background refresh), with a circuit breaker to protect the DB from 52K QPS

Pre-provision PostgreSQL read replicas for this scenario — at least 3 read replicas to spread the fallback load.

Interviewer: "What about the thundering herd — when the Redis cache is rebuilt after a restart?"

Candidate: "Two mitigations:

1. Staggered cache warming: On Redis restart, warm feeds for the most-active users first (top 1% of DAU by recent activity), rather than having all Feed Service instances hammer the DB simultaneously
2. Jittered TTLs: Instead of setting all feed caches with the same TTL, add random jitter (±10% of TTL). This prevents synchronized mass-expiry.

Interviewer: "Hot partition in PostgreSQL — the follows table gets queried heavily for popular celebrities. How do you handle it?"

Candidate: "The follower lookup (SELECT follower_ids WHERE followee = celebrity) runs in the Feed Worker, not the Feed Service. It runs once per post, not per read. For a celebrity with 100M followers, we batch this query across multiple pages.

The bigger concern is that the follows table is large (500M users × avg 500 follows = 250B rows — impractical on a single PostgreSQL instance without aggressive partitioning, and a poor fit for the write/fan-out pattern). Let me reconsider: the follows table for a social graph at this scale should be in a different storage. Options:

• Graph database (Neo4j, Amazon Neptune) for the social graph — but adds operational complexity
• Cassandra with partition key = followee_id, clustering key = follower_id for efficient 'get all followers of X' queries
• Denormalized: Maintain a followers list per celebrity in Redis, updated on follow/unfollow events

I'd use Cassandra for the follows table at scale — it handles the high write rate of follow/unfollow events and the large fan-out reads efficiently.

Key SLIs:

• Feed read P99 < 200ms (Redis path)
• Feed read P99 < 2s (DB fallback path)
• Post fan-out lag P95 < 30s (time from post creation to appearing in followers' feeds)
• Celebrity posts appear in hybrid feed instantly (they're in a shared sorted set)
• Redis cache hit rate > 90%

Executive Summary:

Key trade-offs:

1. Hybrid fan-out: Adds complexity (two code paths) but is the only practical approach at scale. Pure push explodes for celebrities; pure pull is too slow for normal users.
2. Eventual consistency on fan-out: Posts can take up to 30s to appear in followers' feeds. This is the right call — synchronous fan-out would block post creation.
3. Cassandra for social graph over PostgreSQL: At 250B follow relationships, PostgreSQL would need aggressive partitioning and is not a natural fit for this write/fan-out pattern; Cassandra's wide partitions are designed for this exact use case.

V2 improvements:

• Ranking algorithm (engagement signals, recency weighting, graph distance)
• Feed pre-computation for top 1M users (always keep their feeds hot)
• Multi-region active-active with eventual consistency across regions"