News Feed

1. Requirements

Functional:

1. Publish post (text + media refs + visibility).
2. getFeed(user, cursor, limit) — ranked, paginated, no duplicates across pages.
3. Follow/unfollow; feed reflects graph changes within ~1 min.
4. Seen-filtering: don't reshow recently seen posts.
5. Like/comment counts displayed inline (approx ok).

Non-functional:

Out of scope:

• Full-text search over posts.
• Stories/ephemeral (see Instagram case).
• Messaging/notifications fan-out (separate systems, shared primitives).

2. Capacity Estimation

Assumptions: 500M users, 300M DAU; 100M posts/day (0.2/user/day blended); avg 200 followers; feed page = 20 posts; avg user opens feed 5×/day.

3. API Design

POST /api/v1/posts
{ "text": "hello", "media_ids": ["m_9f2"], "visibility": "public" }
201 { "post_id": "p_71xQ2", "created_at": "..." }

GET /api/v1/feed?limit=20&cursor=eyJzY29yZSI6... 
200 { "items": [{ "post_id": "p_71xQ2", "text": "...",
                 "author": {...}, "like_count": 412, "score": 0.87 }],
      "next_cursor": "eyJ..." }

POST /api/v1/follow/{userId}      // 204; feed backfill async
GET  /api/v1/posts/{postId}       // single post (cacheable, public CDN)

4. Data Model & Storage

-- Cassandra
CREATE TABLE posts_by_id (post_id TIMEUUID PRIMARY KEY, author_id BIGINT,
  text TEXT, media_ids LIST<TEXT>, created_at TIMESTAMP);
-- Redis per user: feed:{user_id} -> ZSET (score=rank, member=post_id), MAXLEN ~1000, TTL 7d
-- Graph: follows (user_id, followee_id, created_at) PK(user_id, followee_id)

• Feed entries store ids only — bodies hydrated from post-cache/Cassandra in a parallel MGET. Editing a post updates one row, not 200M feed copies.
• Shard feeds by hash(user_id); celebrity follower lists paginated (never load 100M rows into one worker — shard the fan-out job itself).

5. High-Level Design

Write path: post → API → post store + media refs → fan-out decider → (normal: queue → fan-out workers → push id into followers' Redis zsets) / (celebrity: mark id in celebrity-outbox only). Read path: GET /feed → Redis zset page → hydrate bodies (post-cache → Cassandra) → merge celebrity outboxes (pull) → rank/seen-filter → cursor page.

• Post service: validation, media-ref attach, writes canonical post row.
• Fan-out decider + queue (Kafka): splits normal vs celebrity; backpressure buffer (lag metric = health signal).
• Fan-out workers (stateless, sharded by follower-range): push ids; idempotent (ZADD NX) so retries are safe.
• Cache tiers: L1 feed-id zsets (Redis) → L2 post bodies (Redis/memcached) → L3 graph (Redis + DB).
• Read path ranker: merges push ids + celebrity pulls + ads, applies seen-filter (Bloom/Roaring bitmap per user), sorts, slices cursor page.

6. Deep Dives

6.1 Fan-out-on-write vs read vs hybrid (the celebrity problem)

Threshold (e.g. followers > 10k–100k, tuned): author's posts skip push and land in a per-celebrity outbox (Redis list, capped ~3k). Read path pulls outboxes of the celebrities you follow (usually <50) and merges with your pushed zset. Justin Bieber posting costs 1 write however many followers he has; his followers pay a bounded merge. Follow/unfollow: async patch — unfollow tombstones the id from your zset; new follow triggers a backfill job (top recent ids from followee + outbox).

6.2 Ranking + seen-filtering + pagination that doesn't lie

• Pipeline per page request: candidate fetch (zset range + celebrity pulls + ads slot) → hydrate → filter (seen set, muted, visibility) → score (recency_decay × affinity × quality, weights from offline training) → sort → slice → cursor.
• Seen-filter: per-user Roaring bitmap / Redis set of last ~5k seen ids, 30-day TTL. Checked before scoring to save hydration cost.
• Cursors encode (score, post_id) — stable across concurrent inserts (offset would duplicate/shift). Monotonicity guard: never surface a post older than the newest already-seen id that outranks it ("no time-travel").
• Cold start (new user / cache miss): synchronous pull path builds first page from followees' recent posts (slow once, ~500 ms), then materialises the zset for next time.

6.3 Cache tiers, stampedes, and failure modes

• L1 feed zset: TTL 7 d + LRU; L2 post body: write-through on publish, 24 h TTL; L3 graph: 60 s TTL with version stamp (follow changes must propagate fast).
• Stampede guards: singleflight on zset rebuild; jittered TTLs; stale-while-revalidate (serve slightly old page while rebuilding in background).
• If Redis L1 is down: degrade to pull-only (slower, correct) — never fail the read. If Kafka lags: reads still serve (stale by lag seconds); alert on lag, not on errors.
• Like/comment counts: Redis INCR on hot posts, flushed to Cassandra every ~10 s; a lost increment is invisible — by design.

7. Bottlenecks, Trade-offs & Monitoring

First bottleneck at 10x: fan-out worker throughput during global events (everyone posts at once) → autoscale workers on queue lag + shed celebrity-adjacent work first (their pull path covers it) + cap per-author push rate. Next: Redis memory for feed zsets → tighten cap 1000→500 + shorter TTL for dormant users.

Interview one-liners

• Q: Push or pull? / A: Hybrid — push for normal authors (fast reads), pull for celebrities (bounded writes); threshold on follower count.
• Q: Why store only ids in the feed cache? / A: Edits touch one row, not millions of feed copies; hydration is a parallel MGET.
• Q: Never use OFFSET — why? / A: Concurrent inserts shift pages; cursor on (score,id) is stable.

Related

• Twitter Timeline case — builds on these patterns for home vs user timelines
• Instagram case — media blobs + stories TTL on top of this feed
• Cache Patterns and Eviction — three cache tiers, stampede guards
• Partitioning — feed/post sharding
• Stream Processing — fan-out queue + engagement counters
• Leaderless Replication / Quorums — approximate counters reasoning