Social graph storage in HLD - Scalability & System Analysis

Scalability Analysis - Social graph storage

Growth Table: Social Graph Storage

Scale	Users	Connections (Edges)	Storage Needs	Query Load	System Changes
Small	100 users	~10K edges	Few MBs	Low QPS (10s)	Single DB instance, simple graph model
Medium	10K users	~1M edges	GBs	Hundreds QPS	Indexing, caching, read replicas
Large	1M users	~100M edges	100s GBs to TBs	Thousands QPS	Sharding, graph DB or specialized storage, distributed cache
Very Large	100M users	~10B edges	Multiple TBs to PBs	Hundreds of thousands QPS	Multi-region clusters, advanced partitioning, CDN for metadata, asynchronous processing

First Bottleneck

At small scale, the database handles all queries easily. As users grow to millions, the database storage and query performance become the first bottleneck. This is because social graphs have many connections per user, causing large, complex queries that slow down the DB. Also, single DB instances cannot handle the volume of reads/writes.

Scaling Solutions

• Horizontal scaling: Add more database servers and shard data by user ID or graph partition to distribute load.
• Caching: Use in-memory caches (e.g., Redis) for frequent queries like friend lists to reduce DB hits.
• Graph databases: Use specialized graph DBs (e.g., Neo4j, JanusGraph) optimized for relationship queries.
• Read replicas: Separate read and write traffic to improve throughput.
• Asynchronous processing: For heavy computations (e.g., recommendations), use background jobs to avoid blocking user queries.
• CDN and edge caching: Cache user profile metadata near users to reduce latency.

Back-of-Envelope Cost Analysis

Assuming 1M users with average 100 connections each:

• Edges: 100M connections
• Storage: If each edge record is ~100 bytes, total ~10GB just for edges (excluding indexes and metadata)
• Requests per second (QPS): For 1M users, assume 0.01 QPS per user -> 10K QPS total
• Bandwidth: If each query returns ~1KB, 10K QPS -> ~10MB/s bandwidth
• Server capacity: One DB instance handles ~5K QPS, so at 10K QPS need at least 2 DB servers or read replicas

Interview Tip

Start by defining the scale and data model. Then identify the bottleneck (usually DB). Discuss how to partition data and use caching. Mention trade-offs between consistency and availability. Finally, explain how to handle read/write loads separately and use asynchronous processing for heavy tasks.

Self Check Question

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Add read replicas to distribute read traffic and reduce load on the primary DB. Also, implement caching for frequent queries to reduce DB hits. If writes grow, consider sharding data to multiple DB instances.

Key Result

Social graph storage scales from simple single DB setups at small user counts to complex sharded, cached, and distributed graph databases at large scale, with the database becoming the first bottleneck as user connections grow exponentially.

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