System requirements

Functional:

1. Users should be able to send messages to another user.
2. Users should be able to receive messages from another user.
3. Ability for 1-1 chat and also for group chats.
4. The users should be able to view chat history.

Non-Functional:

1. The messages delivery should have low latency.
2. There should be multiple device support - for example - a user can have the same app on his mobile, laptop, ipad etc.
3. Online Presence Indicator - For a logged in or logged out users, his/her friends should be able to see their status.
4. Push Notification for Messages

Capacity estimation

1. Let's assume we have a total of 50 M daily active users, and about 1M concurrent connections.
2. In order to store the chat history, we need to store the chat messages. Assuming an average message size to be 10 kB , total storage required = 10 * 50 M = 500 GB of data.

API design

1. Stateless Service - APIs for login, authentication and notification, and user related services.
2. Stateful Service - Between the client and the chat server. For this , we'll use a Websocket connection. That is a bidirectional connection between the client and the server. It starts off as a HTTP connection initiated by the client and then can be upgraded via a handshake to a Websocket connection.
3. The methods between the client and the server would look like the below
4. The methods used for sending a message

a) createChat()

b) sendMessage()

methods used for group messaging

c)modifyParticiapants

methods used for receiving the chat

d)newMessageReceived

e) updateChat

Database design

For a chat system, the user might want to view the chat history when logged in, which means that, we need to store the chat details in the system. We also need to store further details like participants of a chat (could be 1-1, or group chat)

The Read - Write ratio is 1:1 . The amount of data that we 'll be dealing with is enormous. on an average it could be about 500 gb of data a day. Therefore, for the chat history and messages, we will be using a NoSQL Key-value store, something like DynamoDB. Key-value stores provide low latency to access the data.

1) Chat table - chatid, chat Metadata, created at

2) Messages for 1-1 chat - message id, message from, message to, content, timestamp.

3) Messages for group chat - channel_id, message_id, content, timestmap

4) ChatParticipant - chat_id, participant_id -> this table can fetch all the participants for a specific chat id.

For all the other user information, user settings and friends list etc, we can use a relational database, that will be well suited for this.

High-level design

The main components for the chat system are

1. Chat Servers - Chat servers, where each user will have a persistent websocket connection with the chat server.
2. Clients - The users connected to the chat servers
3. Databases - Relational DB for stroign user login information and user preferences. Key-Vlaue Store like DynamoDB, for storing the chat history.
4. Message Sync Queue or Inbox - for holding the chat messages for users when they are not offline.
5. Zookeeper - For service discovery of the chat servers, and assigning users to a dedicated chat server.
6. Notification Service for push notifications to an user, when the user is offline and a message is received.
7. Presence Servers for the online/offline status of the user.

Request flows

For a 1-1 Chat.

1. User A wants to send a message to User B.
2. User A logs in and once the user is logged in and authenticated, the Service Discovery(ZooKeeper), fetches the chat server for this User A, and this information is passed back to A.
3. User A will connect to Chat Server A via websocket connection.
4. User A creates a chat message and sends to Chat server A. Chat server A will get the mesage Id, from the Id generator.
5. Chat server A places the message in the message sync queue/inbox for B.
6. The chat message is also written to the Key-value store in the message table.
7. If user B is online, the chat message is forwarded to the Chat server B, where B is connected to.
8. If B is offline, then a A push notification will be send to B via the client they are connected. When user B comes online, then all the messages from the Sync Queue are delivered to B to read.

For a Group chat,

1. Instead of putting into 1 queue, the messages are put into the respective message sync queues for all the users in the group.

Detailed component design

1. The connection between Chat server and users is via a websocket connection . Because we need a bidirectional communication between server and client. This connection is a peristent connection too.
2. When a user logs in and authenticated, zookeeper fetches a chat server and assigns User A to that chat server. User A then maintains a persistent websocket connection to that server.
3. Syncing messages between several clients belonging to the same user - So, there is a value called CURR_MAX_MSG_ID, which is maintained by every client. If there is a message that has been synced in the KV store, and has a message id which is larger than the curr_max_msg_id, then that is a new message.
4. The message id is a unique id, and is supposed to be increasing with every new message. This message id is generated using s unique id sequence generator mechanism, something like Snowflake (64-bit-sequence-number generator)
5. The online presence servers detect the online/offline status of the users. This can be done using a heartbeat mechanism. When a user is connected via a client, they send a periodic heartbeat to the presence server. If the server receives the heartbeat , that means the client is online, however if within x seconds the heartbeat is not received, that means they have gone offline.
6. To broadcast the status to the friend groups of an user, the Presence server use a publish-subscribe model, where they publish A's online status to the several channels that is maintained between every friend group that A has. The friends B, C, D are subscribed to the respective channels, and when the status changes are received on the channel, they can read the updates from that channel.

Trade offs/Tech choices

1. No SQL database for KV store - better than relational DB. relational DB don't provide low latency as the data keeps on increasing. (for chat history)

Failure scenarios/bottlenecks

Horizontal scaling across all servers.

Sharding in the NoSQL database - KV store, the channel id is parition key in case of group messages, and the pariticipant id is parition in case of chat participant information.

Future improvements

1. Handling media attachements over chat.
2. Using Redis Pub/Sub model instead of zookeeper for efficient allocation of chat servers and usage amongst users.
3. Caching recent messages at client side.
4. geographically distributed network for caching user's data and channel information