System requirements

Functional:

List functional requirements for the system (Ask interviewer if stuck)...

1. Realtime messaging: Users can send and receive messages in realtime
2. Group chat support: The system should support group chats, max of 200 people
3. Push Notifications: Users should be notified of new messages when they are offline or not actively using the chat
4. Persistence: Messages should be stored to allow users to fetch their chat history
5. Online presense: Users can see if their friends are online, offline or busy
6. Read Receipts: Users can see if their message has been delivered and read by the recipient
7. Media Uploads: Users can share images and videos within chats
8. Multiple device support

Non-Functional:

List non-functional requirements for the system...

1. Low latency: Messages and media should be delivered with minimal delays
2. Scalability: The system should scale to support millions of concurrent users
3. Reliability: Messages should be delivered reliably and in order
4. Consistency: Users should see the same chat history and statuses across all their device
5. Security: End-to-end encryption

Capacity estimation

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

It should support 100 million daily active users (DAU)

Each user sends 20 messages per day on average

So 2 billion messages per day

Average message size is 100 bytes (text only)

Media files average size is 2MB

10% of messages contain media files

QPS:

messages: 10 million users * 20 messages per user / 86400 ~ 2300 messages/sec

media uploads: 10% ~ 230 uploads/sec

Peek QPS:

Assuming peak times 3x:

Peak messages QPS: 6900 messages/sec

Peak media uploads QPS: 690 uploads/sec

Storage:

Message: 10 million users * 20 messages * 1kb message =200 GB/day

Media: 10 million users * 2 uploads * 2MB = 20TB/day

API design

Define what APIs are expected from the system...

Send message: POST /api/messages/send

{

"fromUserId": "12345",

"toUserId": "67890",

"message": "Hello!",

"timestamp": "2024-03-20T12:34:56Z",

"messageType": "text", // Could be "media" for media messages

"mediaUrl": null, // URL to media if messageType is "media"

"readReceiptRequested": true

}

Update the online status:

POST /api/status/update

{

"userId": "12345",

"status": "online", // Could be "offline", "busy", etc.

"lastSeen": "2024-03-20T12:34:56Z"

}

Read message:

GET /api/messages

Response:

{

"messages": [

{

"messageId": "msg1",

"fromUserId": "12345",

"toUserId": "67890",

"chatSessionId": "123",

"message": "Hello, how are you?",

"timestamp": "2024-03-20T12:34:56Z",

"messageType": "text", // Or "media" for media messages

"mediaUrl": null, // URL to media if messageType is "media"

"readReceipt": false // Indicates if the message has been read

},

{

"messageId": "msg2",

"fromUserId": "12345",

"toUserId": "67890",

"chatSessionId": "123",

"message": "Check out this picture!",

"timestamp": "2024-03-20T12:35:00Z",

"messageType": "media",

"mediaUrl": "https://example.com/path/to/image.jpg",

"readReceipt": false

}

// More messages...

]

}

If we use gRPC, the proto buffer should be like:

// The chat service definition.

service ChatService {

// Sends a message to a chat session.

rpc SendMessage(SendMessageRequest) returns (SendMessageResponse);

// Updates a user's online status.

rpc UpdateOnlineStatus(UpdateOnlineStatusRequest) returns (UpdateOnlineStatusResponse);

}

// Request message for SendMessage.

message SendMessageRequest {

string fromUserId = 1;

string toUserId = 2;

string chatSessionId = 3;

string message = 4;

string timestamp = 5;

MessageType messageType = 6;

string mediaUrl = 7;

bool readReceiptRequested = 8;

}

// Response message for SendMessage.

message SendMessageResponse {

string messageId = 1;

bool success = 2;

string errorMessage = 3; // Empty if success is true

}

// Request message for UpdateOnlineStatus.

message UpdateOnlineStatusRequest {

string userId = 1;

UserStatus status = 2;

string lastSeen = 3;

}

// Response message for UpdateOnlineStatus.

message UpdateOnlineStatusResponse {

bool success = 1;

string errorMessage = 2; // Empty if success is true

}

// An enumeration of message types.

enum MessageType {

TEXT = 0;

MEDIA = 1;

}

// An enumeration of user statuses.

enum UserStatus {

ONLINE = 0;

OFFLINE = 1;

BUSY = 2;

}

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

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

1. Client Applications: The frontend through which users interact with the system, available on various devices
2. API gateway: manages user authentication and security
3. Load balancer
4. Message Service
5. Push Notification service
6. Friendship/Relationship service
7. Storage System: Store messages (NoSQL), user information (relational db, SQL), chat histories
8. User Management Service
9. Media services
10. Security services
11. Search services
12. Archiving services

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

1. Client (User): The client (e.g., a web browser, mobile app, or any other application) sends a request to the public-facing endpoint of the application.
2. API Gateway: The request first hits the API Gateway, which acts as the single entry point for all client requests. The API Gateway is responsible for:

• Authentication and Authorization
• Request Routing
• Request Transformation (e.g., protocol translation, data marshalling/unmarshalling)
• Rate Limiting and Throttling
• Caching
• Logging and Monitoring

1. Load Balancer: After the API Gateway has processed the request, it forwards the request to the appropriate service (or set of services) through a Load Balancer. The Load Balancer distributes the incoming traffic across multiple instances of the service, ensuring high availability, scalability, and fault tolerance.
2. Service Instances: The Load Balancer forwards the request to one of the service instances (e.g., a microservice or a monolithic application server) based on its load balancing algorithm (e.g., round-robin, least connections, IP hash, etc.).
3. Database Interactions:

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.

1. Service Response: The service instance processes the request and sends the response back to the Load Balancer.
2. Load Balancer to API Gateway: The Load Balancer forwards the response from the service instance to the API Gateway.
3. API Gateway to Client: The API Gateway may perform additional processing on the response (e.g., data transformation, caching, logging) and then sends the final response back to the client.

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

Trade offs/Tech choices

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

When a client intends to start a chat, it connects the chat service using one or more network protocols. For a chat service the choice of network protocol is important.

HTTP is client initiated, it is not trival to send messages from the server.

Polling vs Long Polling vs Websocket for Web + MQTT(Message Queuing Telemetry Transport) for mobile:

• WebSockets: This protocol provides a full-duplex communication channel over a single, long-lived connection, allowing for real-time bidirectional data exchange between the client and server. WebSockets are used for delivering messages as soon as they are sent, which is ideal for real-time applications like Facebook Messenger.
• MQTT (Message Queuing Telemetry Transport): Facebook has mentioned using MQTT, a lightweight messaging protocol designed for constrained devices and low-bandwidth, high-latency, or unreliable networks. MQTT is particularly well-suited for mobile chat applications because it efficiently manages battery life while providing real-time updates.

Failure scenarios/bottlenecks

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

Future improvements

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