System requirements

Functional:

1. Find Shortest Connection Path: The system should determine the shortest connection path (in terms of hops) between two users in the professional network.
2. Connection Discovery: Users should be able to discover how they are connected with another user (first-degree, second-degree, etc.).
3. Query for Potential Connections: The system should provide a way to suggest potential contacts based on mutual connections.
4. Real-time Queries: The system should return results in real-time (or near real-time) for queries.
5. Profile Search: A search feature should be available to find users in the network and view their connection path.
6. Scalable Architecture: The system should be able to scale as the user base and connections grow.
7. API for External Access: Provide APIs for third-party applications to access connection paths between users.

Non-Functional:

1. Scalability: The system must handle up to 1 million users with an average of 200 connections per user.
2. Low Latency: Query response time should be under 1 second, even under peak loads (up to 1000 queries per second).
3. Availability: The system must ensure 99.99% uptime and be fault-tolerant.
4. Consistency: Ensure that the data is eventually consistent, with up-to-date connections visible as they are made.
5. Data Privacy: Handle user data securely, ensuring that users only see connection paths they are authorized to view.
6. 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:

1. API Gateway: Handles user requests and routes them to the appropriate microservices.
2. Graph Processor: The service that calculates shortest paths between users.
3. User Service: Manages user data, including profiles and connections.
4. Graph Database: Stores the graph structure of user connections.
5. 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?