05. Twitter/X Hybrid Fanout Feed EngineCopy Anchor Link

Production Paradigm: Asymmetric Push-Write for Normal Users + Pull-Read for Celebrities + O(N log K) Binary Max-Heap Keyset Cursor Merger + Valkey Capped Timeline Mixer.

💥 The Real-World BottleneckCopy Anchor Link

Timeline feeds (Twitter/X, Facebook News Feed, Threads) represent one of the most notorious challenges in distributed systems:

1. The Celebrity Write Explosion (Push Breakdown):
   • When a celebrity with 30,000,000 followers posts a tweet, pushing that tweet into 30 million user timeline inboxes requires 30 million Redis writes and database transactions. The system stalls for minutes.
2. The Follower Read Explosion (Pull Breakdown):
   • If a normal user follows 2,000 accounts and you pull tweets on every feed refresh (WHERE author_id IN (...) ORDER BY created_at DESC LIMIT 20), the relational query must scan, filter, and sort across millions of rows, blowing up database IOPS and memory.

🏛️ High-Concurrency ArchitectureCopy Anchor Link

This blueprint implements the Twitter/X Hybrid Fanout Architecture (proven in GonnaCrash Level 22 fanout_feed):

Key Architectural PhasesCopy Anchor Link

1. Follower Threshold Branching (Celebrity Cutoff = 25,000):
   • Authors with < 25,000 followers fan out asynchronously on write into each follower's Valkey timeline inbox.
   • Authors with >= 25,000 followers skip fanout entirely and write only to their own single outbox list.
2. Capped Sorted Set Inboxes:
   • Follower timelines are capped at 800 items using atomic Redis Lua scripts (LUA_ZADD_CAPPED_TIMELINE). Older items are pruned automatically, keeping RAM usage deterministic.
3. $O(N \log K)$ Binary Max-Heap Cursor Merger:
   • When a user requests their feed, the engine fetches the user's pre-computed timeline plus the outboxes of any followed celebrities.
   • A specialized binary max-heap merges these $K$ streams sorted by createdAtMs DESC, id DESC in $O(N \log K)$ time.
4. Strict Keyset Cursor Pagination:
   • Uses Base64URL-encoded deterministic cursors (createdAtMs + id), eliminating offset pagination drift when new tweets are posted.

🧩 Composed Functional SlicesCopy Anchor Link

💻 Code ImplementationCopy Anchor Link

mkdir -p src/lib/feed
cp packages/hybrid-feed/src/hybrid-fanout-engine.ts src/lib/feed/
cp packages/hybrid-feed/src/k-way-cursor-merger.ts src/lib/feed/
cp packages/hybrid-feed/src/valkey-timeline-mixer.ts src/lib/feed/

import { HybridFanoutEngine } from '@/lib/feed/hybrid-fanout-engine';
import { kWayMergeFeeds, encodeTimelineCursor, decodeTimelineCursor } from '@/lib/feed/k-way-cursor-merger';
import { ValkeyTimelineMixer } from '@/lib/feed/valkey-timeline-mixer';

const CELEBRITY_THRESHOLD = 25000;
const mixer = new ValkeyTimelineMixer({ maxTimelineItems: 800 });

export async function publishPost(authorId: string, followerCount: number, post: { id: string; createdAtMs: number }) {
  if (followerCount >= CELEBRITY_THRESHOLD) {
    // Mode: Celebrity Pull Bypass (Write once to outbox)
    await mixer.appendCelebrityOutbox(authorId, post);
  } else {
    // Mode: Push Write to follower inboxes
    const followerIds = await getFollowerIds(authorId);
    await mixer.fanoutPostToInboxes(followerIds, post);
  }
}

export async function getHomeTimeline(userId: string, cursorStr?: string, limit: number = 20) {
  const cursor = cursorStr ? decodeTimelineCursor(cursorStr) : undefined;

  // 1. Fetch user inbox from Valkey
  const inboxItems = await mixer.getUserInbox(userId);

  // 2. Fetch outboxes of followed celebrities
  const followedCelebrityIds = await getFollowedCelebrities(userId);
  const celebrityFeeds = await Promise.all(
    followedCelebrityIds.map(celebId => mixer.getCelebrityOutbox(celebId))
  );

  // 3. Merge all streams in O(N log K) via Binary Max-Heap
  const allStreams = [inboxItems, ...celebrityFeeds];
  const { items, nextCursor } = kWayMergeFeeds(allStreams, { limit, cursor });

  return {
    items,
    nextCursor: nextCursor ? encodeTimelineCursor(nextCursor) : null,
  };
}

📊 Production Scale Benchmark & VerificationCopy Anchor Link

Verified on the GonnaCrash Level 22 (fanout_feed) simulation: