Requirements

Functional Requirements:

• Determine the shortest connection path in terms of hops between two users in the professional network.
• Enable users to discover how they are connected with another user, showing first-degree, second-degree, and further connections.
• Suggest potential contacts based on mutual connections between users.
• Enable users to search for users in the network and view their connection path to the current user.

Non-Functional Requirements:

• Users should be able to view the number of connections between 2 users with minimal latency. The p99 latency should be less than 100ms.
• Users should be able to search for other users with a p99 latency of less than 100ms.
• The service should be available for 99.99% of time.
• Assuming the connections between 2 users, including the number of hops and details of the hop, is 1KB, and assuming 1 billion MAU. We need 1 TB of storage for the service.
• Assuming 1 billion MAU, we will need to handle up to 1500 peak read QPS, and around 300 write QPS.

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

For the API to view connection detail between 2 users, including the number of hops and the shortest connection path:

GET v1/view_connection_details {

current_user_id: UUID,

user_id_B: UUID,

}

For the API to add new connections between users:

POST v1/add_new_connection {

current_user_id: UUID,

user_id_B: UUID,

}

For the API to search for users in the network and retrieving user profiles:

GET v1/search_user {

user_id: UUID,

search_keywords: String

}

For the API to recommend potential contacts based on mutual connections:

GET v1/suggest_potential_contacts {

user_id: UUID

}

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

The core of this design is a graph database like Neo4j. Each user is a node in the graph, and each edge is a connection between users.

Schema could be defined like this:

Node user {

user_id: UUID,

user_name: String,

user_metadata: String

}

Edge connection {

user_id_A: UUID,

user_id_B: UUID

}

With a graph database, we store users as nodes and connections as edges. We can leverage the graph database to calculate the shortest connection path between 2 users, as well as the number of nodes between 2 users in minimal latency.

For the write path, when we create a new user, we send traffic to user feed service and user connection service. We do 3 things:

1. User feed service writes the user profile metadata to a relational database. The relational database also has a caching layer, which is a redis cluster. In this case, we will use a write through cache, so results are synchronously written to the database and cache. While this increases our write latency, the tradeoff is we can ensure durability and consistency of data when writing to and reading from the cache. For the database cluster, we can create replicas to ensure higher availability. The data is written to any replica, and later propagated to other replicas. While the system is eventually consistent, it reduces read latency and increases availability. It is an acceptable tradeoff for user profile update, which doesn't require the most fresh data.
2. User feed service also triggers an event on Kafka queue, to write the new user profile to ElasticSearch index. We have an index writer service that aggregates the events received, and batch write to ElasticSearch. This will support search of users in the network.
3. User connection service also receives the request upon new user profile creation. It writes a new node to the user connection graph database. The graph database also has replicas for horizontal scalability. We asynchronously propagate writes to all replicas. In this case, we have eventual consistency as a tradeoff, but we get faster writes and high availability. From business perspective, It is acceptable for new user profile creation to be eventually consistent.

For the write path, when we add a new user connection, we need to trigger 2 flows from user connection service:

1. We write an edge between the 2 users, in the user connection graph database. The graph database also has replicas for horizontal scalability. We asynchronously propagate writes to all replicas. In this case, we have eventual consistency as a tradeoff, but we get faster writes and high availability. From business perspective, It is acceptable for new connection creation to be eventually consistent.
2. We trigger an event on Kafka queue, which gets consumed by a ML model training service. We have a productionized ML model that suggest potential contacts based on connections between users. We will need to ingest new connection events into its training data, so the model is fresh and relevant.

For the read path, when we want to view connections between 2 users, or see the shortest path of connection, we query the user connection graph database, and get back results for these queries. Once we have the user_ids, we trigger a request to user feed service, to retrieve the user profile from redis cluster. On cache misses, we query the relational database under it.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

The core of this design is a graph database like Neo4j. Each user is a node in the graph, and each edge is a connection between users.

Schema could be defined like this:

Node user {

user_id: UUID,

user_name: String,

user_metadata: String

}

Edge connection {

user_id_A: UUID,

user_id_B: UUID

}

With a graph database, we store users as nodes and connections as edges. We can leverage the graph database to calculate the shortest connection path between 2 users, as well as the number of nodes between 2 users in minimal latency.

For the write path, when we create a new user, we send traffic to user feed service and user connection service. We do 3 things:

1. User feed service writes the user profile metadata to a relational database. The relational database also has a caching layer, which is a redis cluster. In this case, we will use a write through cache, so results are synchronously written to the database and cache. While this increases our write latency, the tradeoff is we can ensure durability and consistency of data when writing to and reading from the cache. For the database cluster, we can create replicas to ensure higher availability. The data is written to any replica, and later propagated to other replicas. While the system is eventually consistent, it reduces read latency and increases availability. It is an acceptable tradeoff for user profile update, which doesn't require the most fresh data.
2. User feed service also triggers an event on Kafka queue, to write the new user profile to ElasticSearch index. We have an index writer service that aggregates the events received, and batch write to ElasticSearch. This will support search of users in the network.
3. User connection service also receives the request upon new user profile creation. It writes a new node to the user connection graph database. The graph database also has replicas for horizontal scalability. We asynchronously propagate writes to all replicas. In this case, we have eventual consistency as a tradeoff, but we get faster writes and high availability. From business perspective, It is acceptable for new user profile creation to be eventually consistent.

For the write path, when we add a new user connection, we need to trigger 2 flows from user connection service:

1. We write an edge between the 2 users, in the user connection graph database. The graph database also has replicas for horizontal scalability. We asynchronously propagate writes to all replicas. In this case, we have eventual consistency as a tradeoff, but we get faster writes and high availability. From business perspective, It is acceptable for new connection creation to be eventually consistent.
2. We trigger an event on Kafka queue, which gets consumed by a ML model training service. We have a productionized ML model that suggest potential contacts based on connections between users. We will need to ingest new connection events into its training data, so the model is fresh and relevant.

For the read path, when we want to view connections between 2 users, or see the shortest path of connection, we query the user connection graph database, and get back results for these queries. Once we have the user_ids, we trigger a request to user feed service, to retrieve the user profile from redis cluster. On cache misses, we query the relational database under it.