System requirements

Functional:

1. 1:1 chat. Real time typing indicator. See message status. Delete message.
2. Group chat with 100 people.
3. Search for message in chat
4. Store message for 1 year
5. Push notification if user is not in app.

Non-Functional:

1. Recipient in app should see message within 300ms.
2. Typing indicator should be shown within 300ms.

Capacity estimation

500M DAU. 100M concurrent users at peak. User sends 1 message every 10 minutes = 10M/min = 200k/sec.

Storage costs: 10M/min * 60 min * 24hr * 365d = 4,000,000,000,000/year * 1kb = 4TB

API design

Use websockets.

Message:

{

"type: "sendMessage",

"text": string

}

{

"type: "receivedMessage",

"text": string

"from": userId

"timestamp": timestamp

}

Status update (to client)

{

"type": "sendStatus",

"status": enum

}

Typing indicator (from/to client):

{

"type": "typing",

}

Delete message:

{

"type: "deleteMessage",

"messageId": string

}

Search message uses REST.

GET /searchMessage

{

chatId: int

query: string

}

Database design

We will use a document store to store all the messages as the write traffic will be high and a lot of data needs to be written. The key will be the message id and the document will contain chat id and sender and message text and timestamp. There will also be a collection where the key is chat id and the document contains the set of user ids.

High-level design

We will have a web tier to initially route client requests on start up. It will be behind a load balancer. We will have stateless chat servers that clients can attach a Websocket connection to. For real-time chat, clients connect to the same chat server. We have a Redis cache to map chat id to chat server. For users that are offline, messages are sent async to a queue read by a push notification service. The service also writes the message to the database.

Request flows

1. Client initializes by querying the web tier for chat ids that this user has participated in. They can also create new chats this way. Web tier uses chat server cache to map chat id to chat server. Searching chat is also done through web tier.
2. When clicking into a specific chat id, the client connects to the chat server via websocket. It can now send and receive messages in real time.
3. For messages sent to offline user, they are sent to message queue then read by push service which sends push notification.

Detailed component design

Chat servers scale horizontally as they gain/lose ownership of chat ids. Chat server sends heartbeat to connected clients. If no clients are connected to a chat for some time, it gives up ownership of the chat id.

The chat server decides the timestamp of messages. So, all clients will see the same ordering of messages.

Message queue is designed to minimize chat loading latency and database hits when people check chats after getting push notification, which is very common. However, if the queue gets too long or hasn't been read in a long time, the data can be dropped. Then the client will have to query new message from the database when they finally reconnect.

Trade offs/Tech choices

Using a document database improves write scalability, but it may make it more difficult to do joins of data if needed. Uncommon operations like searching chats may be slow. We may need some chat indexing service to make that more efficient.

Failure scenarios/bottlenecks

Initial loading of chats may be slow as there are multiple steps.

Future improvements

Add a search indexing tier. Add a manager service to monitor health of chat servers and redistribute load accordingly.