Loading...
Messenger is a chat application.
User is able to:
If I have time, I will design additional features:
Support web clients and mobile clients.
Scalable - 500M DAU
Low response time - message appears in everyone's chat window within 200 - 300ms after being typed
Availability
Reasonably strong consistency. We would like to minimize of inconsistent communication, e.g., messages arriving out of order. But it does not need to be a strong consistency like ACID properties. Eventual consistency with reasonable limit (e.g. most messages become ordered within 1 second) would suffice.
[Avoid the risk of listing a bucket list of non-func requirements. It'd take too much time. Focus on the requirements that impact the design. For example, consistency always impacts (even dictates) the database choice. Expected response time also often impacts architecture.]
Error scenarios to note:
Network failure preventing user from sending messages and receiving messages. Both cases should be considered and guarded against.
[Failure is also a very good thing to (briefly) consider at this point. It prepares you for a fault tolerance discussion in the deep dive.]
500M DAU
Each person spends 10 minutes on chat, on average.
Each person generates 2KB of text every day.
Each person generates 1MB of media data (pictures or videos) every day.
There are same number of groups to users - 500M groups.
Text Data
500M * 2KB = 1GB text data each day. It would be 365GB per year.
To store the conversations up to 10 years, data size would be 3.7 TB. Considering user growth, let's assume it would need 10TB.
User & Groups Data
User data would have ID, name, email address, etc. It would amount to 1KB / User.
Group data would have ID, name, member list, etc. It would amount to 2KB / Group.
3KB * 500M = 1500GB = 1.5 TB
At peak, let's say 20% of users - 100M users - can be chatting in one second.
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.
[Whenever you make an important decision like this, be sure to be able to explain why you are making that decision.]
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.
Message:
The text data should be indexed by the message ID (primary key), sender, and the timestamp.
Rate Limiter prevents Denial of Service attacks.
API Gateway forwards clients' requests to different micro services, considering the type of requests.
Load Balancer forward the request to an appropriate service, depending on the workload of each server. Weighted round robin algorithm can be used for this.
I chose to have multiple micro services because they serve such different purposes.
Chat Service is responsible for initiating and serving WebSocket connections. (It might be beneficial to further split WebSocket server and Chat Service. This would be future consideration.)
Media Service is responsible for receiving media files and storing them in blob store. It also creates a message in message queue, initiating an async process.
Media Worker takes a message from the message queue, compressing and converting original media file into multiple versions (sizes and formats appropriate for different clients), and storing the resulting URLs on MongoDB.
User Service is responsible for managing users and groups.
We have focused the architecture within one data center. It would make sense to have multiple data centers in multiple geographic region for response time (closer to user), fault tolerance (in case of natural disaster), and scalability.
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
The Messaging Service interacts with the Message Database to store and retrieve messages.
The Presence Service uses a Redis database to quickly update and fetch user online statuses.
Let's discuss how we can make sure this architecture scales and has good performance.
Sharding
Text DB can be sharded by either User (Author) ID or Message ID.
Sharding by User ID makes reading by User ID fast. It can lead to uneven load if one user is extremely active.
Sharding by Message ID makes load distribution more even. However, query by User ID would require a query to all DB nodes.
We lean toward User ID because, humans would not type thousands of text messages per second. If they do, they are likely using some thought of automation with a malicious intent, or involving a bug. These extreme load should be rate-limited. Consistent Hashing can be used to smooth out uneven load.
Response Time
We expect creating groups and starting chat can perform well (~100ms range). Data models are simple. We don't see complex joins. All the data can be cached by Redis. There should be strong locality of access.
One key for good user response time would be WebSocket. As discussed earlier, it is suitable for bi-directional communication between a browser and a server. It should be horizontally scalable. Each client establishes a WebSocket connection with one WebSocket server. Load Balancer makes sure the ensuing packets should go to this server. As the number of clients and requests increase, we can add more WebSocket servers.
WebSocket Service uses Pub/Sub queue for efficient communication. For example, let's say Server A who has WebSocket connection open with User A. User A sends a message. Server A would publish this message in Pub/Sub server. Service B and Server C are listening to a Pub/Sub topic which represents a chat group. Upon receiving User A's message, Servers B and C send this message to User B and C, respectably, via WebSocket.
We can consider using an adjacency list to track user connections in your system, managing contacts and conversations efficiently.
Adjacency List Representation:
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, e.g., https://medium.com/google-cloud/time-synchronisation-problem-and-gcp-products-5e202486b756
[Mid-level deep dive topic.]
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.