System requirements

We assume here that the unique identifier of a user is their username

Functional:

• You should be able to send messages to another user through their username
• You should be able to receive messages from other users
• You should be notified of a new message when you are not using your app
• You should be able to see whether your messages have been read by the other user

Non-Functional:

• Users should have real-time chat experience with little latency
• System should be consistent, users should have the same chat history
• System should be reliable, chat messages should not go missing
• System should be available, this assumes that people are using the app every hour, every minute

Capacity estimation

Assumptions

• 100 million total users, 50 million daily users.
• A user sends 100 messages a day
• We keep text messages for up to 10 years

Data entities

• User
• ID (4 bytes)
• username (4 bytes)
• password (4 bytes)
• online (2 bytes)
• Text messages
• ID (4 bytes)
• sent_by (4 bytes)
• sent_to (4 bytes)
• content (1000 bytes)
• sent_time (4 bytes)
• opened (1 byte)

Storage estimation

• Users = 100 million * 12 bytes = 1.2 GB
• Texts = 50 million * 100 * 365 * 10 * (1036 bytes) = 16.8 PB

Traffic Estimation

• 5000 million texts / day = 210 million / hr = 3.5 million / min = 60000 / second = 60MB / second. Read and Write bandwidths will be the same

API design

• send_message(user_id, target_id, content) - This basically sends the target user a message
• open_chat(user_id, target_id) - Opens the chat between user_id and target_id
• retrieve_chat_history(user_id, target_id) - retrieves chat history between user_id and target_id
• send_notification(user_id) - sends a notification to user_id

Database design

Although the two data entities are related, the relationship is not complex at all, hence we won't be able to fully benefit from using SQL databases.

We will definitely benefit from using databases that are easily scalable horizontally as our app becomes more and more popular, we would need to store even more messages. This is where NoSQL databases like MongoDB are useful because they are easily scalable. HOWEVER, because we will constantly need to retrieve messages from the DB, this will potentially cause high latency, which is not what we want..

So we want our Database to be fast and scalable at the same time. Both of our requirements can be easily met with a wide-column database solution like HBase. HBase is a column-oriented key-value NoSQL database that can store multiple values against one key into multiple columns. HBase is modeled after Google’s BigTable and runs on top of Hadoop Distributed File System (HDFS). HBase groups data together to store new data in a memory buffer and, once the buffer is full, it dumps the data to the disk. This way of storage not only helps storing a lot of small data quickly, but also fetching rows by the key or scanning ranges of rows. HBase is also an efficient database to store variably sized data, which is also required by our service.

Request flows

When a user enter their application, a WebSocket is established between the user and a server, the server then changes the online status of a user to true in the database. The server will continually send heartbeat checks through the WebSocket to check whether a user is online, if there is no response, then the server will change their status to false.

When a user sends a message to a target user, the server will first store the message in the DB, once successful the server will check whether a user is online, if they are online, then the server will mark the message as opened, then send the message over to the target user through the websocket, the server will also send a 'opened' indication to the user. If the user is offline then the server will send a notification to the target user

When a user opens_chat between themselves and another user, all unopened messages are changed to open, the 'opened' indicators of the recently opened messages are then sent to the other user, if the other user is online.

High-level design

Client -> Load Balancers -> Backend Server -> NoSQL DB

We will have load balancers to distribute the load between multiple servers

Detailed component design

In order to reliably check whether a user is online, the server has to constantly check whether the user is using their application. This can be done by establishing a WebSocket when a user uses the application and then sending regular heartbeat checks and awaiting their response. This can actually incur quite a bit of overhead, hence we will have dedicated servers to check whether a user is online and update the User Table in the DB accordingly.

Secondly, how can we ensure that two users will have the same chat history? Whenever a user opens a chat, they will be ordered according to time stored in the DB. If a user has their chat opened between themselves and another user, a little bit of variation is okay, as long as when they re-open the chat the messages are ordered in terms of time.

How can we ensure that when a user loads chat history that it would not be slow? Firstly, we will not load the whole chat history between users, we will do them in increments, every 20 messages or so. When a user calls open_chat(user_id, target_id) a server will start generating a Linked List of messages, with one message leading to the next message. This linked list will be kept in memory for each chat, the LinkedList shall not be longer than 100 messages at any time.

What we could potentially do is for every user, we can keep 10 messages from each of the 5 most recently used chats, in memory. That way, even when a user loads up a chat, it can be retrieved very quickly. This service will also be quite intensive, hence we will use type of server dedicated to loading chat histories.

How do we distribute the data? We will simple distribute the data in terms of the user_id, meaning that the texts are stored in terms of the user who sent it. This is a good way to ensure that the load is distributed evenly throughout the database. Distributing data by messageID would not be good because this means we would need to query ALL the database to retrieve messages

What happens when upon sending a message to a user, the user goes offline? then there would be failure. The troubleshooting method would be to set the message to unopened and then sending a notification to the user.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

If a server fails, the client will simply attempt reconnection to another server

Future improvements

Group chats: All messaging applications have group chats, we will need a separate table that keeps track of the chat's members

being able to edit messages

message searchnig: we can do this by using a separate server and using a Trie data structure