Design an online chat
Users, chats, requests and messages for a chat server.
On this page
Constraints and assumptions#
- Assume we'll focus on the following workflows:
- Text conversations only
- Users
- Add a user
- Remove a user
- Update a user
- Add to a user's friends list
- Add friend request
- Approve friend request
- Reject friend request
- Add friend request
- Remove from a user's friends list
- Create a group chat
- Invite friends to a group chat
- Post a message to a group chat
- Private 1-1 chat
- Invite a friend to a private chat
- Post a meesage to a private chat
- No need to worry about scaling initially
Solution#
python
from abc import ABCMeta
class UserService(object):
def __init__(self):
self.users_by_id = {} # key: user id, value: User
def add_user(self, user_id, name, pass_hash): # ...
def remove_user(self, user_id): # ...
def add_friend_request(self, from_user_id, to_user_id): # ...
def approve_friend_request(self, from_user_id, to_user_id): # ...
def reject_friend_request(self, from_user_id, to_user_id): # ...
class User(object):
def __init__(self, user_id, name, pass_hash):
self.user_id = user_id
self.name = name
self.pass_hash = pass_hash
self.friends_by_id = {} # key: friend id, value: User
self.friend_ids_to_private_chats = {} # key: friend id, value: private chats
self.group_chats_by_id = {} # key: chat id, value: GroupChat
self.received_friend_requests_by_friend_id = {} # key: friend id, value: AddRequest
self.sent_friend_requests_by_friend_id = {} # key: friend id, value: AddRequest
def message_user(self, friend_id, message): # ...
def message_group(self, group_id, message): # ...
def send_friend_request(self, friend_id): # ...
def receive_friend_request(self, friend_id): # ...
def approve_friend_request(self, friend_id): # ...
def reject_friend_request(self, friend_id): # ...
class Chat(metaclass=ABCMeta):
def __init__(self, chat_id):
self.chat_id = chat_id
self.users = []
self.messages = []
class PrivateChat(Chat):
def __init__(self, first_user, second_user):
super(PrivateChat, self).__init__()
self.users.append(first_user)
self.users.append(second_user)
class GroupChat(Chat):
def add_user(self, user): # ...
def remove_user(self, user): # ...
class Message(object):
def __init__(self, message_id, message, timestamp):
self.message_id = message_id
self.message = message
self.timestamp = timestamp
class AddRequest(object):
def __init__(self, from_user_id, to_user_id, request_status, timestamp):
self.from_user_id = from_user_id
self.to_user_id = to_user_id
self.request_status = request_status
self.timestamp = timestamp
class RequestStatus(Enum):
UNREAD = 0
READ = 1
ACCEPTED = 2
REJECTED = 3Added on this site
The one idea#
This exercise is mostly about relationships and permissions, not messages. A message can only be posted by someone who is in the chat. A private chat can only exist between friends. A friend only exists after a request has been approved. Get those rules into the model and the rest is bookkeeping.
How to get there in an interview#
- Turn the workflows into rules. Users can be added, removed and updated. A friend request goes from sent to approved or rejected, and approval makes the friendship mutual. A private chat is between two friends. A group chat is created by one user who invites friends. Only members can post.
- List the nouns. User, FriendRequest (with a status), Chat (private or group), Message.
- Decide who owns what. A
UserService(or the chat service) owns the collection of users and enforces rules that span users. AUserholds its own friends and requests. AChatholds its members and its messages. - Model the request lifecycle explicitly. A request has a status (pending, approved, rejected) so you can answer "what did I send, what is waiting for me, what happened to it".
- Say what you are skipping. No scaling yet, text only. Those are the exact things to come back to once the model is clear.
A working version#
A compact version that enforces the rules above:
python
from enum import Enum
from itertools import count
class Status(Enum):
PENDING = 0
APPROVED = 1
REJECTED = 2
class User:
def __init__(self, user_id, name):
self.user_id = user_id
self.name = name
self.friends = set()
self.requests_received = {} # from user id -> Status
class Chat:
def __init__(self, chat_id, members):
self.chat_id = chat_id
self.members = set(members) # user ids
self.messages = [] # (user id, text)
class ChatService:
def __init__(self):
self.users = {}
self.chats = {}
self._chat_ids = count(1)
def add_user(self, user_id, name):
self.users[user_id] = User(user_id, name)
def remove_user(self, user_id):
user = self.users.pop(user_id)
for friend_id in user.friends:
self.users[friend_id].friends.discard(user_id)
for chat in self.chats.values():
chat.members.discard(user_id)
def send_friend_request(self, from_id, to_id):
if to_id in self.users[from_id].friends:
raise ValueError('already friends')
self.users[to_id].requests_received[from_id] = Status.PENDING
def approve_friend_request(self, from_id, to_id):
self._pending(from_id, to_id)
self.users[to_id].requests_received[from_id] = Status.APPROVED
self.users[from_id].friends.add(to_id) # friendship is mutual
self.users[to_id].friends.add(from_id)
def reject_friend_request(self, from_id, to_id):
self._pending(from_id, to_id)
self.users[to_id].requests_received[from_id] = Status.REJECTED
def _pending(self, from_id, to_id):
if self.users[to_id].requests_received.get(from_id) is not Status.PENDING:
raise ValueError('no pending request')
def start_private_chat(self, first_id, second_id):
if second_id not in self.users[first_id].friends:
raise PermissionError('you can only chat privately with friends')
return self._new_chat({first_id, second_id})
def start_group_chat(self, owner_id, invited_ids):
if not set(invited_ids) <= self.users[owner_id].friends:
raise PermissionError('you can only invite friends')
return self._new_chat({owner_id, *invited_ids})
def post(self, chat_id, user_id, text):
chat = self.chats[chat_id]
if user_id not in chat.members:
raise PermissionError('not a member of this chat')
chat.messages.append((user_id, text))
def _new_chat(self, members):
chat = Chat(next(self._chat_ids), members)
self.chats[chat.chat_id] = chat
return chatTry it:
python
service = ChatService()
for user_id, name in [(1, 'Ana'), (2, 'Ben'), (3, 'Cleo')]:
service.add_user(user_id, name)
try:
service.start_private_chat(1, 2) # not friends yet
except PermissionError:
pass
else:
raise AssertionError('should need friendship first')
service.send_friend_request(1, 2)
service.approve_friend_request(1, 2)
assert 2 in service.users[1].friends and 1 in service.users[2].friends # mutual
chat = service.start_private_chat(1, 2)
service.post(chat.chat_id, 1, 'hello')
assert chat.messages == [(1, 'hello')]
try:
service.post(chat.chat_id, 3, 'let me in') # Cleo is not a member
except PermissionError:
pass
else:
raise AssertionError('non-members must not post')
service.send_friend_request(1, 3)
service.reject_friend_request(1, 3)
assert 3 not in service.users[1].friends
service.remove_user(2)
assert 2 not in service.users[1].friends and 2 not in chat.membersWhat is wrong with the sketch above#
The solution on this page is an outline, and most of it is empty. Each of these was checked by running the code:
PrivateChat(first, second)cannot be created. It callssuper().__init__()without thechat_idthatChatrequires, so it raisesTypeError: Chat.__init__() missing 1 required positional argument: 'chat_id'.- Nearly every method is
pass, including adding and removing users and every friend-request step.UserService().add_user(...)runs but does nothing. - A request lives in two places. Each
Userkeeps both its sent and its received requests, so approving one means updating two objects and keeping them in step. The version above stores a request once, on the receiver. RequestStatushasUNREADandREADas well as accepted and rejected, which mixes "has it been seen" with "what was decided". Those are two separate facts.
Questions to expect next#
- Delivery and history. Store messages in a database keyed by chat and time, and fetch recent ones with a cursor. Online users also need a push channel, such as a long-lived connection.
- Offline users. Keep unread counts and deliver on reconnect.
- Scale. One service cannot hold every user in memory. Shard users and chats, and put a queue between sender and recipients. The message queue lab shows what happens when messages arrive faster than they are delivered, and sharding covers splitting users.
- Blocking, read receipts, group admins. Each is one more rule on the same relationships.