[System Design]Online Chat System

Scenario: Design an online service to support online chat. group chat and friends online status check

Assume we have 100M DAU, and each user send average 30 messages daily, QPS = 100M * 30 / 86400 = 35K, peak QPS = 35K * 5 = 175K, and we need to keep in mind it is a write heavy service.

Services:

The whole system can be split into modules below:

• Message Service: Store and manage all messages
• Thread Service: Manage thread information for each user, and real time message update

Storage:

For message table, we need to store the following information:

Field	Type	Detail
message_id
user_id	foreign key
thread_id	primary key	can be simple user_id + timestamp
content	text
create_at	timestamp

We select this table based on thread_id, so we'd better use this as primary key since we will need to shard based on this key later. Nosql is good for this, row_key = thread_id, column_key=user_id, value can be a json object wraps message information.

For thread table, we need to can store the data below:

Field	Type	Detail
thread_id	int64	can be simple user_id + timestamp
owner_id	int64
participate_ids	text	list of participate ids
thread settings	text	like muted, alias, etc. can also split it into multiple columns
participate_hash	string	hash value to avoid duplicates(optional)
create_at	timestamp
update_at	timestamp

One thing need to notice is that for the same thread, every user has an entry in database for it, since the personal information will be different, like settings, update_time, so every user stores a copy of this data.
Since we will need to select and index based on thread_id, owner_id, update_at and participate hash, SQL database is more appropriate in this case.

Naive workflow:

Sending Message:

• Create a thread in thread table if the participate hash doesn't exist and return it to user
• user send request to message service with the thread id, and create a new entry in the message table

Receiving Message:

• Ask thread service the threads current user owns, SELECT thread_id FROM thread_table WHERE user_id == curr_user_id
• For each of thread, ask message service to return the message after the last updated time. SELECT * FROM message_table WHERE thread_id == curr_thread_id AND update_at > curr_timestamp ORDERED BY create_at
• Return those data to user

Problem with this solution:

• User need to pull every several seconds to see if there is any update, no real-time support

To solve it, we will need web socket, current solution lets client to send request to server and get updates, but once server has update it can not push data to the use. If client has a web socket connection with the server, once user A send message to user B, the server can actually forward the update to the user. 

So we will introduce another service Push Service, which is simply web servers with many sockets, when ever user send a message, the message service receive it, other than update the DB, it will also forward the message to the push service, and the push service will push the data to the user based on participate ids.

Scale:

Message table will be sharded by thread id since we usually fetch the data for the same thread together. Thread table can be sharded by owner id. The front web server can just do load balancing since they will be stateless, what they will do is just get thread ids for current user, and get messages for each thread.
Push Server is stateful, since we need to know where the users are at, so we can do consistent hash based routing, so whenever message service has a update, it can forward to correct node.

More Features:

Group Chat:

• Current solution has a problem since the fanout is too high for large group chat, the Message Service needs to forward the data to every participants. But in most cases it is not necessary since the user might not be online. We can store the user's online status somewhere and check it first before we send data to Push Service, but the load for message service is still too high in this case.
• We need to introduce another Channel Service to keep track of all online users in current group chat/channel. For each group chat thread, we can have a channel field associate with it in DB. So we can store <channel, user_ids> in the memory of Channel service, and whenever user is online, Push Service will know and send a request to Thread Service to get all channel the user involved in and add user id to the list. So whenever there is an update in the channel, the Message Service just forward to Channel Service, and it will know who are online and fanout the update to those online users.

Online Status:

• So here comes the question, how do we know if current user is online?
• Assume the User Service and Friend Service is already there, the client can send heart beat to the server every several second and we can modify the field in table of User Service based on this
• How about friends' status, we just pull every friends' status every several seconds, this can also be included in the heart beat message