logo
CHEATSHEETSTOOLSABOUT中文

System Design - News Feed & Timeline

Designing a real-time Social Media News Feed (like Twitter / X, Facebook, or Instagram) is a quintessential system design question that tests graph relationships, asynchronous event processing, caching topologies, and the fundamental Push vs. Pull architectural trade-off.

1. Requirements & Scope

Functional Requirements

  • Post Publication: A user can publish text and media posts.
  • Feed Generation: A user can view a personalized, aggregated feed consisting of recent posts from people they follow.
  • Follow Graph: Users can follow and unfollow other users.
  • Pagination: Users can scroll through their timeline smoothly (cursor-based pagination).

Non-Functional Requirements

  • High Read-to-Write Ratio: Reading feeds happens orders of magnitude more frequently than publishing posts (e.g. 100:1 to 500:1).
  • Fast Feed Retrieval: Timeline generation and retrieval should complete in < 200ms.
  • Eventual Consistency: A few seconds of delay between when a user posts and when followers see it in their timeline is acceptable.

2. Capacity & Scale Estimations

  • Active Users: 300 million Daily Active Users (DAU).
  • Posting Volume: 100 million new posts/day ≈ 1,150 writes/second. Peak writes ≈ 3,000/sec.
  • Feed Views: Average user checks their feed 10 times/day → 3 billion feed requests/day ≈ 35,000 reads/sec. Peak reads ≈ 70,000 QPS.
  • Timeline Cache: Storing 800 recent post IDs per active user in a Redis sorted set: 300M users × 800 posts × 8 bytes (Post ID) ≈ 1.9 TB RAM Distributing this across a Redis cluster is feasible and cost-effective.

3. The Core Dilemma: Fan-Out on Write vs. Fan-Out on Read

The central design choice for timeline generation is how new posts propagate from an author to their followers' feeds:

Fan-Out on Write (Push Model):
Author Posts ──► Message Queue ──► Fan-Out Workers ──► Write to every Follower's Timeline Cache

Fan-Out on Read (Pull Model):
Follower Requests Feed ──► Query Followees ──► Fetch Recent Posts ──► Merge & Sort on the fly

Option A: Fan-Out on Write (Push Model)

  • Workflow: When an author posts, a background worker looks up all their followers and writes the new PostID directly into each follower's pre-computed timeline cache (e.g. a Redis sorted set).
  • Pros: Reading the feed is nearly instantaneous (O(1) range lookup in Redis).
  • Cons (The "Celebrity Problem"): If a user with 50 million followers posts, that single write triggers 50 million concurrent cache writes. This causes huge queue backlogs, write amplification, and resource spikes.

Option B: Fan-Out on Read (Pull Model)

  • Workflow: Posts are only written to the author's own post list. When a user requests their feed, the system queries the social graph for everyone they follow, queries their recent posts, and merges/sorts them in real time.
  • Pros: Writing is instantaneous with zero write amplification. Inactive users consume no cache resources.
  • Cons: Generating the feed on demand is extremely slow and expensive for users following thousands of accounts (O(N) multi-table queries and sorting).

Option C: The Hybrid Approach (Industry Standard)

Modern platforms combine both strategies based on user follower counts:

  1. Standard Users ($<20,000$ followers): Use Fan-out on Write. Push their posts immediately to their followers' timeline caches.
  2. Celebrity Accounts ($>20,000$ followers): Use Fan-out on Read. Do not push their posts. Instead, when a follower requests their feed, pull the latest posts from any followed celebrities and merge them with the follower's cached feed.
  3. Inactive Users: Stop fanning out to users who haven't logged in for 14 days. When they log back in, rebuild their feed on demand.

4. High-Level Architecture

[ User Publishes Post ]                       [ User Reads Feed ]
        │                                              │
        ▼                                              ▼
[ Post Service ]                                [ Feed Service ]
   ├──► [ Relational / Document DB ]                   │
   │    (Stores post content & media metadata)         ├──► [ Timeline Cache (Redis) ]
   │                                                   │    (ZREVRANGEBYSCORE)
   └──► [ Message Queue (Kafka) ]                      │
               │                                       └──► [ Celebrity Posts Cache ]
               ▼                                            (Merge & Rank on read)
     [ Fan-Out Workers ]
        ├──► Query [ Social Graph Service ]
        │    (Finds user's active followers)
        │
        └──► Update [ Timeline Cache (Redis) ]
             (Pushes PostID into followers' lists)

5. Storage & Data Models

Database Engines

  1. User & Follow Graph: Relational Database (PostgreSQL / MySQL) or Graph DB (Neo4j). High read caching for follower lists.
  2. Posts Content Store: Distributed Document or Key-Value store (Cassandra, MongoDB, DynamoDB) partitioned by user_id or post_id using a 64-bit K-sortable ID (see ID Generation).
  3. Timeline Cache: In-memory store (Redis).

Timeline Cache Structure (Redis Sorted Sets)

Use a Redis ZSET for each user's feed:

  • Key: timeline:<user_id>
  • Score: Post creation timestamp (or algorithmic ranking score).
  • Value: post_id.
# Adding a new post to a follower's timeline
ZADD timeline:user456 1728345600 post98765

# Retrieving the latest 20 posts (Pagination)
ZREVRANGEBYSCORE timeline:user456 +inf -inf LIMIT 0 20

# Trim to keep only the latest 800 posts per user
ZREMRANGEBYRANK timeline:user456 0 -801

6. Feed Ranking & Real-time Delivery

  • Chronological vs. Algorithmic Feed:
    • Chronological feeds sort purely by post timestamp.
    • Algorithmic feeds score posts using engagement signals (likes, comments, relationship affinity, recency). Ranking models compute scores asynchronously and update scores in the cache.
  • Real-Time Push to Client:
    • For active sessions, notify clients of new incoming posts using persistent connections like WebSockets or Server-Sent Events (SSE), showing a "New Posts Available" badge rather than disrupting current reading position.
  • Pagination Strategy:
    • Avoid offset-based pagination (OFFSET 50 LIMIT 10) because new items prepended to the feed cause duplicate or missed records on the next page.
    • Use cursor-based pagination using the post_id or timestamp of the last visible post as the continuation token (GET /feed?cursor=1728345600&limit=20).
Loading...