Design Facebook Messenger - System Design

System requirements

Functional:

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

Be able to message others in real time
View previously communicated messages
Create a group chat with multiple users
Add or remove users to an existing chat group
Post and upload images or videos through messenger to other people

Non-Functional:

List non-functional requirements for the system...

System must be highly available with a focus on minimizing latency as much as possible
System should be able to scale and handle large amounts of data over time
System should be able to handle cross regional communication across multiple geolocations

Capacity estimation

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

Writes: 2 kbytes/day * 500 million users/day * 365 days/year * 5 years = 1.8 TB
50 messages/user * 500 million DAU / 24 hours / 60 minutes / 60 seconds = 290,000 messages/second
Reads: Assume x5 amount of reads based on multiple users in the same chat ~1.5 million reads a second

API design

Define what APIs are expected from the system...

Public Endpoints

/api/v1/createChat

POST - Provides user_ids for chat and returns chat id

Request

{

"user_ids": "["sdean12","carlos1","megan14"]",

"created_at" : "2024-10-01 18:00:00"

}

Response

{

"chat_id": "120729"

}

/api/v1/joinChat

Connects Client to Websocket port on the server where channel is hosted

wss://…/messenger/{chat_id}

Client -> Server

{

"message_id": "1423",

"message":"Where are you?",

"media_links": "[URL]"

}

Server -> Client

{

"message_id": "1423",

"user_id": "sdean12",

"message" : "Where are you?",

"media_links": "[URL]"

}

/api/v1/addUser

UPDATE Request - Adds user_id to existing chat_id list of users and allows them access to the channel.

Request

{

"chat_id":"120729",

"user_id":"carl12"

}

Response

200 Http Response

/api/v1/removeUser

UPDATE Request - Removes given user_id from existing chat_id list of users and restricts them from access to the channel.

Request

{

"chat_id":"120729",

"user_id":"carl12"

}

Response

200 Http Response

/api/v1/uploadImage

POST Request - Sends location of file in local storage to be uploaded to blob storage

Request

{

"chat_id":"120729",

"message_id":"49716",

"user_id":"sdean12",

"file_path":"/home/stephen/documents/image.jpg"

{

Response

200 Http Request

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

Due to the excessive amounts of writes we will have to make - would prefer to use a LSM database such as Cassandra. The memtable component of LSM allows for much faster writes through the use of memory writes before they are moved to disk.
For data retrieval though such as through viewing messages we could employ the use of a relational database to store just the metadata and house the actual messages in Cassandra in a hybrid approach, two databases would be used which would complicate architecture but for a system that requires high write throughput, houses massive amounts of data and with the amount of reads for previous messages I believe its worth the trade off.

Schema:

Postgres (metadata)

Messages_Tbl

message_id: int (key)

user_id: int (serializable, foreign key)

chat_id: int

content_pointer: int (metadata pointer to cassandra db content)

Messengers_Tbl

user_id: int (key)

Schema:

LSM Cassandra Storage (message content)

Content_Tbl

content_pointer: int,

content: varchar

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

Rate limiter is used to prevent overwhelming of the server can utilize AWS Gateway throttling. For our load balancer we can utilize AWS Network Load Balancer due to the high amount of traffic we have and the amount of throughput we need to utilize. From our API Gateway we route the API request based on the type of request.
For createChat API requests we are routed to our chat service which opens up a websocket connection channel between the client and the server to allow bidirectional communication between the clients and servers after we write to the metadata Postgres database of our new chat details. In combination with websockets we also utilize a pub/sub queue such as Kafka to allow all subscribers in a group chat to receive the given messages, with writes being performed extensively to our Cassandra LSM database for content and metadata being stored in our Postgres db. For joinChat() requests we utilize the same chat service and connect the user to the same open websocket channel through the server, however users can only join an existing chat if they are a verified user_id of that chat which is enforced through our security verification service.
For media upload API requests they are routed to our media upload service where users submit the file path of the file they wish to submit and the file gets stored as a typical message with the corresponding metadata while the actual contents of the image/video are stored in our blob storage (AWS S3)
For any chat support service such as adding or removing users we do those through our chat supporting service through UPDATE API Requests we accept the chat_id parameter and affected user_id to update the corresponding chat metadata then allow the user to join the corresponding channel through a joinChat() call. We also utilize a cache function between our chat support and chat service features to allow changes to newly created channels through a LRU eviction policy.

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

API Calls are routed to the API Gateway after making it through the rate limiter, createChat() requests are routed to our chat service that make a POST request with the user_id, a write of the metadata is then made to our PostgresDb and a socket channel is opened between the clients and the server that allows for messages to be received and stored in the text db (Cassandra) through the flow from our pub/sub queue.

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

For our rate limiter, we can employ a token bucket rate limiter policy to provide some burst support with not too much memory usage consumption.
Websockets are the preferred method of communication for this application because of the bidirectional capabilities for a messaging application combined with how much throughput we are required with this system. Pub/Sub queues are also perfect for group chats where we have one publisher that's writing messages to multiple subscribers within the chat.
For our Load Balancer we can employ a least-connection distribution policy because we are opening many different websocket connections, they will give long term support to established connections and route any new connections to least used servers.
We also have a variety of HTTP API Requests such as creating and updating chats with new users/deleting users but all communication between messaging during client/server relations are done through websocket connections between client to server.
We can also implement a cache to help with any support for our chat service and chat support service through a LRU eviction policy, we choose LRU over LFU because older chats will become less active and more stable in terms of adding or removing members typically.
For our stored data, we are storing any metadata such as message_ids, chat_ids, user_ids in a relational database such as Postgres for the ease of querying while the actual message contents are stored in a LSM Cassandra DB which allows for fast time writes through the use of RAM. Metadata in the PostgresDb has a content pointer from the metadata to the actual content in Cassandra that is being used for any read retrievals. We can also use asynchronous replication between databases to allow the system to be more fault tolerant and minimize our latency and increase availability.
For our media upload API calls they will be routed from our API Gateway to our media upload service that also connects to the same websocket channel to upload the requested file path from the user to our S3 blob storage, with metadata writes along with a content pointer to our PostgresDb.

Trade offs/Tech choices

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

We have sacrificed some consistency at the reward of availability in the case of asynchronous database replication.
No way to edit existing messages in Cassandra LSM because Cassandra allows for high write throughput which is necessary for our architecture but entries are immutable.
Relational databases such as the PostgresDb we are using for metadata storage do not scale as well as NoSQL databases. However, the justification here is we are only storing just metadata and simple fields like message_ids while maintaining some consistency for message_ids,user_ids,chat_ids by the utilization of ACID properties from a relational DB.

Failure scenarios/bottlenecks

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

Token bucket based rate limiting does not have the best support for burst traffic, so in cases where there is an excessive spike of traffic there could be some potential bottle neck in getting to the API Gateway.
Media upload service is a single point of failure, user's chat or any potential new messages user wants to send could be handicapped by a slow upload from media upload service API calls.

Future improvements

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

Future improvements could be the implementation of use of emojis or stickers by the expansion of our AWS S3 blob storage to call a new API call by the user to send a particular emoji or image housed in our blob storage to users of the chat.
Add the option for users to send extended documents such as word docs to each other, would require file size verification and expansion to our blob storage as well.

System requirements

Functional:

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

Be able to message others in real time
View previously communicated messages
Create a group chat with multiple users
Add or remove users to an existing chat group
Post and upload images or videos through messenger to other people

Non-Functional:

List non-functional requirements for the system...

System must be highly available with a focus on minimizing latency as much as possible
System should be able to scale and handle large amounts of data over time
System should be able to handle cross regional communication across multiple geolocations

Capacity estimation

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

Writes: 2 kbytes/day * 500 million users/day * 365 days/year * 5 years = 1.8 TB
50 messages/user * 500 million DAU / 24 hours / 60 minutes / 60 seconds = 290,000 messages/second
Reads: Assume x5 amount of reads based on multiple users in the same chat ~1.5 million reads a second

API design

Define what APIs are expected from the system...

Public Endpoints

/api/v1/createChat

POST - Provides user_ids for chat and returns chat id

Request

{

"user_ids": "["sdean12","carlos1","megan14"]",

"created_at" : "2024-10-01 18:00:00"

}

Response

{

"chat_id": "120729"

}

/api/v1/joinChat

Connects Client to Websocket port on the server where channel is hosted

wss://…/messenger/{chat_id}

Client -> Server

{

"message_id": "1423",

"message":"Where are you?",

"media_links": "[URL]"

}

Server -> Client

{

"message_id": "1423",

"user_id": "sdean12",

"message" : "Where are you?",

"media_links": "[URL]"

}

/api/v1/addUser

UPDATE Request - Adds user_id to existing chat_id list of users and allows them access to the channel.

Request

{

"chat_id":"120729",

"user_id":"carl12"

}

Response

200 Http Response

/api/v1/removeUser

UPDATE Request - Removes given user_id from existing chat_id list of users and restricts them from access to the channel.

Request

{

"chat_id":"120729",

"user_id":"carl12"

}

Response

200 Http Response

/api/v1/uploadImage

POST Request - Sends location of file in local storage to be uploaded to blob storage

Request

{

"chat_id":"120729",

"message_id":"49716",

"user_id":"sdean12",

"file_path":"/home/stephen/documents/image.jpg"

{

Response

200 Http Request

Database design

Due to the excessive amounts of writes we will have to make - would prefer to use a LSM database such as Cassandra. The memtable component of LSM allows for much faster writes through the use of memory writes before they are moved to disk.
For data retrieval though such as through viewing messages we could employ the use of a relational database to store just the metadata and house the actual messages in Cassandra in a hybrid approach, two databases would be used which would complicate architecture but for a system that requires high write throughput, houses massive amounts of data and with the amount of reads for previous messages I believe its worth the trade off.

Schema:

Postgres (metadata)

Messages_Tbl

message_id: int (key)

user_id: int (serializable, foreign key)

chat_id: int

content_pointer: int (metadata pointer to cassandra db content)

Messengers_Tbl

user_id: int (key)

Schema:

LSM Cassandra Storage (message content)

Content_Tbl

content_pointer: int,

content: varchar

High-level design

Rate limiter is used to prevent overwhelming of the server can utilize AWS Gateway throttling. For our load balancer we can utilize AWS Network Load Balancer due to the high amount of traffic we have and the amount of throughput we need to utilize. From our API Gateway we route the API request based on the type of request.
For createChat API requests we are routed to our chat service which opens up a websocket connection channel between the client and the server to allow bidirectional communication between the clients and servers after we write to the metadata Postgres database of our new chat details. In combination with websockets we also utilize a pub/sub queue such as Kafka to allow all subscribers in a group chat to receive the given messages, with writes being performed extensively to our Cassandra LSM database for content and metadata being stored in our Postgres db. For joinChat() requests we utilize the same chat service and connect the user to the same open websocket channel through the server, however users can only join an existing chat if they are a verified user_id of that chat which is enforced through our security verification service.
For media upload API requests they are routed to our media upload service where users submit the file path of the file they wish to submit and the file gets stored as a typical message with the corresponding metadata while the actual contents of the image/video are stored in our blob storage (AWS S3)
For any chat support service such as adding or removing users we do those through our chat supporting service through UPDATE API Requests we accept the chat_id parameter and affected user_id to update the corresponding chat metadata then allow the user to join the corresponding channel through a joinChat() call. We also utilize a cache function between our chat support and chat service features to allow changes to newly created channels through a LRU eviction policy.

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

API Calls are routed to the API Gateway after making it through the rate limiter, createChat() requests are routed to our chat service that make a POST request with the user_id, a write of the metadata is then made to our PostgresDb and a socket channel is opened between the clients and the server that allows for messages to be received and stored in the text db (Cassandra) through the flow from our pub/sub queue.

Detailed component design

For our rate limiter, we can employ a token bucket rate limiter policy to provide some burst support with not too much memory usage consumption.
Websockets are the preferred method of communication for this application because of the bidirectional capabilities for a messaging application combined with how much throughput we are required with this system. Pub/Sub queues are also perfect for group chats where we have one publisher that's writing messages to multiple subscribers within the chat.
For our Load Balancer we can employ a least-connection distribution policy because we are opening many different websocket connections, they will give long term support to established connections and route any new connections to least used servers.
We also have a variety of HTTP API Requests such as creating and updating chats with new users/deleting users but all communication between messaging during client/server relations are done through websocket connections between client to server.
We can also implement a cache to help with any support for our chat service and chat support service through a LRU eviction policy, we choose LRU over LFU because older chats will become less active and more stable in terms of adding or removing members typically.
For our stored data, we are storing any metadata such as message_ids, chat_ids, user_ids in a relational database such as Postgres for the ease of querying while the actual message contents are stored in a LSM Cassandra DB which allows for fast time writes through the use of RAM. Metadata in the PostgresDb has a content pointer from the metadata to the actual content in Cassandra that is being used for any read retrievals. We can also use asynchronous replication between databases to allow the system to be more fault tolerant and minimize our latency and increase availability.
For our media upload API calls they will be routed from our API Gateway to our media upload service that also connects to the same websocket channel to upload the requested file path from the user to our S3 blob storage, with metadata writes along with a content pointer to our PostgresDb.

Trade offs/Tech choices

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

We have sacrificed some consistency at the reward of availability in the case of asynchronous database replication.
No way to edit existing messages in Cassandra LSM because Cassandra allows for high write throughput which is necessary for our architecture but entries are immutable.
Relational databases such as the PostgresDb we are using for metadata storage do not scale as well as NoSQL databases. However, the justification here is we are only storing just metadata and simple fields like message_ids while maintaining some consistency for message_ids,user_ids,chat_ids by the utilization of ACID properties from a relational DB.

Failure scenarios/bottlenecks

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

Token bucket based rate limiting does not have the best support for burst traffic, so in cases where there is an excessive spike of traffic there could be some potential bottle neck in getting to the API Gateway.
Media upload service is a single point of failure, user's chat or any potential new messages user wants to send could be handicapped by a slow upload from media upload service API calls.

Future improvements

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

Future improvements could be the implementation of use of emojis or stickers by the expansion of our AWS S3 blob storage to call a new API call by the user to send a particular emoji or image housed in our blob storage to users of the chat.
Add the option for users to send extended documents such as word docs to each other, would require file size verification and expansion to our blob storage as well.