Loading...
Messenger is a chat application.
User is able to:
If I have time, I will design additional features:
[Generally speaking, you would like to keep the requirements scope small. You only have 35 - 50 min in an interview. If you have a lot of requirements, you'd risk running out of time. That's why we are not supporting images & videos. On the other hand, supporting both 1-1 chat and group chat is a good idea, because the former can be modeled as a special case of the latter. It shows your deep understanding.]
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.]
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, ...],
}
[Senior-level deep dive topic. Choosing a database is a good option for a deep dive conversation. Read: https://www.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/]
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.
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...
[Senior-level deep dive topic. Scalability (and performance) is always a good deep discussion choice. Almost mandatory.]
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 related to Users and Groups can be cached, e.g., by Redis. These data are relatively stable. For example, user metadata such as names and email addresses remain constant for a long time. Group members are changed, but not in minute by minute basis. Cache strategies such as LRU would be effective in caching such objects.
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.
[Mid-level deep dive topic.]
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.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?