Social Graph / Social Network

Phase 1 — Clarify & Scope

Interviewer: Design a social graph system — think Facebook's friend graph or Twitter's follow graph. What do you want to clarify?

Candidate: Important distinctions:

1. Undirected (mutual friendship like Facebook) or directed (follow like Twitter/Instagram)?
2. What operations dominate — reads (show my friends), writes (add friend), or graph traversals (friends of friends, mutual friends)?
3. What's the scale — users and connections?
4. Do we need to support graph queries like shortest path, or just direct queries (is A friends with B, list A's friends)?
5. Real-time features — follower counts, activity feed based on social graph?

Interviewer: Both: directed follow graph (Twitter-style) AND undirected friendship (Facebook-style). Focus on the data model and query patterns. 1 billion users, average 500 connections per user. Support: add/remove connections, list followers/following, check if two users are connected, compute mutual friends. No shortest path needed. Follower counts should be real-time.

Candidate: Let me size this:

$\text{Total edges} = 10^9 \text{ users} \times 500 \text{ connections} / 2 = 250 \text{ billion edges (undirected)}$

$\text{Directed edges (follow)} = 10^9 \times 500 = 500 \text{ billion edges}$

At 16 bytes per (user_id, user_id) pair (8 bytes per BIGINT): $\text{Edge storage} = 500 \times 10^9 \times 16 \text{ bytes} = 8 \text{ TB}$

Reads dominate: every timeline render, every profile visit checks the social graph.

$\text{Graph reads} \approx 10^9 \text{ users} \times 50 \text{ reads/day} / 86{,}400 \approx 578{,}703 \text{ reads/sec}$