Social Feed & Activity Stream Architecture: Fan-Out, Caching, and Cursor Pagination

1. The Core Engineering Challenge: Read vs. Write Asymmetry

In traditional enterprise applications, database operations follow symmetric access patterns or read-heavy ratios ($10:1$). In consumer social media platforms (such as X/Twitter, Instagram, LinkedIn, or Facebook), systems must resolve an extreme form of graph-induced asymmetry:

1. Power-Law Social Graph Distribution: The social graph is heavily skewed. The median user has $\approx 200$ followers. However, a small fraction of accounts (celebrities, politicians, global brands) possess over $50,000,000$ followers (extreme in-degree).
2. Sub-100ms Read Latency Requirement: When a user launches the app or scrolls down their home timeline, the system must assemble, rank, hydrate, and return the latest $20$ posts in less than $80\text{ milliseconds}$.
3. Continuous Chronological Ingestion: Hundreds of thousands of posts, likes, and retweets enter the system every second.
4. Infinite Scroll Dynamics: As users scroll down their feed, the system must deliver seamless pagination without repeating items or skipping posts when real-time content inserts at the top of the feed.

+-------------------------------------------------------------------------------+
|                       THE DUAL FEED ARCHITECTURE PARADIGM                     |
+-------------------------------------------------------------------------------+
| Paradigm               | Fan-Out on Write (Push)     | Fan-Out on Read (Pull) |
+------------------------+-----------------------------+------------------------+
| Work Done At           | Post creation time          | Home timeline fetch    |
| Read Complexity        | O(1) - Fast cache lookup    | O(N log K) - Expensive |
| Write Complexity       | O(F) - F writes per post    | O(1) - Single DB write |
| Celebrity Impact       | Catastrophic write storm    | Zero write impact      |
| Inactive User Impact   | Massive wasted cache writes | Zero wasted computation|
| Ideal For              | Normal graph (F < 25,000)   | Celebrities (F > 25,000|
+-------------------------------------------------------------------------------+

2. Mental Model & Design Alternatives: Fan-Out on Write vs. Fan-Out on Read

SYSTEM ARCHITECTURE BLUEPRINTAPPLICATION ARCHITECTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Regular User (Alice) & Celebrity User (Taylor)

Establishes the ingress and structural boundary across Regular User (Alice) & Celebrity User (Taylor): Followers count: 250 (Normal Node); POST /posts { body: "Hello World" }; Followers count: 50,000,000 (Super-Node).

Architectural Invariant: Kafka: post_events topic.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Graph Relationship DB & Follower Threshold Heuristic

Coordinates core data-plane execution and state transitions through Graph Relationship DB & Follower Threshold Heuristic: Followers / Following edges Social Graph Key-Value Index: followers:alice -> [user_1, user_2...] following:bob -> [alice, taylor...]; Is author's followers > 25,000? IF followers <= 25,000; > Push model (Fan-Out on Write) IF followers > 25,000.

Architectural Invariant: ZADD timeline:bob 1730001042 "p_91" Holds recent 800 post IDs per active user Instant O(log N) range queries.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. User Bob Opens App & In-Memory K-Way Merge

Enforces durability, state convergence, and output verification across User Bob Opens App & In-Memory K-Way Merge: GET /feed?cursor=1730001000&limit=20 Cursor-based infinite scroll Zero page drift or missing items; 1. Fetch Bob's ZSET timeline (20 IDs); 2. Query followed celebs list: [Taylor].

Architectural Invariant: Latency: < 8 ms in Go/Rust.

Model 1: Fan-Out on Write (Push / Pre-Computed Feed)

In a pure push model:

1. User Alice posts a photo.
2. The ingestion service looks up Alice’s followers in the social graph.
3. A background worker cluster pushes Alice’s post_id into the pre-computed timeline cache of every single follower.
4. When Alice’s follower Bob opens his app:
   • The server queries timeline:bob from an in-memory cache (Redis).
   • It retrieves the top 20 post_id values instantly in $\mathcal{O}(1)$ time.
   • It hydrates post content and returns the feed.

Why Pure Push Fails: If Taylor Swift ($100\text{M}$ followers) posts, the worker cluster must execute $100,000,000$ cache writes. This write storm saturates message queues, causes multi-minute delivery lag, and writes data into millions of dormant accounts that will never log in to read it.

Model 2: Fan-Out on Read (Pull / On-Demand Feed)

In a pure pull model:

1. User Alice posts a photo.
2. The server writes Alice’s post once to her personal timeline table. No fan-out occurs.
3. When Bob opens his app:
   • The server looks up all $1,000$ accounts Bob follows.
   • It fetches the recent posts for all $1,000$ accounts from storage.
   • It merges, sorts, and ranks all fetched posts chronologically on-the-fly.

Why Pure Pull Fails: Pull eliminates write amplification. However, reading a home feed requires querying hundreds of database partitions and merging tens of thousands of candidate rows on every single page load. Under $500,000\text{ read queries/second}$, the database layer collapses under catastrophic read I/O exhaustion.

3. Mathematical Model: Workload Sizing & The Celebrity Multiplier

To design an optimal hybrid architecture, we quantify the storage and network throughput bounds.

Global Scale Assumptions

• Daily Active Users (DAU): $300,000,000$ users.
• Average Posts per User per Day: $2$ posts/day.
• Average Feed Reads per User per Day: $15$ timeline requests/day.
• Average Followers per User ($\bar{F}$): $250$ followers.
• Celebrity Accounts ($>1\text{M}$ followers): $10,000$ accounts.

Write vs. Read QPS Derivation

Write Amplification under Pure Push

If all posts are fanned out on write across an average follower count $\bar{F}=250$:

Now consider a celebrity with $50,000,000$ followers posting during peak traffic:

If the fan-out worker fleet can process $250,000\text{ writes/second}$, a single celebrity post monopolizes the entire cluster’s queue capacity for 200 seconds (over 3.3 minutes!), stalling all regular users’ updates.

Deriving the Hybrid Celebrity Crossover Threshold ($F^{\ast }$)

We choose the push-vs.-pull crossover threshold $F^{\ast }$ using two complementary constraints:

1. Fan-Out Queue Latency Bound: To guarantee that no single post occupies a shard’s fan-out worker pool (${\mu }_{\text{shard}}=250,000\text{ writes/sec}$) for longer than $\Delta T_{\max }=100\text{ ms}$ ($0.1\text{ s}$): $$F^{\ast }\le {\mu }_{\text{shard}}\cdot \Delta T_{\max }=250,000\times 0.1=25,000\text{ active followers}$$
2. I/O Cost Crossover: Suppose an author publishes $r_w$ posts/day and only fraction $\alpha \in (0,1]$ of their $F$ followers actively read $r_r$ feeds/day, with cache write cost $c_w$ and replicated in-memory celebrity list read cost $c_r$. Pushing costs $C_{\text{push}}=r_w\cdot \alpha F\cdot c_w$ mutations/day (plus burst queue delay), whereas pulling from a replicated celebrity key costs $C_{\text{pull}}=r_r\cdot \alpha F\cdot c_r$ reads/day with zero write-queue contention. Whenever a prolific account posts frequently ($r_w\cdot c_w>r_r\cdot c_r$) or exceeds the $100\text{ ms}$ burst budget ($F>25,000$), switching to pull strictly dominates.

Timeline Cache Memory Sizing (Redis)

To ensure instant reads, each active user’s timeline in Redis holds the most recent $800\text{ post IDs}$.

A single timeline entry in a Redis Sorted Set (ZSET) consists of:

• Member: 64-bit integer post_id ($8\text{ bytes}$).
• Score: 64-bit float/epoch timestamp ($8\text{ bytes}$).
• Skip-List & Dict Overhead: Internal Redis skiplist + hashtable node pointer overhead ($\approx 48\text{ bytes}$).

For $300,000,000$ active users:

With $64\text{ GB}$ (decimal) Redis instances configured with $25\%$ headroom for jemalloc allocator fragmentation, copy-on-write snapshot buffers, and OS kernel memory ($48\text{ GB}$ usable per shard):

4. The Hybrid Fan-Out Architecture

To achieve the sub-50ms read latency of the push model while eliminating the catastrophic write storms of the pull model, industry-standard social platforms (X/Twitter, Instagram) deploy a Hybrid Fan-Out Architecture:

The Hybrid Threshold Heuristic:
---------------------------------------------------------------------------------
                     Author publishes new Post
                                |
               Check Author Follower Count (F)
                                |
                +---------------+---------------+
                |                               |
        F <= 25,000 (99.9% of users)     F > 25,000 (Celebrity)
                |                               |
                v                               v
    FAN-OUT ON WRITE (PUSH)             FAN-OUT ON READ (PULL)
    Worker pushes post_id into          Worker writes post_id ONCE
    all F followers' Redis              into Author's Recent Post List
    Timeline Sorted Sets.               (celeb:author_id:posts)
                |                               |
                +---------------+---------------+
                                |
                                v
               When Follower reads Timeline:
               1. Fetch pre-computed Timeline ZSET.
               2. Fetch recent posts from followed Celebrities.
               3. In-memory K-way merge sort.

1. Ingestion & Sharding Rule

• When an account publishes a post, the Ingestion Service writes the post entity to a distributed database (e.g. ScyllaDB or PostgreSQL partitioned by post_id).
• It emits a PostCreatedEvent(post_id, author_id, timestamp) to a partitioned Kafka topic.

2. The Worker Branching Logic

• A fleet of asynchronous Fan-Out Workers consumes the event.
• It queries the Social Graph Service for followers_count.
• Case 1: Regular User ($F\le 25,000$):
  • The worker retrieves the follower IDs.
  • It filters out dormant/inactive accounts (accounts that have not logged in within 14 days).
  • It pipelines batch ZADD commands to Redis:

    ZADD timeline:<follower_id> <timestamp> <post_id>
    ZREMRANGEBYRANK timeline:<follower_id> 0 -801  -- Cap timeline to latest 800 items

• Case 2: Celebrity Super-Node ($F>25,000$):
  • The worker completely skips fan-out to followers.
  • It appends the post_id strictly to the celebrity’s personal post list:

    LPUSH celeb:<author_id>:posts <post_id>
    LTRIM celeb:<author_id>:posts 0 99            -- Retain recent 100 posts

5. In-Memory K-Way Merge & Timeline Construction

When follower Bob requests his home timeline (GET /api/v1/feed), the Timeline Service executes a low-latency In-Memory K-Way Merge Sort:

K-Way Merge Assembly on Read:
---------------------------------------------------------------------------------
Step 1: Fetch Bob's pre-computed timeline from Redis (Top 20 items):
Cached Stream:    [P_102 (12:05), P_101 (12:02), P_98 (11:50), P_95 (11:40)]

Step 2: Query Social Graph for followed celebrities:
Bob follows: [Taylor_Swift, Elon_Musk]

Step 3: Fetch latest post IDs for followed celebrities from Redis:
Taylor Stream:    [P_205 (12:08), P_199 (11:55)]
Elon Stream:      [P_301 (12:04), P_290 (11:45)]

Step 4: Min-Heap / Max-Heap K-Way Merge:
Pointers iterate through sorted streams in descending chronological order:
1. P_205 (12:08 - Taylor)
2. P_102 (12:05 - Alice)
3. P_301 (12:04 - Elon)
4. P_101 (12:02 - Bob's friend Charlie)
5. P_199 (11:55 - Taylor)

Result: Exactly the top 20 globally ordered posts in < 12 milliseconds!

Algorithmic Complexity

If a user follows $C$ celebrities, and the target page size is $K=20$:

• Extracting the top element from $C+1$ streams using a binary heap requires $\mathcal{O}(\log C)$ time.
• Assembling a full page of $K$ items requires:

Even if an avid user follows $C=200$ celebrities:

$153$ comparisons execute in less than $0.2\text{ milliseconds}$ in Go, Rust, or C++, ensuring that the merge step adds near-zero latency to the user request.

6. Entity Hydration & Multi-Tier Caching

Timelines in Redis store only 64-bit integer pointers (post_id), never full JSON objects:

• Why? Storing full post bodies in millions of user timelines multiplies storage by $500\times$, rendering in-memory caching economically impossible. Furthermore, if an author edits or deletes a post, updating millions of pre-rendered JSON payloads across Redis is impossible.

The Hydration Pipeline

Once the top 20 post_id values are selected by the K-way merge:

1. The Timeline Service issues a single parallel batch MGET to a dedicated Post Cache Cluster (Memcached / Redis):

   MGET post:205 post:102 post:301 post:101 ...

2. Any cache misses are fetched from the primary database (ScyllaDB / PostgreSQL) and backfilled into the cache.
3. The service fetches author profile snippets (avatar URL, display name, verification badge) from a User Profile Cache.
4. It combines the components into an aggregated JSON response payload.
5. Overall read SLA: $p95<35\text{ ms},p99<60\text{ ms}$.

7. Infinite Scroll & Cursor-Based Pagination

A fundamental failure mode in high-concurrency feeds is using traditional relational database offset pagination:

-- DANGEROUS: Do NOT use in production feeds!
SELECT * FROM posts WHERE author_id IN (...) 
ORDER BY created_at DESC 
LIMIT 20 OFFSET 40;

The Pitfalls of Offset Pagination

1. Page Drift & Duplicates: Suppose Bob is reading Page 1 ($20$ posts). While he reads, friends publish $5$ new posts. Bob clicks “Next Page” (OFFSET 20). Because 5 new items were inserted at the top of the table, all historical items shifted down by 5 rows. The database returns rows $21-40$, which includes 5 duplicate posts Bob already read on Page 1!
2. Missing Items: If posts are deleted, items are silently skipped.
3. $\mathcal{O}(N)$ Database Performance Penalty: An offset query of OFFSET 50000 forces the database storage engine to scan and discard 50,000 rows from disk before returning the target 20 rows.

The Cursor Pagination Solution

Feeds must use Deterministic Cursor Pagination:

• The client passes an opaque token representing the exact position of the last post observed:

Cursor-Based Range Query:
---------------------------------------------------------------------------------
Client Request:
GET /api/v1/feed?cursor=eyJ0IjoxNzMwMDAxMDIwLCJpZCI6MTAxfQ==&limit=20
(Decodes to: timestamp = 1730001020, post_id = 101)

Redis Sorted Set Query:
ZREVRANGEBYSCORE timeline:bob (1730001020 -inf LIMIT 0 20

Database Fallback Query:
SELECT * FROM posts 
WHERE (created_at, post_id) < (:last_timestamp, :last_post_id)
ORDER BY created_at DESC, post_id DESC 
LIMIT 20;

Why Compound Key (created_at, post_id)?

Physical timestamps can collide when multiple posts are created within the same millisecond. Using the compound tuple (created_at, post_id) creates a strictly deterministic, total order across all items, guaranteeing that no item is ever repeated or skipped, regardless of how many new posts are published in real time.

8. Active vs. Inactive User Lifecycle

Pre-computing timelines for all $1,000,000,000$ registered accounts would require hundreds of terabytes of wasted RAM. Over $60\%$ of registered users on major social platforms do not open the app on any given day.

The TTL Lease & Eviction Policy

1. Active Timeline TTL: Every timeline key in Redis is assigned an expiration Time-To-Live (e.g. EX 604800 = 7 days).
2. Lease Extension: Whenever a user opens the app or receives a push notification, the TTL is reset to 7 days.
3. Automatic Dormancy Eviction: If a user does not log in for 7 days, Redis automatically evicts their timeline key via its standard LRU policy. Zero RAM is wasted on dormant accounts.

The Cold-Start Reconstruction Pipeline

When a dormant user logs in after 6 months:

1. The Timeline Service queries Redis for timeline:user_id. Cache returns nil.
2. A Cold-Start Generator executes a synchronous fallback query:
   • Fetches the accounts the user follows from the Social Graph.
   • Queries the primary Post DB for the most recent $50$ posts created by those accounts within the last 7 days.
   • Populates the user’s Redis ZSET cache.
3. Future requests hit the warm in-memory cache instantly.

9. Operational Failure Modes & Production Troubleshooting

+-------------------------------------------------------------------------------+
|                      COMMON FEED INFRASTRUCTURE FAILURES                      |
+-------------------------------------------------------------------------------+
| Symptom                  | Root Cause               | Mitigation Strategy     |
+--------------------------+--------------------------+-------------------------+
| 1. Redis Cluster OOM     | Sudden surge of active   | Cap all timelines at    |
|    Crashes               | users without strict     | ZREMRANGEBYRANK 800;    |
|                          | timeline length limits   | decrease TTL to 3 days  |
|                          |                          |                         |
| 2. Celebrity Cache       | Millions of followers    | Single-Flight / Coalesce|
|    Stampede (Thundering  | requesting celebrity post| reads (e.g. Go single-  |
|    Herd)                 | on cache miss            | flight); probabilistic  |
|                          |                          | early expiration (XFetch|
|                          |                          |                         |
| 3. Breaking News Queue   | Global breaking news     | Dynamic worker priority |
|    Backlog               | triggers 500x write burst| queues; shed fan-out for|
|                          | across fan-out workers   | non-active users        |
|                          |                          |                         |
| 4. Cross-Shard Read      | Hot celebrity key        | Replicate celebrity post|
|    Imbalance in Redis    | pinned to a single Redis | lists across multiple   |
|                          | master shard             | read-replica nodes      |
+-------------------------------------------------------------------------------+

Deep Dive: Celebrity Cache Stampede Mitigation

When an influential account posts breaking news, hundreds of thousands of users refresh their feeds within seconds. If the celebrity’s recent post cache key expires or suffers a cache miss:

1. $50,000$ concurrent requests simultaneously detect a cache miss.
2. All $50,000$ requests execute identical queries against the primary database.
3. The database CPU reaches $100\%$, connection pools exhaust, and the application crashes (Cache Stampede).

Remediation: Request Coalescing (Single-Flight Pattern): Implement an in-memory lock or single-flight coordinator (e.g. golang.org/x/sync/singleflight):

• If 10,000 concurrent threads request celeb:taylor:posts, the application initiates exactly one database query.
• The other 9,999 requests subscribe to the pending promise and receive the same fetched result once it arrives, protecting the database tier completely.

10. Concrete Implementation: Hybrid Feed Engine

The following complete, runnable TypeScript implementation demonstrates the core mechanics of a Hybrid Fan-Out Feed Engine: fan-out on write for regular users, celebrity push bypass, in-memory K-way priority queue merge, and cursor-based pagination.

// hybrid-feed-engine.ts
export interface Post {
  id: string;
  authorId: string;
  content: string;
  createdAt: number;
}

export interface FeedCursor {
  timestamp: number;
  id: string;
}

export interface CursorPaginationResult {
  posts: Post[];
  nextCursor: string | null;
}

const BASE64_ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

function encodeCursorBase64(cursor: FeedCursor): string {
  const bytes = new TextEncoder().encode(JSON.stringify(cursor));
  let out = '';
  for (let i = 0; i < bytes.length; i += 3) {
    const b0 = bytes[i];
    const b1 = i + 1 < bytes.length ? bytes[i + 1] : 0;
    const b2 = i + 2 < bytes.length ? bytes[i + 2] : 0;
    const triple = (b0 << 16) | (b1 << 8) | b2;
    out += BASE64_ALPHABET[(triple >> 18) & 0x3f];
    out += BASE64_ALPHABET[(triple >> 12) & 0x3f];
    out += i + 1 < bytes.length ? BASE64_ALPHABET[(triple >> 6) & 0x3f] : '=';
    out += i + 2 < bytes.length ? BASE64_ALPHABET[triple & 0x3f] : '=';
  }
  return out;
}

function decodeCursorBase64(token: string): FeedCursor {
  const clean = token.replace(/=+$/, '');
  const bytes: number[] = [];
  for (let i = 0; i < clean.length; i += 4) {
    const c0 = BASE64_ALPHABET.indexOf(clean[i]);
    const c1 = BASE64_ALPHABET.indexOf(clean[i + 1]);
    const c2 = i + 2 < clean.length ? BASE64_ALPHABET.indexOf(clean[i + 2]) : 0;
    const c3 = i + 3 < clean.length ? BASE64_ALPHABET.indexOf(clean[i + 3]) : 0;
    if (c0 < 0 || c1 < 0 || c2 < 0 || c3 < 0) {
      throw new Error('Malformed Base64 cursor');
    }
    const triple = (c0 << 18) | (c1 << 12) | (c2 << 6) | c3;
    bytes.push((triple >> 16) & 0xff);
    if (i + 2 < clean.length) bytes.push((triple >> 8) & 0xff);
    if (i + 3 < clean.length) bytes.push(triple & 0xff);
  }
  return JSON.parse(new TextDecoder().decode(new Uint8Array(bytes))) as FeedCursor;
}

/**
 * Total-order comparator: descending by (createdAt, id)
 * Returns true if candidate comes strictly after (is older than) the cursor boundary.
 */
function isStrictlyOlderThanCursor(post: Post, cursor: FeedCursor | null): boolean {
  if (!cursor) return true;
  if (post.createdAt !== cursor.timestamp) {
    return post.createdAt < cursor.timestamp;
  }
  return post.id < cursor.id;
}

function isNewerPost(a: Post, b: Post): boolean {
  if (a.createdAt !== b.createdAt) {
    return a.createdAt > b.createdAt;
  }
  return a.id > b.id;
}

/**
 * Compound-cursor K-Way Merge implementation for descending chronological timeline streams
 */
export class KWayTimelineMerger {
  public static merge(streams: Post[][], pageSize: number, cursor: FeedCursor | null = null): Post[] {
    const indices = new Array<number>(streams.length).fill(0);
    const result: Post[] = [];

    while (result.length < pageSize) {
      let newestPost: Post | null = null;
      let newestStreamIdx = -1;

      for (let i = 0; i < streams.length; i++) {
        const stream = streams[i];
        let idx = indices[i];

        while (idx < stream.length && !isStrictlyOlderThanCursor(stream[idx], cursor)) {
          idx++;
          indices[i] = idx;
        }

        if (idx < stream.length) {
          const candidate = stream[idx];
          if (!newestPost || isNewerPost(candidate, newestPost)) {
            newestPost = candidate;
            newestStreamIdx = i;
          }
        }
      }

      if (newestStreamIdx === -1 || !newestPost) {
        break;
      }

      result.push(newestPost);
      indices[newestStreamIdx]++;
    }

    return result;
  }
}

/**
 * Hybrid Fan-Out Social Feed Manager
 */
export class HybridFeedEngine {
  public static readonly CELEBRITY_THRESHOLD = 25000;

  private postsDb = new Map<string, Post>();
  private socialGraph = new Map<string, string[]>(); // authorId -> followerIds
  private followerCounts = new Map<string, number>(); // supports simulated high-fanout celebrities
  private userTimelines = new Map<string, Post[]>(); // userId -> cached timeline
  private celebrityPosts = new Map<string, Post[]>(); // celebId -> post list
  private seqCounter = 0;

  public registerFollower(authorId: string, followerId: string): void {
    const list = this.socialGraph.get(authorId) || [];
    list.push(followerId);
    this.socialGraph.set(authorId, list);
    this.followerCounts.set(authorId, Math.max(list.length, this.followerCounts.get(authorId) ?? 0));
  }

  public setSimulatedFollowerCount(authorId: string, count: number): void {
    this.followerCounts.set(authorId, count);
  }

  public publishPost(authorId: string, content: string, timestampMs = Date.now()): Post {
    this.seqCounter += 1;
    const post: Post = {
      id: `p_${String(this.seqCounter).padStart(6, '0')}`,
      authorId,
      content,
      createdAt: timestampMs,
    };

    this.postsDb.set(post.id, post);
    const followers = this.socialGraph.get(authorId) || [];
    const totalFollowers = Math.max(followers.length, this.followerCounts.get(authorId) ?? 0);

    if (totalFollowers > HybridFeedEngine.CELEBRITY_THRESHOLD) {
      // CELEBRITY PATH: Write once to celebrity's personal post stream
      const celebList = this.celebrityPosts.get(authorId) || [];
      celebList.unshift(post);
      this.celebrityPosts.set(authorId, celebList.slice(0, 100));
    } else {
      // REGULAR PATH: Fan-out on write to active followers' timelines
      for (const followerId of followers) {
        const timeline = this.userTimelines.get(followerId) || [];
        timeline.unshift(post);
        this.userTimelines.set(followerId, timeline.slice(0, 800));
      }
    }

    return post;
  }

  public getHomeFeed(
    userId: string,
    followedCelebrityIds: string[],
    limit = 20,
    cursorToken?: string
  ): CursorPaginationResult {
    let parsedCursor: FeedCursor | null = null;

    if (cursorToken) {
      try {
        parsedCursor = decodeCursorBase64(cursorToken);
      } catch {
        parsedCursor = null;
      }
    }

    const streamsToMerge: Post[][] = [];
    streamsToMerge.push(this.userTimelines.get(userId) || []);

    for (const celebId of followedCelebrityIds) {
      streamsToMerge.push(this.celebrityPosts.get(celebId) || []);
    }

    const pagePosts = KWayTimelineMerger.merge(streamsToMerge, limit, parsedCursor);

    let nextCursor: string | null = null;
    if (pagePosts.length === limit) {
      const lastItem = pagePosts[pagePosts.length - 1];
      nextCursor = encodeCursorBase64({ timestamp: lastItem.createdAt, id: lastItem.id });
    }

    return {
      posts: pagePosts,
      nextCursor,
    };
  }
}

function runDemo(): void {
  console.log('=== Social Feed Engine: Hybrid Fan-Out & K-Way Timeline Merge ===');
  const engine = new HybridFeedEngine();
  engine.registerFollower('alice', 'bob');
  engine.registerFollower('charlie', 'bob');
  engine.setSimulatedFollowerCount('taylor_celeb', 50_000_000);

  const baseTs = 1_762_000_000_000;
  engine.publishPost('alice', 'Hello distributed systems world!', baseTs + 10);
  engine.publishPost('charlie', 'Same-millisecond tie-breaking via compound cursor!', baseTs + 20);
  engine.publishPost('taylor_celeb', 'Breaking announcement to 50M followers (pull path)!', baseTs + 20);

  const page1 = engine.getHomeFeed('bob', ['taylor_celeb'], 2);
  console.log(`Page 1 (${page1.posts.length} posts, nextCursor=${page1.nextCursor !== null}):`);
  for (const p of page1.posts) console.log(`  [${p.id} @ ${p.authorId}]: ${p.content}`);

  const page2 = engine.getHomeFeed('bob', ['taylor_celeb'], 2, page1.nextCursor ?? undefined);
  console.log(`Page 2 (${page2.posts.length} posts, nextCursor=${page2.nextCursor !== null}):`);
  for (const p of page2.posts) console.log(`  [${p.id} @ ${p.authorId}]: ${p.content}`);
}
runDemo();

11. Exercises with Observable Deliverables

Exercise 1: Calculate Redis Cluster Capacity for Peak News Events

Scenario: You are architecting the timeline cache for a social platform with $200,000,000$ active daily users.

1. If the average user timeline maintains $600$ post references ($64\text{ bytes}$ per entry), calculate the total in-memory RAM required to hold all user timelines.
2. During the World Cup final, $500$ celebrities ($10\text{M}$ followers each) post concurrently within a $10\text{-minute}$ window. Calculate the total number of cache write operations generated under:
   • A pure Fan-Out on Write model.
   • A Hybrid Fan-Out model where accounts with $>25,000$ followers use pull fan-out.
3. Quantify the percentage reduction in write operations achieved by the hybrid model.

Exercise 2: Implement and Verify Cursor Pagination

Deliverable: Using HybridFeedEngine:

1. Register author Alice (regular user) and Taylor (celebrity with $30,000$ followers).
2. Register Bob as a follower of both Alice and Taylor.
3. Publish 15 posts from Alice and 15 posts from Taylor with sequential timestamps.
4. Execute getHomeFeed(userId="bob", followedCelebrityIds=["taylor"], limit=10). Verify that Page 1 returns the newest 10 posts in strict chronological order.
5. Use each returned nextCursor to fetch Pages 2 and 3 (limit=10 per request). Verify that Pages 2 and 3 return the remaining 20 posts (10 items each) with zero duplicate post IDs and zero skipped posts, even when multiple posts share the exact same millisecond timestamp.

12. Summary & The Social Systems Architect’s Rules of Thumb

+-------------------------------------------------------------------------------+
|                    THE SOCIAL FEED ARCHITECT'S DECISION GUIDE                 |
+-------------------------------------------------------------------------------+
| Problem Dimension         | Battle-Tested Architectural Pattern               |
+---------------------------+---------------------------------------------------+
| Normal Users (F <= 25k)   | Fan-Out on Write (Push) into Redis ZSET timelines |
| Celebrities (F > 25k)     | Fan-Out on Read (Pull) from celebrity post list   |
| Read Assembly             | In-memory K-Way Merge sort (O(K log C) via Heap)  |
| Data Representation       | Store only 64-bit post_ids in cache; hydrate async|
| Pagination Method         | Deterministic Cursor (timestamp + post_id)        |
| Dormant User Management   | 7-day TTL on timeline keys; cold-start on demand  |
| Cache Stampede Defense    | Single-Flight / Request coalescing on celeb reads |
+-------------------------------------------------------------------------------+

1. Never Store Full Post Payloads in Timelines: Cache only 64-bit ID pointers in Redis Sorted Sets. Hydrate post content, avatars, and engagement counts via batch MGET queries to avoid $500\times$ cache inflation.
2. Never Use SQL Offset Pagination: Offset pagination produces duplicate items and page drift when new posts insert at the top of the feed. Always use deterministic cursor pagination based on compound keys (created_at, post_id).
3. Cap Timeline Length Strictly: Users rarely scroll past 500 items. Cap Redis Sorted Sets at 800 items using ZREMRANGEBYRANK on every push to prevent unbounded memory growth.
4. Isolate Celebrities from Message Queues: A single account with 50M followers will choke async worker queues for minutes. Divert celebrity posts to dedicated personal streams and resolve them on the read path.

13. Authoritative References & Version Context

• Adam Silberstein et al. (Yahoo! Research, ACM SIGMOD 2010): Feeding Frenzy: Selectively Materializing Users’ Event Feeds (formal mathematical cost optimization of push vs. pull selective feed materialization).
• Nathan Bronson et al. (Meta / USENIX ATC ‘13): TAO: Facebook’s Distributed Data Store for the Social Graph (two-tier social graph caching, association lists, and high-fanout read scaling).
• Redis Official Documentation — Sorted Sets (ZSET): Redis Sorted Sets Data Type & Time Complexity (ZADD, ZREVRANGEBYSCORE, and ZREMRANGEBYRANK skiplist internals; baseline Redis 7.2+).
• IETF RFC 4648 — The Base16, Base32, and Base64 Data Encodings: RFC 4648 (opaque cursor token serialization; storage stack context: Apache Kafka 3.7+, ScyllaDB 6.x, Memcached 1.6+).