Social graph storage in HLD - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a social graph in system design?

A social graph is a representation of users as nodes and their relationships (like friendships or follows) as edges connecting these nodes.

intermediate

Why is graph database often preferred for social graph storage?

Graph databases efficiently store and query relationships between entities, making it easier to traverse connections like friends-of-friends quickly.

intermediate

What is the main challenge in scaling social graph storage?

Handling a large number of users and their connections while maintaining fast query response times and data consistency.

advanced

Explain the difference between adjacency list and adjacency matrix in social graph storage.

Adjacency list stores neighbors for each node, saving space for sparse graphs. Adjacency matrix uses a 2D array to represent connections, which is space-heavy but allows quick edge checks.

intermediate

What is sharding in the context of social graph storage?

Sharding means splitting the graph data across multiple servers or databases to distribute load and improve scalability.

Which database type is best suited for storing social graphs?

A Key-value store

B Relational database

C Graph database

D Document database

Graph databases are designed to efficiently handle relationships and traversals common in social graphs.

What does an edge represent in a social graph?

A A relationship between users

B A server node

C A database shard

D A user

Edges connect nodes (users) and represent their relationships.

Which data structure is more space-efficient for sparse social graphs?

A Adjacency matrix

B 2D array

C Hash map

D Adjacency list

Adjacency lists store only existing connections, saving space when many nodes have few edges.

What is a common method to scale social graph storage?

A Sharding

B Indexing

C Caching

D Compression

Sharding splits data across servers to handle large scale and load.

Which query is typical in social graph systems?

A Calculate sum of user ages

B Find all friends of a user

C Retrieve user passwords

D Sort users by name

Social graph queries often involve traversing relationships like friends or followers.

Describe how you would design a scalable social graph storage system.

Think about how to store users and their connections efficiently and how to keep the system fast as it grows.

Explain the advantages and disadvantages of adjacency list vs adjacency matrix for social graph storage.

Compare space usage and query speed for both data structures.

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