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.

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:

We need high ACID guarantees for a messenger app, we can't have different clients of the same user seeing a different version of chat history if they log on at the same time.
We could have complex join queries based on business needs, across groups and users table, which a relational database inherently supports.

The tradeoffs are:

Compared to cassandra, we won't as scalable and support huge write throughput easily. However, we can still scale through sharding and replication.
Compared to document database, we won't be as scalable or have flexible data schema. However, our data schema doesn't change that often.

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<String>,

message_metadata: String,

is_archived: Boolean

}

Here's the table that stores groups:

table groups {

group_id: UUID,

group_admin_ids: List<UUID>,

group_member_ids: List<UUID>,

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.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10