Loading...
Extended Requirements:
Let's assume that we have 500 million daily active users, and on average, each user sends 40 messages daily; this gives us 20 billion messages per day.
Storage Estimation: Let's assume that, on average, a message is 100 bytes. So to store all the messages for one day, we would need 2TB of storage.
20 billion messages * 100 bytes => 2 TB/day
To store five years of chat history, we would need 3.6 petabytes of storage.
2 TB * 365 days * 5 years ~= 3.6 PB
Besides chat messages, we also need to store users' information, messages' metadata (ID, Timestamp, etc.). Not to mention, the above calculation doesn’t take data compression and replication into consideration.
Bandwidth Estimation: If our service is getting 2TB of data every day, this will give us 25MB of incoming data for each second.
2 TB / 86400 sec ~= 25 MB/s
Since each incoming message needs to go out to another user, we will need the same amount of bandwidth 25MB/s for both upload and download.
At an API level, we will try to combine 1-1 chat and group chat. In other words, 1-1 chat is a special case of a group chat (where only 2 users participate).
create_chat_group(participants' user IDs): returns group ID
Client and server exchange messages. There are several ways to do this:
We pick WebSocket for exchanging messages.
join_chat(user_ID, group_ID) : this establishes a WebSocket connection between the client (browser or mobile app) and the server (Chat Service).
Within the WebSocket connection, the following JSON messages are sent:
User -> Service:
{
'message_ID': "",
'message': ""
'media_links: [URL, URL, ...],
}
Service -> User:
{
'message_ID': "",
'timestamp: ,
'message': ""
'media_links: [URL, URL, ...],
}
We need to store text messages. They have the following properties:
We also need to store users and groups data.
[It is helpful to discuss the properties of the data. E.g., size, write & read throughput, consistency. Then use it to pick a DB and design a data model.]
Pro of LSM-based DB (e.g. Cassandra):
Con of LSM-based DB:
The characteristics of text messages are: (1) the system needs to write a lot of small messages, (2) once written, the data won't change often. So this suits Cassandra.
Pro of B-Tree based DB (e.g. RDB or MongoDB):
Con of Doc DB:
The User & Group data are mutable, and the application would benefit from relational queries. Therefore, B-Tree based DBs are suitable for User & Group data.
There are three ways we can go:
Approach (3) would be a very attractive approach because it takes the best of both worlds. The caveat is that with two DBs, it would complicate the architecture, but if we are building such a big app with so many users, this is justifiable.
Media Files
For the media files (images and videos), blob store would be the most appropriate data store, due to the expected size (in petabytes) and the nature of the files (write once, read many times).
An interesting design question is whether to store media files in CDN. Welean toward no, because, the media files are viewed only by participants of a chat. We would imagine this would be usually between 10, instead of millions of users. As such, no media files will be needed by millions of users. Therefore, it does not suit CDN's caching capability well. Instead, we will cache in our datacenter.
Message:
The text data should be indexed by the message ID (primary key), sender, and the timestamp.
The detailed workflow would look like this:
How would we efficiently send/receive messages? To send messages, a user needs to connect to the server and post messages for the other users. To get a message from the server, the user has two options:
In the first approach, the server needs to keep track of messages that are still waiting to be delivered, and as soon as the receiving user connects to the server to ask for any new message, the server can return all the pending messages. To minimize latency for the user, they have to check the server quite frequently, and most of the time, they will be getting an empty response if there are no pending messages. This will waste a lot of resources and does not look like an efficient solution.
If we go with our second approach, where all the active users keep a connection open with the server, then as soon as the server receives a message, it can immediately pass the message to the intended user. This way, the server does not need to keep track of the pending messages, and we will have minimum latency, as the messages are delivered instantly on the opened connection.
How will clients maintain an open connection with the server? We can use HTTP 'Long Polling' or 'WebSockets'. In long polling, clients can request information from the server with the expectation that the server may not respond immediately. If the server has no new data for the client when the poll is received, instead of sending an empty response, the server holds the request open and waits for response information to become available. Once it does have new information, the server immediately sends the response to the client, completing the open request. Upon receipt of the server response, the client can immediately issue another server request for future updates. This gives a lot of improvements in latencies, throughputs, and performance. However, the long polling request can timeout or receive a disconnect from the server; in that case, the client has to open a new request.
How can the server keep track of all the opened connections to efficiently redirect messages to the users? The server can maintain a hash table, where "key" would be the UserID and "value" would be the connection object. So whenever the server receives a message for a user, it looks up that user in the hash table to find the connection object and sends the message on the open request.
What will happen when the server receives a message for a user who has gone offline? If the receiver has disconnected, the server can notify the sender about the delivery failure. However, if it is a temporary disconnect, e.g., the receiver's long-poll request just timed out, then we should expect a reconnect from the user. In that case, we can ask the sender to retry sending the message. This retry could be embedded in the client's logic so that users don't have to retype the message. The server can also store the message for a while and retry sending it once the receiver reconnects.
How many chat servers do we need? Let's plan for 500 million connections at any time. Assuming a modern server can handle 50K concurrent connections at any time, we would need 10K such servers.
How do we know which server holds the connection to which user? We can introduce a software load balancer in front of our chat servers; that can map each UserID to a server to redirect the request.
How should the server process a 'deliver message' request? The server needs to do the following things upon receiving a new message: 1) Store the message in the database, 2) Send the message to the receiver, and 3) Send an acknowledgment to the sender.
The chat server will first find the server that holds the connection for the receiver and pass the message to that server to send it to the receiver. The chat server can then send the acknowledgment to the sender; we don't need to wait to store the message in the database (this can happen in the background). Storing the message is discussed in the next section.
How does the messenger maintain the sequencing of the messages? We can store a timestamp with each message, which is the time when the server receives the message. However, this will still not ensure the correct ordering of messages for clients. The scenario where the server timestamp cannot determine the exact order of messages would look like this:
So User-1 will see M1 first and then M2, whereas User-2 will see M2 first and then M1.
To resolve this, we need to keep a sequence number with every message for each client. This sequence number will determine the exact ordering of messages for EACH user. With this solution, both clients will see a different view of the message sequence, but this view will be consistent for them on all devices.
Whenever the chat server receives a new message, it needs to store it in the database. To do so, we have two options:
We have to keep certain things in mind while designing our database:
Which storage system should we use? We need to have a database that can support a very high rate of small updates and also fetch a range of records quickly. This is required because we have a huge number of small messages that need to be inserted in the database and, while querying, a user is mostly interested in sequentially accessing the messages.
We cannot use RDBMS like MySQL or NoSQL like MongoDB because we cannot afford to read/write a row from the database every time a user receives/sends a message. This will not only make the basic operations of our service run with high latency but also create a huge load on databases.
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 to store 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 variable-sized data, which is also required by our service.
How should clients efficiently fetch data from the server? Clients should paginate while fetching data from the server. Page size could be different for different clients, e.g., cell phones have smaller screens, so we need fewer messages/conversations in the viewport.
We need to keep track of user's online/offline status and notify all the relevant users whenever a status change happens. Since we are maintaining a connection object on the server for all active users, we can easily figure out the user's current status from this. With 500M active users at any time, if we have to broadcast each status change to all the relevant active users, it will consume a lot of resources. We can do the following optimization around this:
Design Summary: Clients will open a connection to the chat server to send a message; the server will then pass it to the requested user. All the active users will keep a connection open with the server to receive messages. Whenever a new message arrives, the chat server will push it to the receiving user on the long poll request. Messages can be stored in HBase, which supports quick small updates and range-based searches. The servers can broadcast the online status of a user to other relevant users. Clients can pull status updates for users who are visible in the client’s viewport on a less frequent basis.
Message Timestamp
Message timestamp is important because it is used to order messages. It presents an interesting design choice. Should it be timestamped by client or by server?
We lean toward relying solely in server's timestamp, as it would be much easier to keep servers time in sync at a reasonable level. We don't have a control over clients' clock (and clock skews). One advantage of client side timestamp is that a user will be able to prove they have sent a message by the client side timestamp, even if the message transmission fails due to a network failure. But we are mainly building this for consumer use, instead of a legal use. Therefore, this advantage of client side timestamp can be deprioritized.
As the number of servers grow, it may become too difficult to synchronize the clock even among the servers. If this happens, we can consider a more robust system based on atomic clock
.
It is quite common that a network failure would prevent the client from sending the message to the server. Client should store the messages locally so that they can be re-sent. The client should retry sending the message to the server, perhaps every minute and a handful of times. If all retries fail, it should clearly tell the user that the sending failed so that the user can decide what to do. Silently failing would be very bad for users.
Likewise, Chat Service should have a retry mechanism, in case it fails to send a message to the client via WebSocket. Chat Service should be persistent in sending it. For example, a client may go offline for extended period of time. When the client re-connects to Chat Service, the service should attempt to deliver all the messages it failed to send earlier.
User or the client software may act irrationally, for example, by sending the same message multiple times, causing message deliver failures. This should be handled by rate limiters.
User may type something that is against the rules (e.g. offensive messages). To respond to such behavior, we can have a Message Queue through which the text messages are passed through. Content Check service would be pulling messages from this queue. When it detects offensive content, it would take actions such as deleting messages and notifying users and administrators.