System Design #15: Design a News Feed

Users: 500 million DAU

Posts:
  Each user creates ~2 posts/day
  Total: 1 billion posts/day
  Posts per second: 1B / 86,400 = ~11,600 posts/sec

Feed Reads:
  Each user opens the feed ~10 times/day
  Total: 5 billion feed reads/day
  Reads per second: 5B / 86,400 = ~57,870 reads/sec

Following:
  Average user follows 300 people
  Some users have millions of followers (celebrities)

Storage:
  Average post: 1 KB (text + metadata)
  1 billion posts/day * 1 KB = 1 TB/day
  Per year: ~365 TB
  Media (images, videos): stored in blob storage + CDN

Fan-Out on Write:

  Alex creates a post. Alex has 1,000 followers.

  1. Alex's post is stored in the posts table
  2. Look up Alex's 1,000 followers
  3. For each follower, insert the post into their feed cache

  [Alex posts] --> [Post Service] --> [1,000 followers' feed caches updated]

  When Sam (a follower) opens the feed:
    Simply read from Sam's pre-built feed cache.
    No computation needed at read time.

  Pros:
    - Feed reads are very fast (just read from cache)
    - New posts appear in followers' feeds immediately

  Cons:
    - Write amplification: 1 post = 1,000 writes
    - Celebrity problem: a user with 50M followers = 50M writes per post
    - Wasted work if most followers never check their feed

Fan-Out on Read:

  Sam opens their feed. Sam follows 300 people.

  1. Look up Sam's 300 followed users
  2. For each followed user, get their recent posts
  3. Merge all posts
  4. Rank and sort
  5. Return top N posts

  [Sam opens feed] --> [Fetch 300 users' posts] --> [Merge + Rank] --> [Feed]

  Pros:
    - No write amplification (post is stored once)
    - No wasted work — only compute when the user asks
    - Celebrity posts do not cause problems

  Cons:
    - Feed reads are slow (must query 300 users' posts and merge)
    - Increased read latency (hundreds of database queries)

Hybrid Fan-Out:

  Normal users (< 10,000 followers): fan-out on write
    - When Alex (5,000 followers) posts:
      push to all 5,000 followers' feed caches
    - Fast feed reads for their followers

  Celebrities (> 10,000 followers): fan-out on read
    - When a celebrity (50M followers) posts:
      do NOT push to 50M caches
    - Store the post in the celebrity's timeline only
    - When a fan opens their feed:
      merge the pre-built feed cache + latest celebrity posts

  Feed generation for Sam:
    1. Read Sam's pre-built feed cache (posts from normal users)
    2. Fetch latest posts from celebrities Sam follows (maybe 10-20 celebrities)
    3. Merge and rank
    4. Return the feed

  This balances write cost and read speed.

Architecture:

  [Client (Mobile/Web)]
        |
  [Load Balancer]
        |
  [API Gateway]
     /        \
  [Post       [Feed
   Service]    Service]
     |            |
  [Kafka]    [Feed Cache (Redis)]
     |            |
  [Fan-Out   [Feed
   Service]    Generator]
     |            |
  [Write to  [Read from
   follower    posts DB +
   caches]     merge]
     |
  [Posts DB (Cassandra)]

  Supporting:
  [Graph DB / Service] -- follows relationships
  [Media Service] --> [S3 + CDN]
  [Ranking Service] -- ML-based post ranking
  [Trending Service] -- trending topics

Post Creation:

  1. Client sends POST /api/posts
     { "text": "Hello world!", "media": ["photo.jpg"] }

  2. API Gateway routes to Post Service

  3. Post Service:
     a. Validates the request
     b. Stores media in S3, gets media URLs
     c. Stores the post in Posts DB
     d. Sends event to Kafka: "new_post" { post_id, user_id }

  4. Fan-Out Service consumes the Kafka event:
     a. Look up the poster's follower list
     b. If followers < 10,000: fan-out on write
        - For each follower: add post_id to their Redis feed cache
     c. If followers >= 10,000: skip fan-out
        - Post is only in the celebrity's timeline

  5. Post appears in followers' feeds.

  Time: < 5 seconds for the post to appear in feeds.

Feed Read:

  1. Client sends GET /api/feed?page=1

  2. Feed Service:
     a. Read user's feed cache from Redis (pre-built by fan-out)
        --> Returns a list of post_ids: [p123, p456, p789, ...]
     b. Fetch latest posts from celebrities the user follows
        --> Returns more post_ids: [c001, c002, ...]
     c. Merge both lists
     d. Send merged post_ids to Ranking Service

  3. Ranking Service:
     a. Score each post based on: recency, engagement, relevance
     b. Return sorted post_ids

  4. Feed Service:
     a. Fetch full post objects (text, media URLs, like count, etc.)
     b. Return the feed to the client

  Feed cache in Redis:
    Key: "feed:user_sam"
    Value: sorted set of (post_id, timestamp)
    Max size: 1000 post_ids per user

  Time: < 200ms (cache hit), < 500ms (cache miss with celebrity merge)

Ranking Signals:

  1. Recency (time decay)
     - Newer posts rank higher
     - Score decreases over time (exponential decay)

  2. Engagement
     - Posts with more likes, comments, shares rank higher
     - Weighted: share > comment > like

  3. User Affinity
     - Posts from users you interact with often rank higher
     - Based on: profile visits, likes, comments, DMs

  4. Content Type
     - Images and videos may rank higher than text-only posts
     - Based on the user's past engagement patterns

  5. Diversity
     - Avoid showing 10 posts from the same user in a row
     - Mix content types and topics

Simplified Scoring Formula:

  score = (affinity_weight * user_affinity)
        + (engagement_weight * normalized_engagement)
        + (recency_weight * time_decay_factor)
        + (content_weight * content_type_score)

  Where:
    time_decay_factor = 1 / (1 + hours_since_posted)
    normalized_engagement = (likes + 2*comments + 3*shares) / max_engagement
    user_affinity = interactions_with_poster / total_interactions

Redis Feed Cache:

  Key: "feed:{user_id}"
  Type: Sorted Set
  Score: timestamp (or ranking score)
  Member: post_id

  Example:
    feed:user_sam = {
      (post_123, 1748520000),
      (post_456, 1748519000),
      (post_789, 1748518000),
      ... up to 1000 entries
    }

  Operations:
    Add post to feed:     ZADD feed:user_sam 1748520000 post_123
    Get top 20 posts:     ZREVRANGE feed:user_sam 0 19
    Remove old posts:     ZREMRANGEBYRANK feed:user_sam 0 -1001
    Feed cache TTL:       7 days (rebuild if expired)

  Memory per user:
    1000 post_ids * 20 bytes = 20 KB per user
    500M users * 20 KB = 10 TB total

  This fits in a Redis cluster with 50-100 nodes
  (each handling 100-200 GB).

Trending Topics:

  Approach: Sliding window count

  1. Track hashtags and keywords in posts
  2. Count occurrences in the last 1 hour (sliding window)
  3. Compare to the baseline (average for this time of day)
  4. Topics with the biggest spike above baseline are "trending"

  Data structure: Count-Min Sketch
    - Probabilistic data structure for counting frequencies
    - Uses very little memory (a few MB for millions of topics)
    - Small chance of overcount, never undercounts
    - Perfect for trending topics (exact counts are not needed)

  Implementation:
    1. For each post: extract hashtags and significant words
    2. Increment their count in the Count-Min Sketch
    3. Every minute: compute trending scores
       trending_score = current_count / baseline_count
    4. Top 10 by trending_score = trending topics

  Alternative: Use Redis sorted sets
    Key: "trending:2026-06-01:10"  (hour bucket)
    ZINCRBY trending:... 1 "#systemdesign"
    ZREVRANGE trending:... 0 9  (top 10)

Posts Database Scaling:

  Database: Cassandra (or DynamoDB)
  Partition key: user_id
  Clustering key: post_id (time-ordered)

  Sharding strategy:
    - Partition by user_id (hash-based)
    - Each partition holds one user's posts
    - Even distribution across nodes

  For "get posts by user" queries: hits one partition (fast)
  For "get post by post_id": need a secondary index or separate lookup table

Follower Graph Storage:

  Option 1: Relational database (PostgreSQL)
    follows(follower_id, followed_id, created_at)
    Index on follower_id (who do I follow?)
    Index on followed_id (who follows me?)

    Works for < 1B edges. Use read replicas for scale.

  Option 2: Graph database (Neo4j, Amazon Neptune)
    Better for complex queries like "mutual followers"
    or "friends of friends"

  Option 3: Adjacency list in Cassandra
    Key: user_id
    Value: list of followed user_ids

    Fast lookups: "who does user_sam follow?" --> one partition read

  For a Twitter-like system, Option 3 (Cassandra) works well
  because the primary query is "get followers of user X."

Multi-Region:

  US data center: serves US users
  EU data center: serves EU users
  APAC data center: serves Asian users

  Posts are replicated across all regions (async).
  Feed caches are local to each region.

  When Alex in the US posts:
    1. Post stored in US database
    2. Replicated to EU and APAC (async, ~200ms delay)
    3. Fan-out happens in each region locally

  This keeps feed latency low (< 200ms) regardless of user location.

                    [GeoDNS]
                   /    |    \
            [US LB]  [EU LB]  [APAC LB]
               |        |         |
          [API Gateway Cluster]
           /        |         \
     [Post       [Feed       [User
      Service]    Service]    Service]
        |            |           |
     [Kafka]   [Redis Feed   [Graph
        |       Cache Cluster] Store]
        |            |
  [Fan-Out       [Ranking
   Workers]       Service]
        |
  [Posts DB: Cassandra Cluster]

  Supporting:
    [Media: S3 + CDN]
    [Trending: Count-Min Sketch + Redis]
    [Search: Elasticsearch]
    [Notifications: Push Service]