Social graph storage in HLD - System Design Exercise

Design: Social Graph Storage System

Design focuses on storage and query of social graph connections. User authentication, UI, and recommendation algorithms are out of scope.

Functional Requirements

FR1: Store user profiles and their connections (friends, followers).

FR2: Support adding and removing connections between users.

FR3: Efficiently query direct connections of a user.

FR4: Support querying mutual connections between two users.

FR5: Handle up to 100 million users and 10 billion connections.

FR6: Provide low latency queries (p99 < 100ms) for connection lookups.

FR7: Ensure data consistency for connection updates.

FR8: Support eventual consistency for large-scale replication.

Non-Functional Requirements

NFR1: Scale to 100 million users and 10 billion edges.

NFR2: API response latency p99 under 100ms for read queries.

NFR3: Availability target 99.9% uptime (about 8.77 hours downtime/year).

NFR4: Data storage must be cost-effective and scalable.

NFR5: Support horizontal scaling for both reads and writes.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

❓ Question 7

Key Components

Graph database or specialized graph storage system

Caching layer for frequent queries

API layer for connection management and queries

Replication and backup system

Load balancer for distributing requests

Monitoring and alerting system

Design Patterns

Graph data modeling (adjacency list, edge list)

Sharding and partitioning of graph data

Caching strategies for graph queries

Eventual consistency with conflict resolution

Batch processing for analytics and maintenance

Reference Architecture

Client
  |
  v
Load Balancer
  |
  v
API Servers (REST/gRPC)
  |
  v
Cache Layer (Redis or Memcached)
  |
  v
Graph Storage Cluster (e.g., Neo4j, JanusGraph with Cassandra)
  |
  v
Replication & Backup Storage

Monitoring & Alerting System (parallel)

Components

API Servers

REST/gRPC services

Handle client requests for adding/removing connections and querying social graph

Load Balancer

Nginx or cloud LB

Distribute incoming requests evenly across API servers

Cache Layer

Redis or Memcached

Cache frequent queries like user connections to reduce latency

Graph Storage Cluster

Neo4j or JanusGraph with Cassandra backend

Store user nodes and edges representing connections; support graph queries

Replication & Backup Storage

Cassandra or distributed file system

Ensure data durability and availability across data centers

Monitoring & Alerting System

Prometheus, Grafana

Track system health, latency, errors, and trigger alerts

Request Flow

1. Client sends request to add/remove connection or query connections.

2. Load balancer routes request to one of the API servers.

3. API server checks cache for query requests; if cache miss, queries graph storage.

4. For write requests, API server updates graph storage and invalidates relevant cache entries.

5. Graph storage persists changes and replicates data asynchronously.

6. API server returns response to client with connection data or confirmation.

7. Monitoring system collects metrics from all components continuously.

Database Schema

Entities: - User: user_id (PK), name, profile_data - Connection: from_user_id (FK to User), to_user_id (FK to User), connection_type, created_at Relationships: - User to Connection is 1:N (one user can have many connections) - Connections can be directed (follower) or undirected (friendship stored as two directed edges) Indexes: - Index on from_user_id for fast lookup of user's connections - Composite index on (from_user_id, to_user_id) for quick existence checks Storage: - Use adjacency list model storing edges per user node for efficient traversal

Scaling Discussion

Bottlenecks

Graph storage cluster can become slow with very large number of edges per user.

Cache invalidation complexity increases with frequent writes.

Load balancer and API servers can become overwhelmed with high request volume.

Replication lag can cause stale reads in multi-region setups.

Solutions

Shard graph data by user_id ranges or hash to distribute load across multiple storage nodes.

Use write-back cache with TTL and selective invalidation to balance freshness and performance.

Auto-scale API servers and load balancers based on traffic patterns.

Implement multi-master replication with conflict resolution or use read-your-writes consistency models.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing architecture and data model, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Clarify types of connections and query patterns before designing.

Explain choice of graph database and caching for performance.

Discuss data model focusing on adjacency list for efficient queries.

Highlight how to handle scale with sharding and replication.

Mention trade-offs between consistency and availability.

Show awareness of monitoring and operational concerns.

Practice

1. What is the primary purpose of social graph storage in system design?

easy

A. To handle user authentication and authorization

B. To store only user profile data without connections

C. To manage database backups efficiently

D. To store users as nodes and their relationships as edges

Solution

1. Step 1: Understand social graph components

   Social graph storage models users as nodes and their relationships as edges.

2. Step 2: Identify the main function

   The main function is to represent and query user connections, not just user data or security.

3. Final Answer:

   To store users as nodes and their relationships as edges -> Option D

4. Quick Check:

   Social graph = nodes + edges [OK]

Hint: Remember: social graph = users + connections [OK]

Common Mistakes:

• Confusing social graph with user profile storage
• Thinking it handles authentication
• Assuming it manages backups

2. Which data structure is most suitable to represent a social graph for efficient traversal?

easy

A. Stack

B. Array

C. Adjacency list

D. Queue

Solution

1. Step 1: Review data structures for graph representation

   Adjacency lists store each node with a list of connected nodes, ideal for sparse graphs like social networks.

2. Step 2: Compare with other options

   Arrays don't efficiently represent connections; stacks and queues are traversal helpers, not storage.

3. Final Answer:

   Adjacency list -> Option C

4. Quick Check:

   Efficient graph storage = adjacency list [OK]

Hint: Use adjacency list for sparse graph storage [OK]

Common Mistakes:

• Choosing arrays which waste space
• Confusing traversal structures with storage
• Ignoring graph sparsity

3. Given a social graph stored as an adjacency list: {'Alice': ['Bob', 'Carol'], 'Bob': ['Alice'], 'Carol': ['Alice']}, what is the output of querying Alice's friends?

medium

A. ['Bob']

B. ['Bob', 'Carol']

C. ['Alice']

D. []

Solution

1. Step 1: Locate Alice in adjacency list

   Alice's entry shows connections to Bob and Carol.

2. Step 2: Return Alice's friends list

   The list associated with Alice is ['Bob', 'Carol'].

3. Final Answer:

   ['Bob', 'Carol'] -> Option B

4. Quick Check:

   Alice's friends = ['Bob', 'Carol'] [OK]

Hint: Check adjacency list key for user connections [OK]

Common Mistakes:

• Returning the user name instead of friends
• Confusing direction of edges
• Returning empty list by mistake

4. In a social graph system, a developer tries to add a friendship edge between two users but the system crashes. Which is the most likely cause?

medium

A. The users do not exist in the graph nodes

B. The graph uses an adjacency list

C. The system uses directed edges

D. The graph is stored in a relational database

Solution

1. Step 1: Analyze the crash cause

   Adding an edge requires both users to exist as nodes; missing nodes cause errors.

2. Step 2: Evaluate other options

   Adjacency list, directed edges, or relational storage do not inherently cause crashes when adding edges.

3. Final Answer:

   The users do not exist in the graph nodes -> Option A

4. Quick Check:

   Missing nodes cause edge addition failure [OK]

Hint: Ensure both users exist before adding edges [OK]

Common Mistakes:

• Blaming data structure choice for crash
• Ignoring node existence before edge creation
• Assuming direction causes crash

5. You need to design a social graph storage system that supports millions of users and fast friend-of-friend queries. Which approach is best?

hard

A. Use a distributed graph database with adjacency lists and caching

B. Store all connections in a single relational table with indexes

C. Use flat files to store user connections sequentially

D. Keep all data in memory without persistence

Solution

1. Step 1: Consider scalability and query needs

   Millions of users require distributed storage and efficient traversal for friend-of-friend queries.

2. Step 2: Evaluate options for performance and scalability

   Distributed graph databases with adjacency lists and caching optimize query speed and handle scale; relational tables or flat files are less efficient; in-memory only lacks persistence.

3. Final Answer:

   Use a distributed graph database with adjacency lists and caching -> Option A

4. Quick Check:

   Scale + fast queries = distributed graph DB + caching [OK]

Hint: Combine distribution, adjacency lists, and caching for scale [OK]

Common Mistakes:

• Choosing relational tables for large graph queries
• Using flat files which are slow
• Ignoring persistence by using memory only