Design the data structures for a social network
Design the data structures for a social network
Step 1: Outline use cases and constraints
Use cases
User searches for someone and sees the shortest path to the searched person
Service has high availability
Constraints and assumptions
State assumptions
Traffic is not evenly distributed
Some searches are more popular than others, while others are only executed once
Graph data won't fit on a single machine
Graph edges are unweighted
100 million users
50 friends per user average
1 billion friend searches per month
Calculate usage
5 billion friend relationships
100 million users * 50 friends per user average
400 search requests per second
Handy conversion guide:
2.5 million seconds per month
1 request per second = 2.5 million requests per month
40 requests per second = 100 million requests * per month
400 requests per second = 1 billion requests per month
Step 2: Create a high level design
Step 3: Design core components
Use case: User searches for someone and sees the shortest path to the searched person
Without the constraint of millions of users (vertices) and billions of friend relationships (edges), we could solve this unweighted shortest path task with a general BFS approach:
The Client sends a request to the Web Server, running as a reverse proxy
The Web Server forwards the request to the Search API server
The Search API server forwards the request to the User Graph Service
The User Graph Service does the following:
Uses the Lookup Service to find the Person Server where the current user's info is stored
Finds the appropriate Person Server to retrieve the current user's list of
friend_ids
Runs a BFS search using the current user as the
source
and the current user'sfriend_ids
as the ids for eachadjacent_node
To get the
adjacent_node
from a given id:The User Graph Service will again need to communicate with the Lookup Service to determine which Person Server stores the
adjacent_node
matching the given id (potential for optimization)
Note: Error handling is excluded below for simplicity. Ask if you should code proper error handing.
Lookup Service implementation:
Person Server implementation:
Person implementation:
User Graph Service implementation:
We'll use a public REST API:
Response:
Step 4: Scale the design
Important: Do not simply jump right into the final design from the initial design!
It's important to discuss what bottlenecks you might encounter with the initial design and how you might address each of them. For example, what issues are addressed by adding a Load Balancer with multiple Web Servers? CDN? Master-Slave Replicas? What are the alternatives and Trade-Offs for each?
We'll introduce some components to complete the design and to address scalability issues. Internal load balancers are not shown to reduce clutter.
Below are further optimizations:
Store complete or partial BFS traversals to speed up subsequent lookups in the Memory Cache
Batch compute offline then store complete or partial BFS traversals to speed up subsequent lookups in a NoSQL Database
Reduce machine jumps by batching together friend lookups hosted on the same Person Server
Do two BFS searches at the same time, one starting from the source, and one from the destination, then merge the two paths
Set a limit based on time or number of hops before asking the user if they want to continue searching, as searching could take a considerable amount of time in some cases
Additional talking points
Additional topics to dive into, depending on the problem scope and time remaining.
SQL scaling patterns
NoSQL
Caching
Where to cache
What to cache
When to update the cache
Asynchronism and microservices
Communications
Discuss tradeoffs:
Security
Latency numbers
Ongoing
Continue benchmarking and monitoring your system to address bottlenecks as they come up
Scaling is an iterative process
Last updated
Was this helpful?