System requirements
Functional:
- Find Shortest Connection Path: The system should determine the shortest connection path (in terms of hops) between two users in the professional network.
- Connection Discovery: Users should be able to discover how they are connected with another user (first-degree, second-degree, etc.).
- Query for Potential Connections: The system should provide a way to suggest potential contacts based on mutual connections.
- Real-time Queries: The system should return results in real-time (or near real-time) for queries.
- Profile Search: A search feature should be available to find users in the network and view their connection path.
- Scalable Architecture: The system should be able to scale as the user base and connections grow.
- API for External Access: Provide APIs for third-party applications to access connection paths between users.
Non-Functional:
- Scalability: The system must handle up to 1 million users with an average of 200 connections per user.
- Low Latency: Query response time should be under 1 second, even under peak loads (up to 1000 queries per second).
- Availability: The system must ensure 99.99% uptime and be fault-tolerant.
- Consistency: Ensure that the data is eventually consistent, with up-to-date connections visible as they are made.
- Data Privacy: Handle user data securely, ensuring that users only see connection paths they are authorized to view.
- Fault Tolerance: The system should handle hardware failures, network issues, and handle automatic recovery in case of a crash.
Capacity estimation
o estimate capacity, we can use the following assumptions:
- Users: 1 million users.
- Average Connections per User: 200 connections per user.
- Peak Queries per Second (QPS): Up to 1000 queries during peak time.
Storage Estimation
We assume that the connections are stored as an adjacency list or graph structure in a database. Each connection consists of two user IDs, so the required storage space can be calculated as:
- Total Connections: 1,000,000×200=200,000,0001,000,000 \times 200 = 200,000,0001,000,000×200=200,000,000 connections.
- Each connection entry: Assuming each user ID is 8 bytes (64-bit), a connection between two users requires 16 bytes.
- Total Storage for Connections: 200,000,000×16 bytes≈3.2 GB200,000,000 \times 16 \text{ bytes} \approx 3.2 \text{ GB}200,000,000×16 bytes≈3.2 GB.
We need to allocate additional space for indexing, metadata, and other entities, such as user profiles. Estimating around 50% overhead, the total space required for storing connections and metadata would be approximately 4.8-5 GB.
API design
- Find Shortest Connection Path
- Add New Connection
- Search for User
Database design
High-level design
We can break the system into the following components:
- API Gateway: Handles user requests and routes them to the appropriate microservices.
- Graph Processor: The service that calculates shortest paths between users.
- User Service: Manages user data, including profiles and connections.
- Graph Database: Stores the graph structure of user connections.
- Cache Layer: For faster retrieval of frequently queried connection paths.
Request flows
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Detailed component design
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Trade offs/Tech choices
Explain any trade offs you have made and why you made certain tech choices...
Failure scenarios/bottlenecks
Try to discuss as many failure scenarios/bottlenecks as possible.
Future improvements
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?