Social graph storage in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Architecture

intermediate

Designing a scalable social graph storage system

You need to design a system to store and query a social graph with billions of users and their connections. Which architecture best supports fast retrieval of a user's friends and mutual friends?

A Use a relational database with tables for users and friendships, indexed by user IDs.

B Use a key-value store where each user ID maps to a list of friend IDs.

C Use a graph database optimized for traversals, storing users as nodes and friendships as edges.

D Use a document database storing each user document with embedded friend lists.

💡 Hint

Think about which storage type naturally represents relationships and supports fast graph queries.

Graph databases are designed to efficiently store and traverse relationships, making them ideal for social graphs where queries like mutual friends are common.

❓ scaling

intermediate

Scaling social graph storage for high write throughput

Your social graph system must handle millions of new friendship connections per minute. Which approach best supports this write load while maintaining query performance?

A Use a single master database to serialize all writes and replicate to read replicas.

B Partition the graph by user ID ranges and distribute partitions across multiple servers.

C Store all friendships in a single large cache to speed up writes.

D Batch all writes and apply them once per hour to reduce load.

💡 Hint

Consider how to distribute data to avoid bottlenecks and allow parallel writes.

Partitioning the graph by user ID distributes write load across servers, enabling high throughput and maintaining query speed by limiting data scope per server.

❓ tradeoff

advanced

Tradeoffs between consistency and availability in social graph storage

In a distributed social graph system, which choice best describes the tradeoff when prioritizing availability over consistency?

A Users may see stale friend data during network partitions but the system remains available.

B Users always see the most up-to-date friend list but the system may be unavailable during network issues.

C The system rejects writes during network partitions to maintain consistency.

D The system duplicates data to all nodes synchronously to ensure consistency.

💡 Hint

Think about the CAP theorem and what happens when availability is prioritized.

Prioritizing availability means the system continues to operate during network issues but may serve stale or inconsistent data temporarily.

🧠 Conceptual

advanced

Choosing data models for social graph storage

Which data model best supports efficient queries for "friends of friends" in a social graph?

A Relational tables with join queries on user and friendship tables.

B Key-value store with user IDs as keys and friend lists as values.

C Document store with embedded friend lists inside user documents.

D Graph model with nodes representing users and edges representing friendships.

💡 Hint

Consider which model naturally expresses multi-level relationships.

The graph model allows direct traversal of edges to find friends of friends efficiently without expensive joins or lookups.

❓ estimation

expert

Estimating storage requirements for a social graph

Estimate the storage needed to store a social graph with 1 billion users, each having an average of 200 friends. Assume each user ID and friend ID requires 8 bytes, and each friendship is stored bidirectionally.

A Approximately 3.2 terabytes

B Approximately 1.6 terabytes

C Approximately 6.4 terabytes

D Approximately 12.8 terabytes

💡 Hint

Calculate total friendships, multiply by bytes per friendship, and consider bidirectional storage.

1 billion users × 200 friends = 200 billion directed edges (bidirectional storage). Each edge stores two 8-byte IDs = 16 bytes. Total: 200B × 16 bytes = 3.2 TB.

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