Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 1 billion DAU, peak QPS for viewing messages will be around 25000 QPS, and for sending messages it will be around 9000 QPS.
If we have a total of 2 billion users, and for each user, we have an average of 100 messages, where each message needs 1KB of text and metadata, we will need 200TB of database storage.
Also, for 2 billion users, assume we have 20 million groups. For each user and group, metadata storage takes 1 MB, we will need 2PB of storage.
Assume for each user, we also store on average 10MB of media files, then we need 20PB of file storage.
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 sending a message:
POST v1/send_message {
user_id: UUID,
target_user_id: UUID,
target_group_id: UUID,
message_content: String,
message_media_links: List
}
For viewing messages:
GET v1/view_messages {
user_id: UUID,
target_user_id: UUID,
target_group_id: UUID,
}
For creating/deleting groups:
PUT v1/create_group {
group_creator_id: UUID,
group_name: String,
group_category: String,
group_member_ids: List
group_admin_ids: List
}
DELETE v1/delete_group {
group_owner_id: UUID,
group_id: UUID
}
For inviting/removing people to groups:
POST v1/add_group_user {
group_id: UUID,
user_id: UUID
}
POST v1/remove_group_user {
group_id: UUID,
group_user_id: UUID
}
For accepting an invite to join a group chat:
POST v1/accept_invite {
inviter_user_id: UUID,
group_id: UUID,
invited_user_id: UUID
}
For server to deliver real time messages to clients:
POST v1/send_message {
target_user_id: UUID,
sender_user_id: UUID,
message_id: UUID
}
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.
First of all, all the requests from the client to the server go through API gateway, that does login authorization, authentication for following requests, and rate limiting for each user based on user identification/IP/client. Then we hit load balancer, which routes request evenly to different servers of chat service using consistent hashing.
Whenever a user logins, we establish a websocket connection with the client. This ensures that any messages received on the server can be sent to the client in real time. In the event of a WebSocket disconnection, the client will utilize a resume token or last message ID to reconnect to the server. Upon re-establishing the connection, the server will check the last acknowledged message from the client and send any missed messages that were delivered during the disconnection period. This ensures that users do not experience gaps in their message history, maintaining a seamless user experience even during network interruptions.
To effectively handle large spikes in group chat activity, the system will implement a pub/sub architecture using a message broker such as Kafka. When a message is sent to a group, it will be published to a topic corresponding to that group. All subscribed clients will receive the message without overloading a single WebSocket node, allowing for efficient scaling during peak times. This design choice ensures that the system can handle high message throughput while maintaining responsiveness and reliability.
When user sends a message, either to another user or to a group, it goes to the chat service. We do 2 things in this case, we write to the redis cluster, which also writes to the relational database, and we sends the request through websocket to the associated clients.
Here, we use the redis cluster as a write through cache, so any message sent will be written synchronously to both the cache and the database. In messenger apps, we need to ensure durability and consistency of messages sent by the user, so we need to use a write through cache, with tradeoff of higher latency. In case of cache failures, database cluster will serve as source of truth, handling all reads and writes until the cache comes back online and is synced with the database. To clarify, in our system, the cache is advisory only. It is not durable. In failure, we can still get the updated information from the database. It is only added to improve performance.
For the media that was sent with the message, we upload the image/video etc. to object storage, and cache it in CDN, and provide the CDN link.
When user creates a group, we write to the relational database as well through the user/group service.
When user tries to read messages from another user, or from a group, we serve the messages in chronological order from the redis cache. In case of redis cache miss, we query the relational database for the chat history in this group/with this user for the past year. The caching helps us with repeated reads with the TTL.
However, since our QPS and storage size is very large, we need to use sharding and replication in our relational database.
For sharding, we will shard by sender's user_id. This way, requests to view messages from the same user will hit the same database shard.
To handle the huge throughput, we will also create read/write replicas for the messages table. To ensure consistency such that 2 concurrent requests from different clients will same the same message history, we will use a quorum approach with W + R > N. In this case, we ensure that at least 1 table replica will have the latest data, and we have strong consistency. The tradeoff is relatively slower reads and writes from the database.
In our system, we need to make sure that different users see messages in the exact same order, and in the correct order. For example, if two users are chatting to each other and are typing and sending messages at the same time, and one of the server has clock skew, causing a later timestamp for messages in that server, the ordering could then be wrong for the messages. In this case, we implement NTP, for servers to sync the messages over the Internet, to avoid too much of a time gap.
In this case, since the read never reads stale data, and the messages are ordered chronologically, different users should see the same set of messages in the same order.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
There are 3 tables that we need to manage, the table to store messages, the table to store users, and the table to store groups.
We will use a relational SQL database for the messenger app, the main reasons are:
The tradeoffs are:
Here's the table that stores users:
table users {
user_id: UUID,
user_name: String,
profile_picture_link: String,
user_bio: String,
}
Here's the table that stores messages:
table messages {
sender_user_id: UUID,
receiver_user_id: UUID,
sent_at: Timestamp,
group_id: UUID,
message_content: String,
message_media_links: List
message_metadata: String,
is_archived: Boolean
}
Here's the table that stores groups:
table groups {
group_id: UUID,
group_admin_ids: List
group_member_ids: List
group_type: String,
group_description: String,
}
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
There are 3 tables that we need to manage, the table to store messages, the table to store users, and the table to store groups.
We will use a relational SQL database for the messenger app, the main reasons are:
The tradeoffs are:
Here's the table that stores users:
table users {
user_id: UUID,
user_name: String,
profile_picture_link: String,
user_bio: String,
}
Here's the table that stores messages:
table messages {
sender_user_id: UUID,
receiver_user_id: UUID,
sent_at: Timestamp,
group_id: UUID,
message_content: String,
message_media_links: List
message_metadata: String,
is_archived: Boolean
}
Here's the table that stores groups:
table groups {
group_id: UUID,
group_admin_ids: List
group_member_ids: List
group_type: String,
group_description: String,
}
First of all, all the requests from the client to the server go through API gateway, that does login authorization, authentication for following requests, and rate limiting for each user based on user identification/IP/client. Then we hit load balancer, which routes request evenly to different servers of chat service using consistent hashing.
Whenever a user logins, we establish a websocket connection with the client. This ensures that any messages received on the server can be sent to the client in real time. In the event of a WebSocket disconnection, the client will utilize a resume token or last message ID to reconnect to the server. Upon re-establishing the connection, the server will check the last acknowledged message from the client and send any missed messages that were delivered during the disconnection period. This ensures that users do not experience gaps in their message history, maintaining a seamless user experience even during network interruptions.
To effectively handle large spikes in group chat activity, the system will implement a pub/sub architecture using a message broker such as Kafka. When a message is sent to a group, it will be published to a topic corresponding to that group. All subscribed clients will receive the message without overloading a single WebSocket node, allowing for efficient scaling during peak times. This design choice ensures that the system can handle high message throughput while maintaining responsiveness and reliability.
When user sends a message, either to another user or to a group, it goes to the chat service. We do 2 things in this case, we write to the redis cluster, which also writes to the relational database, and we sends the request through websocket to the associated clients.
Here, we use the redis cluster as a write through cache, so any message sent will be written synchronously to both the cache and the database. In messenger apps, we need to ensure durability and consistency of messages sent by the user, so we need to use a write through cache, with tradeoff of higher latency. In case of cache failures, database cluster will serve as source of truth, handling all reads and writes until the cache comes back online and is synced with the database. To clarify, in our system, the cache is advisory only. It is not durable. In failure, we can still get the updated information from the database. It is only added to improve performance.
For the media that was sent with the message, we upload the image/video etc. to object storage, and cache it in CDN, and provide the CDN link.
When user creates a group, we write to the relational database as well through the user/group service.
When user tries to read messages from another user, or from a group, we serve the messages in chronological order from the redis cache. In case of redis cache miss, we query the relational database for the chat history in this group/with this user for the past year. The caching helps us with repeated reads with the TTL.
However, since our QPS and storage size is very large, we need to use sharding and replication in our relational database.
For sharding, we will shard by sender's user_id. This way, requests to view messages from the same user will hit the same database shard.
To handle the huge throughput, we will also create read/write replicas for the messages table. To ensure consistency such that 2 concurrent requests from different clients will same the same message history, we will use a quorum approach with W + R > N. In this case, we ensure that at least 1 table replica will have the latest data, and we have strong consistency. The tradeoff is relatively slower reads and writes from the database.
In our system, we need to make sure that different users see messages in the exact same order, and in the correct order. For example, if two users are chatting to each other and are typing and sending messages at the same time, and one of the server has clock skew, causing a later timestamp for messages in that server, the ordering could then be wrong for the messages. In this case, we implement NTP, for servers to sync the messages over the Internet, to avoid too much of a time gap.
In this case, since the read never reads stale data, and the messages are ordered chronologically, different users should see the same set of messages in the same order.