Bird
Raised Fist0

Design a Generic Newsfeed System - Pull vs Push vs Hybrid Fan-Out at Any Scale

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Generic Newsfeed System - Pull vs Push vs Hybrid Fan-Out at Any Scale
Designing scalable newsfeed delivery with pull, push, and hybrid fan-out strategies for billions of users
hardSocial Media and Feed SystemsFreq: high
Prerequisites:System Design FundamentalsCAP TheoremDistributed SystemsData Modeling for Social Graphs
⚙️
Functional Requirements
  • Users can see a personalized newsfeed with posts from followed users and pages.
  • Support real-time updates to the feed with new posts appearing within seconds.
  • Allow users to fetch older posts with pagination (infinite scroll).
  • Support feed ranking and filtering (e.g., most recent, most relevant).
  • Allow users to like, comment, and share posts with updates reflected in the feed.
  • Support multi-device consistency and offline read capabilities.
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU).
  • Handle peak write throughput of ~925K new posts per second (2B users × 40 posts/user/day / 86400 seconds).
  • Ensure 99.99% availability for feed read and write APIs.
  • Feed read latency P99 under 100ms for personalized feed retrieval.
  • Data retention for at least 30 days with efficient archival.
❓
Clarifying Questions to Ask
  • What is the average number of followers per user and distribution (power law)?
  • Are posts immutable or can they be edited/deleted after publishing?
  • What is the expected read-to-write ratio for the feed?
  • Is the feed strictly chronological or does it require complex ranking?
  • What is the acceptable staleness for real-time updates?
  • Are there any constraints on device types or network conditions?
Out of Scope
✗ Feed ranking algorithms and machine learning models.
✗ User authentication and authorization mechanisms.
✗ Content moderation and filtering policies.
✗ Ad targeting and monetization features.
📌
Assumptions
  • 2 billion DAU
  • 40 posts per user per day on average
  • 100 bytes average post metadata size (excluding media)
  • Average followers per user: 500 (power law with heavy tail)
⚡
QPS Calculation
write qps925926
peak write qps2780000
read qps231481
peak read qps694444
💾
Storage Estimate
daily storage8 TB/day
30 day retention240 TB
with replication720 TB total storage
🖥️
Server Estimate
write pathKafka cluster with 1000 brokers to handle 2.78M writes/sec peak (assuming 3K writes/sec per broker)
read pathRedis cluster with 2000 nodes for sub-ms feed retrieval at 700K QPS peak (350 reads/sec per node)
🏗️
Architecture Diagram
Architecture Diagram
          +------------+
          |  Clients   |
          +-----+------+
                | Pull/Push Requests
                v
          +-----+------+
          | API Gateway|
          +-----+------+
                |
       +--------+--------+
       |                 |
 +-----v-----+     +-----v-----+
 | Write Svc |     | Read Svc  |
 +-----+-----+     +-----+-----+
       |                 |
       v                 v
 +-----+-----+     +-----+-----+
 | Kafka     |     | Redis     |
 | (Pub/Sub) |     | (Cache)   |
 +-----+-----+     +-----+-----+
       |                 |
       v                 |
 +-----+-----+           |
 | Fan-out  |<-----------+
 | Workers  |
 +-----+-----+
       |
       v
 +-----+-----+
 | Cassandra |
 | (Storage) |
 +-----------+
🧩
Components
API Gateway
Entry point for all client requests, routes to read or write services
Why thisNginx and Envoy proxy provide high throughput, low latency routing with TLS termination
Why notDirect client-to-service communication lacks centralized control and complicates scaling
Write Service
Handles new post submissions, validates and publishes to Kafka
Why thisStateless microservice implemented in Go for concurrency and low latency, integrates with Kafka producer API
Why notMonolithic write service limits scalability and fault isolation
Kafka (Pub/Sub)
Durable, partitioned log for write buffering and asynchronous fan-out processing
Why thisApache Kafka scales to millions of writes/sec with partitioning and replication, supports consumer groups for fan-out
Why notRabbitMQ lacks Kafka’s throughput and partitioning model at this scale
Fan-out Workers
Consume Kafka topics, fan-out posts to followers’ feeds in Redis and Cassandra
Why thisKubernetes-managed stateless workers enable horizontal scaling and fault tolerance
Why notDirect synchronous fan-out blocks writes and increases latency
Redis (Cache)
Stores precomputed user feeds for low-latency reads
Why thisRedis Sorted Sets enable efficient feed pagination and TTL-based eviction for freshness
Why notMemcached lacks sorted data structures and TTL granularity needed for feed ordering
Cassandra (Storage)
Persistent storage for all posts and user feed metadata with high write throughput
Why thisApache Cassandra’s wide-column model supports time-series data with tunable consistency and linear scalability
Why notPostgreSQL requires complex manual sharding and does not scale linearly at 2.78M writes/sec
Read Service
Serves feed read requests by querying Redis cache or falling back to Cassandra
Why thisStateless microservice optimized for low-latency queries with Redis fallback
Why notDirect Cassandra queries for all reads cause high latency and overload storage
🔄
Data Flow
1
Client → API Gateway
User submits new post
API Gateway routes write requests to Write Service
2
Write Service → Kafka
Publish new post event to Kafka topic
Decouples write ingestion from fan-out processing
3
Fan-out Workers → Kafka
Consume post events
Workers scale horizontally to handle peak write throughput
4
Fan-out Workers → Redis and Cassandra
Fan-out post to followers’ feeds in Redis cache and persist in Cassandra storage
Ensures low-latency feed reads and durable storage

Practice

(1/5)
1. If the purge API service in a CDN is down, what exactly breaks in the cache invalidation process?
medium
A. Cached content never expires and clients always get stale data
B. Surrogate key invalidations queue up but are not applied, causing delayed invalidation
C. TTL-based expirations continue but manual purge requests fail, so immediate invalidation is lost
D. Client-side cache control headers override server cache, causing inconsistent cache states

Solution

  1. Step 1: Identify purge API role

    Purge API triggers immediate invalidation; TTL expirations are independent and continue.

  2. Step 2: Analyze failure impact

    Without purge API, manual or programmatic immediate invalidations fail; TTL still expires cache eventually; surrogate key invalidations may be separate.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    TTL expirations unaffected; purge requests fail causing delayed invalidation [check]
Hint: Purge API down blocks immediate invalidation, TTL still expires [check]
Common Mistakes:
2. In a primary-replica system, what exactly breaks if the replication log (WAL) on the primary is lost before being sent to replicas?
medium
A. Replicas request full data snapshot from primary, causing high load and delayed recovery
B. Primary blocks all writes until WAL is restored, causing system-wide write unavailability
C. Primary loses committed transactions permanently, causing data loss and inconsistency
D. Replicas continue serving stale reads but cannot apply new writes, causing data divergence

Solution

  1. Step 1: Understand WAL role in replication

    WAL is the source of truth for replicas to catch up incrementally.

  2. Step 2: Trace failure impact

    If WAL is lost, replicas cannot catch up incrementally and must request full snapshot, causing load and delay.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Lost WAL -> replicas request full snapshot -> recovery delay [check]
Hint: Lost WAL -> full snapshot fetch delays recovery [check]
Common Mistakes:
3. For a global API rate limiter with strict per-user limits, which architecture best balances consistency and latency?
medium
A. Use client-side counters with periodic server reconciliation
B. Use a single centralized Redis instance for all counters
C. Use a sharded Redis cluster with consistent hashing per user ID
D. Use a distributed SQL database with strong consistency guarantees

Solution

  1. Step 1: Analyze consistency and latency needs

    Strict per-user limits require consistent counters with low latency.

  2. Step 2: Evaluate architectures

    Centralized Redis (A) is a bottleneck; client-side counters (C) are eventually consistent and unreliable; distributed SQL (D) has high latency. Sharded Redis with consistent hashing (B) balances load and maintains per-user consistency.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sharded Redis cluster scales with consistent hashing per user [check]
Hint: Shard counters by user ID for scalable consistency [check]
Common Mistakes:
4. Without the shard-level cache in the faceted search system, what exactly breaks during high query load spikes?
medium
A. The Query Coordinator fails to merge results correctly causing incorrect counts
B. Shard nodes become overloaded, causing increased query latency and timeouts
C. Queries return stale facet counts due to delayed cache invalidation
D. The inverted index becomes inconsistent and returns wrong documents

Solution

  1. Step 1: Understand shard-level cache role

    The cache reduces load on shard nodes by serving frequent queries quickly, preventing overload during spikes.

  2. Step 2: Trace failure without cache

    Without cache, all queries hit shard nodes directly, causing CPU and I/O overload, increasing latency and timeouts.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Cache absence -> shard overload -> latency spikes [check]
Hint: No cache -> shard overload -> latency spikes [check]
Common Mistakes:
5. At 10x scale, which Pastebin component is most likely to fail first and why?
hard
A. The relational database, because complex joins for analytics become a bottleneck
B. The analytics event ingestion pipeline, because Kafka partitions saturate and cause backpressure
C. The Expiration Worker, because scanning all snippets for TTL expiry becomes too slow
D. The snippet storage layer, because key-value stores cannot shard keys efficiently at scale

Solution

  1. Step 1: Analyze scaling bottlenecks

    Expiration Worker scans all snippets to delete expired ones; at 10x scale, scan latency grows linearly.

  2. Step 2: Compare other components

    Relational DB (A) is not primary storage; key-value stores (C) shard well; Kafka (D) scales with partitioning but expiration scanning is a linear bottleneck.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Expiration scanning is linear and slows down first at scale [check]
Hint: Expiration scanning scales linearly, fails first at 10x [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard