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")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/DELETEon a resource, notPOST /follow. The operation is naturally idempotent, so a retried request cannot double-count or toggle back. Idempotency-Keyon 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_countendpoint 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 pagesFive 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
followstable 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), notDELETE. The id is still sitting in hundreds of inboxes; the tombstone is how the read path knows to skip it (Step 14). fanout_modeis a stored per-user flag, set by a job, not recomputed fromfollower_counton every post. Otherwise an account crossing the threshold flips back and forth and leaves inboxes half-populated.
Step 5 — High-level design
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
postsanduser_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.changedso timelines can backfill or prune. - Fan-out workers — consume
post.created, read follower lists in pages, andZADDinto 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
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
- 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.
- Server-chosen object keys.
orig/2026/09/23/<media_id>, never the user's filename. It prevents overwrites, path tricks and hot key prefixes. - 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.
- 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.
- Dedupe by hash (optional): identical uploads — memes, reposted photos — share one stored object and just gain another media row.
- 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.
- 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}")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
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
- 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.
- 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.
- 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_idso one author's posts are fanned out in order. - Trim on every insert.
ZREMRANGEBYRANKkeeps each inbox at 800 entries, so memory is bounded by users x 800, not by history. - 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.
- 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)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 pullsrecent:{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:
- 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.
- 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.
- 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}")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_sessionfor ~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)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 10000still 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 20orZREVRANGEBYSCORE (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 underfeedpage:{user}:{session}. When that session expires, fall back to amax_idcursor 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 cheapZCOUNTon 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}")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 key | What it makes cheap | What it makes painful |
|---|---|---|
author_id | A 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
| Layer | Key | What it holds | Invalidation |
|---|---|---|---|
| CDN | immutable media URL | All image/video variants, avatars | None needed — keys never change; 1-year TTL |
| Timeline cache | tl:{user} | 800 newest inbox ids per active user | Push writes; trim; rebuilt on miss; evicted if inactive for ~30 days |
| Author recents | recent:{author} | ~200 newest ids per author | Written on every post; read by every hybrid merge and profile view |
| Post cache | post:{id} | Hydrated post bodies | Write-through on create; delete event sets tombstone; TTL 1 day |
| Counters | cnt:{id} | Like/reply/repost counts | Incremented in Redis, flushed to the DB every few seconds |
| Ranked page | feedpage:{user}:{session} | Ordered ids for one scroll session | TTL 5 minutes; new session on refresh |
| In-process | per app server | The hottest ~10k posts and celebrity recents | TTL 1–2 s; absorbs hot-key storms |
- Hot keys. When a celebrity posts,
recent:{celeb}andpost:{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 + 1would 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 = deletedinposts, updatepost:{id}in the cache synchronously, remove it fromrecent:{author}anduser_posts, and emitpost.deleted. The id remains in up to hundreds of inboxes, and every read skips it at hydration. A background consumer can optionallyZREMit 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 = followersare 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 fromrecent:{author}and merges them intotl:{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}")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.createdfrom 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
| Data | Guarantee | Why |
|---|---|---|
| Post creation | Durable on ack (replicated write + outbox) | Losing an acknowledged post is the one unforgivable failure |
| Author sees own post | Read-your-own-writes | Returned in the 201 and inserted client-side; also merged from recent:{self} |
| Follower timelines | Eventual, ~seconds | Nobody can tell whether a post arrived 2 s or 5 s after it was written |
| Blocks | Strong on the next read | A safety feature; synchronous update of the hide sets |
| Deletes | Effective on the next read, cleanup eventual | Tombstone checked at hydration; inbox cleanup can lag |
| Like and reply counts | Eventual, approximate | Rounded display; exactness is not a feature |
| Follower counts | Eventual, minutes | Aggregated asynchronously; drives the fan-out mode job |
| Search and trends | Eventual, seconds to minutes | Separate index fed by the log |
Step 17 — Failure modes and graceful degradation
| What fails | What the user sees | Mechanism |
|---|---|---|
| Fan-out workers lag (a celebrity-free spike, a bad deploy) | New posts appear late | Kafka buffers durably; alert on consumer lag; readers can fall back to pulling recents for followees whose posts are stuck |
| A Redis timeline shard is lost | Slightly slower first load for those users | Promote 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 down | A chronological feed | 100 ms timeout, then serve the merged candidates by id; a circuit breaker stops calling it |
| Post store shard unavailable | Some posts missing from the page | Serve from the post cache; skip unhydratable ids rather than failing the page |
| Object storage or media processing down | Can post text; photo uploads fail with retry | Media is decoupled from posts; CDN keeps serving already-cached media |
| CDN edge outage | Images load slower | Multi-CDN with DNS failover; origin shield in front of storage so the origin is not stampeded |
| Celebrity posts during a world event | Nothing unusual | Pull mode means no fan-out spike; hot-key replication and in-process caching absorb the reads |
Duplicate post.created delivery | Nothing | ZADD with the post id as member is idempotent; the same post twice is one entry |
| Region lost | Reads served elsewhere, possibly minutes stale | Posts replicated cross-region asynchronously; timelines rebuilt or replicated; writes fail over to the surviving region |
| Traffic 3x above plan | Fewer extras | Shed 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.
