HLD: Social Media Feed (Twitter/X)

Designing a massively scalable social media platform like Twitter (X) requires architecting real-time timeline generation, high-throughput content ingestion, and robust global search under strict sub-second latency constraints. A distributed social graph poses unique data routing challenges, especially when balancing instant visibility against exponential fan-out complexity.

1. System Requirements & Design Goals

Functional Requirements

• Tweet Ingestion: Users must be able to publish text, media, and polls. Tweets appear in real-time on the author's profile and their followers' timelines.
• Timeline Generation:
  • Home Timeline (Feed): An aggregated, chronologically or algorithmically sorted feed of recent tweets from accounts the user follows.
  • User Timeline: A curated list of all tweets and retweets published by a single specific user.
• Social Graph Navigation: Support unidirectional follow relationships (User A follows User B without requiring reciprocal approval).
• Search & Trends: Real-time indexing of newly ingested tweets to support full-text search, hashtag tracking, and trending topics.

Non-Functional Requirements

• High Availability (HA): The timeline service must achieve $99.999\%$ uptime. Read availability is strictly prioritized over immediate write consistency during network partitions (CAP Theorem: AP system).
• Low Latency: Generating and fetching the home timeline should complete in $< 200\text{ms}$ at the API router boundary.
• Eventual Consistency: While user profiles reflect published posts immediately (strong read-your-own-writes consistency), distribution to followers' home feeds can tolerate eventual consistency delays ranging from $50\text{ms}$ to several seconds for ultra-large accounts.
• Scale & Surge Tolerance: Must withstand dramatic traffic spikes during breaking global events (thundering herd problem).

2. Scale Estimation & Mathematical Modeling

Twitter exhibits a heavily asymmetric read-heavy workload. Designing caching tiers and database topologies depends directly on rigorous capacity forecasting.

       [ Read/Write Workload Ratio: ~100 : 1 ]
   
   Write Ingestion                     Read Timeline Consumption
  [5,000 tweets/s]                 [350,000 timeline requests/s]
   ===                               ===============================================

Traffic & Throughput

• Daily Active Users (DAU): $300\text{ million}$
• Tweet Publishing Rate:
  • Average: $300\text{M} \times 1.5\text{ tweets/day} \approx 450\text{ million tweets/day} = 5,208\text{ tweets/sec}$
  • Peak traffic multiplier: $5\times \implies \mathbf{26,000\text{ tweets/sec}}$
• Timeline Consumption Rate:
  • Average user visits home timeline $5\text{ times/day}$, scrolling through $4$ pages ($20$ tweets per fetch):
  • $300\text{M} \times 20\text{ requests} = 6\text{ billion requests/day} \approx \mathbf{69,444\text{ requests/sec}}$
  • Peak read rate: $5\times \implies \mathbf{347,220\text{ read requests/sec}}$
• Read-to-Write Ratio: Approximately $\mathbf{67 : 1}$ (often rounded to $100 : 1$ when accounting for external API and non-authenticated embed traffic).

Storage & Network Bandwidth Sizing

• Text & Metadata Payload: $500\text{ bytes}$ per tweet (text, timestamp, location, author ID, routing flags).
• Media Attachment Ratio: $20\%$ of tweets include compressed photos/videos (average media size: $2\text{ MB}$).
• Daily Ingestion Storage: $\text{Text Storage} = 450 \times 10^6 \times 500\text{ B} = 225\text{ GB/day}$ $\text{Media Storage} = (450 \times 10^6 \times 0.20) \times 2\text{ MB} = 180\text{ TB/day}$
• Network Bandwidth Inflow: $\text{Ingress} = \frac{180.225\text{ TB}}{86,400\text{ s}} \approx 2.08\text{ GB/s} \approx \mathbf{16.6\text{ Gbps}}$
• Network Bandwidth Outflow (Egress): Assuming $100\text{ B}$ compressed representation per timeline payload and CDN media delivery: $\text{API Egress} = 347,220\text{ req/s} \times (20\text{ tweets} \times 500\text{ B}) \approx \mathbf{3.47\text{ GB/s} = 27.7\text{ Gbps}}$

3. High-Level Architecture & Data Flow

flowchart TD
    Client["Mobile / Web Client"] -->|HTTPS / gRPC| CDN["Cloudflare Edge CDN"]
    CDN --> API["API Gateway & Load Balancer"]
    
    subgraph Write Path
        API -->|POST /tweet| TS["Tweet Ingestion Service"]
        TS -->|1. Store| TDB[(Tweet Sharded Store\nCassandra / CockroachDB)]
        TS -->|2. Publish| Kafka["Apache Kafka\n(Event Stream)"]
        Kafka -->|Consume| FAS["Fan-out Service (Push Worker)"]
        FAS -->|Lookup Followers| Graph["Social Graph Service\n(In-Memory Adjacency List)"]
        FAS -->|Write IDs| Redis[(Redis Home Timelines\nIn-Memory ZSETs)]
    end
    
    subgraph Read Path
        API -->|GET /timeline| TLS["Timeline Query Service"]
        TLS -->|Fetch Pushed Feed| Redis
        TLS -->|Merge Celebrity Feeds| PullS["Celebrity Pull Engine"]
        PullS -->|Fetch Recent| TDB
    end
    
    subgraph Real-Time Search
        Kafka -->|Consume| SearchWorker["Search Ingestion Workers"]
        SearchWorker -->|Index| ES["Elasticsearch Cluster\n(Time-Partitioned)"]
    end

4. Timeline Generation & The Fan-out Problem

At the core of social media architecture lies the debate between push vs. pull routing strategies during content delivery.

Option A: Fan-out on Write (Push Model)

When User A publishes a tweet, a background orchestration service fetches User A's follower list from the social graph and pushes the new Tweet ID directly into an in-memory cache (Redis Sorted Set, or ZSET) dedicated to each follower's Home Timeline.

• Pros: Reading a timeline is instantaneous—an $O(1)$ range lookup (ZREVRANGEBYSCORE) against the follower’s Redis cache.
• Cons (The Celebrity Problem): If a public figure with $100\text{ million}$ followers tweets, the system must generate $100\text{ million}$ cache write operations for a single post. At peak traffic, this creates an extreme hotspot bottleneck, saturating background queues and inducing latency cascades across regular accounts.

Option B: Fan-out on Read (Pull Model)

When User B opens the application to view their timeline, the backend dynamically looks up the list of accounts User B follows, queries each account's recent posts from a secondary database index, and executes a multi-way merge sort in memory.

• Pros: Zero computational overhead at publication time. Eliminates the celebrity write hotspot.
• Cons: Read operations require an expensive $O(N \log N)$ distributed join and merge across numerous storage nodes. With $350,000\text{ read requests/sec}$, query processing times spike far above the $200\text{ms}$ SLA threshold.

The Production Solution: Hybrid Timeline Architecture

Modern scalable feeds implement an adaptive hybrid architecture, establishing an algorithmic threshold based on an author's follower graph density.

| Parameter | Ordinary Users (< 10,000 Followers) | Celebrities / Mega-Nodes (≥ 10,000 Followers) | | :--- | :--- | :--- | | Strategy | Fan-out on Write (Push) | Fan-out on Read (Pull) | | Write Cost | Moderate ($< 10,000$ cache updates) | Zero cache fan-out (written only to author's user profile) | | Read Cost | $O(1)$ cache read | Dynamic query + merge during timeline load | | Storage Topology | Dedicated Redis ZSETs per follower | Secondary read replicas & specialized memory buffers |

sequenceDiagram
    autonumber
    actor Alice as Regular User
    actor Bieber as Celebrity (100M Followers)
    actor Bob as Follower (Follows Both)
    participant API as API Gateway
    participant TS as Tweet Service
    participant Fan as Fanout Worker
    participant Redis as Redis Timeline Cache
    participant Pull as Pull Service
    
    Alice->>API: POST /tweet (Text)
    API->>TS: Ingest & Store
    TS->>Fan: Async Fan-out Event
    Fan->>Fan: Check Author Followers (< 10k?)
    Fan->>Redis: ZADD Bob_Home_Timeline (Tweet ID)
    
    Bieber->>API: POST /tweet (Text)
    API->>TS: Ingest & Store
    TS->>Fan: Async Fan-out Event
    Fan->>Fan: Check Author Followers (≥ 10k!)
    Note over Fan,Pull: Skipped Push Fanout to prevent write storm
    
    Bob->>API: GET /timeline
    API->>Pull: Request Composite Feed
    Pull->>Redis: ZREVRANGE Bob_Home_Timeline (Pushed Tweets)
    Pull->>TS: Query Bieber's latest tweets (Pull)
    Note over Pull: Multi-way In-Memory Merge Sort & Dedup
    Pull-->>API: Return Top 20 Merged Tweets
    API-->>Bob: Render Home Timeline

5. Storage Hierarchy & Data Partitioning

Distributed Tweet Store (Apache Cassandra / ScyllaDB)

To endure high write velocity without distributed locking contention, tweets are committed to a wide-column NoSQL store formatted as append-only structures.

• Primary Key Strategy: To optimize fetching an individual author's timeline while mitigating partition hotspots, composite database keys are utilized:

  PRIMARY KEY ((user_id, month_year_bucket), tweet_id)
  WITH CLUSTERING ORDER BY (tweet_id DESC);
  

• Snowflake IDs for Temporal Ordering: Instead of serial auto-incrementing integers (which introduce database coordination overhead), Tweet IDs are generated using 64-bit decentralized Snowflake tokens.
  • Bits 0–41 (42 bits): Milliseconds timestamp since a custom epoch (provides ~69 years of addressable space).
  • Bits 42–51 (10 bits): Machine / Worker ID (supports up to $1,024$ nodes).
  • Bits 52–63 (12 bits): Per-machine sequential sequence number (allows generating $4,096$ IDs per millisecond per node).
  • Architectural Benefit: Sorting tweets lexicographically by tweet_id inherently orders them by accurate temporal creation time without secondary timestamp indexes.

In-Memory Cache Design (Redis ZSET Architecture)

Each active user maintains a persistent memory footprint representing their curated home feed.

• Structure: Redis Sorted Set (ZSET).
• Key: user:{user_id}:timeline
• Score: 64-bit Snowflake Timestamp / Ranking algorithm weight.
• Member: tweet_id (Store IDs only, never duplicate text bodies in timeline caches).
• Memory Boundedness: Timelines are capped at a hard threshold of 800 tweets per cache. Older tweets are progressively evicted via ZREMRANGEBYRANK. If an ultra-deep pagination request exceeds 800 items, the backend gracefully falls back to querying Cassandra read replicas.

6. Real-Time Search & Indexing Pipeline

Searching a dynamic corpus of hundreds of billions of tweets requires isolating historical cold storage from volatile real-time event streams.

Time-Partitioned Search Indices

1. Ingestion Router: Newly emitted tweets enter an Apache Kafka partition keyed by author_id.
2. Real-Time Indexing Workers (Apache Flink): Consumers parse token streams, execute multilingual stemming, strip stop-words, extract #hashtags, and construct inverted indices.
3. Dual-Tier Search Engines:
   • Hot / Recent Index (Elasticsearch / Lucene RAM Buffers): Stores tweets from the last $7\text{ days}$. Partitions are sliced into discrete 2-hour rolling indices. Because recent news dominates over $85\%$ of search queries, keeping these shards small ensures entire inverted index structures sit entirely within OS system filesystem cache (zero disk read I/O).
   • Cold / Historical Index: Tweets older than $7\text{ days}$ are consolidated into immutable, highly compressed daily shards hosted on SSD backing storage and queried via distributed scatter-gather federated search.

7. Production Implementation: Hybrid Timeline Merge

The following Python production snippet implements the hybrid read engine, querying an in-memory pushed feed and blending it seamlessly with celebrity pull-model queues using asyncio and an efficient min-heap merge.

import asyncio
import time
import heapq
from typing import List, Dict, Any

class HybridTimelineEngine:
    def __init__(self, redis_client, db_client):
        self.redis = redis_client
        self.db = db_client
        self.celebrity_threshold = 10_000

    async def fetch_home_timeline(self, user_id: int, limit: int = 20) -> List[Dict[str, Any]]:
        # 1. Fetch pushed timeline IDs from Redis ZSET (O(1) fast path for regular users)
        cache_key = f"user:{user_id}:timeline"
        pushed_ids_task = self.redis.zrevrange(cache_key, 0, limit - 1, withscores=False)
        
        # 2. Identify which followed accounts are Celebrities (Pull required)
        celebrities_task = self.get_followed_celebrities(user_id)
        
        pushed_ids, celebrities = await asyncio.gather(pushed_ids_task, celebrities_task)
        
        # 3. Simultaneously fetch actual payload data for pushed IDs and Pull-Celebrity recent tweets
        pushed_payloads_task = self.db.multi_get_tweets(pushed_ids)
        celebrity_pull_tasks = [
            self.db.get_recent_author_tweets(author_id=celeb_id, limit=limit)
            for celeb_id in celebrities
        ]
        
        results = await asyncio.gather(pushed_payloads_task, *celebrity_pull_tasks)
        pushed_tweets = results[0]
        celeb_tweet_lists = results[1:]
        
        # 4. Perform an efficient in-memory K-way merge sort using a priority queue
        merged_feed = self.merge_k_sorted_feeds([pushed_tweets] + celeb_tweet_lists, limit)
        return merged_feed

    async def get_followed_celebrities(self, user_id: int) -> List[int]:
        """
        Returns a tiny subset of followed IDs whose follower count exceeds celebrity_threshold.
        Normally cached in local application memory or specialized Bloom/Cuckoo filters.
        """
        followed_ids = await self.db.get_following_list(user_id)
        # Filter strictly for high-fanout nodes
        return [uid for uid, count in followed_ids.items() if count >= self.celebrity_threshold]

    def merge_k_sorted_feeds(self, feeds: List[List[Dict[str, Any]]], limit: int) -> List[Dict[str, Any]]:
        """
        Merges K descending-sorted feed arrays in O(N * log(K)) complexity.
        """
        merged = []
        # Max-heap emulation by storing negative timestamp as priority weight
        heap = []
        
        for feed_idx, feed in enumerate(feeds):
            if feed:
                first_tweet = feed[0]
                heapq.heappush(heap, (-first_tweet["timestamp"], feed_idx, 0, first_tweet))
                
        while heap and len(merged) < limit:
            neg_ts, feed_idx, elem_idx, tweet = heapq.heappop(heap)
            
            # Deduplicate if a tweet somehow leaked between pull and push pipelines
            if not any(t["id"] == tweet["id"] for t in merged):
                merged.append(tweet)
                
            next_idx = elem_idx + 1
            if next_idx < len(feeds[feed_idx]):
                next_tweet = feeds[feed_idx][next_idx]
                heapq.heappush(heap, (-next_tweet["timestamp"], feed_idx, next_idx, next_tweet))
                
        return merged

8. Edge Cases, Failure Modes & Resilience

Thundering Herd during Breaking News

When global breaking news emerges, massive synchronized user influxes can overwhelm edge API gateways and exhaust cache thread pools.

• ** mitigation Strategy:** Implement Coalescing Request Shifting (Single-flight execution) at the routing gateway. When $1,000$ concurrent read requests arrive simultaneously asking for an identical viral tweet or profile page that just expired from cache, only one thread is allowed through to query backend replica instances. The remaining $999$ worker threads hold in short-lived memory queues and are instantly served the resultant payload once the pioneer thread populates the edge cache.

Cache Stampede & Replication Warming

If a master Redis node housing $5\text{ million}$ timelines suffers hardware fault and crashes, routing fallback traffic directly to relational persistence tiers will instantly melt database I/O capacities.

• Warm-up Replication: Timelines are maintained in Active-Passive asynchronous clusters with Sentinel auto-failover.
• Graceful Degradation: If cache loss occurs without immediate hot standbys, the API gateway falls back into a Degraded Feed Mode, constructing partial feeds dynamically using strictly the top $20$ most prominent accounts the user follows, bypassing exhaustive graph traversals until caches rebuild asynchronously via log replay.

Hot Keys in Partitioned Databases

A globally viral tweet generates excessive read requests to a single physical partition key, creating unbalanced network saturation on that specific node.

• Salt Ring Distribution: For tweets crossing dynamic velocity thresholds ($> 1,000\text{ req/sec}$), the API tier proactively injects randomized integer suffixes (e.g., tweet_id:shard_0 to tweet_id:shard_9) across $10$ independent cache shards, effectively dispersing CPU network routing loads across multiple physical servers.

9. Comprehensive Interview Questions & Answers

Q1: Why use an in-memory cache for Home Timelines instead of simply querying a tuned database view?

Answer: A single database view query requires performing dynamic joins across the user’s social graph (which may contain thousands of followed entities) and scanning indices across millions of table records. Under a continuous load of $350,000$ reads/sec, database buffer pools experience severe thrashing, and lock contention skyrockets. By pre-computing feeds into persistent Redis Sorted Sets (ZSETs), timeline rendering becomes a predictable, deterministic memory lookup ($O(1)$ disk I/O), guaranteeing sub-200ms API latencies regardless of systemic load spikes.

Q2: How do you handle deep pagination when a user continuously scrolls past the 800-item cache memory limit?

Answer: Because less than $1\%$ of user daily sessions scroll past 800 items, keeping thousands of stale historical IDs per user in high-cost RAM represents inefficient resource allocation. When pagination requests exceed the in-memory threshold, the API gateway triggers an fallback query to the primary wide-column database (Cassandra). To maintain seamless visual scrolling without duplicate items caused by incoming concurrent tweets, pagination relies on Cursor-based pagination (Snowflake ID markers) (WHERE tweet_id < cursor_id LIMIT 20) rather than standard database offset clauses (OFFSET 800 LIMIT 20), ensuring stable time-space consistency.

Q3: How do we prevent race conditions when a user deletes a tweet after it has already fanned out to millions of follower caches?

Answer: Deletion instructions bypass asynchronous fan-out processing and instead issue a Tombstone Broadcast Event via high-priority Kafka queues directly to indexing and API rendering engines. While sweeping millions of individual Redis user caches synchronously would cause systemic latency spikes, the system takes an eventual consistency approach:

1. The tweet state in the authoritative source store is flipped to DELETED_TOMBSTONE.
2. As background scrubbing workers gracefully iterate through cache shards removing the specific ID via ZREM, any read queries that accidentally pull the lingering ID from an uncleaned timeline cache fail their secondary payload hydration verification against the primary store and are silently dropped prior to client rendering.

Q4: Explain how machine learning ranking pipelines integrate without degrading real-time rendering SLAs.

Answer: Injecting ML ranking inference into an active HTTP request-response cycle cannot comfortably execute within a $200\text{ms}$ overall latency budget if computing complex predictive features on the fly. To reconcile this:

• A real-time feature streaming architecture continuously computes algorithmic relevance weights (user affinity, engagement velocity) offline and stores pre-scored weights inside specialized feature stores (e.g., Redis Streams / Feast).
• When a read occurs, the Timeline Query Service retrieves the raw reverse-chronological pool of candidates ($200$ IDs), passes the concise ID batch through a localized low-latency C++ / ONNX scoring proxy to re-order the vector array entirely in memory within $< 15\text{ms}$, and crops the definitive top $20$ items for payload rendering.