System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. A user is able to send a message to another user.
2. A user is able to receive a a message.
3. A user is able to create groups.
4. A user is able to send a message in a group.
5. Able to send images/videos as well.
6. Group size is max 100.
7. Sent/ delivered/ read status sign.
8. Last seen and online status.

Non-Functional:

List non-functional requirements for the system...

1. Message transfer latency should be very low.
2. Durability: Messages should not be lost.
3. Scalable: Should be able to handle millions of users and concurrent connections.

Capacity estimation

Estimate the scale of the system you are going to design...

5 Million DAU

20 message per user avg

msg transfer TPS= 1,000

Peak TPS= 10,000

Avg msg size= 20 bytes

Total storage for 5 years= 365*5*5* 10^6* 20= 182 GB

avg multimedia size = 1 Mb

Total multimedia storage for 5 years= * 1.82 GB = 1.82 TB

API design

Define what APIs are expected from the system...

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

We require high scale, high availability, structured data, high write and read both.

Hence we will use a NoSQL DB like Casandra.

MESSAGE DB:

MESSAGE TABLE

MessageId:

Content:

Image URL in S3:

SenderID

ReceiverId

Timestamp

USER TABLE

UserId:

UserName:

UserProfile

......

GROUP DB:

GROUP TABLE

GroupId:

MemberId:

JoiningDate

IsAdmin

...

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

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...

Send Msg flow for 1: 1 chat:

1. Client 1 sends the message to load balancer which redirects it to chat server and establishes a web socket connection.
2. Client 1 forwards the msg to a MessageSyncQueue which sends message to Chat Server 2.
3. If client 2 is online, Chat server 2 holds connection with client 2 and sends message to client 2 over ws.
4. If client 2 is offline, Chat server 2 sends message to client 2 over PN servers.

Send msg flow for group chat:

1. Client 1 sends the message to load balancer which redirects it to chat server.
2. Now chat server 1 queries group service to fetch all the members of group.
3. Now each member has an associated message sync queue and chat server 1 fans out message to all message sync queues.
4. The messages are sent to online recipients via corresponding chat servers.
5. For offline recipients push notification is sent.

Sending Images

1. Client 1 directly uploads the media to CDN and sends only image URL in message. this does not put load on chat server.
2. When client 2 needs to download the media it downloads from CDN improving latency
3. Image service pulls media from CDN and uploads it to blob storage like Amazon S3 for permanent storage.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Chat Servers:

1. Chat servers are a pool of servers responsible for holding a web socket connection with client device.
2. To ensure the clients connect to same cache servers each time, we will use sticky sessions based on IP hashing of client in Load Balancer.
3. The flow how a message is sent from one device to another is explained in Request Flows.

Message Sync Queue:

It is a distributed queue like Kafka responsible from sending a msg from one chat server to another in order.

Client Connection Cache:

It is a in memory cache responsible for storing the user and server holding the connection details, so a message can be sent to recipient server.

UserId: ServerId

Message Server:

Service responsible for retrieving message from sync queue and storing in DB.

Group Service:

Service responsible for managing all group related tasks like group creation, adding/ removing/ retrieving members of a group.

CDN

1. When a client wants to send a media item, this is uploaded to CDN and only image URL is sent in the message. This does not put load on chat server.
2. When client 2 needs to download the media it downloads from CDN improving latency
3. Image service pulls media from CDN and uploads it to blob storage like Amazon S3 for permanent storage.

Sent/ Delivered and Read Status

1. Sent status
   1. When client 1 sends a message to chat server 1, chat server 1 responds back to client 1 with acknowledgement that message is received. Client 1 device receives this notification and updates the status in app to sent.
   2. If client 1 is offline, it will not receive the acknowledgement and hence status will not be updated.
2. Delivered status
   1. When chat server 2 sends the message to client 2, client 2 responds back with ack, chat server 2 sends this ack to chat server 1, which sends it back to client 1 and updates the status in app to delivered.
   2. If client 2 is offline, then no ack gets sent.
3. Read Status
   1. When user 2 opens the chat and reads the message, client 2 updates the status in client 2 device and sends the notification to chat server 2 which sends the same to chat server 1 and then client 1 and updates the status in app of client 1 to read as well.
   2. If client 2 is offline, then no ack gets sent.

Last Seen/Online

1. We are maintaining each client's connection information in redis cache.
2. Each client sends a heartbeat every sec indicating it is live and connecting to chat server.
3. If a client has sent a notification in last x seconds( eg 5 seconds), then client's status is maintained as online.
4. If a client's last heartbeat was more than x sec ago, then the status is changed to last seen at x time.

Trade offs/Tech choices

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

1. Polling vs Long Polling vs Web Socket- Since polling and long polling are resource intensive and require managing connections even with inactive clients, web sockets are preferred.
2. Message Sync Queue vs Direct Transfer message to recipient Chat server- For high scale and better decoupling message sync queue is preferred
3. Monolithic vs micro service- Each service can be scaled independently according to various scales of different paths. and can be helpful in providing graceful degradation behaviour is some component is down.
4. DB- SQL vs NoSQL- We require high scale, high availability, structured data, high write and read both. Hence we will use a NoSQL DB like Casandra.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

1. Client Connection Cache Needs to manage active connection informations. This is a single point of information for connection info and if goes down can bring down the whole system. Though we can use replication, but this is a bottleneck as servers are added/ removed. Even though Consistent Hashing minimises the no of movements, we can offload this responsibility to a managed Service Discovery service like Apache Zookeeper, etcd etc. Now chat server 1 will need to query Service Discovery to find the chat servers for client 2.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

1. We can have analytics etc added to the system.