Social Graph

Problem Statement & Requirements

Design a social graph system that models relationships between users and powers core social features — friend/connection management, "People You May Know" suggestions, mutual connections, degree-of-separation queries, and graph-based feed ranking — similar to LinkedIn's connection graph, Facebook's social graph, or Twitter's follower graph.

Functional Requirements

• Add / remove connection — send connection request, accept/reject, remove existing connection
• Follow / unfollow — asymmetric follow relationship (Twitter model) alongside symmetric connections (LinkedIn/Facebook model)
• Get connections — list a user's 1st-degree connections with pagination
• Mutual connections — "You and Alice have 12 mutual connections"
• Degree of separation — "Alice is a 2nd-degree connection" (friend of a friend)
• People You May Know (PYMK) — recommend new connections based on graph proximity, shared attributes, mutual connections
• Connection count — display connection/follower/following counts
• Graph search — "Find people named Bob who work at Google and are connected to Alice"
• Privacy controls — control who can see your connections, who can send requests
• Block user — hide from each other's graph entirely

Non-Functional Requirements

• Low latency — connection lookup < 10 ms; mutual connections < 50 ms; PYMK < 200 ms
• High read throughput — 500K+ graph queries/sec (connections list, mutual, PYMK)
• Consistency — connection state must be strongly consistent (if I connect, both parties see it immediately)
• Scale — 1B+ users, 500B+ edges (connections + follows)
• Availability — 99.99% for read operations
• Efficient traversal — 2nd and 3rd degree queries must be fast despite billions of edges

Out of Scope

• News feed generation (see News Feed design)
• Messaging system (see Chat System design)
• Profile / content management
• Full knowledge graph (entity relationships beyond people)

Scale Estimations

Traffic

Storage

Bandwidth

Hardware Estimate

High-Level Architecture

Component Breakdown

API Design

Send Connection Request

POST /api/v1/connections/request
Authorization: Bearer <token>

Request:
{
  "target_user_id": "user-bob-456",
  "message": "Hi Bob, we met at the conference!"   // optional
}

Response (201 Created):
{
  "request_id": "req-abc123",
  "status": "pending",
  "from": "user-alice-123",
  "to": "user-bob-456",
  "created_at": "2026-04-03T10:00:00Z"
}

Accept / Reject Connection

POST /api/v1/connections/request/{request_id}/accept

Response (200 OK):
{
  "connection_id": "conn-xyz789",
  "users": ["user-alice-123", "user-bob-456"],
  "connected_at": "2026-04-03T10:05:00Z"
}

POST /api/v1/connections/request/{request_id}/reject
Response: 204 No Content

Get Connections (Adjacency List)

GET /api/v1/users/{user_id}/connections?limit=20&cursor=eyJsYXN0IjoiY29ubl8xMjM0NTY3In0=

Response (200 OK):
{
  "user_id": "user-alice-123",
  "total_connections": 847,
  "connections": [
    {
      "user_id": "user-bob-456",
      "name": "Bob Smith",
      "headline": "VP Engineering at Acme Corp",
      "profile_image": "https://cdn.example.com/bob.jpg",
      "connected_at": "2026-04-03T10:05:00Z",
      "mutual_connection_count": 12
    },
    ...
  ],
  "next_cursor": "eyJsYXN0IjoiY29ubl85OTk5In0="
}

Get Mutual Connections

GET /api/v1/users/{user_id_a}/mutual/{user_id_b}?limit=10

Response (200 OK):
{
  "user_a": "user-alice-123",
  "user_b": "user-charlie-789",
  "mutual_count": 12,
  "mutual_connections": [
    {
      "user_id": "user-bob-456",
      "name": "Bob Smith",
      "headline": "VP Engineering at Acme Corp"
    },
    ...
  ]
}

Get Degree of Separation

GET /api/v1/users/{user_id_a}/degree/{user_id_b}

Response (200 OK):
{
  "user_a": "user-alice-123",
  "user_b": "user-dave-999",
  "degree": 2,
  "path": [
    "user-alice-123",      // Alice
    "user-bob-456",        // → Bob (1st degree)
    "user-dave-999"        // → Dave (2nd degree via Bob)
  ]
}

People You May Know

GET /api/v1/users/{user_id}/pymk?limit=20

Response (200 OK):
{
  "suggestions": [
    {
      "user_id": "user-eve-111",
      "name": "Eve Johnson",
      "headline": "Data Scientist at BigCorp",
      "mutual_connections": 8,
      "shared_company": "Acme Corp",
      "shared_school": null,
      "score": 0.87,
      "reason": "8 mutual connections"
    },
    ...
  ]
}

Graph Search

GET /api/v1/search/people?q=product+manager
    &company=Google
    &location=San+Francisco
    &degree=2
    &limit=20

Response (200 OK):
{
  "total": 342,
  "results": [
    {
      "user_id": "user-frank-222",
      "name": "Frank Lee",
      "headline": "Sr. Product Manager at Google",
      "location": "San Francisco, CA",
      "degree": 2,
      "mutual_connections": 5,
      "relevance_score": 0.92
    },
    ...
  ]
}

Data Model

Edge Table (Persistent Store)

Adjacency List (In-Memory Index)

Connection Request

Core Design Decisions

Decision 1: Graph Storage — How to Store 500B Edges

Option A: Relational Database (MySQL/PostgreSQL)

Option B: Native Graph Database (Neo4j / JanusGraph)

Option C: Adjacency List in KV Store + SQL Edge Table (LinkedIn/Facebook Approach)

Recommendation: Option C (Adjacency in Memory + SQL Edges)

This is what Facebook (TAO) and LinkedIn (follow graph) actually use.
In-memory adjacency for reads (hot path), SQL for writes (durability).
Graph DBs are great for exploration queries but harder to shard at 500B edges.

Decision 2: Mutual Connection Computation

Decision 3: Degree of Separation — BFS on Billion-Node Graph

Detailed Flow Diagrams

Connection Request → Accept Flow

Mutual Connections Query

PYMK Batch Computation

Workshop note · added for the website’s common reading format

Start with the dominant access pattern of Social Graph. Adjacency cache is one place to inspect capacity and tail latency. Measure before introducing a cache: define the cache key, invalidation policy, stale-data budget, and cold-start behavior.

Batch independent work where the latency budget allows it. Bound queues and concurrency, and verify that an optimization does not move the bottleneck to a dependency.

Graph Search

Handling Edge Cases

Celebrity / High Fan-Out Users

Problem: Elon Musk has 150M followers
  → Adjacency list: 150M × 8 bytes = 1.2 GB for ONE user
  → Mutual connections with 150M: sort-merge = very expensive

Solution: Tiered Storage

  Normal users (< 50K connections):
    → Full adjacency list in memory (standard path)
    → Real-time set intersection for mutuals

  High fan-out users (> 50K followers):
    → Followers stored in persistent store only (not in-memory)
    → Follower count maintained as counter (not list length)
    → Mutual connections: use bloom filter approximation
    → "~23 mutual connections" (approximate, not exact list)
    → Exact mutual list computed on-demand (paginated, not all at once)

  Bidirectional connections (LinkedIn-style) naturally bounded:
    → Max ~30K connections on LinkedIn
    → Always fits in memory
    → Followers (asymmetric) can be unlimited → tiered

Consistency on Connection Create

Problem: Alice connects to Bob
  → Must update: edge table, Alice's adjacency, Bob's adjacency
  → If Alice's adjacency updates but Bob's fails → inconsistent

Solution: Event-Sourced Writes

  1. Write to edge table (source of truth) — atomic DB transaction
  2. Publish "connection_created" event to Kafka
  3. Adjacency list updater consumes event:
     → Update Alice's list (retry on failure)
     → Update Bob's list (retry on failure)
  4. If adjacency update fails:
     → Consumer retries (Kafka guarantees at-least-once)
     → Adjacency store is eventually consistent (seconds lag OK)
  5. Worst case: adjacency stale → user refreshes → reads from edge table

  Critical: Edge table write is the commit point.
  Adjacency lists are derived views (can always be rebuilt).

Graph Partitioning (Sharding)

Blocking and Privacy

Block user:
  1. INSERT edge (A, B, type=blocked)
  2. Remove connection edge if exists: DELETE (A,B) and (B,A)
  3. Update adjacency lists: remove from both
  4. Block record checked on ALL graph operations:
     → A never appears in B's search results, PYMK, or mutual lists
     → B never appears in A's search results, PYMK, or mutual lists
  5. Bloom filter of blocked pairs checked before any result returned
     → Fast O(1) check, minimal false positives

Privacy settings:
  "Only connections can see my connections list"
  → Graph Query Service checks viewer's relation to target
  → If viewer is not connected AND target's setting = private:
    → Return: "Connection list is private" (not the data)
  → Applied at API layer, not storage layer

Tradeoffs & Design Decisions Summary

Reliability & Fault Tolerance

Single Points of Failure & Mitigations

Graceful Degradation

Tier 1 (PYMK service down):
  → Profile page shows no suggestions
  → Core connections/search unaffected
  → PYMK rebuilds when service recovers

Tier 2 (Graph search degraded):
  → Fall back to text-only search (no graph ranking)
  → Results still useful, just not personalized by degree
  → "N mutual connections" badge missing

Tier 3 (Adjacency store shard down):
  → Connections for affected users fetched from edge table (slower, ~20 ms)
  → Read replica of adjacency store serves reads if available
  → Mutual connections degrade to approximate (bloom filter) or unavailable

Tier 4 (Edge table shard down):
  → Cannot create new connections (writes fail)
  → Existing adjacency lists still serve reads (in-memory)
  → Auto-failover to standby (< 30s)

Full System Architecture (Production-Grade)

Graph Algorithms Used in Production

Facebook TAO — Reference Architecture

Interview Tips

1. Start with the data model: two rows per bidirectional connection — Store edges (A→B) and (B→A). 2× storage but each user's connection list is a simple prefix scan. This is the non-obvious insight that shows you've thought deeply about read patterns.

2. In-memory adjacency lists are the key performance decision — "500B edges × 32 bytes = 16 TB on disk. But adjacency lists (sorted user_id arrays) = 4 TB, which fits in a 100-node cluster's RAM. Sub-millisecond reads, set intersection for mutuals in microseconds." This is how Facebook TAO and LinkedIn actually work.

3. Mutual connections = set intersection, not SQL JOIN — Load A's sorted array and B's sorted array. Merge-intersect in O(n+m). For 500 + 800 connections = ~1,300 comparisons = microseconds. SQL JOIN on a 500B-row table would take seconds.

4. Bidirectional BFS for degree of separation — Don't do naive BFS from one end. Expand from BOTH endpoints, meet in middle. O(b^(d/2)) vs O(b^d) = 5,700× faster for depth 3 with branching factor 500. Limit to 3rd degree (LinkedIn does "3rd+").

5. PYMK is the hardest problem — Can't compute in real-time for 500M users. Explain: nightly batch job (Spark, ~5 hours) computes 2nd-degree candidates, scores by mutual count + shared attributes. Incremental updates via Kafka events when connections change. Serve from Redis cache.

6. Celebrity/influencer problem — Normal users have ~500 connections (fits in memory). Elon has 150M followers (1.2 GB). Solution: tiered storage — connections in memory, follower lists on disk. Approximate mutual count via bloom filters for high fan-out users.

7. Graph sharding is hard — Graph partitioning is NP-hard. Don't try social-cluster partitioning. Use hash sharding (simple, even) and aggressive caching of adjacency lists. The adjacency list IS the cache — 4 TB fits in memory.

8. Event-sourced writes for consistency — Edge table write is the commit point (ACID). Adjacency list updates are derived via Kafka events (eventually consistent, seconds lag). If adjacency store fails, edges still safe in DB; adjacency rebuilt.

9. Graph search = Elasticsearch + graph re-ranking — Don't build a graph-native search engine. Use ES for text/attribute search, then re-rank results by graph distance (1st degree = boost 3×, 2nd degree = boost 2×, mutual count). Two systems, each doing what it does best.

10. Reference Facebook TAO — "Facebook TAO: in-memory cache (99.8% hit rate, < 1 ms reads) backed by sharded MySQL. Billions of reads/sec. Writes go to MySQL first, then invalidate cache. Scale reads by adding cache nodes. This is the architecture I'm following." Instant credibility.