News Feed Fan-Out: Deep Dives, Data Models, and Schemas

Chapter 14 continued: sections 4 and 5, covering the deep-dive subsystems and core algorithms, then data models, storage engines, and schemas. It continues Framing, Scale Math, and Architecture and is followed by Resilience, Runbooks, and Checklist.

4. Deep-Dive Subsystems & Core Algorithms

Deep Dive 1: Push vs. Pull vs. The Staff Hybrid Model

The central fault line in all feed systems is the mathematical tension between write-time work and read-time work:

Figure 14.2: The Fan-Out Dilemma: Pure Push vs. Pure Pull vs. Staff Hybrid

Let us analyze the mathematical failure modes of both extremes:

THE FAILURE MODE OF PURE PUSH (FAN-OUT ON WRITE)

In a pure push model, every single post is pushed to all followers at write time:

• Consider a celebrity with 100,000,000 followers.
• When they post, the system must perform 100,000,000 writes.
• If a single write to Redis/Cassandra takes 1 millisecond, sequential execution takes 100,000 seconds (27 hours!).
• Even with 1,000 worker threads executing in parallel, pushing one post takes 100 seconds. During those 100 seconds, the message queues backlog, consuming gigabytes of buffer memory and delaying real-time posts from normal users.
• Furthermore, out of those 100 million followers, over 70% may not open the app today. Performing 70 million writes for users who never read them is massive operational waste.

THE FAILURE MODE OF PURE PULL (FAN-OUT ON READ)

In a pure pull model, no post is pushed to follower inboxes. When a user opens their app:

• The system looks up all accounts the user follows (e.g. 1,000 accounts).
• It queries the outboxes of all 1,000 accounts in parallel, retrieves their recent posts, and merges them.
• Scatter-Gather Latency Amplification: The overall read latency is bounded by the slowest of the 1,000 queries. If an individual query has a 99th percentile latency of 15ms, querying 1,000 shards simultaneously results in an effective p99 latency exceeding 2,500ms!
• The database is crushed by read traffic under peak morning usage hours.

THE STAFF HYBRID RESOLUTION: THE 25,000 FOLLOWER CUTOFF

By splitting users into two cohorts based on a follower threshold (K = 25,000):

1. Normal Accounts (< K followers): Represent 99.9% of users. Their posts are fanned out on write to in-memory Redis timelines. The maximum write amplification for any normal user is bounded at 25,000 writes - easily absorbed by worker pools in under 200ms.
2. Celebrity Accounts (>= K followers): Represent 0.1% of users, but account for 90% of write load. They write to an outbox once. At read time, the reader queries their normal timeline (1 Redis call) plus their followed celebrities (<= 50 parallel Redis calls).
3. The K-Way Merge: Merging 51 sorted streams in RAM requires maintaining a min-heap of size 51. Extracting the top 20 items takes 20 * log2(51) ~ 113 operations. This completes in less than 0.2 milliseconds on modern CPU cores!

Deep Dive 2: In-Memory Timeline Storage & Keyset Cursor Pagination

Storing and paginating timelines in high-throughput environments requires eliminating relational database queries entirely from the read path:

Figure 14.3: Redis Timeline Storage Layout & Keyset Cursor Pagination

THE MEMORY LAYOUT OF A REDIS TIMELINE

Each active user timeline is stored as a Redis Sorted Set (ZSET):

• Key: timeline:<user_id>
• Score: 64-bit millisecond timestamp (created_at)
• Member: 64-bit integer post_id

REDIS SORTED SET TIMELINE MEMORY BREAKDOWN

WHY OFFSET PAGINATION IS FATAL IN FEED DESIGN

Naive engineers paginate feeds using SQL OFFSET and LIMIT:

-- THE L5 PITFALL:
SELECT post_id FROM posts
WHERE author_id IN (SELECT followee_id FROM follows WHERE follower_id = 101)
ORDER BY created_at DESC
LIMIT 20 OFFSET 10000;

This fails for two fundamental reasons:

1. Performance Collapse: The database storage engine must scan, sort, and discard 10,000 rows on disk before returning 20 rows. Under high concurrency, this saturates IOPS and database buffer pools.
2. The Page-Drift Bug: If three new posts are published while the user is reading Page 1, all existing posts shift downward by 3 positions. When the user requests Page 2 with OFFSET 20, they see the last 3 posts from Page 1 a second time! If posts are deleted, items are skipped entirely.

THE STAFF STANDARD: KEYSET CURSOR PAGINATION

Staff engineers enforce Opaque Keyset Cursors. The client receives a cursor token encoding the last visible item's sort key:

cursor = base64_encode(timestamp:post_id)

When requesting the next page:

GET /v1/feed?cursor=MTcyNTM4MDQ1MjAwMDpwb3N0Xzg5NDkyMDE=&limit=20

The Redis query seeks directly to the cursor boundary in O(log N) time:

ZREVRANGEBYSCORE timeline:user_101 (1725380452000 -inf WITHSCORES LIMIT 0 20

• Execution Time: Constant 0.2 milliseconds.
• Page Drift: Zero. New posts inserted at the head of the timeline have higher timestamps and do not perturb the cursor slice.
• Tie-Breaking: If two posts share the exact same millisecond timestamp, the unique post_id acts as the deterministic secondary tie-breaker.

Deep Dive 3: The Two-Stage Feed Ranking Pipeline

In algorithmic feeds, reverse-chronological order is insufficient. However, evaluating a complex deep neural network over thousands of posts on every request would exceed the 120ms latency SLA.

Staff engineers decompose feed ranking into a pipelined two-stage funnel:

THE TWO-STAGE FEED RANKING FUNNEL

flowchart TD
    A["[ Candidate Sourcing ]<br/>Fetch 500 candidate post IDs from Redis Timeline + Celebrity Outboxes<br/>Latency Budget: 15ms"]
    B["[ Stage 1: Light Ranker (Scoring & Filtering) ]<br/>Heuristic filtering + Fast Gradient Boosted Decision Tree (GBDT)<br/>Features: Recency decay, author affinity score, content format match<br/>Output: Reduces 500 candidates down to top 100 posts<br/>Latency Budget: 15ms"]
    C["[ Stage 2: Heavy Ranker (Deep Inference) ]<br/>Multi-Task Neural Network (MTNN)<br/>Predicts: P(click), P(like), P(comment), P(share), P(dwell_time #gt; 10s)<br/>Final Score = w1*P(like) + w2*P(comment) + w3*P(share) - w4*P(report)<br/>Output: Top 20 ranked posts<br/>Latency Budget: 35ms (Hard Circuit Breaker Timeout)"]
    D["[ Stage 3: Diversity & Business Logic Injection ]<br/>Prevents 3 consecutive posts from the same author<br/>Injects sponsored ad slots (1 ad every 5 organic posts)<br/>Latency Budget: 5ms"]
    A --> B --> C --> D

THE CIRCUIT BREAKER DEGRADATION CONTRACT

What happens when the Heavy Ranker experiences GPU contention or garbage collection pauses?

• The Feed Gateway wraps the Heavy Ranker in a circuit breaker with a hard 40ms timeout.
• If the Heavy Ranker times out or error rate exceeds 2%, the system automatically degrades to the Light Ranker's output or directly to pure reverse-chronological order.
• The user receives their feed in 45ms. They never see a spinner or error screen. The business trade-off is explicit: we temporarily sacrifice engagement optimization to preserve system availability.

Deep Dive 4: The TAO Social Graph Architecture (Objects, Associations & Edge Sharding)

A core flaw of naive system design candidates is proposing a specialized graph database (like Neo4j) to store social connections at a scale of 500 million users. While native graph databases excel at multi-hop graph traversal (e.g., finding the shortest path between two distant users), feed generation requires only 1-hop directed edge queries:

1. Whom does User A follow? (To query celebrity outboxes at read time)
2. Who follows User B? (To fan out posts at write time)

At Big Tech scale, social graph storage is modeled after Meta's TAO (The Associations and Objects engine) - a geographically distributed data store built on top of horizontally sharded relational databases (MySQL/CockroachDB) fronted by a unified caching layer.

TAO GRAPH DATA MODEL: OBJECTS & ASSOCIATIONS

1. OBJECTS (Typed Nodes)
   • Schema: (id, otype, data)
   • Examples: (User_101, 'USER', {...}), (Post_9002, 'POST', {...})
2. ASSOCIATIONS (Typed Directed Edges with Time-Ordered Sort Keys)
   • Schema: (id1, atype, id2, time, data)
   • Examples: (User_101, 'FOLLOWS', User_202, 1725380400, '')
   • Inverse: (User_202, 'FOLLOWED_BY', User_101, 1725380400, '')

THE SHARDING STRATEGY FOR SOCIAL ASSOCIATIONS

In relational databases, storing billions of edges in a single table requires partitioning. The critical architectural decision is the sharding key:

• Sharded by id1 (Origin Node): All outgoing edges from an origin node reside on the exact same physical database shard!
• When User 101 requests their following list, the query executes as a single local index scan on Shard Hash(User_101) % N:

SELECT id2, time FROM associations
WHERE id1 = 101 AND atype = 'FOLLOWS'
ORDER BY time DESC LIMIT 500;

• Zero Cross-Shard Joins: Because all outgoing edges for id1 are co-located, fetching followees never requires cross-network scatter-gather queries across database shards.

THE TAO CACHING HIERARCHY: LEADERS AND FOLLOWERS

To achieve sub-5ms graph read latency, TAO deploys a two-tier caching architecture:

1. Follower Caches (Client-Facing Tier): Deployed across edge data centers worldwide. They serve read queries (assoc_get, assoc_range) directly from in-memory LRU buffers. Over 99.7% of social graph edge queries are absorbed by Follower caches without ever touching storage.
2. Leader Caches (Storage-Adjacent Tier): Co-located with the primary database shards. All graph mutations (following or unfollowing an account) are routed to the Leader cache, which writes synchronously to MySQL/CockroachDB and asynchronously invalidates stale Follower cache entries.
3. Read-Your-Writes Guarantee: When User A taps "Follow" on Creator B, the client establishes a sticky session to the local Follower cache, which immediately records an optimistic local edge so the UI updates instantly with zero perception of lag.

Deep Dive 5: Algorithmic Implementation of the K-Way Min-Heap Merge

When a user opens the mobile app, the Feed Serving Gateway must combine two distinct data sources into a single chronologically descending or score-ranked stream:

1. The user's precomputed push timeline inbox (from Redis).
2. The recent posts from all followed celebrities (pulled from celebrity outboxes).

If a user follows 40 celebrities, we have 41 independent sorted streams of posts. Merging these streams naively by concatenating all items and sorting them has a time complexity of O(M log M), where $M$ is the total number of candidate posts ($41 \times 20 = 820$ items).

Staff engineers execute an in-memory K-Way Min-Heap Merge, which extracts the top N = 20 posts in O(N log K) time:

import heapq

class StreamNode:
    def __init__(self, post, stream_idx, post_idx):
        self.post = post                # Dict: {post_id, timestamp, author_id}
        self.stream_idx = stream_idx    # Which celebrity or normal timeline
        self.post_idx = post_idx        # Index within that stream

    # Python heapq implements a Min-Heap.
    # For descending chronological order, we invert comparisons:
    def __lt__(self, other):
        if self.post["timestamp"] == other.post["timestamp"]:
            return self.post["post_id"] > other.post["post_id"]
        return self.post["timestamp"] > other.post["timestamp"]

def k_way_heap_merge(streams, target_limit=20):
    """
    streams: List of sorted post lists, e.g.
    streams[0] = normal_push_inbox (top 50 posts)
    streams[1..K] = celebrity_outboxes (top 20 posts each)
    """
    min_heap = []

    # 1. Initialize heap with the 0-th element of each non-empty stream
    for s_idx, stream in enumerate(streams):
        if stream:
            heapq.heappush(min_heap, StreamNode(stream[0], s_idx, 0))

    merged_results = []

    # 2. Extract the globally latest post and advance that specific stream
    while min_heap and len(merged_results) < target_limit:
        top_node = heapq.heappop(min_heap)
        merged_results.append(top_node.post)

        # Advance to the next element in the winning stream
        next_post_idx = top_node.post_idx + 1
        winning_stream = streams[top_node.stream_idx]

        if next_post_idx < len(winning_stream):
            next_node = StreamNode(winning_stream[next_post_idx],
                                   top_node.stream_idx,
                                   next_post_idx)
            heapq.heappush(min_heap, next_node)

    return merged_results

MATHEMATICAL COMPLEXITY & PERFORMANCE PROFILE:

• Heap Size (K): At most 50 elements (1 normal inbox + up to 49 followed celebrities).
• Time Complexity: Initializing the heap takes O(K) time. Extracting the top 20 posts requires 20 extraction and insertion steps, taking $20 \times \log_2(50) \approx 20 \times 5.64 \approx 113$ comparison operations.
• CPU Execution Time: On modern multi-core server hardware, 113 CPU operations execute in approximately 0.08 milliseconds (80 microseconds).
• Memory Footprint: The heap holds references to 50 lightweight pointers in user space, consuming less than 4 Kilobytes of RAM per request.

The Staff Advantage: The K-Way Heap stops execution the exact moment 20 items are assembled. It never evaluates or sorts the remaining 800 items in the candidate streams, keeping tail latency strictly bounded.

5. Data Models, Storage Engines & Schemas

Relational Storage: Posts & Authors (CockroachDB / Sharded PostgreSQL)

-- Posts Table: Sharded by author_id to keep creator queries local to one shard
CREATE TABLE posts (
    post_id BIGINT NOT NULL,
    author_id BIGINT NOT NULL,
    media_url VARCHAR(512) NOT NULL,
    media_type VARCHAR(16) NOT NULL,       -- 'IMAGE', 'VIDEO'
    caption TEXT,
    created_at TIMESTAMPTZ NOT NULL,
    like_count INT DEFAULT 0,
    comment_count INT DEFAULT 0,
    status VARCHAR(16) DEFAULT 'PUBLISHED',
    PRIMARY KEY (author_id, post_id)
);

-- Index for cold historical pagination beyond the 800-item Redis window
CREATE INDEX idx_author_created ON posts (author_id, created_at DESC);

Social Graph Storage: TAO-Style Associations

Rather than querying a monolithic relational table with billions of rows, the social graph is structured as directed edges in an adjacency store:

-- Follows Table: Sharded by follower_id for fast outgoing edge traversal
CREATE TABLE user_follows (
    follower_id BIGINT NOT NULL,
    followee_id BIGINT NOT NULL,
    created_at TIMESTAMPTZ NOT NULL,
    is_active BOOLEAN DEFAULT TRUE,
    PRIMARY KEY (follower_id, followee_id)
);

-- Inverted Follower Count Table: Maintained via atomic counter in Redis / DB
CREATE TABLE user_stats (
    user_id BIGINT PRIMARY KEY,
    follower_count INT NOT NULL DEFAULT 0,
    following_count INT NOT NULL DEFAULT 0,
    is_celebrity BOOLEAN GENERATED ALWAYS AS (follower_count >= 25000) STORED
);