Social graphs and feed generation — push, pull, hybrid
The graph modeling and feed taxonomy — with your double-row friendship as the case study.
Concept → your projects
Graph modeling choices:
- Adjacency list (edge table):
follows(follower_id, followee_id)— the default; "who do I follow" and "who follows me" are two indexed directions. - Double-row storage (your friendship): write A→B and B→A → "my friends" is one scan, no OR, no UNION. Cost: 2× rows, and symmetry must be maintained by a single writer (
upsertFriendshipPair). - FlockDB-style (Twitter's): adjacency with time-ordered edge ids (Snowflake) → O(1) "who does X follow, newest first" pagination, plus denormalized counts, all sharded by user. The pattern to know: edges as the primary data, with ordering baked into the key.
- Closure tables / materialized paths for transitive queries (friends-of-friends) — precomputed reachability, refreshed on write; the cost of "instant" multi-hop queries is write amplification. (This is where a graph DB would earn its keep — Day 37's boundary.)
Feed generation taxonomy:
- Fanout-on-write (push): on post, insert into every follower's feed table → reads are a single indexed scan (the celebrity problem: 10M followers = 10M writes per post).
- Fanout-on-read (pull): on read, query the followee set's posts, merge by time → writes cheap, reads expensive (N-way merge, and worse as followee count grows).
- Hybrid: push for the majority, pull for high-follower accounts (merge at read time for just those) — the industry answer; also push-only-to-active-followers (lazy backfill on next login).
- Ranked feeds: instead of strict chronology, score candidates (recency decay + affinity + engagement) — the ML layer; the systems requirement is a candidate pool + a scorer + caching of results.
Unread indicators (your topic list's design item): the classic trap is per-post read receipts (write amplification). The patterns: per-feed cursor (last_seen_at — cheap, coarse), per-conversation last-read (the standard for chat), counters with invalidation (badge = increment on write, reset on read — your unread count!), and watermark + exceptions (a "seen" set for items before the watermark — the hybrid used when reads aren't monotonic). Your traverse design uses counters + explicit invalidation — the right choice at small scale.
Your systems' social surface
Traverse: double-row Friendship (PENDING/ACCEPTED/BLOCKED states — the state machine from Day 36), FriendStreak keyed by canonical pair (userId1 < userId2) with a CHECK constraint (Day 25's "constraints as invariants"), blocks with hidden-user filtering, friend-request rate limits (30/hour, 50 pending), and a read-time activity feed (fanout-on-read: friend activity is queried, not precomputed — correct for ≤100 friends, and the reason broadcast fanout exists separately for explicit broadcasts). The distinction to articulate: implicit feed (activity stream) = pull; explicit broadcast = push. You run both, chosen per semantics — that's the sophistication.
Bulletproof your resume
Say these answers aloud before moving on
These are the follow-ups an interviewer will actually ask about your projects.
Why double-row friendships instead of a single edge?
Read simplicity: 'my friends' is one indexed scan on the requesting user's rows — no OR across two columns, no UNION, no per-query symmetry logic. The cost is 2× storage (trivial) and the discipline that exactly one writer maintains both rows (my upsertFriendshipPair), which is the same single-writer rule I apply to any denormalization. The alternative — single row with an ordered pair and OR queries — saves rows and complicates every read path; at social-graph scale I'd revisit for write volume, but not for read ergonomics.
When does traverse's feed need to become push?
When read cost or latency grows: today friend activity is computed at read time from a small friend set with per-user indexes — O(friends) per read, fine at ≤100 friends. At thousands of friends, or with ranking requirements, the pull becomes expensive and stale-sensitive; then I'd add a feed table with fanout-on-write for normal accounts and keep pull for high-follower accounts (hybrid). The trigger is measurable: p95 feed latency or query cost, not follower count alone.
How do you implement an unread indicator without write amplification?
Counters with explicit invalidation: increment an unread counter on write (or derive it cheaply), reset/decache on read. Per-item read receipts are the anti-pattern — one write per user per item. My implementation: unread counts derived from the notifications table with a cached value invalidated on mark-read, so the badge is immediate after my own action (the only freshness anyone notices) and TTL-bounded otherwise. Chat-style conversations would use per-conversation last-read timestamps — a different granularity for a different UI.