Facebook Newsfeed Design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// Different update granularities require different architectures
 
// Full Post Update - Send complete post data
interface NewPostUpdate {
  type: 'new_post';
  post: FullPostData;  // All content, author info, etc.
  timestamp: number;
}
 
// Incremental Counter Update - Send only delta
interface EngagementDelta {
  type: 'engagement_delta';
  postId: string;
  field: 'likes' | 'comments' | 'shares';
  delta: number;  // +1, -1, etc.
}
 
// Coalesced Update - Batched changes
interface BatchedUpdate {
  type: 'batch';
  postId: string;
  likes: number;      // Absolute count (not delta)
  comments: number;
  lastUpdated: number;
}
 
// Presence Update - Ephemeral state
interface PresenceUpdate {
  type: 'presence';
  userId: string;
  state: 'online' | 'away' | 'offline';
  lastSeen?: number;
}
 
// Strategy: Use deltas for high-frequency updates (engagement)
// Use full data for low-frequency updates (new posts)
// Use absolute counts when coalescing (batch updates)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Connection server capacity planning
 
# Per-server limits (modern hardware)
MAX_CONNECTIONS_PER_SERVER = 100_000  # Limited by file descriptors
MEMORY_PER_CONNECTION = 10_KB         # State, buffers
CPU_FOR_HEARTBEATS = 0.1_MS          # Per connection per second
 
# Global scale
CONCURRENT_USERS = 500_000_000        # Peak DAU online simultaneously
# (Not all 2B users are online at once; typical: 25%)
 
# Server count needed
servers_needed = CONCURRENT_USERS / MAX_CONNECTIONS_PER_SERVER
# = 500M / 100K = 5,000 connection servers
 
# Memory per server
memory_per_server = MAX_CONNECTIONS_PER_SERVER * MEMORY_PER_CONNECTION
# = 100K * 10KB = 1 GB per server
 
# Heartbeat CPU per server
heartbeat_cpu_ms = MAX_CONNECTIONS_PER_SERVER * CPU_FOR_HEARTBEATS
# = 100K * 0.1ms = 10,000 ms = 10 seconds CPU per second
# Requires multi-core (typically 16+ cores per server)
 
# Connection registry storage
registry_entry_size = 100  # bytes (userId -> serverId mapping)
registry_storage = CONCURRENT_USERS * registry_entry_size
# = 500M * 100 = 50 GB (fits in Redis cluster)
 
# Message throughput (updates per second)
updates_per_user_per_minute = 2  # avg new content, engagements
total_updates_per_second = CONCURRENT_USERS * updates_per_user_per_minute / 60
# = 500M * 2 / 60 = 16.7 million messages/second

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// Distributed connection registry
// Maps users to their current connection servers
 
interface ConnectionRegistry {
  // Primary lookup: user → connection server
  userToServer: Map<UserId, ServerId>;
  
  // Reverse lookup: server → users (for reconnection handling)
  serverToUsers: Map<ServerId, Set<UserId>>;
  
  // Connection metadata
  connectionMeta: Map<UserId, ConnectionMetadata>;
}
 
interface ConnectionMetadata {
  userId: string;
  serverId: string;
  connectedAt: timestamp;
  lastHeartbeat: timestamp;
  clientType: 'ios' | 'android' | 'web' | 'desktop';
  capabilities: string[];  // Supported update types
}
 
// Registry operations
class DistributedRegistry {
  private redis: RedisCluster;
  
  async registerConnection(userId: string, serverId: string, meta: ConnectionMetadata) {
    const key = `conn:${userId}`;
    const serverKey = `server:${serverId}`;
    
    await this.redis.multi()
      .hset(key, 'server', serverId)
      .hset(key, 'meta', JSON.stringify(meta))
      .sadd(serverKey, userId)
      .expire(key, 300)  // TTL for stale connections
      .exec();
  }
  
  async unregisterConnection(userId: string) {
    const serverKey = await this.getServerForUser(userId);
    
    await this.redis.multi()
      .del(`conn:${userId}`)
      .srem(`server:${serverKey}`, userId)
      .exec();
  }
  
  async getServerForUser(userId: string): Promise<string | null> {
    return this.redis.hget(`conn:${userId}`, 'server');
  }
  
  async getUsersOnServer(serverId: string): Promise<string[]> {
    return this.redis.smembers(`server:${serverId}`);
  }
  
  // Heartbeat-based liveness checking
  async refreshConnection(userId: string) {
    await this.redis.expire(`conn:${userId}`, 300);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

// Update Routing Service
 
class UpdateRouter {
  
  async routeNewPost(post: Post) {
    // Step 1: Get potentially interested users
    const followers = await socialGraph.getFollowers(post.authorId);
    
    // Step 2: Filter to online users only (efficiency)
    const onlineFollowers = await connectionRegistry.filterOnline(followers);
    
    // Step 3: Further filter by relevance (reduce noise)
    const relevantFollowers = await this.filterByRelevance(
      onlineFollowers, 
      post
    );
    
    // Step 4: Group by connection server
    const serverGroups = await this.groupByServer(relevantFollowers);
    
    // Step 5: Enqueue messages per server
    for (const [serverId, userIds] of serverGroups) {
      await messageQueue.enqueue(`server:${serverId}`, {
        type: 'new_post',
        post: this.compactPost(post),
        targetUsers: userIds,
      });
    }
  }
  
  async filterByRelevance(userIds: string[], post: Post): Promise<string[]> {
    // Don't push every post to every follower
    // Use lightweight ranking to determine who would care
    
    const results = [];
    for (const userId of userIds) {
      const affinity = await affinityScore.get(userId, post.authorId);
      
      // Only push to users with strong relationship
      if (affinity > 0.5) {
        results.push(userId);
      }
    }
    return results;
  }
  
  async routeEngagement(engagement: Engagement) {
    // Step 1: Get post author (always notify)
    const post = await postStore.get(engagement.postId);
    
    // Step 2: Get current viewers of this post
    const viewers = await viewerTracker.getCurrentViewers(engagement.postId);
    
    // Step 3: Route to author + viewers
    const targets = [post.authorId, ...viewers];
    const serverGroups = await this.groupByServer(targets);
    
    for (const [serverId, userIds] of serverGroups) {
      await messageQueue.enqueue(`server:${serverId}`, {
        type: 'engagement_update',
        postId: engagement.postId,
        engagementType: engagement.type,
        count: await engagementStore.getCount(engagement.postId, engagement.type),
        targetUsers: userIds,
      });
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Pub/Sub for Feed Subscriptions
 
interface Subscription {
  userId: string;
  topic: string;  // post:{postId}, author:{authorId}, etc.
  createdAt: timestamp;
  expiresAt: timestamp;  // Auto-cleanup for inactive
}
 
class FeedPubSub {
  private redis: RedisCluster;
  
  // When user views a post, subscribe to its updates
  async subscribeToPost(userId: string, postId: string) {
    const topic = `post:${postId}`;
    
    await this.redis.sadd(`topic:${topic}`, userId);
    await this.redis.expire(`topic:${topic}`, 3600);  // 1 hour TTL
    
    // Track user's subscriptions for cleanup
    await this.redis.sadd(`user_subs:${userId}`, topic);
  }
  
  // When engagement happens, notify subscribers
  async publishToPost(postId: string, update: EngagementUpdate) {
    const topic = `post:${postId}`;
    const subscribers = await this.redis.smembers(`topic:${topic}`);
    
    // Batch by connection server
    const serverGroups = await this.groupByServer(subscribers);
    
    for (const [serverId, userIds] of serverGroups) {
      await this.deliverToServer(serverId, userIds, update);
    }
  }
  
  // Cleanup when user disconnects
  async unsubscribeAll(userId: string) {
    const topics = await this.redis.smembers(`user_subs:${userId}`);
    
    for (const topic of topics) {
      await this.redis.srem(`topic:${topic}`, userId);
    }
    
    await this.redis.del(`user_subs:${userId}`);
  }
}
 
// Advantages of Pub/Sub:
// - O(1) lookup for interested users (vs O(n) follower expansion)
// - Automatic scoping to active viewers
// - Natural TTL-based cleanup
// - Scales with active interest, not total follower count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

// Client-side feed state manager
 
interface FeedState {
  posts: Map<PostId, Post>;       // Normalized post storage
  ordering: PostId[];             // Current feed order
  pendingUpdates: Update[];       // Buffered updates
  lastSyncToken: string;          // For incremental sync
  scrollPosition: number;         // Current scroll position
}
 
class FeedStateManager {
  private state: FeedState;
  private socket: WebSocket;
  
  // Handle incoming real-time update
  handleUpdate(update: Update) {
    switch (update.type) {
      case 'new_post':
        this.handleNewPost(update.post);
        break;
      case 'engagement_delta':
        this.handleEngagementDelta(update);
        break;
      case 'post_deleted':
        this.handlePostDeleted(update.postId);
        break;
    }
  }
  
  handleNewPost(post: Post) {
    // Don't immediately insert at top (jarring UX)
    // Instead, show "New posts available" indicator
    
    // Store the post
    this.state.posts.set(post.id, post);
    
    // Add to pending if user has scrolled
    if (this.state.scrollPosition > 0) {
      this.state.pendingUpdates.push({
        type: 'new_post',
        postId: post.id,
        timestamp: Date.now(),
      });
      
      // Update UI indicator
      this.showNewPostsIndicator(this.state.pendingUpdates.length);
    } else {
      // User is at top, insert directly with animation
      this.insertPostAtTop(post);
    }
  }
  
  handleEngagementDelta(update: EngagementDelta) {
    const post = this.state.posts.get(update.postId);
    if (!post) return;  // Post not in view
    
    // Apply delta to local state
    post.engagement[update.field] += update.delta;
    
    // Update UI immediately (no buffering needed)
    this.updatePostUI(update.postId);
  }
  
  // When user clicks "Show new posts"
  flushPendingUpdates() {
    // Sort pending posts by timestamp
    const newPosts = this.state.pendingUpdates
      .filter(u => u.type === 'new_post')
      .map(u => this.state.posts.get(u.postId))
      .sort((a, b) => b.createdAt - a.createdAt);
    
    // Scroll to top with animation
    this.scrollToTop();
    
    // Insert all pending posts
    for (const post of newPosts) {
      this.insertPostAtTop(post, { animate: true });
    }
    
    // Clear pending
    this.state.pendingUpdates = [];
    this.hideNewPostsIndicator();
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

// Incremental sync protocol
 
interface SyncResponse {
  updates: Update[];           // New/changed content since last sync
  deletions: string[];         // Removed content
  syncToken: string;           // New sync cursor
  hasMore: boolean;            // Pagination
}
 
class SyncManager {
  
  async syncFeed(): Promise<void> {
    const token = await storage.get('feedSyncToken') || '0';
    
    const response = await api.syncFeed({
      since: token,
      limit: 100
    });
    
    // Apply updates
    for (const update of response.updates) {
      await this.applyUpdate(update);
    }
    
    // Handle deletions
    for (const postId of response.deletions) {
      await this.removePost(postId);
    }
    
    // Save new token
    await storage.set('feedSyncToken', response.syncToken);
    
    // Continue if more updates available
    if (response.hasMore) {
      await this.syncFeed();
    }
  }
  
  // Handle reconnection after offline period
  async onReconnect() {
    // 1. Flush local action queue to server
    await this.flushPendingActions();
    
    // 2. Sync to get latest state
    await this.syncFeed();
    
    // 3. Resolve any conflicts
    await this.resolveConflicts();
    
    // 4. Update UI
    this.refreshFeedUI();
  }
  
  async flushPendingActions() {
    const pending = await actionQueue.getAll();
    
    for (const action of pending) {
      try {
        await this.sendAction(action);
        await actionQueue.remove(action.id);
      } catch (e) {
        if (e.isConflict) {
          // Action no longer valid (e.g., liking deleted post)
          await actionQueue.remove(action.id);
          await this.revertLocalAction(action);
        }
        // Other errors: keep in queue for retry
      }
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

// Push notification evaluation service
 
interface NotificationCandidate {
  userId: string;
  event: Event;
  priority: 'high' | 'medium' | 'low';
}
 
class NotificationEvaluator {
  
  async shouldSendPushNotification(
    candidate: NotificationCandidate
  ): Promise<boolean> {
    
    const userId = candidate.userId;
    
    // Check 1: User notification settings
    const settings = await notificationSettings.get(userId);
    if (!settings.pushEnabled) return false;
    if (!settings.allowedTypes.includes(candidate.event.type)) return false;
    
    // Check 2: Rate limiting (prevent notification spam)
    const recentCount = await this.getRecentNotificationCount(userId, '1h');
    if (recentCount > 20) {
      // Too many notifications, skip low-priority
      if (candidate.priority === 'low') return false;
    }
    if (recentCount > 50) {
      // Way too many, skip medium too
      if (candidate.priority !== 'high') return false;
    }
    
    // Check 3: Quiet hours (user preference)
    if (settings.quietHoursEnabled) {
      const userLocalTime = await this.getUserLocalTime(userId);
      if (this.isQuietHour(userLocalTime, settings.quietHours)) {
        if (candidate.priority !== 'high') return false;
      }
    }
    
    // Check 4: Recent app activity (don't notify if user just used app)
    const lastActivity = await this.getLastAppActivity(userId);
    if (Date.now() - lastActivity < 5 * 60 * 1000) {  // 5 minutes
      // User was recently active, they might see it organically
      if (candidate.priority === 'low') return false;
    }
    
    // Check 5: Deduplication (don't repeat similar notifications)
    const similar = await this.findSimilarRecentNotification(userId, candidate);
    if (similar) {
      // Coalesce: update count instead of new notification
      await this.updateNotificationCount(similar);
      return false;
    }
    
    return true;
  }
  
  // Coalescing: "John and 5 others liked your post"
  async coalesceEngagementNotifications(
    userId: string,
    postId: string,
    engagementType: string
  ): Promise<NotificationPayload> {
    
    const recent = await this.getRecentEngagements(postId, engagementType, '1h');
    
    if (recent.length === 1) {
      return {
        title: `${recent[0].userName} liked your post`,
        body: recent[0].postPreview,
      };
    } else {
      return {
        title: `${recent[0].userName} and ${recent.length - 1} others liked your post`,
        body: recent[0].postPreview,
      };
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

// Update ordering and deduplication
 
class UpdateOrderer {
  // Logical clock for update ordering
  private lastSeenClock: Map<string, number> = new Map();
  
  // Dedup window
  private seenUpdates: Set<string> = new Set();
  
  shouldApplyUpdate(update: Update): boolean {
    // Deduplication by update ID
    if (this.seenUpdates.has(update.id)) {
      return false;  // Already processed
    }
    this.seenUpdates.add(update.id);
    
    // Size bound the dedup set
    if (this.seenUpdates.size > 10000) {
      // Remove oldest entries
      const toRemove = [...this.seenUpdates].slice(0, 5000);
      toRemove.forEach(id => this.seenUpdates.delete(id));
    }
    
    return true;
  }
  
  orderUpdates(updates: Update[]): Update[] {
    // Sort by logical clock (server-assigned sequence number)
    return updates.sort((a, b) => a.sequenceNumber - b.sequenceNumber);
  }
  
  handleEngagementUpdate(postId: string, newCount: number, timestamp: number) {
    // For counters, use last-write-wins with timestamp
    const key = `engagement:${postId}`;
    const lastTimestamp = this.lastSeenClock.get(key) || 0;
    
    if (timestamp > lastTimestamp) {
      this.lastSeenClock.set(key, timestamp);
      return true;  // Apply this update
    } else {
      return false;  // Stale update, ignore
    }
  }
}
 
// Alternative: Use CRDTs for conflict-free merging
interface GCounterCRDT {
  // Per-server counters that can be merged
  counts: Map<ServerId, number>;
  
  merge(other: GCounterCRDT): GCounterCRDT {
    // Take max of each server's count
    const merged = new Map();
    for (const [server, count] of this.counts) {
      merged.set(server, Math.max(count, other.counts.get(server) || 0));
    }
    for (const [server, count] of other.counts) {
      if (!merged.has(server)) {
        merged.set(server, count);
      }
    }
    return { counts: merged };
  }
  
  value(): number {
    return [...this.counts.values()].reduce((a, b) => a + b, 0);
  }
}