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

This first layer defines the system boundary. The next chapters add application logic and data dependencies. After examining the request paths and tradeoffs, we will add operational safeguards and bring the complete architecture together.

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

Neighbor-list caches make common graph reads cheap, but very high-degree users can still dominate memory and intersection work. Fetch bounded subsets where the product allows it and choose intersection algorithms suited to list sizes. Recheck privacy and block rules before displaying a cached relationship or suggestion.

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)

High-Level Architecture

Component Breakdown

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.