Requirements

Functional Requirements:

1. User can send and receive messages
2. User can get notifications when offline
3. User can add friends and remove friends
4. User can create a group chat

Non-Functional Requirements:

1. Availability, the system should be up for 99.99% time.
2. Scalability, should support 100M users, 10M online users at the same time.
3. Low latency, less than 500ms for receive and send.
4. Reliability, no message loss.
5. Message ordering, eventual ordering is acceptable.
6. Keep chat history for 7 years.

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

We can use REST API to add and remove friends, create groups:

1. Post v1/CreateGroup, body: {group_id: id, member: user_ids, timestamp: time}
2. Post v1/DeleteGroup, body: {group_id:id, timestamp: time}
3. Post v1/Add, body: {id: user_id, timestamp: time}
4. Post v1/Remove, body: {id: user_id, timestamp: time}

We can use WebSocket to send and poll message when the user is online instead of REST API:

1. v1/send, body: {sender: user_id, receiver: group_id, message: text, timestamp: time}
2. v1/get: body: {groups:group_id_list, timestamp: time}

We can use server side event to push notifications to clients when user is offline:

1. v1/notify, body: {receiver: user_id, timestamp: time}

High-Level Design

Sending and receiving path:

When users get online, they first connect to API gateway to authenticate, rate limit, security check etc. And keep the connection with message service via WebSocket to send and receive incoming messages.

When sent a message, message service insert the record into the message table, message tables look like:

Message table schema:

message_id,

group_id,

content,

status (pending, delivered),

timestamp

Once a message is inserted into the message table, the service push it into a delivery queue, the delivery workers will pop it and deliver it to the receiver. Worker gets the member list of the group and based on the registration table to find all message service node for the members belong to this group.

Note, for large group, e.g. a group contains 10k members, we can use pub sub. Each message service subscribes the topics (topic is the group id) from the users who are connected to this node. So that when there is a new message for a group, the nodes can receive the message from pub sub.

Registration table is to keep which message service instance a user is connecting to. When user connect to a message service it should update the registration table, and ping registration service every 10 seconds to update the current connection status.

Registration table, it can be stored in in-memory database:

user_id->service_id

Once the delivery worker successfully deliver the message to the receiver, it updates the message table to change the status from pending to deliver.

If a user is offline, the delivery worker will push the information to notification service whose job is to push a notification to the offline user.

Create groups path:

User can create a group via user service, the group table looks like below

Group table schema:

group_id,

members,

created_time,

Note, direct message can be treated as a group that contains only two users.

Deal with reconnection:

If an offline user becomes online, the client pulls all messages since last seen message from database. For example, using the v1/get REST API which includes the user_id and last seen message_id.

The database retrieves all messages like:

select * from message where user_id = X and message_id > Y

Database Design

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...

Detailed Component Design

A pool of message service nodes whose number is changed based on the concurrent online users. And the API gateway is responsible for load balancing the connection. (When reconnect, we can use a shared session that is stored in redis)

Each single message is persistent in the database, so there won't be message loss. The database is replicated into 3 pieces, 2 are in different regions of the same continent and 1 is in another continent. Message retention is configurable, say 7 years by default.

Message service generates unique message id which is increasing. So that client can pull missing messages based on last_seen_message_id.

When an online user gets messages for example, 1,3,4. Because the network latency 2 is not arriving on time or lost because of network issues. The client can pull all messages from database and then show the messages in order to users.