3. Capacity Estimation: Building intuition behind 3. capacity estimation.
1. What is Instagram?
Instagram is a social networking service primarily focused on photo and video sharing. The core feature we are designing is the News Feed: a constantly updating list of photos and videos from people a user follows.
[!TIP]
In a System Design interview, clarify if you are designing the Feed Generation or the Image Storage. Usually, the Feed logic (Fanout) is the harder algorithmic challenge, while Image Storage is an infrastructure challenge (Blob storage + CDN). We will focus heavily on the Feed Generation.
Real-World Analogies
The Mailbox (Push Model): Imagine a physical mailbox. When your friend writes a letter, the postman delivers it to your box immediately. When you get home (open the app), the letters are already waiting. Reading is instant, but the postman works hard.
The Newspaper (Pull Model): Imagine a newspaper stand. The printer doesn’t deliver to your house. Instead, when you wake up, you must go to the stand and ask, “Do you have any news for me?” The stand then compiles stories just for you.
Try it yourself
[!TIP] Try it yourself: Open Instagram or Threads. Post a photo. How quickly does it appear on your friend’s phone? If you edit the caption, does it update instantly? This latency vs consistency trade-off is what we are building.
2. Requirements & Goals
Functional Requirements
Post Media: Users can upload photos and videos.
Follow Graph: Users can follow other users.
View Feed: Users see a list of posts from followees, sorted by time (Chronological) or relevance (Ranked).
Non-Functional Requirements
Latency: Feed generation must be ultra-fast (< 200ms). The user should never see a loading spinner for more than a split second.
Availability: The system should be highly available (AP over CP). It’s okay if a user sees a post a few seconds late (Eventual Consistency), but not okay if the feed fails to load.
Reliability: Uploaded photos must never be lost.
Extended Requirements
Analytics: Track engagement (Views, Likes).
Celebrities: Handle users with millions of followers (The “Justin Bieber” problem).
Pagination: Efficiently load older posts as the user scrolls.
3. Capacity Estimation
Let’s assume:
DAU: 500 Million users.
Read/Write Ratio: 100:1 (Users view feeds much more often than they post).
Conclusion: We absolutely need a CDN for media delivery. Our servers only handle the 231 MB/s ingress, while the CDN offloads the massive egress.
Memory Estimates (Redis)
We store the “Home Timeline” for active users in Redis.
Structure: List of Post IDs (8 bytes each).
Capacity: 500 Posts per user.
Total Active Users: 300 Million (Daily).
Memory: 300 × 106 × 500 × 8 bytes ≈ 1.2 TB.
Shard Sizing: If we use 64GB RAM instances, we need ~20 shards (plus replicas). This is very manageable.
4. System APIs
We need RESTful APIs for the client.
Method
Endpoint
Description
POST
/v1/media/upload
Upload a photo/video. Returns media_id.
POST
/v1/users/follow
Follow a target user. Body: { target_id: "123" }
GET
/v1/feed
Get the user’s news feed. Params: cursor (for pagination), limit.
Feed Navigation: Cursor vs Offset
Why do we use cursor instead of OFFSET?
Feature
OFFSET Pagination
Cursor Pagination
Query
LIMIT 10 OFFSET 1000
WHERE id < 1000 LIMIT 10
Performance
O(N). DB must scan and skip 1000 rows. Slow for deep pages.
O(1) (with Index). DB jumps directly to ID 1000.
Data Integrity
Unsafe. If a new post is added while scrolling, OFFSET shifts, showing duplicates.
Safe. The cursor points to a specific record, unaffected by new inserts.
Verdict
Avoid for Feeds.
Preferred.
5. Database Design
We need three main stores:
Relational DB (SQL): For Users, Follows, and Metadata. We need structured relationships.
NoSQL / K-V Store: For the Feed Cache (Redis/Cassandra).
Blob Storage: For actual image files (S3).
SQL Schema (Simplified)
Users Table
id:PK,BigIntusername:Varcharavatar_url:Varchar
Relations Table (Follow Graph)
follower_id:FK->Users.idfollowee_id:FK->Users.idcreated_at:Timestamp-- Index on (follower_id, followee_id) to answer "Who follows X?" and "Who does X follow?"
Graph Databases are excellent for “Friends of Friends” queries, but they are notoriously hard to shard.
Sharding SQL: We can easily shard SQL tables by User ID. All of User A’s follows live on Shard 1.
Sharding Graph: A graph is highly connected. Cutting it across servers (“Vertex Cut” or “Edge Cut”) results in expensive cross-network traversals for simple queries.
Verdict: Since our queries are simple (“Who does X follow?”), sharded SQL or a specialized graph store like Facebook’s TAO (which sits on top of MySQL) is better than a native Graph DB for this scale.
Global ID Generation (Snowflake)
We cannot use auto-incrementing integers because we are sharding across multiple database instances. We need a globally unique ID generator that is also time-sortable.
Snowflake ID: A 64-bit integer.
1 bit: Sign.
41 bits: Timestamp (Milliseconds).
10 bits: Machine ID.
12 bits: Sequence Number.
Why?: This allows us to sort posts by id effectively sorting them by time, without needing a separate index on created_at.
6. High-Level Design
The Hybrid Architecture combines Push and Pull models efficiently.
System Architecture: Instagram Hybrid Feed
Push (Fanout) vs Pull (Celebrities) | S3 Media Storage
Write / Upload Path
Fanout (Async)
Read Feed Path
Client
Client
Service Layer
Storage & Cache
User
Load Balancer
Post Service
Writes Meta & Media
Fanout Service
Async Timeline Push
Feed Service
Merges Cache & Celebs
S3 Bucket
Media (Photos/Videos)
Primary DB
Users/Followers/Meta
Feed Cache
Redis Timelines
### System Walkthrough (Dry Run)
1. **User A Posts**:
* **Post Service** saves image to S3 (returns URL).
* **Post Service** saves metadata to **Primary DB** (Post ID `101`, User `A`, Time `T1`).
* **Post Service** places a "New Post" event onto a Kafka topic.
2. **Fanout Workers**:
* Pick up the event.
* Query **Follow Graph**: "Who follows User A?". Result: `[User B, User C]`.
* **Push**: Append Post ID `101` to `Redis List: Timeline:UserB` and `Timeline:UserC`.
3. **User B Reads Feed**:
* **Feed Service** calls `Redis LRANGE Timeline:UserB 0 20`.
* Returns `[101, 99, 85]`.
* **Feed Service** hydrates these IDs by fetching metadata/content from DB/Cache.
* **Feed Service** calls **Ranking Service** to re-order them (if not chronological).
* Returns JSON response to client.
> [!TIP]
> **Separation of Concerns: Feed vs Ranking**
> Why do we have a separate "Feed Service" and "Ranking Service"?
> * **Feed Service**: Responsible for *retrieval* and *aggregation* (I/O Bound). It fetches 1000 candidate posts.
> * **Ranking Service**: Responsible for *scoring* (CPU Bound). It runs ML models.
> By separating them, we can scale the CPU-heavy Ranking Service independently of the I/O-heavy Feed Service.
---
## 7. Component Design: Feed Generation Models
This is the core of the interview. How do we generate the feed?
### A. Pull Model (Fanout-on-Read)
* **Logic**: When User A requests the feed, the **Feed Service** queries the DB:
```sql
SELECT * FROM posts
WHERE user_id IN (SELECT followee_id FROM relations WHERE follower_id = 'UserA')
ORDER BY created_at DESC
LIMIT 20;
```
* **Pros**: Simple. No storage overhead (Space Complexity is O(1) in cache). Real-time consistency.
* **Cons**: The read time complexity is **O(N × M)** where `N` is the number of followers and `M` is the average posts per followee. The database must scan massive indexed tables and perform expensive joins or IN clauses on every read. This is extremely slow for users following thousands of people and is fundamentally unscalable for high read traffic.
### B. Push Model (Fanout-on-Write)
* **Logic**: Each user has a "Home Timeline" list in Redis (e.g., a Linked List or Sorted Set).
* When User B posts, we find all their followers and *push* the Post ID into their Redis lists.
* **Reading**: User A just reads their Redis list. The read time complexity becomes an ultra-fast **O(1)** operation.
* **Pros**: Instant reads. Phenomenal user experience.
* **Cons**: **The Celebrity Problem**. If a user with 100M followers posts, the system has to perform a fanout operation requiring 100M writes instantly.
* **Hardware Reality**: At this scale, the network bandwidth becomes completely saturated. Assuming an 8-byte Post ID, pushing to 100M lists is over 800MB of pure payload data hitting the network switches at once. This creates a massive backlog ("Thundering Herd") that spikes Redis CPU, fills up task queues, and ultimately delays feed updates for the entire platform.
### C. Hybrid Model (The Winner)
* **Normal Users**: Use **Push**.
* **Celebrities**: Use **Pull**.
**Step-by-Step Hybrid Flow**:
1. **User B Posts**: System checks `FollowerCount(B)`.
2. **If Normal (<50k followers)**: **Fanout Service** pushes Post ID to all followers' Redis caches immediately (visualized as orange dashed line).
3. **If Celebrity (>50k followers)**: Do nothing (or only push to active followers). The post is just saved to the DB.
4. **User A Reads Feed**:
* System fetches User A's pre-computed Redis list (Normal posts).
* System checks which Celebrities User A follows.
* System queries DB for *recent* posts from those Celebrities.
* System **merges** the two lists in memory (Sorted by Time).
This approach balances write load and read latency perfectly.
---
## 8. Data Partitioning & Sharding
As we scale to billions of posts, one DB instance isn't enough.
* **Sharding by User ID**: Store all data for a user on one shard.
* *Pro*: Fast to get all posts by one user.
* *Con*: Hot spots (Celebrities). A shard with Justin Bieber will melt.
* **Sharding by Post ID**: Distribute posts randomly/hashed.
* *Pro*: Even distribution.
* *Con*: To generate a feed (Pull model), you must query ALL shards ("Scatter-Gather").
**Verdict**: Sharding by **User ID** is usually preferred for the metadata, but we rely heavily on the **Feed Cache** (Redis Cluster) which is sharded by the *Viewer's ID*.
---
## 9. Reliability, Caching & Load Balancing
* **CDN**: All images/videos served via CDN (Cloudflare/Akamai). This reduces load on our servers by 90%+. See [CDN Explained](/system-design/06-caching/05-cdn/).
* **Redis Cluster**: Stores the pre-computed feeds.
* **Data Structure**: We use `LIST` or `ZSET` (Sorted Set).
* `LPUSH` to add new Post IDs.
* `LTRIM` to keep the list size fixed (e.g., 800 items).
* **Optimization**: Redis uses **ziplist** encoding for small lists, which saves memory by storing integers in a compact byte array instead of linked pointers.
* **Pipelining**: When fetching a feed, we don't do 20 round trips. We use `MGET` or Pipelining to fetch all metadata in one go.
* **Feed Size Limit**: We don't store *all* posts in Redis. Only the last ~800 Post IDs. If the user scrolls past that, we fall back to DB (Pagination).
---
## 10. Interactive Decision Visualizer
### Fanout Cost Simulator
> [!TIP] **Try it yourself**: Adjust the follower count to see how the system load scales between Push and Pull models. Notice the breaking point for "Celebrity" users.
Fanout Cost Simulator
Select a scenario to see the System Load.
System LoadIdle
Push Model
Write to every follower's Timeline immediately.
Total Writes:0
Read Latency:-
Pull Model
Save once. Followers query DB on read.
Total Writes:1
Read Latency:O(N) Scans
---
## 11. Requirements Traceability
Requirement
Design Decision
Justification
Ultra-fast Reads (<200ms)
Push Model (Redis)
Pre-computing timelines ensures O(1) read time.
High Availability
Eventual Consistency
We prioritize AP. If a post takes 5s to propagate, it’s acceptable.
Celebrity Scaling
Hybrid Architecture
Pull model for celebrities prevents Thundering Herd on cache.
Pagination
Cursor-Based
last_post_id prevents duplicates when scrolling dynamic feeds.
Reliability
S3 + SQL
Metadata in SQL (ACID) and Media in S3 (Durability 99.999999999%) ensures no data loss.
---
## 12. Observability (RED Method)
We must monitor the health of the Feed Service.
* **Rate**: Requests per Second (RPS) to `/feed`.
* **Errors**: 5xx Error Rate (Alert if > 0.1%).
* **Duration**: P99 Latency for Feed Generation (Target < 200ms).
**Key Metrics to Watch**:
* `fanout_lag`: Time difference between "Post Created" and "Post Visible in Feed".
* `cache_hit_ratio`: Percentage of feeds served from Redis (Should be > 95%).
---
## 13. Deployment Strategy
* **Canary Deployment**: Roll out new Feed Logic to 1% of users first.
* **Feature Flags**: Use flags like `enable_hybrid_feed` to toggle logic without redeploying.
* **Database Migrations**: Use `pt-online-schema-change` or similar tools to add columns to the `Posts` table without locking it.
---
## 14. Interview Gauntlet
**Q1: What happens if the Redis Cluster goes down?**
* **Answer**: We fall back to the DB (Pull Model). However, this will be slow. We should implement a "Circuit Breaker" to fail fast or serve a "Stale Feed" rather than crashing the DB.
**Q2: How do you handle "Unfollow" in the Push Model?**
* **Answer**: We must asynchronously remove the Followee's posts from the Follower's Redis list. This is an O(N) operation on the list size (e.g., 800 items), which is fast.
**Q3: How do you sort the Hybrid Feed?**
* **Answer**: The "Push" feed is already sorted. The "Pull" feed is fetched sorted. We use a **Merge Sort** (like the Merge step in MergeSort) to combine two sorted lists in O(N) linear time.
---
## 15. Whiteboard Summary
Core Arch
Hybrid Model: Push (Normal) + Pull (Celeb).
Storage: S3 (Media), SQL (Meta), Redis (Feed).
ID Gen: Snowflake (Time-sortable).
Scale & Ops
Sharding: User ID (consistent hashing).
Fanout: Async Workers (Kafka).
Obs: RED Method (Lag, Hit Ratio).
Found this lesson helpful?
Mark it as mastered to track your progress through the course.