System Design · Topic 15 of 16

Design: News Feed

200 XP

A news feed system is one of the canonical system design questions because it elegantly surfaces the core tension in distributed systems: consistency vs performance at scale. The naive approach works for 10,000 users. It collapses for 500 million. This walkthrough covers the full design, including the celebrity problem that trips up most candidates.

Step 1 — Clarify requirements

Functional requirements

  • Post: Users can create posts (text up to 500 chars, optionally with images/videos).
  • Follow: User A can follow User B. Following is one-directional (like Twitter, not Facebook friends).
  • News feed: Each user sees a ranked list of posts from people they follow.
  • Like / comment: Users can react to posts (important for ranking signals).
  • Search: Basic post search (out of scope for this design — treat as separate service).

Non-functional requirements

  • Scale: 500M registered users, 300M DAU (Daily Active Users).
  • Post volume: Average user posts twice a week → 300M DAU × (2/7) ≈ ~86M posts/day → ~1,000 posts/sec.
  • Feed read volume: Average user reads feed 5x/day → 300M × 5 = 1.5B feed loads/day → ~17,000 feed reads/sec.
  • Celebrity accounts: 5M accounts with 10M+ followers. Largest: ~100M followers (think BTS, Lady Gaga).
  • Feed freshness: New posts should appear in follower feeds within 5 seconds (near real-time).
  • Feed latency: p99 feed load < 200ms.
  • Availability: 99.99% uptime. Eventual consistency is acceptable — it’s OK if a post appears in feeds 1-5 seconds after posting.

Out of scope

Stories (ephemeral), live video, ads ranking, DMs.

Step 2 — Capacity estimation

Post storage

Per post:
  post_id:    8 bytes
  user_id:    8 bytes
  content:    500 bytes (text)
  created_at: 8 bytes
  like_count: 8 bytes
  ─────────────────
  Total:      ~532 bytes/post

1,000 posts/sec × 86,400 sec/day × 365 days × 532 bytes
≈ 16.8 TB/year for post text data

Media (images/videos):
  Assume 30% of posts have an image, avg 1 MB compressed
  1,000 × 0.3 × 86,400 = 25.9M images/day × 1 MB ≈ 25 TB/day
  → Media goes to object storage (S3), not your database

Feed read QPS

17,000 feed reads/sec baseline
  Peak (morning commute, evening): 3-5× → 85,000 feed reads/sec
  Each feed load returns 20 posts
  Each post is ~532 bytes → 20 × 532 ≈ 10 KB per feed response
  → 85,000 × 10 KB ≈ 850 MB/sec outbound bandwidth (manageable with CDN)

Follow graph size

Average user follows 300 people
300M DAU × 300 follows = 90B follow edges
At 16 bytes per edge (follower_id + followee_id): 1.4 TB
→ Cannot fit in memory; needs a database with efficient graph traversal

Step 3 — The two core approaches

This is the heart of the interview. Most candidates know the names; strong candidates can articulate the exact failure modes.

Approach A: Fan-out on read (Pull model)

When User A opens their feed:

  1. Look up all users A follows (followee list).
  2. Fetch the N most recent posts from each followee.
  3. Merge and sort by timestamp.
  4. Return top 20.
User A opens feed
    │
    ▼
Feed Service: "Who does A follow?"
    │
    ▼
Social Graph Service: returns [user1, user2, ... userN]
    │
    ▼
Post Service: SELECT * FROM posts WHERE user_id IN (user1...userN)
              ORDER BY created_at DESC LIMIT 20
    │
    ▼
Merge + rank → return to user

Advantages:

  • Simple. No background jobs.
  • New posts are immediately visible (no propagation delay).
  • No wasted work — you only compute feeds when users actually open the app.

Disadvantages:

  • Latency is proportional to followee count. If User A follows 2,000 people, you’re doing 2,000 DB lookups (or one massive IN query) on every feed open. At p99 with 17,000 feed opens/sec, the DB cannot keep up.
  • Not cacheable in a meaningful way — the feed is unique to each user and changes constantly.
  • N+1 query problem at massive scale — even batched, fetching recent posts for 2,000 followees is slow.

Approach B: Fan-out on write (Push model)

When User B creates a post:

  1. Write the post to the posts table.
  2. Look up all of User B’s followers.
  3. For each follower, insert the post ID into their personal feed queue.

When User A opens their feed:

  1. Read the top 20 post IDs from A’s pre-computed feed.
  2. Fetch post details for those IDs (one batched query).
  3. Return.
User B posts
    │
    ▼
Post Service: INSERT INTO posts ...
    │
    ▼
Fanout Worker: SELECT followers WHERE followee_id = B
    │
    ▼ (for each follower)
Feed Cache: ZADD feed:{follower_id} timestamp post_id
            (Redis sorted set, score = timestamp)

Advantages:

  • Feed reads are O(1) — just read from a pre-computed sorted set.
  • Extremely cacheable — the feed for user A is a stable, reusable structure.
  • Feed latency is predictable regardless of followee count.

Disadvantages:

  • Write amplification: One post by Lady Gaga (100M followers) requires 100M Redis writes. At ~10μs per write, that’s 1,000 seconds — unacceptable.
  • Storage amplification: Each post ID is stored N times (once per follower’s feed). For 1,000 posts/sec with avg 300 followers, that’s 300,000 Redis writes/sec sustained. The storage for feed queues is 300× larger than the raw post storage.
  • Wasted work: ~40% of users are inactive on any given day. You’re fanning out to their feeds for nothing.

Step 4 — The celebrity problem

This is where most candidates stumble. The interviewer is specifically probing for this.

Setup: Lady Gaga posts a selfie. She has 50M followers. With naive fan-out on write:

50,000,000 followers
    × 1 Redis ZADD per follower
    × ~10 microseconds per operation
    = 500 seconds to complete fanout

During those 500 seconds, 50M users see a stale feed that doesn’t include the new post. This is completely unacceptable.

Why not just do it faster with parallelism?

Even with 1,000 parallel workers each handling 50,000 followers:

50,000 writes × 10μs = 0.5 seconds per worker (OK)
But all 1,000 workers hit Redis simultaneously
→ Redis cluster saturation at 100M writes/sec
→ Redis cluster has ~500K ops/sec capacity
→ You've overloaded Redis by 200×

The problem is fundamental: fan-out on write doesn’t scale for high-follower-count accounts.

Step 5 — The hybrid approach (how Instagram actually does it)

The key insight: separate regular users from celebrities at the fan-out stage.

Definition: A “celebrity” account is any account with followers > threshold (e.g., 1M followers).

Fan-out strategy by account type

Account typeFan-out strategy
Regular user (<1M followers)Fan-out on write (push)
Celebrity (>1M followers)Fan-out on read (pull)

How the feed is assembled

When User A opens their feed:

async function assembleFeed(userId: string): Promise<Post[]> {
  // 1. Load pre-computed feed from Redis (posts from regular followees)
  const regularPostIds = await redis.zrevrange(
    `feed:${userId}`, 0, 100, 'WITHSCORES'
  );

  // 2. Fetch celebrity followees for this user
  const celebFollowees = await socialGraph.getCelebrityFollowees(userId);

  // 3. Pull recent posts from each celebrity (fan-out on read, but only N celebrities)
  const celebPosts = await Promise.all(
    celebFollowees.map(celebId =>
      postService.getRecentPosts(celebId, limit=20)
    )
  );

  // 4. Merge: regular pre-computed posts + celebrity pulled posts
  const allPosts = mergeAndSort([...regularPostIds, ...celebPosts.flat()]);

  // 5. Rank and return top 20
  return rankFeed(allPosts, userId).slice(0, 20);
}

Why does this work?

  • For regular users: fan-out on write remains fast (they have <1M followers → manageable write amplification).
  • For celebrities: instead of fanning out to 50M inboxes, you pull from the celebrity’s post list at read time. The celebrity’s post list is a single sorted set in Redis — easily cacheable and shared across ALL their followers.
  • The number of celebrity accounts a user follows is small (usually <10). So the fan-out on read overhead is bounded to a tiny N.
Celebrity fan-out on write (old):   50M Redis writes × $
Celebrity fan-out on read (new):    1 Redis read (shared post list) × 300M users reading it
                                    = 1 cache entry, N reads → massively efficient

Step 6 — Feed pre-computation and caching

Redis sorted set as feed storage

Key:   feed:{userId}
Type:  Sorted Set (ZSET)
Score: Unix timestamp (milliseconds) of the post
Member: post_id (as string)
ZADD feed:user_123 1705312000000 "post_abc"
ZADD feed:user_123 1705312100000 "post_def"
ZREVRANGE feed:user_123 0 19  → top 20 most recent post IDs

Feed size limit: Cap each feed at 1,000 entries (ZREMRANGEBYRANK to trim oldest). Users who scroll past 1,000 posts are a tiny fraction — serve them via fallback DB query.

TTL: 7-day TTL on feed keys. Inactive users’ feeds expire and are rebuilt on next login.

Storage estimate:

300M DAU × 1,000 post IDs × 8 bytes per ID = 2.4 TB Redis storage
→ Requires Redis cluster (3-6 shards of 500GB RAM each)

Pre-warming on login

For users who haven’t opened the app in >7 days (feed expired):

  1. Detect expired feed on login.
  2. Trigger async feed rebuild job.
  3. Return a “loading feed” state to the client.
  4. Client polls for ready signal.

Step 7 — Post service and schema

CREATE TABLE posts (
  id            BIGINT UNSIGNED  NOT NULL,  -- Snowflake ID
  user_id       BIGINT UNSIGNED  NOT NULL,
  content       VARCHAR(500)     NOT NULL,
  media_keys    JSON,            -- S3 keys: ["images/abc.jpg", "videos/xyz.mp4"]
  like_count    BIGINT           NOT NULL DEFAULT 0,
  comment_count BIGINT           NOT NULL DEFAULT 0,
  repost_count  BIGINT           NOT NULL DEFAULT 0,
  created_at    DATETIME(3)      NOT NULL,
  is_deleted    BOOLEAN          NOT NULL DEFAULT FALSE,
  PRIMARY KEY (id),
  KEY idx_user_created (user_id, created_at DESC)
) ENGINE=InnoDB;

CREATE TABLE post_likes (
  post_id   BIGINT UNSIGNED NOT NULL,
  user_id   BIGINT UNSIGNED NOT NULL,
  liked_at  DATETIME(3)     NOT NULL DEFAULT CURRENT_TIMESTAMP(3),
  PRIMARY KEY (post_id, user_id)
);

CREATE TABLE follows (
  follower_id  BIGINT UNSIGNED NOT NULL,
  followee_id  BIGINT UNSIGNED NOT NULL,
  followed_at  DATETIME(3)     NOT NULL DEFAULT CURRENT_TIMESTAMP(3),
  is_celebrity BOOLEAN         NOT NULL DEFAULT FALSE,  -- denormalized for fast lookup
  PRIMARY KEY (follower_id, followee_id),
  KEY idx_followee (followee_id, follower_id)  -- "who follows me"
);

Note on idx_user_created: This index is critical for celebrity fan-out on read — SELECT id FROM posts WHERE user_id = ? ORDER BY created_at DESC LIMIT 20 uses a covering index and is O(log N).

Note on is_celebrity denormalization: Pre-computing this flag avoids a join on every fanout decision. Update it via a background job when follower count crosses the threshold.

Step 8 — Follow graph storage

The follow graph (90B edges, 1.4 TB) raises the question: relational or graph database?

Relational (MySQL + indexes)

The follows table above handles:

  • “Who does User A follow?” → SELECT followee_id FROM follows WHERE follower_id = A
  • “Who follows User B?” → SELECT follower_id FROM follows WHERE followee_id = B (via idx_followee)

For the fan-out worker, we need all followers of a user: this is a simple indexed scan. At 300 followers average, the query returns fast. For celebrities with 50M followers, we paginate the scan and process in batches.

Graph database (Neo4j / Amazon Neptune)

Graph DBs excel at multi-hop traversals: “Friends of friends”, “Suggested follows”, “Who in my network liked this?”. For simple follow/follower lookups, the overhead isn’t justified.

Verdict: MySQL relational model is sufficient for follow/follower lookups. Use a graph DB only if you need multi-hop graph queries (suggestions, influence mapping).

Social graph in Redis for hot paths

Cache the followee list for each active user:

Key:   followees:{userId}
Type:  Set
Value: set of followee user IDs
TTL:   24 hours

The fan-out worker and feed assembler use this cached set to avoid DB queries on the hot path.

Step 9 — Media storage

All images and videos are stored in S3, never in the database.

Upload flow

Client → POST /api/v1/media/presigned-url
    │
    ▼
Media Service: generates S3 pre-signed PUT URL (expires in 10 min)
    │
Client uploads directly to S3 (bypasses your servers)
    │
S3 triggers Lambda/event → Media Processor
    │
Media Processor:
  - Generates multiple resolutions (thumbnail, medium, full)
  - For video: transcodes to HLS (adaptive bitrate streaming)
  - Stores processed variants at: media/{userId}/{postId}/{size}.webp
    │
    ▼
CDN (CloudFront) sits in front of S3
Media URL in post: https://media.bck.ly/images/user123/postABC/medium.webp

CDN strategy

  • All media served exclusively through CDN — origin (S3) is never hit directly by clients.
  • CDN caches based on the full URL path (which includes postId), so cache invalidation is clean.
  • Use CDN geo-distribution: user in Mumbai gets media from Mumbai edge, not Frankfurt.

Step 10 — Feed ranking

Chronological ordering is the starting point, but engagement-based ranking is where real products go.

Stage 1: Chronological (baseline)

function rankChronological(posts: Post[]): Post[] {
  return posts.sort((a, b) => b.createdAt - a.createdAt);
}

Simple, predictable. Good for early product. Bad for retention — users miss posts from their most important connections.

Stage 2: Engagement score (intermediate)

function engagementScore(post: Post, userContext: UserContext): number {
  const agePenalty = Math.exp(-0.1 * hoursOld(post));  // exponential decay
  const engagementSignal =
    post.likeCount * 1.0 +
    post.commentCount * 3.0 +  // comments signal stronger engagement
    post.repostCount * 2.0;
  const affinityScore = userContext.affinityWith(post.userId); // how often user interacts
  return engagementSignal * agePenalty * affinityScore;
}

Stage 3: ML ranking (production)

Real systems (Facebook EdgeRank, Twitter Algorithm) use gradient-boosted trees or neural networks trained on:

  • Engagement signals: likes, comments, shares, click-through rate, time spent reading.
  • User affinity: frequency of past interaction with author.
  • Content signals: topic relevance, media type preference, language.
  • Context signals: time of day, device type.

The feed ranking model is a separate ML service. The feed service passes candidate posts to the ranking service, which scores each and returns a ranked order. Inference must be <50ms — use a cached model served via TensorFlow Serving or Triton.

Step 11 — Notification service

When User B (who User A follows) posts, User A should get a push notification.

Post Service (post created event)
    │
    ▼
Kafka Topic: "post-created"
    │
    ▼
Notification Fan-out Service
  - Fetches B's followers (paginated)
  - For each follower: checks notification preferences
  - Sends to Push Notification Service
    │
    ▼
Push Notification Service
  - iOS: APNs (Apple Push Notification service)
  - Android: FCM (Firebase Cloud Messaging)
  - Web: Web Push (VAPID)

Rate limiting notifications: Don’t send a push for every post by every followee. Batch: “3 people you follow posted in the last hour”. Otherwise you’ll get app uninstalls.

Step 12 — Complete architecture diagram

                         ┌──────────────────────────────────┐
                         │           CLIENTS                  │
                         │  (iOS / Android / Web)            │
                         └──────┬────────────┬───────────────┘
                                │            │
                         Feed reads      Post writes
                                │            │
                ┌───────────────▼────────────▼────────────────┐
                │              API Gateway / Load Balancer      │
                └──────┬────────────────────┬──────────────────┘
                       │                    │
          ┌────────────▼──────┐   ┌─────────▼──────────────┐
          │   Feed Service     │   │    Post Service         │
          │ (reads pre-computed│   │ (write posts, trigger   │
          │  feed from Redis)  │   │  fanout via Kafka)      │
          └────────┬───────────┘   └─────────┬──────────────┘
                   │                         │
      ┌────────────▼──────────┐   ┌──────────▼────────────────┐
      │   Redis Cluster        │   │      Kafka                 │
      │   feed:{userId} ZSET   │   │   Topic: post-created      │
      │   followees:{userId}   │◄──┤   Topic: feed-fanout       │
      │   post:{postId} hash   │   └──────────┬────────────────┘
      └────────────┬───────────┘              │
                   │               ┌──────────▼────────────────┐
      ┌────────────▼──────────┐   │   Fan-out Worker Service   │
      │  Post DB (MySQL)       │   │   - Regular users: push    │
      │  Sharded by post_id    │   │     to Redis feed ZSETs   │
      │  Read replicas         │   │   - Celebrities: skip push │
      └───────────────────────┘   └──────────┬────────────────┘
                                             │
                              ┌──────────────▼─────────────┐
                              │  Social Graph DB (MySQL)    │
                              │  follows table              │
                              └─────────────────────────────┘

      ┌─────────────────────────────────────────────────────┐
      │                  MEDIA PIPELINE                      │
      │  Client → S3 (pre-signed) → Lambda → CDN            │
      │  https://media.bck.ly/{userId}/{postId}/medium.webp  │
      └─────────────────────────────────────────────────────┘

      ┌─────────────────────────────────────────────────────┐
      │               NOTIFICATION PIPELINE                  │
      │  Kafka → Notification Service → APNs/FCM/WebPush    │
      └─────────────────────────────────────────────────────┘

Step 13 — Pagination

Why offset pagination breaks at scale

The naive approach:

SELECT * FROM posts ORDER BY created_at DESC LIMIT 20 OFFSET 200;

At OFFSET 200, the DB scans and discards 200 rows. At OFFSET 10000, it scans 10,000 rows. This is O(offset) work per page request. For a user deep in their feed history, this is catastrophic.

Cursor-based pagination (the correct approach)

First request:  GET /feed?limit=20
                → Returns posts, last post has: created_at = 1705312000, id = post_abc
                → Response includes: { data: [...], nextCursor: "1705312000_post_abc" }

Second request: GET /feed?limit=20&cursor=1705312000_post_abc
                → Server decodes cursor: created_at = 1705312000, id = post_abc
-- Cursor-based query (efficient, uses index)
SELECT * FROM posts
WHERE user_id IN (...)
  AND (created_at, id) < (1705312000, 'post_abc')  -- composite cursor
ORDER BY created_at DESC, id DESC
LIMIT 20;

This is O(1) regardless of page depth — the DB uses the index to jump directly to the cursor position.

For the Redis-backed feed: Use ZREVRANGEBYSCORE with the last score as the cursor:

ZREVRANGEBYSCORE feed:{userId} (lastScore -inf LIMIT 0 20

Step 14 — Common follow-up questions

Q: What if a user has 1 billion followers?

The hybrid model handles celebrities with 100M followers, but 1B is a different magnitude. Approaches:

  1. Skip fanout entirely: Store the post in a “celebrity post queue”. On feed read, query this queue for any celebrity the user follows.
  2. Sampled fanout: Only fan-out to the most active 10M followers. The other 990M pull on read. Accept that less active users have a slower feed refresh.
  3. Rate-limit celebrity posts: Celebrities at this scale post infrequently. Pre-warm the post into a global hot cache.

Q: How do you implement infinite scroll without showing the same posts?

Use cursor-based pagination and store the user’s scroll state client-side (the last cursor). On the server, don’t re-rank — return results in a stable order from the cursor position. The “seen posts” problem (user scrolls back up, then continues down) is handled client-side by deduplicating post IDs.

Q: What if a user’s feed is very stale (they haven’t opened the app in 30 days)?

The Redis feed key has expired. On login:

  1. Trigger async feed rebuild from DB (fan-out on read for their followees’ recent posts, last 7 days).
  2. Show skeleton loading state while rebuild completes.
  3. Do NOT try to reconstruct 30 days of missed content — just show the last 7 days.

Q: How do you handle a post going viral (10M likes in 1 hour)?

Like counts are stored in two places:

  • MySQL: Authoritative count (updated via batched writes, not per-like).
  • Redis counter: INCR likes:{postId} on every like. This is the real-time count served to users.

A viral post’s Redis counter key becomes a hot key. Mitigate with:

  • Local counters: Each app server keeps a local counter and flushes to Redis every 100ms.
  • Key-level sharding: INCR likes:{postId}:shard{1-10} — use multiple keys and sum at read time.

Q: How do you detect and remove spam posts from feeds?

Async content moderation pipeline:

  1. Post created → event published to Kafka.
  2. Content moderation service consumes event → runs ML classifier (spam, NSFW, hate speech).
  3. If flagged: UPDATE posts SET is_deleted = TRUE; HDEL post:{postId} from Redis feed caches.
  4. Feed assembler always checks is_deleted when hydrating post IDs from the feed cache.