SLIDE 34: Feed Generation - The Challenge
Step 5: Feed Generation Algorithm (Most Complex Component)
The Challenge:
Problem Statement:
- User follows 500 people
- Each person posts ~1 photo/day
- Need to generate personalized, ranked feed
- Must be fast (target: <500ms)
- Must scale to 500 million daily active users
SLIDE 34B: Feed Generation - Naive Approach
Naive Approach (Doesn’t Scale):
CODE
-- Query all posts from people I follow, sort by time
SELECT posts.*
FROM posts
JOIN follows ON posts.user_id = follows.followee_id
WHERE follows.follower_id = 12345
ORDER BY posts.created_at DESC
LIMIT 20;
-- Problems:
-- 1. If user follows 500 people, this joins 500 users' posts
-- 2. At scale (each person has 1000 posts), this scans 500K rows
-- 3. Sorting 500K rows is expensive
-- 4. 500M users doing this simultaneously = database meltdown
SLIDE 34C: Feed Generation - Two Approaches
Two Fundamental Approaches:
- Fan-Out on Write (Push Model)
- When user posts, push to all followers’ feeds immediately
- Read is fast (feed pre-computed)
- Write is expensive (high fan-out)
- Fan-Out on Read (Pull Model)
- When user requests feed, query in real-time
- Write is fast (just insert post)
- Read is expensive (must merge and rank)
Instagram’s Solution:
Hybrid approach combining both, optimized for user characteristics.
SLIDE 35: Fan-Out on Write - How It Works
Approach 1: Fan-Out on Write
How It Works:
CODE
BobDave's Feed CacheCarol's Feed CacheBob's Feed CacheFan-Out WorkerPost ServiceAliceBobDave's Feed CacheCarol's Feed CacheBob's Feed CacheFan-Out WorkerPost ServiceAlice#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .error-icon{fill:#552222;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .error-text{fill:#552222;stroke:#552222;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-thickness-normal{stroke-width:1px;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .marker{fill:#666;stroke:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .marker.cross{stroke:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 svg{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 p{margin:0;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .actor{stroke:hsl(0, 0%, 83%);fill:#eee;stroke-width:1;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 rect.actor.outer-path[data-look="neo"]{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 rect.note[data-look="neo"]{stroke:#999;fill:#666;filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 text.actor>tspan{fill:#333;stroke:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .actor-line{stroke:hsl(0, 0%, 83%);}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .innerArc{stroke-width:1.5;stroke-dasharray:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [id$="-arrowhead"] path{fill:#333;stroke:#333;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .sequenceNumber{fill:white;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [id$="-sequencenumber"]{fill:#333;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [id$="-crosshead"] path{fill:#333;stroke:#333;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .messageText{fill:#333;stroke:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .labelBox{stroke:hsl(0, 0%, 83%);fill:#eee;filter:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .labelText,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .labelText>tspan{fill:#333;stroke:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .loopText,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .loopText>tspan{fill:#333;stroke:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .sectionTitle,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .sectionTitle>tspan{fill:#333;stroke:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(0, 0%, 83%);fill:hsl(0, 0%, 83%);}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .note{stroke:#999;fill:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .noteText,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .noteText>tspan{fill:#fff;stroke:none;font-weight:normal;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .actorPopupMenu{position:absolute;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .actorPopupMenuPanel{position:absolute;fill:#eee;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .actor-man circle,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 line{fill:#eee;stroke-width:2px;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 g rect.rect{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));stroke:#999;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 .node .neo-node{stroke:#999;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node rect,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].cluster rect,#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node polygon{stroke:url(#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].swimlane.cluster rect{filter:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node path{stroke:url(#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714-gradient);stroke-width:1px;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node .outer-path{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node .neo-line path{stroke:#999;filter:none;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node circle{stroke:url(#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].node circle .state-start{fill:#000000;}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].icon-shape .icon{fill:url(#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 [data-look="neo"].icon-shape .icon-neo path{stroke:url(#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a112562f-a642-4cc8-bc52-fa933b4f0714 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}par[Fan-out to all followers]Feeds pre-computedCreate post (post_id=123)Store post metadataTrigger fan-out (post_id=123)Fetch Alice's followers[Bob, Carol, Dave, ...]INSERT post_id=123INSERT post_id=123INSERT post_id=123GET /feed[123, 120, 115, ...] (instant)
SLIDE 35B: Fan-Out on Write - Implementation
Implementation Details:
Feed Cache Structure (Redis):
CODE
Key: feed:{user_id}
Value: Sorted set of post IDs with scores (timestamp)
Example:
feed:12345 = [
(post_id: 123, score: 1736956800),
(post_id: 120, score: 1736956700),
(post_id: 115, score: 1736956600),
...
]
When Alice Posts:
CODE
1. Store post in Posts table
2. Fetch all of Alice's followers (say, 10,000 users)
3. For each follower:
ZADD feed:{follower_id} {timestamp} {post_id}
4. If follower is online, push notification
SLIDE 35C: Fan-Out on Write - Pros and Cons
Pros:
Cons:
SLIDE 35D: Fan-Out on Write - When It Works
When This Works:
- Normal users with <10,000 followers
- Majority of Instagram users (99%+)
When This Fails:
- Celebrities, influencers with millions of followers
- Write cost becomes prohibitive
SLIDE 36: Fan-Out on Read - How It Works
Approach 2: Fan-Out on Read
How It Works:
CODE
Posts DatabaseFollows DatabaseFeed ServiceBobPosts DatabaseFollows DatabaseFeed ServiceBob#mermaid-9412da43-1bbf-4432-ab19-413714f7940e{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .error-icon{fill:#552222;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .error-text{fill:#552222;stroke:#552222;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-thickness-normal{stroke-width:1px;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-thickness-thick{stroke-width:3.5px;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-pattern-solid{stroke-dasharray:0;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .marker{fill:#666;stroke:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .marker.cross{stroke:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e svg{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e p{margin:0;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .actor{stroke:hsl(0, 0%, 83%);fill:#eee;stroke-width:1;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e rect.actor.outer-path[data-look="neo"]{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e rect.note[data-look="neo"]{stroke:#999;fill:#666;filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e text.actor>tspan{fill:#333;stroke:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .actor-line{stroke:hsl(0, 0%, 83%);}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .innerArc{stroke-width:1.5;stroke-dasharray:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [id$="-arrowhead"] path{fill:#333;stroke:#333;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .sequenceNumber{fill:white;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [id$="-sequencenumber"]{fill:#333;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [id$="-crosshead"] path{fill:#333;stroke:#333;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .messageText{fill:#333;stroke:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .labelBox{stroke:hsl(0, 0%, 83%);fill:#eee;filter:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .labelText,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .labelText>tspan{fill:#333;stroke:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .loopText,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .loopText>tspan{fill:#333;stroke:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .sectionTitle,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .sectionTitle>tspan{fill:#333;stroke:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(0, 0%, 83%);fill:hsl(0, 0%, 83%);}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .note{stroke:#999;fill:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .noteText,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .noteText>tspan{fill:#fff;stroke:none;font-weight:normal;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .actorPopupMenu{position:absolute;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .actorPopupMenuPanel{position:absolute;fill:#eee;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .actor-man circle,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e line{fill:#eee;stroke-width:2px;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e g rect.rect{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));stroke:#999;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e .node .neo-node{stroke:#999;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node rect,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].cluster rect,#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node polygon{stroke:url(#mermaid-9412da43-1bbf-4432-ab19-413714f7940e-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].swimlane.cluster rect{filter:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node path{stroke:url(#mermaid-9412da43-1bbf-4432-ab19-413714f7940e-gradient);stroke-width:1px;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node .outer-path{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node .neo-line path{stroke:#999;filter:none;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node circle{stroke:url(#mermaid-9412da43-1bbf-4432-ab19-413714f7940e-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].node circle .state-start{fill:#000000;}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].icon-shape .icon{fill:url(#mermaid-9412da43-1bbf-4432-ab19-413714f7940e-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e [data-look="neo"].icon-shape .icon-neo path{stroke:url(#mermaid-9412da43-1bbf-4432-ab19-413714f7940e-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-9412da43-1bbf-4432-ab19-413714f7940e :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}GET /feedWho does Bob follow?[Alice, Carol, Dave, ...]SELECT posts WHERE user_id IN (Alice, Carol, Dave)ORDER BY created_at DESC LIMIT 100[post_id: 123, 120, 115, ...]Merge and rank postsFeed
SLIDE 36B: Fan-Out on Read - SQL Example
SQL Query Example:
CODE
-- Step 1: Get list of people Bob follows
SELECT followee_id FROM follows
WHERE follower_id = 12345;
-- Result: [999, 888, 777, ...]
-- Step 2: Get recent posts from those users
SELECT * FROM posts
WHERE user_id IN (999, 888, 777, ...)
ORDER BY created_at DESC
LIMIT 100;
-- Step 3: Rank posts (in application code)
-- Step 4: Return top 20
SLIDE 36C: Fan-Out on Read - Pros and Cons
Pros:
Cons:
SLIDE 36D: Fan-Out on Read - Caching Optimization
Optimization: Caching
Even with fan-out on read, aggressive caching is needed:
CODE
1. User requests feed
2. Check Redis cache (key: feed:{user_id})
3. If cached (80% of requests):
- Return cached feed (50-100ms)
4. If not cached (20% of requests):
- Compute feed from database (300-500ms)
- Store in cache (TTL: 5 minutes)
- Return to user
When This Works:
- Celebrities with millions of followers
- Write-heavy scenarios
- When storage cost is higher than compute cost
SLIDE 37: Hybrid Approach - Overview
Hybrid Strategy: Best of Both Worlds
Core Idea:
Use different strategies for different user types based on follower count.
User Segmentation:
SLIDE 37B: Hybrid Approach - Flow Diagram
Implementation:
CODE
#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .error-icon{fill:#552222;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .error-text{fill:#552222;stroke:#552222;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-thickness-normal{stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .marker{fill:#666;stroke:#666;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .marker.cross{stroke:#666;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 svg{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 p{margin:0;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .label{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";color:#000000;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster-label text{fill:#333;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster-label span{color:#333;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster-label span p{background-color:transparent;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .label text,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 span{fill:#000000;color:#000000;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node rect,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node circle,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node ellipse,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node polygon,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node path{fill:#eee;stroke:#999;stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .rough-node .label text,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node .label text,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .image-shape .label,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .icon-shape .label{text-anchor:middle;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .rough-node .label,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node .label,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .image-shape .label,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .icon-shape .label{text-align:center;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node.clickable{cursor:pointer;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .root .anchor path{fill:#666!important;stroke-width:0;stroke:#666;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .arrowheadPath{fill:#333333;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edgePath .path{stroke:#666;stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .flowchart-link{stroke:#666;fill:none;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edgeLabel{background-color:white;text-align:center;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edgeLabel p{background-color:white;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .labelBkg{background-color:rgba(255, 255, 255, 0.5);}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster rect{fill:hsl(0, 0%, 98.9215686275%);stroke:#707070;stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster text{fill:#333;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .cluster span{color:#333;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:12px;background:hsl(-160, 0%, 93.3333333333%);border:1px solid #707070;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#000000;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 rect.text{fill:none;stroke-width:0;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .icon-shape,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .image-shape{background-color:white;text-align:center;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .icon-shape p,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .image-shape p{background-color:white;padding:2px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .icon-shape .label rect,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .image-shape .label rect{opacity:0.5;background-color:white;fill:white;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 .node .neo-node{stroke:#999;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node rect,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].cluster rect,#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node polygon{stroke:url(#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].swimlane.cluster rect{filter:none;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node path{stroke:url(#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288-gradient);stroke-width:1px;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node .outer-path{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node .neo-line path{stroke:#999;filter:none;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node circle{stroke:url(#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].node circle .state-start{fill:#000000;}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].icon-shape .icon{fill:url(#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 [data-look="neo"].icon-shape .icon-neo path{stroke:url(#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-4c4c1625-7bec-4cd8-b0ef-40e168a6c288 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}User Creates PostFollower Count?Fan-Out on WritePush to follower feedsCelebrity Posts PoolStore separatelyUser Requests FeedFollows anycelebrities?Read Pre-computed Feedfrom cacheMerge Normal Feed +Celebrity Posts< 10K followers> 10K followersNoYes
SLIDE 37C: Hybrid Approach - Normal User Posts
When Normal User (Alice, 500 followers) Posts:
CODE
1. Store post in Posts table
2. Check follower_count: 500 < 10,000 (threshold)
3. Fan-out to 500 followers' caches:
FOR each follower:
ZADD feed:{follower_id} {timestamp} {post_id}
4. Done (500 writes, acceptable)
SLIDE 37D: Hybrid Approach - Celebrity Posts
When Celebrity (Cristiano Ronaldo, 600M followers) Posts:
CODE
1. Store post in Posts table
2. Check follower_count: 600M > 10,000 (threshold)
3. DO NOT fan-out (600M writes = too expensive)
4. Mark as "celebrity post" (flag in database)
5. Store in celebrity posts pool
6. Done (1 write, very cheap)
SLIDE 37E: Hybrid Approach - User Reads Feed
When User (Bob) Requests Feed:
CODE
1. Check: Does Bob follow any celebrities?
SELECT followee_id FROM follows
WHERE follower_id = Bob AND followee_id IN (celebrity_ids)
2. Fetch pre-computed feed (normal users Bob follows):
ZRANGE feed:Bob 0 50
3. If Bob follows celebrities:
- Fetch recent posts from those celebrities:
SELECT * FROM posts
WHERE user_id IN (celeb_ids)
ORDER BY created_at DESC LIMIT 20
4. Merge both lists:
- Combine normal feed + celebrity posts
- Re-rank by algorithm (next slide)
5. Return top 20 posts
SLIDE 37F: Hybrid Approach - Performance Comparison
Storage and Performance:
Why This Works:
- 99% of users have <10K followers (fan-out is cheap)
- 1% of users are celebrities (fan-out is expensive)
- Most users follow few/no celebrities (fast read path)
- Small percentage pay slight latency cost for celebrity content
SLIDE 38: Feed Ranking - Objective and Factors
Feed Ranking: How to Order Posts
Objective:
Given 100 candidate posts, rank them to show user the 20 most relevant posts first.
Ranking Factors:
1. Recency (Freshness)
- Weight: 40%
- Newer posts ranked higher
- Exponential decay: Post from 1 hour ago >> post from 1 day ago
CODE
recency_score = e^(-age_in_hours / 24)
Examples:
- Post from 1 hour ago: e^(-1/24) = 0.96
- Post from 12 hours ago: e^(-12/24) = 0.61
- Post from 48 hours ago: e^(-48/24) = 0.14
SLIDE 38B: Feed Ranking - Engagement
2. Engagement (Popularity)
- Weight: 30%
- Posts with more likes/comments ranked higher
CODE
engagement_score = log(1 + like_count + 3 * comment_count)
Why log?
- Diminishing returns (post with 1000 likes not 10x better than 100 likes)
- Prevents viral posts from dominating entirely
Why 3x weight for comments?
- Comments indicate deeper engagement than likes
SLIDE 38C: Feed Ranking - Relationship and Content
3. Relationship Strength (Affinity)
- Weight: 20%
- Prioritize posts from users you interact with frequently
Structure & Concept Flow
4. Content Type Preference
- Weight: 10%
- Personalize based on user preferences (photos vs videos, certain topics)
Structure & Concept Flow
SLIDE 38D: Feed Ranking - Combined Formula
Combined Ranking Formula:
CODE
final_score = 0.4 * recency_score
+ 0.3 * engagement_score
+ 0.2 * relationship_score
+ 0.1 * content_score
Posts sorted by final_score descending
Top 20 returned to user
SLIDE 38E: Feed Ranking - Example Calculation
Example Calculation:
Ranking: A > C > B
SLIDE 38F: Feed Ranking - Production Complexity
Production Complexity:
In real Instagram:
- Machine learning models (not simple formulas)
- Hundreds of features (time of day, user location, post topic, etc.)
- A/B testing of different models
- Personalized per user segment
Interview Answer:
“For this interview, I’m using a simplified weighted scoring model with four factors: recency, engagement, relationship strength, and content type. In production, this would be a sophisticated machine learning model trained on user interaction data, but the concept is similar - we’re trying to predict which posts a user will engage with.”
SLIDE 39: Feed Caching Strategy - Architecture
Caching Strategy for Feed Performance
Cache Architecture:
CODE
#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .error-icon{fill:#552222;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .error-text{fill:#552222;stroke:#552222;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-thickness-normal{stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-thickness-thick{stroke-width:3.5px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-pattern-solid{stroke-dasharray:0;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .marker{fill:#666;stroke:#666;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .marker.cross{stroke:#666;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d svg{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d p{margin:0;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .label{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";color:#000000;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster-label text{fill:#333;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster-label span{color:#333;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster-label span p{background-color:transparent;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .label text,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d span{fill:#000000;color:#000000;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node rect,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node circle,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node ellipse,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node polygon,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node path{fill:#eee;stroke:#999;stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .rough-node .label text,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node .label text,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .image-shape .label,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .icon-shape .label{text-anchor:middle;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .rough-node .label,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node .label,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .image-shape .label,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .icon-shape .label{text-align:center;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node.clickable{cursor:pointer;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .root .anchor path{fill:#666!important;stroke-width:0;stroke:#666;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .arrowheadPath{fill:#333333;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edgePath .path{stroke:#666;stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .flowchart-link{stroke:#666;fill:none;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edgeLabel{background-color:white;text-align:center;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edgeLabel p{background-color:white;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .labelBkg{background-color:rgba(255, 255, 255, 0.5);}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster rect{fill:hsl(0, 0%, 98.9215686275%);stroke:#707070;stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster text{fill:#333;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .cluster span{color:#333;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:12px;background:hsl(-160, 0%, 93.3333333333%);border:1px solid #707070;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#000000;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d rect.text{fill:none;stroke-width:0;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .icon-shape,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .image-shape{background-color:white;text-align:center;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .icon-shape p,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .image-shape p{background-color:white;padding:2px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .icon-shape .label rect,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .image-shape .label rect{opacity:0.5;background-color:white;fill:white;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d .node .neo-node{stroke:#999;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node rect,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].cluster rect,#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node polygon{stroke:url(#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].swimlane.cluster rect{filter:none;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node path{stroke:url(#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d-gradient);stroke-width:1px;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node .outer-path{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node .neo-line path{stroke:#999;filter:none;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node circle{stroke:url(#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].node circle .state-start{fill:#000000;}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].icon-shape .icon{fill:url(#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d [data-look="neo"].icon-shape .icon-neo path{stroke:url(#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-a65d7ff6-332b-427d-add9-bc66d591213d :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}Feed RequestL1: Redis CachePre-computed FeedsL2: DatabasePosts, FollowsReturn Feed50-100msCompute FeedRank PostsUpdate L1 CacheReturn Feed300-500msCache Hit80%Cache Miss20%
SLIDE 39B: Feed Caching Strategy - Hit Rates
Cache Hit Rates (Cumulative):
In practice: 70%+ requests never hit database
SLIDE 39C: Feed Caching Strategy - Redis Structure
Redis Cache Structure:
Key Structure:
CODE
feed:{user_id}
Example:
feed:12345
Value Structure (Sorted Set):
CODE
Sorted Set (ZSET) with post IDs and scores
Members: post_id
Scores: timestamp (for sorting)
Example:
ZADD feed:12345 1736956800 post_123
ZADD feed:12345 1736956700 post_120
ZADD feed:12345 1736956600 post_115
Retrieve:
ZREVRANGE feed:12345 0 19 (get top 20 posts)
SLIDE 39D: Feed Caching Strategy - Parameters
Cache Parameters:
SLIDE 39E: Feed Caching Strategy - Invalidation
Cache Invalidation (When to Clear Cache):
1. User Unfollows Someone:
CODE
When Bob unfollows Alice:
- DELETE feed:Bob
- Next feed request will regenerate without Alice's posts
2. Post Deleted:
CODE
When post_id=123 is deleted:
- Option A: Remove from all feeds (expensive, not worth it)
- Option B: Do nothing, filter out on read (lazy invalidation)
Instagram uses Option B.
3. User Changes Settings:
CODE
When Bob mutes Carol:
- DELETE feed:Bob
- Regenerate without Carol's posts
SLIDE 39F: Feed Caching Strategy - Hit Rate Targets
Cache Hit Rate Target:
SLIDE 39G: Feed Caching Strategy - TTL Trade-offs
Why 5-Minute TTL:
Trade-off Analysis:
Decision: 5 minutes balances freshness and performance.
SLIDE 39H: Feed Caching Strategy - Memory Requirements
Memory Requirements:
CODE
Average feed cache size per user:
- 100 post IDs × 8 bytes per ID = 800 bytes
- Plus sorted set overhead = ~1 KB per user
For 500M active users:
- 500M × 1 KB = 500 GB total
- Split across multiple Redis instances (100 instances × 5 GB each)
SLIDE 40: Complete Feed Generation Flow (Diagram)
End-to-End Feed Generation Flow
CODE
#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;fill:#000000;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .error-icon{fill:#552222;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .error-text{fill:#552222;stroke:#552222;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-thickness-normal{stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-thickness-thick{stroke-width:3.5px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-pattern-solid{stroke-dasharray:0;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .marker{fill:#666;stroke:#666;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .marker.cross{stroke:#666;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c svg{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:16px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c p{margin:0;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .label{font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";color:#000000;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster-label text{fill:#333;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster-label span{color:#333;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster-label span p{background-color:transparent;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .label text,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c span{fill:#000000;color:#000000;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node rect,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node circle,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node ellipse,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node polygon,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node path{fill:#eee;stroke:#999;stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .rough-node .label text,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node .label text,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .image-shape .label,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .icon-shape .label{text-anchor:middle;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .rough-node .label,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node .label,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .image-shape .label,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .icon-shape .label{text-align:center;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node.clickable{cursor:pointer;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .root .anchor path{fill:#666!important;stroke-width:0;stroke:#666;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .arrowheadPath{fill:#333333;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edgePath .path{stroke:#666;stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .flowchart-link{stroke:#666;fill:none;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edgeLabel{background-color:white;text-align:center;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edgeLabel p{background-color:white;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .labelBkg{background-color:rgba(255, 255, 255, 0.5);}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster rect{fill:hsl(0, 0%, 98.9215686275%);stroke:#707070;stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster text{fill:#333;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .cluster span{color:#333;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:ui-sans-serif,-apple-system,BlinkMacSystemFont,"Segoe UI Variable Display","Segoe UI",Helvetica,"Apple Color Emoji","Noto Sans Arabic","Noto Sans Hebrew",Arial,sans-serif,"Segoe UI Emoji","Segoe UI Symbol";font-size:12px;background:hsl(-160, 0%, 93.3333333333%);border:1px solid #707070;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#000000;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c rect.text{fill:none;stroke-width:0;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .icon-shape,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .image-shape{background-color:white;text-align:center;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .icon-shape p,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .image-shape p{background-color:white;padding:2px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .icon-shape .label rect,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .image-shape .label rect{opacity:0.5;background-color:white;fill:white;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c .node .neo-node{stroke:#999;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node rect,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].cluster rect,#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node polygon{stroke:url(#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].swimlane.cluster rect{filter:none;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node path{stroke:url(#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c-gradient);stroke-width:1px;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node .outer-path{filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node .neo-line path{stroke:#999;filter:none;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node circle{stroke:url(#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].node circle .state-start{fill:#000000;}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].icon-shape .icon{fill:url(#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c [data-look="neo"].icon-shape .icon-neo path{stroke:url(#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c-gradient);filter:drop-shadow( 1px 2px 2px rgba(185,185,185,1));}#mermaid-e0a3b8b5-afa9-477e-a95d-2b4d059e582c :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}User Requests FeedValid Auth?Feed inRedis Cache?Return Cached Feed50-100msGet User's FolloweesFROM follows tableAny celebritiesin followees?Get Pre-Computed FeedFROM feed cacheQuery Celebrity PostsFROM posts tableMerge Normal + Celebrity PostsApply Ranking AlgorithmScore each postHydrate Post DetailsGet full objects from DBUpdate Redis CacheTTL: 5 minutesReturn Feed to Client401 UnauthorizedNoYesHit 80%Miss 20%No CelebsHas CelebsHas Celebs
SLIDE 40B: Complete Feed Generation - Steps 1-3
Detailed Steps with Timings:
Step 1: Authentication (5-10ms)
CODE
- Validate JWT token
- Extract user_id
- Check rate limits
Step 2: Cache Check (10-20ms)
CODE
Redis command:
ZREVRANGE feed:{user_id} 0 19
If exists: Return immediately (cache hit)
If not: Proceed to generation (cache miss)
Step 3: Get Followees (20-30ms)
CODE
SELECT followee_id, is_celebrity
FROM follows
WHERE follower_id = {user_id};
Result: [
{followee_id: 999, is_celebrity: false},
{followee_id: 888, is_celebrity: false},
{followee_id: 777, is_celebrity: true}
]
SLIDE 40C: Complete Feed Generation - Steps 4-5
Step 4a: Get Normal User Posts (30-50ms)
CODE
For non-celebrity followees:
- Already pre-computed in their feed caches
- Merge from multiple caches
Redis commands:
ZUNION temp_feed feed:999 feed:888
ZREVRANGE temp_feed 0 99
Step 4b: Get Celebrity Posts (50-100ms)
CODE
SELECT * FROM posts
WHERE user_id IN (777, ...)
AND created_at > NOW() - INTERVAL '7 days'
ORDER BY created_at DESC
LIMIT 50;
Step 5: Merge and Rank (30-50ms)
CODE
- Combine normal posts + celebrity posts
- Calculate score for each post (ranking algorithm)
- Sort by score descending
- Select top 100 candidates
SLIDE 40D: Complete Feed Generation - Steps 6-8
Step 6: Hydration (50-100ms)
CODE
-- Get full post objects
SELECT posts.*, users.username, users.profile_pic_url
FROM posts
JOIN users ON posts.user_id = users.user_id
WHERE posts.post_id IN (123, 120, 115, ...);
-- Add personalization flags
For each post:
Check if current user has liked:
SELECT 1 FROM likes WHERE user_id={current_user} AND post_id={post_id}
Step 7: Update Cache (10-20ms)
CODE
Redis command:
ZADD feed:{user_id} {timestamp_1} {post_id_1}
ZADD feed:{user_id} {timestamp_2} {post_id_2}
...
EXPIRE feed:{user_id} 300 (5 minutes TTL)
Step 8: Return to Client (5ms)
CODE
Serialize to JSON
Return HTTP 200 OK response
SLIDE 40E: Complete Feed Generation - Latency Breakdown
Total Latency Breakdown:
SLIDE 40F: Complete Feed Generation - Optimization Tips
Performance Optimization Tips:
- Parallel Queries: Fetch normal posts and celebrity posts in parallel
- Connection Pooling: Reuse database connections
- Batch Hydration: Fetch all post details in one query (not N queries)
- Lazy Loading: Don’t fetch comments in feed request (load separately)
- Compression: Use protocol buffers or MessagePack (smaller than JSON)