System Design · Lesson 11 of 18

News Feed (Twitter / Instagram)

Fan-out on write vs read, celebrity problem, ranking and timeline caching.

  • Advanced
  • 65 min read
  • 6 objectives

Before this lessonLesson 10: Key-Value Store and Pastebin

What you will learn

  • Size a feed system and model posts, follows and Redis timelines
  • Upload media via pre-signed URLs, object storage and a CDN
  • Choose hybrid fan-out and a celebrity threshold from measured trade-offs
  • Rank candidates and paginate with cursors instead of offsets
  • Shard posts with time-sortable ids and layer the caches
  • Handle deletes, blocks, search, trends and failures

Your Progress

0 of 18 lessons 0%

  • Lessons0 / 18
  • Completed0
  • Est. time left~ 16 hours

Progress is saved in this browser. No account needed.

Tip: pressing Next marks this lesson complete automatically.

Design the home timeline of a social app like Twitter/X, Instagram or the Facebook News Feed. A user opens the app and within a few hundred milliseconds sees a ranked, scrollable list of recent posts from the accounts they follow, with photos loading instantly from somewhere near them. It must feel the same for a user who follows 30 friends and for one who follows 3,000 accounts, and it must keep working when an account with a hundred million followers posts.

This prompt is popular because one innocent-looking feature hides three separate hard problems:

  • A graph-shaped write amplification problem. One post has to become visible to every follower. Whether you do that work when the post is written or when the feed is read is the central decision, and the right answer is "both, split by follower count".
  • A read-heavy serving problem. Feed reads outnumber posts roughly 50 to 1, and each read merges, filters, ranks and hydrates hundreds of candidates. It is a caching problem with a precomputation pipeline behind it.
  • A media bytes problem. Text is tiny; photos and video are petabytes a year and almost all of your egress. They never touch your application servers.

The sentence that frames the interview: "Posts are written once and read by many, but the 'many' is wildly uneven, so I will push to ordinary followers' inboxes at write time and pull the few very large accounts at read time." Everything else in this lesson is the detail that makes that sentence true.

Step 1 — Clarify the requirements

Ask, and write the answers down. Here is a realistic set to design against.

Functional, in scope for v1

  • Post: create a post with up to 280 characters of text and up to 4 photos or 1 short video. Delete your own post.
  • Follow graph: follow and unfollow (asymmetric, Twitter/Instagram style). Block and mute.
  • Home timeline: a paginated feed of posts from followed accounts, newest or ranked, infinite scroll.
  • Profile timeline: one author's posts, newest first.
  • Engagement: like and reply counts shown on every post (the counts, not the reply threads themselves).
  • Search and trending: a light sketch only — keyword and hashtag search over recent posts, a trending list per region.

Explicitly out of scope (say this out loud)

Direct messages (that is the chat lesson), push notifications (lesson 17), ads insertion and auctions, the full ML ranking platform, content moderation pipelines, stories/reels, video transcoding internals (lesson 13), and account/auth. Naming them shows you know the real product is bigger than 45 minutes.

Non-functional

  • Scale: 1B registered users, 300M daily actives, 150M new posts/day. Average account has ~250 followers; the largest have 100M+.
  • Latency: home feed first page p99 < 400 ms server time; subsequent pages p99 < 250 ms; post creation p99 < 500 ms (excluding media upload, which is client-to-storage).
  • Freshness: a new post should appear in followers' feeds within ~5 s p95 for normal accounts. A minute is acceptable under load. Seconds-late is fine; lost is not.
  • Availability: 99.95% for reading the feed — a slightly stale feed is far better than an error screen. Post creation must be durable once acknowledged.
  • Consistency: eventual for timelines, counts and search. Read-your-own-writes for the author: you must see your own post immediately, even if nobody else does yet. Strong for blocks: once you block someone, they must not see your new posts.
  • Durability: posts and media are never lost (multi-AZ, replicated object storage). Timelines are a cache and can be rebuilt.

That last line is the most useful thing on this list. The timeline is derived data. The source of truth is posts plus the follow graph; every inbox can be recomputed from them. That frees you to keep timelines in memory, trim them, drop them for inactive users and rebuild them on demand.

Step 2 — Back-of-the-envelope estimation

DAU               = 300_000_000
SECONDS_PER_DAY   = 86_400

# --- Writes: posts ---
posts_per_day     = 150_000_000          # ~0.5 posts per DAU per day
posts_avg = posts_per_day / SECONDS_PER_DAY
print(f"posts: {posts_avg:,.0f}/s avg, {posts_avg * 3:,.0f}/s peak")

# --- Reads: feed opens + scrolls ---
feed_opens_per_user = 12                 # app opens + pull-to-refresh
pages_per_open      = 2                  # 20 items per page, most never reach page 3
feed_reads = DAU * feed_opens_per_user * pages_per_open / SECONDS_PER_DAY
print(f"feed page reads: {feed_reads:,.0f}/s avg, {feed_reads * 3:,.0f}/s peak")
print(f"read:write ratio ~ {feed_reads / posts_avg:,.0f}:1")

# --- Fan-out on write, naive (every post pushed to every follower) ---
avg_followers = 250
fanout_writes = posts_avg * avg_followers
print(f"naive fan-out: {fanout_writes / 1e6:,.2f}M timeline inserts/s")
print(f"one post by a 100M-follower account: {100_000_000:,} inserts")

# --- Storage: post metadata, media, timelines ---
post_row_bytes = 500                     # ids, text (<=280 chars UTF-8), counters, flags
meta_tb_year = posts_per_day * 365 * post_row_bytes / 1e12
media_share, avg_media_mb = 0.30, 1.5    # 30% of posts carry media; 1.5 MB after resize set
media_pb_year = posts_per_day * media_share * avg_media_mb * 365 / 1e9
print(f"post metadata: {meta_tb_year:,.1f} TB/year   media: {media_pb_year:,.1f} PB/year before replication")

timeline_len, entry_bytes = 800, 16      # post_id (8) + author_id (8)
active_users_cached = 200_000_000
timeline_tb = active_users_cached * timeline_len * entry_bytes / 1e12
print(f"timeline cache: {timeline_tb:,.2f} TB of RAM -> ~{timeline_tb * 1000 / 64:,.0f} x 64 GB nodes (before replicas)")

# --- Egress: media dominates everything ---
media_views_per_open = 8
image_mb = 0.3                           # feed-sized variant, not the original
egress_gbps = DAU * feed_opens_per_user * media_views_per_open * image_mb * 8 / 1000 / SECONDS_PER_DAY
print(f"media egress: ~{egress_gbps:,.0f} Gbit/s avg -> CDN, not origin")
Output
posts: 1,736/s avg, 5,208/s peak
feed page reads: 83,333/s avg, 250,000/s peak
read:write ratio ~ 48:1
naive fan-out: 0.43M timeline inserts/s
one post by a 100M-follower account: 100,000,000 inserts
post metadata: 27.4 TB/year   media: 24.6 PB/year before replication
timeline cache: 2.56 TB of RAM -> ~40 x 64 GB nodes (before replicas)
media egress: ~800 Gbit/s avg -> CDN, not origin

What the numbers actually decide

  • ~1.7k posts/s (5k peak) is a modest write rate for the posts table itself. The post store is not the hard part; a sharded MySQL/Postgres cluster or Cassandra handles it comfortably.
  • 250k feed page reads/s at peak is the load that shapes the design. Each read must be a handful of in-memory lookups, not a scatter over 250 followees' post lists. That is the argument for precomputing timelines.
  • 430k timeline inserts/s from naive fan-out is large but affordable — it is sequential appends into Redis, batched per shard. What is not affordable is the tail: one post from a 100M-follower account is 100M inserts, taking minutes and starving everyone else's fan-out. That single line is why hybrid fan-out exists.
  • Timelines of 800 ids for 200M active users fit in ~2.6 TB of RAM — about 40 large cache nodes before replication. Store ids only, never post bodies: storing the full post in every follower's inbox would multiply that by ~30 and make every edit or delete a 250-way rewrite.
  • Media is 25 PB/year and ~800 Gbit/s of egress. That dwarfs everything else by three orders of magnitude and dictates object storage plus a CDN, with the app servers never proxying bytes.
  • Post metadata is ~27 TB/year — too big for one box after a couple of years, so posts are sharded from the start (Step 12), and old posts can move to cheaper tiers.

Step 3 — API design

Resource-oriented, versioned, bearer-token auth. The gateway resolves the token to a user_id; the client never sends its own id.

## Media — uploaded BEFORE the post, straight to object storage

POST /api/v1/media/uploads          { content_type: "image/jpeg", bytes: 3481221, sha256 }
  -> 201 { media_id, upload_url, upload_headers, expires_at }
     # upload_url is a pre-signed PUT to object storage, valid ~15 min,
     # bound to content-type and max size. App servers never see the bytes.
     400 UNSUPPORTED_TYPE | 413 TOO_LARGE | 429 + Retry-After

PUT  {upload_url}                   <raw bytes>            # client -> object storage directly
POST /api/v1/media/{media_id}/complete
  -> 202 { media_id, state: "PROCESSING" }                  # resize/strip EXIF asynchronously
GET  /api/v1/media/{media_id}       -> 200 { state: "READY", variants: {thumb, feed, full} }

## Posts

POST /api/v1/posts
  Headers: Idempotency-Key: 3c9e...  (client UUID, required)
  { text: "...", media_ids: ["m_81", "m_82"], reply_to?: post_id, visibility: "public" }
  -> 201 { post_id, created_at, author, text, media: [...] }
     400 TEXT_TOO_LONG | 409 MEDIA_NOT_READY | 403 MEDIA_NOT_OWNED | 429
  # Retry with the same key returns the same 201, never a second post.
  # The response is the full rendered post, so the client inserts it at
  # the top of the author's own feed immediately (read-your-own-writes).

DELETE /api/v1/posts/{post_id}      -> 204 | 403 NOT_AUTHOR | 404
GET    /api/v1/posts/{post_id}      -> 200 Post | 404 (deleted, or hidden from you)
GET    /api/v1/users/{id}/posts?cursor=&limit=20       # profile timeline
  -> 200 { items: [Post], next_cursor }

## Home timeline — cursor paginated, never offset

GET /api/v1/feed?limit=20&cursor=<opaque>&mode=ranked|latest
  -> 200 { items: [Post], next_cursor, feed_session }
     # cursor is opaque (base64 of {v, max_id, session}); the server can
     # change what is inside it without breaking clients.
GET /api/v1/feed/new_count?since=<newest post_id on screen>
  -> 200 { count: 7 }        # drives the "7 new posts" pill; cheap, cacheable 10 s

## Graph

PUT    /api/v1/following/{target_id}      -> 204     # idempotent by construction
DELETE /api/v1/following/{target_id}      -> 204
PUT    /api/v1/blocks/{target_id}         -> 204
PUT    /api/v1/mutes/{target_id}          -> 204
GET    /api/v1/users/{id}/followers?cursor=  -> 200 { users: [...], next_cursor }

## Engagement

PUT    /api/v1/posts/{post_id}/like       -> 204     # PUT, not POST: liking twice is a no-op
DELETE /api/v1/posts/{post_id}/like       -> 204

## Search (sketch)

GET /api/v1/search?q=%23launch+stream&cursor=     -> 200 { items: [Post], next_cursor }
GET /api/v1/trends?region=IN                     -> 200 { trends: [{ tag, post_count }] }

Five API decisions worth defending

  • Media is a separate, earlier call. A post request carrying 10 MB of photo over a flaky mobile link would tie up an app server thread for seconds and make the post non-retryable. Upload first, post a reference second; the post call stays tiny and idempotent.
  • Follow and like are PUT/DELETE on a resource, not POST /follow. The operation is naturally idempotent, so a retried request cannot double-count or toggle back.
  • Idempotency-Key on post creation. Mobile clients retry on timeout; without the key, a slow network produces duplicate posts that then fan out to every follower.
  • The cursor is opaque and versioned. Today it holds a max post id; tomorrow it may hold a ranking session id. Clients just echo it back.
  • A separate new_count endpoint instead of re-fetching the feed to detect new posts. The client polls something cheap and only reloads when the user taps the pill.

Step 4 — Data model

Four stores with four different access patterns. Posts and the graph are the durable truth; the timeline cache is derived and disposable.

-- =========================================================
-- USERS  (sharded SQL, small: ~1B rows x ~300 B = ~300 GB)
-- =========================================================
users (
  user_id          BIGINT PRIMARY KEY,        -- Snowflake id
  handle           TEXT UNIQUE NOT NULL,
  display_name     TEXT NOT NULL,
  avatar_media_id  BIGINT,
  is_private       BOOLEAN NOT NULL DEFAULT FALSE,   -- followers-only posts
  follower_count   BIGINT NOT NULL DEFAULT 0,  -- denormalised, updated async
  following_count  INT NOT NULL DEFAULT 0,
  fanout_mode      SMALLINT NOT NULL DEFAULT 0, -- 0 push, 1 pull (celebrity); set by a job
  last_active_at   TIMESTAMPTZ                  -- drives "skip inactive" in fan-out
);

-- =========================================================
-- FOLLOW GRAPH  (two tables, each sharded by its FIRST column)
-- =========================================================
following (                    -- "whom does X follow?"  -> read path, feed merge
  follower_id  BIGINT NOT NULL,
  followee_id  BIGINT NOT NULL,
  created_at   TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (follower_id, followee_id)
);
followers (                    -- "who follows X?"       -> write path, fan-out
  followee_id  BIGINT NOT NULL,
  follower_id  BIGINT NOT NULL,
  created_at   TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (followee_id, follower_id)
);
-- The same edge stored twice. One table indexed both ways would force one
-- of the two queries to scatter across every shard. ~250B edges x 2 x ~24 B
-- = ~12 TB. Both writes go through one service; a repair job reconciles.

blocks (blocker_id, blocked_id, created_at, PRIMARY KEY (blocker_id, blocked_id));
mutes  (muter_id,   muted_id,   created_at, PRIMARY KEY (muter_id, muted_id));

-- =========================================================
-- POSTS  (sharded by post_id; Cassandra or sharded MySQL)
-- =========================================================
posts (
  post_id      BIGINT PRIMARY KEY,   -- Snowflake: 41-bit ms time | machine | seq
  author_id    BIGINT NOT NULL,
  text         TEXT,                 -- <= 280 chars
  media_ids    BIGINT[],             -- pointers, never bytes
  reply_to     BIGINT NULL,
  visibility   SMALLINT NOT NULL,    -- public | followers | mentioned
  state        SMALLINT NOT NULL,    -- 0 live, 1 deleted (tombstone), 2 hidden by moderation
  created_at   TIMESTAMPTZ NOT NULL  -- redundant with the id, kept for humans and TTL tiers
);

user_posts (                          -- the profile timeline index, sharded by author_id
  author_id  BIGINT NOT NULL,
  post_id    BIGINT NOT NULL,         -- clustering key, DESC
  PRIMARY KEY (author_id, post_id)
) WITH CLUSTERING ORDER BY (post_id DESC);
-- "Latest 20 posts by X" is one partition read, while the posts themselves
-- stay evenly spread by post_id. This pair is the answer to the sharding question.

post_counters (post_id BIGINT PRIMARY KEY, likes BIGINT, replies BIGINT, reposts BIGINT);
likes (post_id, user_id, created_at, PRIMARY KEY (post_id, user_id));   -- dedupe source

-- =========================================================
-- MEDIA  (metadata in SQL; bytes in object storage behind a CDN)
-- =========================================================
media (
  media_id     BIGINT PRIMARY KEY,
  owner_id     BIGINT NOT NULL,
  state        SMALLINT NOT NULL,    -- UPLOADING | PROCESSING | READY | FAILED
  object_key   TEXT NOT NULL,        -- orig/2026/09/23/<media_id>  (never user-chosen)
  variants     JSONB,                -- {thumb: {key,w,h}, feed: {...}, full: {...}}
  sha256       CHAR(64),             -- dedupe + integrity check
  created_at   TIMESTAMPTZ NOT NULL
);

-- =========================================================
-- TIMELINE CACHE  (Redis cluster; derived, rebuildable)
-- =========================================================
ZADD  tl:{user_id}        <post_id> "<post_id>:<author_id>"   -- home inbox
ZREMRANGEBYRANK tl:{user_id} 0 -801                              -- keep newest 800
ZREVRANGEBYSCORE tl:{user_id} (<max_id> -inf LIMIT 0 60          -- one page of candidates
-- score = post_id (time-sortable), member carries author_id so the read path
-- can filter blocks/mutes WITHOUT fetching the post. ~16 B payload per entry.

ZADD  recent:{author_id}  <post_id> <post_id>     -- every author's newest ~200 posts;
                                                -- celebrities are merged from here
HSET  post:{post_id}  author 42 text "..." media "..." state 0   -- hydrated post, TTL 1 day
HINCRBY cnt:{post_id} likes 1                   -- hot counters, flushed to post_counters
SADD  hide:{user_id}  <author_id> ...           -- blocked + muted authors, read-path filter
SET   feedpage:{user_id}:{session} <ranked ids> EX 300   -- ranked first pages

Five modelling decisions to explain

  • The timeline stores ids, not posts. An inbox entry is ~16 bytes; a hydrated post is ~500 bytes plus media descriptors. Ids keep the cache 30x smaller, and edits, deletes and counter changes happen in exactly one place (post:{id}) instead of in 250 copies.
  • The follow edge is stored twice. Fan-out needs "who follows X" (sharded by followee); the read-time merge needs "whom does X follow" (sharded by follower). Each query stays on one shard. Candidates who draw one follows table with two indexes have made one of the two hot paths a scatter-gather.
  • The author id rides inside the inbox entry. Blocks and mutes can be applied before hydration, so you never load a post only to throw it away.
  • Deletes are tombstones (state = 1), not DELETE. The id is still sitting in hundreds of inboxes; the tombstone is how the read path knows to skip it (Step 14).
  • fanout_mode is a stored per-user flag, set by a job, not recomputed from follower_count on every post. Otherwise an account crossing the threshold flips back and forth and leaves inboxes half-populated.

Step 5 — High-level design

flowchart TB APP[Mobile / web client] --> CDN[CDN
images, video, avatars] CDN --> OBJ[(Object storage
originals + variants)] APP --> GW[API gateway
auth, rate limit, routing] APP -.->|pre-signed PUT| OBJ GW --> POST[Post service] GW --> FEED[Feed service] GW --> GRAPH[Graph service] GW --> MEDIA[Media service] GW --> SRCH[Search service] MEDIA --> OBJ MEDIA --> MQ[[Image processing workers]] MQ --> OBJ POST --> PDB[(Posts + user_posts
sharded by post_id / author_id)] POST --> OUT[[Outbox]] --> K[(Kafka: post.created,
post.deleted, follow.changed)] GRAPH --> GDB[(Graph store
followers / following)] GRAPH --> K K --> FAN[Fan-out workers] FAN --> GDB FAN --> TL[(Redis: timelines
tl:user, recent:author)] K --> IDX[Search indexer] --> ES[(Search index)] K --> TRD[Trends job] K --> CNT[Counter aggregator] --> PDB FEED --> TL FEED --> PC[(Redis: post cache,
counters, hide sets)] FEED --> RANK[Ranking service] FEED --> GDB PC -->|miss| PDB

The write path stores a post once and emits one event. Fan-out, search indexing, trends and counters all hang off Kafka. The read path is almost entirely Redis: inbox ids, celebrity recents, hydrated posts and filter sets.

What each service owns

  • API gateway — TLS, token validation, per-user rate limits (see the rate limiter lesson), routing, load shedding.
  • Media service — issues pre-signed upload URLs, validates and processes uploads into variants, tracks media.state. Owns nothing on the hot read path; the CDN serves bytes.
  • Post service — the only writer of posts and user_posts. Validates text and media ownership, assigns the Snowflake id, writes the post and an outbox row in one transaction, and returns. It does not fan out.
  • Graph service — owns both edge tables, blocks and mutes, and follower counts. Emits follow.changed so timelines can backfill or prune.
  • Fan-out workers — consume post.created, read follower lists in pages, and ZADD into inboxes in pipelined batches. Stateless, horizontally scaled, partitioned by author so one author's posts stay ordered.
  • Feed service — assembles a page: reads the inbox, merges celebrity recents, filters, asks the ranker to order candidates, hydrates, paginates. Read-only against every store.
  • Ranking service — scores candidates with features from a feature store. Stateless; can be switched off, falling back to reverse-chronological.
  • Search, trends, counters — pure Kafka consumers. If they lag, the feed still works.

Step 6 — The media upload path

sequenceDiagram participant C as Client participant M as Media service participant S as Object storage participant W as Image workers participant P as Post service participant D as CDN C->>M: POST /media/uploads (type, size, sha256) M->>M: insert media row UPLOADING, sign PUT URL M-->>C: 201 media_id + upload_url (15 min) C->>S: PUT bytes directly (resumable for video) C->>M: POST /media/id/complete M->>S: HEAD object, verify size + hash M->>W: enqueue process(media_id) M-->>C: 202 PROCESSING W->>S: read original, strip EXIF, resize to thumb/feed/full, WebP + JPEG W->>S: write variants under immutable keys W->>M: state READY + variant keys C->>P: POST /posts (text, media_ids) P->>M: check owner + READY P-->>C: 201 post with CDN URLs Note over C,D: Followers later fetch cdn.example/v/feed/media_id.webp. First request misses to storage, the rest are edge hits.

Bytes flow client to storage and storage to CDN. The application tier only handles small JSON calls, so a slow upload never holds an app server thread.

The choices in this path, and why

  1. Pre-signed URLs, not proxying. At 25 PB/year, routing bytes through app servers would need a fleet sized for bandwidth rather than requests, and one slow 3G upload would pin a worker for a minute. The signature binds bucket, key, content type and max size, so the client cannot write anywhere else.
  2. Server-chosen object keys. orig/2026/09/23/<media_id>, never the user's filename. It prevents overwrites, path tricks and hot key prefixes.
  3. Process into fixed variants — a ~150 px thumbnail, a ~1080 px feed image, the full size — in modern formats. Feeds request the feed variant (~300 KB), not a 4 MB original; this alone cuts egress by an order of magnitude. Strip EXIF, because GPS coordinates in a photo are a privacy leak.
  4. Immutable keys, long cache headers. A variant never changes, so the CDN can cache it for a year. An edit produces a new media id, not an overwrite, so there is never a CDN purge on the happy path.
  5. Dedupe by hash (optional): identical uploads — memes, reposted photos — share one stored object and just gain another media row.
  6. Lifecycle rules: originals that were uploaded but never attached to a post are deleted after 24 hours; originals move to an infrequent-access tier after 30 days while the small variants stay hot.
  7. Video follows the same shape with resumable multipart upload and a transcoding pipeline producing adaptive bitrate renditions — the whole of the video lesson.

Step 7 — Fan-out: on write, on read, or hybrid

This is the heart of the interview. There are three ways to get a post in front of its followers.

Fan-out on write (push)

At post time, a worker looks up the author's followers and inserts the post id into each follower's inbox. Reading a feed is then one range read on one key. Reads are as cheap as they will ever be; writes cost O(followers). For a normal account with 250 followers that is 250 pipelined ZADDs — a couple of milliseconds of Redis time, done asynchronously. For an account with 100M followers it is 100M inserts: at a generous 1M inserts/s per worker pool that is well over a minute of delay for the last follower, and every other author's fan-out queues behind it.

Fan-out on read (pull)

At read time, look up whom the viewer follows, fetch each followee's recent posts and merge. Writes are one row. Reads cost O(followees) lookups on every refresh: 250 or 2,000 lookups, many on different shards, multiplied by 250k feed reads/s. That is 60M+ lookups per second and a p99 governed by the slowest of 2,000 parallel calls.

Hybrid — the answer to give

Push for everyone below a follower threshold; mark accounts above it as pull (fanout_mode = 1). Their posts are written only to recent:{author_id}, one small sorted set that every follower's read merges in. A viewer's read then costs one inbox read plus one small read per celebrity they follow — typically single digits — and the celebrity recents are the hottest, best-cached keys in the system.

The simulation below builds a small network with a realistic heavy-tailed follower distribution and measures both sides of the trade for each strategy: total fan-out writes, the worst single post (your latency spike), and how many sources a feed read has to merge.

import random

rng = random.Random(42)
N = 10_000                                    # users in our toy network

# Follower counts are heavy-tailed: most users have a few dozen, a handful have
# a large share of the whole network. Pareto sampling gives that shape.
def follower_count():
    u = 1.0 - rng.random()
    return min(N - 1, int(8 / u ** (1 / 1.1)))

followers = {a: set() for a in range(N)}      # author -> who follows them
followees = {u: set() for u in range(N)}      # reader -> whom they follow
for author in range(N):
    for _ in range(follower_count()):
        f = int(rng.random() * N)
        if f != author:
            followers[author].add(f)
            followees[f].add(author)
active = {u for u in range(N) if rng.random() < 0.4}    # opened the app this week

posts = [int(rng.random() * N) for _ in range(5_000)]   # who posted
reads = [int(rng.random() * N) for _ in range(50_000)]  # who opened their feed (10:1)

def simulate(threshold, skip_inactive=False):
    """threshold=None -> pure pull; threshold=inf -> pure push; else hybrid."""
    celeb = set() if threshold is None else {a for a in range(N) if len(followers[a]) >= threshold}
    push_everything = threshold is not None
    writes, worst = 0, 0
    for a in posts:
        if not push_everything or a in celeb:
            continue                                         # stored once, pulled at read time
        targets = followers[a] & active if skip_inactive else followers[a]
        writes += len(targets); worst = max(worst, len(targets))
    # Read cost = number of sources merged: 1 for the precomputed inbox, plus one
    # per followee whose posts must be fetched live.
    read_cost = 0
    for r in reads:
        pulled = len(followees[r]) if not push_everything else len(followees[r] & celeb)
        read_cost += pulled + (1 if push_everything else 0)
    return writes, worst, read_cost / len(reads), len(celeb)

sizes = sorted((len(s) for s in followers.values()), reverse=True)
print(f"edges={sum(sizes):,}  median followers={sizes[N // 2]}  top account={sizes[0]:,}"
      f"  top 1% own {sum(sizes[:N // 100]) / sum(sizes):.0%} of edges")
print(f"{'strategy':<24}{'celebs':>7}{'fan-out writes':>16}{'worst post':>12}{'sources/read':>14}")
INF = float('inf')
for label, t, skip in [("pull (fan-out on read)", None, False),
                       ("push (fan-out on write)", INF, False),
                       ("hybrid, T=1000", 1000, False),
                       ("hybrid, T=300", 300, False),
                       ("hybrid, T=100", 100, False),
                       ("hybrid T=300 + active", 300, True)]:
    w, worst, rc, nc = simulate(t, skip)
    print(f"{label:<24}{nc:>7}{w:>16,}{worst:>12,}{rc:>14.1f}")
Output
edges=432,584  median followers=15  top account=6,351  top 1% own 32% of edges
strategy                 celebs  fan-out writes  worst post  sources/read
pull (fan-out on read)        0               0           0          43.3
push (fan-out on write)       0         216,705       5,892           1.0
hybrid, T=1000               44         165,459         996          11.4
hybrid, T=300               180         131,393         299          17.9
hybrid, T=100               606          97,167          99          25.0
hybrid T=300 + active       180          52,712         132          17.9

Reading the results

  • Pull writes nothing and pays for it on every read: 43 sources merged per feed open. Multiply by 250k reads/s.
  • Push gets reads down to 1 source, but the worst single post fans out to 5,892 inboxes — in a network of only 10k users. Scale the same shape to a billion and that worst post is the 100M-insert case.
  • Hybrid caps the worst post at the threshold by construction (996, 299, 99) — the bound comes from the definition, not luck. The price moves to reads: the lower the threshold, the more celebrities each viewer must merge. The knob trades write tail latency for read fan-in.
  • Skipping inactive followers cut writes by another 60% for free. Most accounts' followers include many people who have not opened the app in weeks; they get their timeline rebuilt from scratch when they return (Step 9).
  • The toy network is tiny and densely connected, so everyone follows many "celebrities". In a real network the top accounts are a much smaller fraction and a typical user follows a handful, so hybrid reads stay close to 1 + a few.

Choosing the threshold

Pick it from the budget, not from folklore. If fan-out must finish within ~5 s and one worker pool sustains ~200k inserts/s per author partition, then any author above ~1M followers cannot meet the freshness target by push — so the threshold sits somewhere between 100k and 1M. Two refinements worth stating:

  • Hysteresis. Switch to pull above 1M followers but only back to push below 800k, so an account hovering at the line does not flip modes weekly. The switch itself is a job: when an account goes to pull, its existing inbox entries simply age out; when it goes to push, nothing needs backfilling because followers' reads were already merging its recents.
  • Per-follower, not only per-author. Some systems push a celebrity's post to the small set of followers who are online right now and have high affinity, and let everyone else pull. That keeps freshness for the engaged audience without the 100M-write tail.

Wrong answers candidates commonly give

  • "Fan-out on write, it's fastest to read." Correct for 99.9% of accounts and catastrophic for the top 0.1%, which is exactly where the interviewer will push.
  • "Fan-out on read with a good cache." The cache key would be per viewer, and the merge still happens on every miss across hundreds of shards. You have rebuilt fan-out on write, badly.
  • "Store the whole post in each inbox." Deletes, edits and like counts become N-way rewrites, and the cache is 30x bigger.
  • "Fan out synchronously in the post request." The author waits for 250 (or 100M) writes. Fan-out is always asynchronous, behind a durable log.

Step 8 — Walk one post end to end

sequenceDiagram participant A as Author app participant P as Post service participant DB as Posts DB participant K as Kafka participant F as Fan-out workers participant G as Graph store participant R as Redis timelines participant V as Viewer app participant FS as Feed service A->>P: POST /posts (Idempotency-Key) P->>DB: TX: insert posts + user_posts + outbox P-->>A: 201 full post (app shows it at the top immediately) DB->>K: outbox relay publishes post.created K->>F: post.created(author 42, post 9001) F->>R: ZADD recent:42 F->>G: page through followers of 42 (skip inactive) F->>R: pipelined ZADD tl:follower + trim, 1k per batch V->>FS: GET /feed FS->>R: ZREVRANGE tl:viewer (60 candidates) FS->>R: ZREVRANGE recent:celeb for each pulled followee FS->>FS: merge, drop hidden authors and tombstones, rank FS->>R: HMGET post:id for the 20 winners (miss goes to DB) FS-->>V: 200 items + next_cursor

The author's request ends after one transaction. The follower sees the post a few seconds later, when fan-out has reached their inbox, or immediately if the author is pulled.

The order of operations, and why

  1. Write the post, the profile index and the outbox row in one transaction. If the event were published separately, a crash between the two would leave a post nobody's feed ever shows, or an event pointing at a post that rolled back.
  2. Return the full post to the author. The client inserts it at the top of the author's own feed. That is read-your-own-writes for free, without making fan-out synchronous.
  3. Fan-out reads followers in pages and writes in pipelined batches. One command per follower would spend its life on round-trips. Partition the Kafka topic by author_id so one author's posts are fanned out in order.
  4. Trim on every insert. ZREMRANGEBYRANK keeps each inbox at 800 entries, so memory is bounded by users x 800, not by history.
  5. Read fetches ~3x the page size in candidates. Filtering and ranking discard some; fetching 60 to show 20 avoids a second round-trip in almost every case.
  6. Hydrate last, and only the winners. Fetching 20 post bodies, not 60, is the cheapest point in the pipeline to be lazy.

Step 9 — Low-level design: fan-out worker and feed assembly

The two pieces worth writing out: the worker that decides push versus pull, and the read path that merges sorted sources and applies filters. In-memory stand-ins replace Redis and the databases so the logic runs as-is.

import heapq, itertools
from collections import defaultdict

CELEB_THRESHOLD = 10_000        # followers; above this an author is pulled, not pushed
TIMELINE_MAX    = 800           # entries kept per inbox (ZREMRANGEBYRANK in Redis)

class Store:
    """In-memory stand-ins for: posts table, follow graph, Redis inboxes and filter sets."""
    def __init__(self):
        self.posts = {}                          # post_id -> {author, text, deleted}
        self.followers = defaultdict(set)        # author -> followers   (sharded by author)
        self.following = defaultdict(set)        # viewer -> followees   (sharded by viewer)
        self.follower_count = defaultdict(int)
        self.inbox = defaultdict(list)           # viewer -> [post_id] newest first (ZSET)
        self.author_recent = defaultdict(list)   # author -> [post_id] newest first (celeb cache)
        self.hidden_authors = defaultdict(set)   # viewer -> blocked + muted + unfollowed
        self.ids = itertools.count(1000)         # Snowflake stand-in: bigger id = newer

class FanoutWorker:
    """Consumes post.created events. Runs off the request path."""
    def __init__(self, s): self.s = s
    def handle(self, post_id, author):
        s = self.s
        s.author_recent[author].insert(0, post_id)           # every author, always
        del s.author_recent[author][TIMELINE_MAX:]
        if s.follower_count[author] >= CELEB_THRESHOLD:
            return 0                                          # pulled at read time instead
        for f in s.followers[author]:                         # batched pipelines in real life
            s.inbox[f].insert(0, post_id)
            del s.inbox[f][TIMELINE_MAX:]
        return len(s.followers[author])

class FeedService:
    def __init__(self, s): self.s = s
    def publish(self, author, text, worker):
        pid = next(self.s.ids)
        self.s.posts[pid] = {"author": author, "text": text, "deleted": False}
        return pid, worker.handle(pid, author)                # in prod: outbox -> Kafka
    def feed(self, viewer, max_id=None, limit=3):
        s = self.s
        celebs = [a for a in s.following[viewer] if s.follower_count[a] >= CELEB_THRESHOLD]
        sources = [s.inbox[viewer]] + [s.author_recent[c] for c in celebs]
        # Each source is already sorted newest-first; a k-way merge is O(n log k).
        merged = heapq.merge(*sources, key=lambda pid: -pid)
        out = []
        for pid in merged:
            if max_id is not None and pid >= max_id:
                continue
            p = s.posts.get(pid)
            if p is None or p["deleted"]:                     # tombstoned since fan-out
                continue
            if p["author"] in s.hidden_authors[viewer]:       # block / mute / unfollow
                continue
            if p["author"] not in s.following[viewer]:
                continue
            out.append((pid, p["author"], p["text"]))
            if len(out) == limit:
                break
        next_cursor = out[-1][0] if len(out) == limit else None
        return out, next_cursor

s = Store(); w = FanoutWorker(s); svc = FeedService(s)
def follow(viewer, author):
    s.followers[author].add(viewer); s.following[viewer].add(author)
    s.follower_count[author] += 1
for a in ("ana", "bo", "cy", "star"):
    follow("me", a)
s.follower_count["star"] = 25_000_000                        # pretend the rest exist

log = [svc.publish(a, t, w) for a, t in [("ana", "coffee"), ("star", "tour dates"),
       ("bo", "new job"), ("cy", "cat photo"), ("star", "album out"), ("ana", "hike")]]
print("fan-out writes per post:", [n for _, n in log])
s.posts[log[2][0]]["deleted"] = True                        # bo deletes "new job"
s.hidden_authors["me"].add("cy")                            # I mute cy

page, cur = svc.feed("me")
print("page 1:", page, "next:", cur)
page, cur = svc.feed("me", max_id=cur)
print("page 2:", page, "next:", cur)
Output
fan-out writes per post: [1, 0, 1, 1, 0, 1]
page 1: [(1005, 'ana', 'hike'), (1004, 'star', 'album out'), (1001, 'star', 'tour dates')] next: 1001
page 2: [(1000, 'ana', 'coffee')] next: None

The LLD points an interviewer is listening for

  • Every source is already sorted, so the merge is a k-way heap merge — O(n log k) and lazy. It stops pulling from sources the moment the page is full. This is why time-sortable ids matter: the merge key is the id itself.
  • Filtering happens between merge and hydration. The deleted post and the muted author were skipped without loading anything heavy. Note that the author id carried in the inbox entry is what made the mute check free.
  • The "still following?" check makes unfollow instant without deleting 800 inbox entries. Stale entries from unfollowed authors are filtered out on read and age out through trimming.
  • Celebrity posts were never written to any inbox (0 fan-out writes), yet appeared in the right place on page 1.
  • The cursor is an id, not a position, so page 2 continued exactly after page 1 even though entries were filtered.
  • Rebuilding a missing inbox is the pull path: when an inactive user returns and tl:{user_id} does not exist, the feed service pulls recent:{author} for everyone they follow, merges, writes the result as their new inbox, and from then on push keeps it warm. The slow path runs once per returning user, not once per read.

Step 10 — Feed generation and ranking

A ranked feed is a funnel with three stages, each an order of magnitude smaller than the last:

  1. Candidate generation (~500–1,000 ids). The inbox, celebrity recents, and optionally out-of-network sources — posts liked by people you follow, popular posts in topics you engage with. Cheap: all ids from Redis.
  2. Scoring (~500 → ~50). Each candidate gets a score from features. v1 is a hand-tuned weighted formula; v2 is a trained model predicting the probability of a like, reply or long dwell, combined into one value.
  3. Re-ranking and policy (~50 → 20). Diversity (no author five times in a row), freshness guarantees, already-seen demotion, ads slots, and hard filters (blocked, sensitive-content settings).

The features that matter

  • Affinity between viewer and author: recent likes, replies, profile visits, DMs. The single strongest signal — people care about their friends more than about what is globally popular.
  • Engagement velocity: likes and replies per hour since posting, log-scaled so viral posts do not drown everything.
  • Recency: exponential decay with a half-life of a few hours.
  • Content type: photo, video, text, link — and the viewer's historical preference among them.
  • Negative signals: already seen, "show less of this", hides, quick scroll-pasts.
  • Source: in-network posts get a boost over discovered posts, so the feed still feels like your feed.
import math
from dataclasses import dataclass

@dataclass
class Candidate:
    post_id: int
    author: str
    age_hours: float
    affinity: float        # 0..1, viewer's recent likes/replies/profile visits to this author
    likes: int
    replies: int
    has_media: bool
    seen: bool             # already rendered to this viewer in an earlier session
    source: str            # "inbox" (pushed), "celeb" (pulled), "discover" (out of network)

W = {"affinity": 5.0, "engagement": 0.6, "media": 0.4, "discover": -1.5, "seen": -4.0}
HALF_LIFE_HOURS = 6.0

def score(c: Candidate) -> float:
    # log-scaled engagement velocity: 10k likes should not beat 100 likes by 100x
    velocity = math.log1p((c.likes + 3 * c.replies) / max(c.age_hours, 0.25))
    base = (W["affinity"] * c.affinity
            + W["engagement"] * velocity
            + W["media"] * c.has_media
            + W["discover"] * (c.source == "discover")
            + W["seen"] * c.seen)
    decay = 0.5 ** (c.age_hours / HALF_LIFE_HOURS)          # freshness still matters
    return base * decay

def rank(cands, page_size=5, same_author_penalty=0.7):
    """Greedy re-rank: each extra post by an author already on the page is damped,
    so one prolific account cannot take over the top of the feed."""
    pool = {c.post_id: score(c) for c in cands}
    by_id = {c.post_id: c for c in cands}
    page, shown = [], {}
    while pool and len(page) < page_size:
        best = max(pool, key=lambda pid: pool[pid] * same_author_penalty ** shown.get(by_id[pid].author, 0))
        c = by_id[best]
        page.append((c, pool.pop(best) * same_author_penalty ** shown.get(c.author, 0)))
        shown[c.author] = shown.get(c.author, 0) + 1
    return page

cands = [
    Candidate(101, "close_friend", 5.0, 0.90, 12,   4,  True,  False, "inbox"),
    Candidate(102, "news_outlet",  0.5, 0.10, 900,  150, False, False, "inbox"),
    Candidate(103, "news_outlet",  0.8, 0.10, 700,  90,  True,  False, "inbox"),
    Candidate(104, "news_outlet",  1.0, 0.10, 650,  80,  False, False, "inbox"),
    Candidate(105, "pop_star",     2.0, 0.30, 90000, 8000, True, False, "celeb"),
    Candidate(106, "coworker",     0.3, 0.50, 2,    0,  False, False, "inbox"),
    Candidate(107, "stranger",     1.0, 0.00, 4000, 300, True,  False, "discover"),
    Candidate(108, "close_friend", 1.0, 0.90, 30,   6,  True,  True,  "inbox"),
]
for c, s in rank(cands):
    print(f"{c.post_id}  {c.author:<13} {c.source:<9} age={c.age_hours:>4}h  score={s:5.2f}")
Output
105  pop_star      celeb     age= 2.0h  score= 6.72
102  news_outlet   inbox     age= 0.5h  score= 4.95
106  coworker      inbox     age= 0.3h  score= 3.60
107  stranger      discover  age= 1.0h  score= 3.56
101  close_friend  inbox     age= 5.0h  score= 3.34

Read the result carefully. The celebrity post wins on sheer engagement. The news outlet posted three times; its second post (raw score 4.71) was damped to 3.30 by the same-author penalty and fell off the page, leaving room for the coworker's quiet post. The close friend's 5-hour-old post made it on affinity alone, and the close friend's already-seen post was demoted out of the top five. Each of those outcomes is a product decision encoded as one named weight — which is exactly how you should present ranking in an interview.

Where ranking runs, and when

  • At read time, on the first page only, with a precomputed ranked page cached per feed_session for ~5 minutes. Scrolling reads from that cached ordering; pull-to-refresh creates a new session.
  • Features are precomputed into a feature store (affinity scores updated hourly by a batch job, engagement counters in near real time). The ranker does lookups and arithmetic, not joins.
  • Budget it: 500 candidates x a model call must fit inside ~100 ms. If the ranker times out, serve reverse-chronological. A feed that is unranked is a degraded feed; a feed that errors is an outage.

A common wrong answer is to rank at write time ("sort each inbox by score as posts arrive"). Scores depend on the viewer and change every minute as engagement accrues; the inbox should stay ordered by id, and ranking happens over a snapshot at read time.

Step 11 — Pagination: cursors, and why OFFSET fails

The feed is a list whose head changes constantly. Position-based pagination assumes it does not.

import base64, json

timeline = list(range(120, 100, -1))          # post ids, newest first (Snowflake-style: bigger = newer)

def page_offset(tl, offset, limit=5):
    return tl[offset:offset + limit]

def encode_cursor(last_id):                    # opaque to the client, versioned for us
    return base64.urlsafe_b64encode(json.dumps({"v": 1, "max_id": last_id}).encode()).decode()

def page_cursor(tl, cursor=None, limit=5):
    max_id = json.loads(base64.urlsafe_b64decode(cursor))["max_id"] if cursor else None
    items = [p for p in tl if max_id is None or p < max_id][:limit]   # WHERE id < :max_id
    return items, (encode_cursor(items[-1]) if items else None)

# --- OFFSET: user reads page 1, then 3 new posts arrive and 1 old one is deleted ---
p1 = page_offset(timeline, 0)
live = [123, 122, 121] + [p for p in timeline if p != 113]
p2 = page_offset(live, 5)
print("offset  page1:", p1)
print("offset  page2:", p2, "<- repeats", sorted(set(p1) & set(p2), reverse=True))

# --- CURSOR: same sequence of events ---
c1, cur = page_cursor(timeline)
c2, cur2 = page_cursor(live, cur)
print("cursor  page1:", c1)
print("cursor  page2:", c2, "<- continues after 116, no repeats")
print("cursor token :", cur)

# --- The cost side: OFFSET 10000 on an index still walks 10000 entries ---
print("rows touched for page 501:  offset =", 500 * 20 + 20, "  cursor =", 20)
Output
offset  page1: [120, 119, 118, 117, 116]
offset  page2: [118, 117, 116, 115, 114] <- repeats [118, 117, 116]
cursor  page1: [120, 119, 118, 117, 116]
cursor  page2: [115, 114, 112, 111, 110] <- continues after 116, no repeats
cursor token : eyJ2IjogMSwgIm1heF9pZCI6IDExNn0=
rows touched for page 501:  offset = 10020   cursor = 20
  • Correctness: with OFFSET, three new posts at the top shifted everything down, so page 2 repeated three posts the user had just seen. A delete would have made it silently skip one. Users notice duplicates immediately.
  • Cost: OFFSET 10000 still walks 10,000 index entries to throw them away; deep scrolling gets linearly slower. The cursor turns every page into an indexed range seek — WHERE post_id < :max_id ORDER BY post_id DESC LIMIT 20 or ZREVRANGEBYSCORE (max_id — constant cost at any depth.
  • Ranked feeds need a session cursor. "Everything with id below X" does not work when the order is by score. The cursor instead carries {session, position}, pointing into the ranked list cached under feedpage:{user}:{session}. When that session expires, fall back to a max_id cursor into the chronological tail.
  • New posts go on top via a pill, not by shifting the list under the user's thumb. GET /feed/new_count?since=<newest id on screen> is a cheap ZCOUNT on the inbox.
  • Keep the cursor opaque. A base64 JSON blob with a version field lets you change the scheme without a client release. Sign it if it carries anything you would not want a client to forge.

Step 12 — Sharding the posts

At 27 TB/year and growing, posts must be partitioned. There are three natural keys, and each makes a different query cheap.

import random, hashlib

rng = random.Random(7)
SHARDS, EPOCH_MS = 16, 1_700_000_000_000

def snowflake(ts_ms, machine, seq):
    # 41 bits of milliseconds | 10 bits machine | 12 bits sequence  (lesson 7)
    return ((ts_ms - EPOCH_MS) << 22) | (machine << 12) | seq

def h(x):                                  # stable hash (Python's hash() is salted per process)
    return int(hashlib.md5(str(x).encode()).hexdigest(), 16)

# 2,000 authors with heavy-tailed popularity; 40,000 posts spread over 16 days.
followers = {a: int(10 / (1.0 - rng.random()) ** 1.2) for a in range(2_000)}
authors = list(followers)
posts = []
for i in range(40_000):
    a = authors[int(rng.random() ** 3 * len(authors))]      # a few authors post a lot
    ts = EPOCH_MS + int(rng.random() * 16 * 86_400_000)
    posts.append((snowflake(ts, i % 1024, i % 4096), a, ts))

strategies = {
    "by author_id":  lambda pid, a, ts: h(a) % SHARDS,
    "by post_id":    lambda pid, a, ts: h(pid) % SHARDS,
    "by time (day)": lambda pid, a, ts: (ts - EPOCH_MS) // 86_400_000 % SHARDS,
}
last_day = max(ts for _, _, ts in posts) - 86_400_000
star = max(authors, key=followers.get)

print(f"{'strategy':<15}{'storage skew':>13}{'write skew (today)':>20}{'read skew':>11}{'shards/profile':>16}")
for name, place in strategies.items():
    store, writes, reads = [0] * SHARDS, [0] * SHARDS, [0] * SHARDS
    star_shards = set()
    for pid, a, ts in posts:
        s = place(pid, a, ts)
        store[s] += 1
        if ts >= last_day:
            writes[s] += 1
            reads[s] += followers[a]        # fresh posts are read ~ in proportion to audience
        if a == star:
            star_shards.add(s)
    skew = lambda xs: max(xs) / (sum(xs) / SHARDS)
    print(f"{name:<15}{skew(store):>12.1f}x{skew(writes):>19.1f}x{skew(reads):>10.1f}x{len(star_shards):>16}")
Output
strategy        storage skew  write skew (today)  read skew  shards/profile
by author_id            2.0x                2.0x       3.8x               1
by post_id              1.1x                1.1x       2.4x              10
by time (day)           1.0x               16.0x      16.0x              11
Shard keyWhat it makes cheapWhat it makes painful
author_idA profile page is one shard. All of an author's data is together.Hot users: one celebrity's shard takes a disproportionate share of reads (3.8x above). Prolific authors make storage uneven (2.0x). A single user can outgrow a shard.
post_id (hashed)Even storage and write load (1.1x). Fetching a post by id is one shard. No hot shard from one author."Latest posts by X" must scatter to many shards (10 of 16 above) and merge.
Time range (e.g. per day)Recent-first reads and archival: old shards go read-only and move to cold storage.Every write today hits one shard (16x skew). The newest shard also takes all the fresh reads.

The answer: shard the posts table by hashed post_id for even load, and keep a separate user_posts index sharded by author_id that holds only ids. "Latest 20 by X" reads one user_posts partition (small, cheap even for a hot author, and heavily cached in recent:{author}), then does a multi-get of 20 posts by id. You get locality for the profile query and even distribution for the bytes.

Why the id must be time-sortable. A Snowflake id (41 bits of milliseconds, 10 of machine, 12 of sequence — built in the unique ID lesson) sorts by creation time. That lets the id itself be the timeline score, the merge key and the pagination cursor, with no secondary index on created_at. A random UUID would force a second index and break every one of those. The time bits also give you time-range archival without time-range sharding: a background job can move ids older than a cutoff to cold storage, knowing the cutoff from the id alone.

Use consistent hashing or a large fixed number of logical partitions (say 4,096) mapped onto a smaller number of physical nodes, so adding capacity moves whole partitions rather than rehashing every row — see the key-value store lesson.

Step 13 — Caching layers

LayerKeyWhat it holdsInvalidation
CDNimmutable media URLAll image/video variants, avatarsNone needed — keys never change; 1-year TTL
Timeline cachetl:{user}800 newest inbox ids per active userPush writes; trim; rebuilt on miss; evicted if inactive for ~30 days
Author recentsrecent:{author}~200 newest ids per authorWritten on every post; read by every hybrid merge and profile view
Post cachepost:{id}Hydrated post bodiesWrite-through on create; delete event sets tombstone; TTL 1 day
Counterscnt:{id}Like/reply/repost countsIncremented in Redis, flushed to the DB every few seconds
Ranked pagefeedpage:{user}:{session}Ordered ids for one scroll sessionTTL 5 minutes; new session on refresh
In-processper app serverThe hottest ~10k posts and celebrity recentsTTL 1–2 s; absorbs hot-key storms
  • Hot keys. When a celebrity posts, recent:{celeb} and post:{id} are read by millions of feeds within minutes. Replicate those keys across several cache nodes (key suffix #1..#8, read a random one) and put a 1-second in-process cache in front. This is the same trick as the viral restaurant in the capstone.
  • Hot counters. A viral post can take 50k likes/s. A single row UPDATE ... likes = likes + 1 would serialize on a lock. Increment a sharded counter in Redis, flush the sum periodically, and show approximate counts ("1.2M") — nobody can tell whether it is 1,203,441 or 1,203,502.
  • Stampedes. When a popular key expires, thousands of misses hit the database at once. Use a per-key lock or request coalescing so only one request refills it, and jitter TTLs (see scaling and caching).
  • Replicate the timeline cache (primary + replica per shard, across AZs). It is rebuildable, but rebuilding 200M inboxes after losing a node is a thundering herd on the posts store.

Step 14 — Deletes, privacy and blocks

Push fan-out copies an id into many places. Every "make this disappear" feature has to deal with those copies, and the answer is nearly always filter at read time, clean up lazily.

  • Delete a post. Set state = deleted in posts, update post:{id} in the cache synchronously, remove it from recent:{author} and user_posts, and emit post.deleted. The id remains in up to hundreds of inboxes, and every read skips it at hydration. A background consumer can optionally ZREM it from inboxes, but correctness never depends on that. Media variants are purged from storage and the CDN after a grace period; that is the one place a CDN purge is needed.
  • Block. The strongest guarantee in the system. Write the block, and synchronously add the blocked user to both users' hide: sets, so the next feed read on either side filters immediately. Also remove the follow edges both ways. The profile and post-by-id endpoints check blocks directly, since a blocked user could otherwise open a post link.
  • Mute and unfollow. Same read-time filter, lower stakes. Unfollow removes the edge, so the "still following?" check hides old entries at once and trimming removes them within days.
  • Private accounts. Posts with visibility = followers are only fanned out to approved followers, and the read path re-checks the edge before hydrating — if you are removed as a follower, the post id already in your inbox must not render.
  • Follow a new account. The reverse problem: your inbox has none of their past posts. On follow.changed, a worker pulls their latest ~20 from recent:{author} and merges them into tl:{follower}, so the new account shows up on your next refresh rather than only when they next post.
  • Account deletion and legal takedown. The user's posts become tombstones, search entries are removed via the same event stream, media is hard-deleted after the retention window, and the job is tracked to completion because it is a legal obligation, not a best effort.

Step 15 — Search and trending (sketch)

Search is a separate system fed from the same event stream. A post must be searchable within seconds, and the index covers recent posts in memory with older posts on disk.

import re
from collections import Counter, defaultdict

posts = {  # post_id -> text; ids are time-sortable, so "newest" = largest id
    501: "Rain again in the city #monsoon",
    502: "Launch day for our new phone #launch",
    503: "Traffic is terrible, #monsoon flooding downtown",
    504: "Watching the #launch stream with the team",
    505: "#monsoon ruined my commute",
    506: "Coffee first, emails later",
    507: "#launch keynote was short and good",
    508: "#launch pricing announced",
}
STOP = {"the", "is", "in", "for", "our", "with", "my", "was", "and", "a"}

# --- Inverted index: term -> posting list of post ids, kept newest-first ---
index = defaultdict(list)
for pid in sorted(posts, reverse=True):
    for term in set(re.findall(r"#?\w+", posts[pid].lower())) - STOP:
        index[term].append(pid)

def search(query, limit=3):
    """AND query: intersect posting lists, smallest list first (cheapest intersection)."""
    lists = sorted((index.get(t, []) for t in query.lower().split()), key=len)
    hits = set(lists[0]).intersection(*lists[1:]) if lists else set()
    return sorted(hits, reverse=True)[:limit]
print("search 'monsoon' hashtag:", search("#monsoon"))
print("search 'launch stream':  ", search("#launch stream"))

# --- Trending: velocity against the topic's own baseline, not raw volume ---
last_hour  = Counter({"#launch": 4_200, "#monsoon": 900,  "#coffee": 5_000})
baseline_h = Counter({"#launch":   150, "#monsoon": 700,  "#coffee": 4_800})  # same hour, prior weeks
def trend_score(tag, smoothing=100):
    return (last_hour[tag] + smoothing) / (baseline_h[tag] + smoothing)
for tag in sorted(last_hour, key=trend_score, reverse=True):
    print(f"{tag:<9} now={last_hour[tag]:>5}  usual={baseline_h[tag]:>5}  score={trend_score(tag):5.1f}")
Output
search 'monsoon' hashtag: [505, 503, 501]
search 'launch stream':   [504]
#launch   now= 4200  usual=  150  score= 17.2
#monsoon  now=  900  usual=  700  score=  1.2
#coffee   now= 5000  usual= 4800  score=  1.0
  • Inverted index: term → posting list of post ids, newest first. Because ids are time-sortable, "most recent matches" is just the head of the intersection. Intersect starting from the shortest list.
  • Index size: 150M posts/day x ~15 indexed terms x ~8 bytes per posting ≈ 18 GB/day of postings. Keep the last week or two in memory; older segments on SSD.
  • Shard by post id (document partitioning), not by term. Term partitioning puts every "#worldcup" posting on one machine during the final. Document partitioning spreads every term across all shards: each query fans out to every shard and an aggregator merges the top results — more work per query, but no hot shard and a lost node only loses a slice of results, not a whole word.
  • Rebuilding a lost index shard is a replay: the indexer consumes post.created from Kafka from a checkpoint, or re-reads the shard's post id range from the post store.
  • Ranking search results combines text relevance with recency and engagement, the same features as the feed, computed per shard before the merge.
  • Trending is not "most posts": "#coffee" would trend every morning forever. Score each tag's volume in the last window against its own baseline for that hour of the week (with smoothing so tiny tags do not jump from 1 to 20), per region. Count with a streaming job over Kafka in 5-minute windows; filter spam and coordinated campaigns before publishing.

Step 16 — Consistency, decided per feature

DataGuaranteeWhy
Post creationDurable on ack (replicated write + outbox)Losing an acknowledged post is the one unforgivable failure
Author sees own postRead-your-own-writesReturned in the 201 and inserted client-side; also merged from recent:{self}
Follower timelinesEventual, ~secondsNobody can tell whether a post arrived 2 s or 5 s after it was written
BlocksStrong on the next readA safety feature; synchronous update of the hide sets
DeletesEffective on the next read, cleanup eventualTombstone checked at hydration; inbox cleanup can lag
Like and reply countsEventual, approximateRounded display; exactness is not a feature
Follower countsEventual, minutesAggregated asynchronously; drives the fan-out mode job
Search and trendsEventual, seconds to minutesSeparate index fed by the log

Step 17 — Failure modes and graceful degradation

What failsWhat the user seesMechanism
Fan-out workers lag (a celebrity-free spike, a bad deploy)New posts appear lateKafka buffers durably; alert on consumer lag; readers can fall back to pulling recents for followees whose posts are stuck
A Redis timeline shard is lostSlightly slower first load for those usersPromote the replica; for users with no inbox, rebuild on read via the pull path, with a concurrency cap so rebuilds do not flood the post store
Ranking service slow or downA chronological feed100 ms timeout, then serve the merged candidates by id; a circuit breaker stops calling it
Post store shard unavailableSome posts missing from the pageServe from the post cache; skip unhydratable ids rather than failing the page
Object storage or media processing downCan post text; photo uploads fail with retryMedia is decoupled from posts; CDN keeps serving already-cached media
CDN edge outageImages load slowerMulti-CDN with DNS failover; origin shield in front of storage so the origin is not stampeded
Celebrity posts during a world eventNothing unusualPull mode means no fan-out spike; hot-key replication and in-process caching absorb the reads
Duplicate post.created deliveryNothingZADD with the post id as member is idempotent; the same post twice is one entry
Region lostReads served elsewhere, possibly minutes stalePosts replicated cross-region asynchronously; timelines rebuilt or replicated; writes fail over to the surviving region
Traffic 3x above planFewer extrasShed by priority: post > feed page 1 > later pages > ranking > counts > trends > out-of-network candidates

Step 18 — Observability

  • Product SLIs: time from post to visible in a follower's feed (sample with synthetic accounts that post and read every minute), feed load success rate, empty-feed rate, duplicate-item rate per session.
  • Pipeline health: fan-out consumer lag per partition, inserts/s, largest in-flight fan-out job, inbox rebuilds/s.
  • Serving: p50/p99 per endpoint and per stage (candidates, rank, hydrate), cache hit rate per key family, hot-key detection, ranker timeout rate.
  • Alert on symptoms: "post-to-feed p95 above 30 s for 10 minutes" or "feed error rate above 0.5%", not "Redis CPU at 70%".

The trade-off summary — how to close

  • Hybrid fan-out, not pure push or pull. Push makes reads a single key lookup for almost everyone; pulling the top accounts caps the write tail. We pay with a merge step on every read and a mode flag to manage.
  • Timelines of ids in Redis, not rows in a database. They are derived data, bounded at 800 entries, and rebuildable. We accept that a lost shard means a slow first load, not lost data.
  • Filter at read, clean up lazily. Deletes, blocks and unfollows take effect instantly without N-way rewrites. We pay a few set lookups per read and some wasted inbox slots.
  • Posts sharded by id, plus an author index. Even load and single-shard profile reads at once, at the cost of maintaining two structures.
  • Time-sortable ids everywhere. They are the timeline score, the merge key and the cursor. One design choice removes three indexes.
  • Rank at read time on a snapshot, fall back to chronological. Ranking improves engagement; it must never be able to take the feed down.
  • Media never touches the app tier. Pre-signed uploads, immutable variants, CDN everywhere.
  • What I would build first: pure push fan-out with a Redis inbox, chronological order, and a hard-coded celebrity list. The threshold job, ranking and out-of-network candidates come next, each measured.
// Write your solution here
// Write your solution here
// Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 12Chat System (WhatsApp / Messenger)WebSockets, presence, message ordering, delivery receipts and group fan-out.