Chat Application

Real-Time Messaging System

Design the core of a chat server: direct and group conversations, server-assigned order, an offline queue flushed on reconnect, delivery and read receipts kept as watermarks, and paged history.

Overview

A chat server takes a message from one user and gets it to everyone else in the conversation, in the same order for all of them, whether they are online now or connect an hour later. It also tells the sender how far the message got: stored, delivered to every device, read by everyone.

Interviewers use this problem to see whether you can pick the right source of order (the server, not the clocks on the phones), keep an offline user's messages without losing or reordering them, and track receipts without storing one row per message per reader. Concurrency is part of it too: two people in a group send at the same moment, and both messages must get distinct, gap-free positions.

A strong answer gives each conversation its own sequence counter and lock, pushes to online users and queues for offline ones in the same locked step, and keeps two numbers per member (delivered up to, read up to) instead of a status on every message.

Scoping the problem

One-to-one only, or groups too? — Groups add membership, admins and receipts from many readers — Both; groups have admins
How big can a group be? — Decides whether sending copies to every member is fine — Small groups, tens to hundreds of members
What must the sender see? — Decides what receipts to track — Sent, delivered to all, read by all
What happens when a user is offline? — Needs a queue per user and a flush on reconnect — Queue on the server, deliver on connect in order
Does a new group member see old messages? — Changes where their watermarks start — No, they start at the current end
Media, typing indicators, presence? — Each is its own feature — Name them; typing is not stored
One server or many? — Decides how order and routing are shared — One process here; many servers as a follow-up

Core entities

There is no User class: a user is a name that appears in member sets, the socket table and the offline queues. A direct chat and a group are the same class; a direct chat simply has two members and no admins.

Receipts as watermarks

A receipt is 'this member has everything up to seq N', not 'this member has message 17'. Because a conversation is delivered in order, one number per member per kind of receipt says everything. The status of message seq is READ when every other member's read watermark is at least seq, DELIVERED when every delivered watermark is, and SENT otherwise.

The trace below is the start of the demo, for message 1 in a group of Alice, Bob and Carol.

1 — Alice sends m1; Bob online, Carol offline — 1 / 0 — 0 / 0 — SENT
2 — Carol connects; her queue is flushed — 1 / 0 — 1 / 0 — DELIVERED
3 — Bob reads up to 1 — 1 / 1 — 1 / 0 — DELIVERED
4 — Carol reads up to 1 — 1 / 1 — 1 / 1 — READ

Status per message per reader — 1,000 × 49 = 49,000 — 20 writes
Two watermarks per member (the code) — 50 × 2 = 100 — 1 write

Order and thread safety

The server decides the order. Each conversation has a counter, and send takes the conversation's lock, gives the message the next sequence number, stores it and hands it to every recipient before releasing the lock. Two messages in one conversation therefore get consecutive numbers and reach every device in number order. Different conversations have different locks and do not wait for each other.

The server lock guards the socket table and the offline queues. send takes the conversation lock and then, briefly, the server lock; connect takes the server lock to move the queue, releases it, and only then takes each conversation lock to update watermarks. No code holds the server lock while waiting for a conversation lock, so there is no deadlock. connect also moves the queue and marks the user online in one locked step, so a message sent during the reconnect lands after the queued ones, not before.

The demo runs 4 threads that each send 50 messages into one group, and asserts that the sequence numbers are exactly 1 to 200 and that both the online member and the member who connects afterwards receive them in that order.

Paging history

History is read backwards in pages: 'the 20 messages before seq 181'. A cursor on the sequence number stays correct when new messages arrive, whereas an offset ('skip 40') shifts by one every time someone sends. The same query in SQL uses the primary key, so each page is an index range read.

4 — bob — msg 2
5 — bob — msg 3

The next page passes the smallest seq on this page, 4, as the new cursor.

What you will be able to do

Explain why the server, not the client clock, orders a conversation, and implement it with a counter and a lock per conversation.
Deliver to online users at once and queue for offline users, flushing the queue in order on reconnect.
Keep delivered and read receipts as two watermarks per member and compute the sender's status from them.
Page history with a sequence cursor, in Python and in SQL.
Name the lock order and show a test where many threads send into one conversation.

Functional requirements

Direct conversations (one per pair of users) and groups with admins
send(conversation, sender, text) gives the message the next sequence number in that conversation
Online recipients get the message at once; offline recipients get it, in order, when they connect
mark_read(conversation, user, up_to_seq) records that the user has read everything up to a message
status(conversation, seq) tells the sender SENT, DELIVERED (to every recipient) or READ (by every recipient)
history(conversation, user, before, limit) pages backwards with a sequence cursor
Only admins add or remove members; non-members cannot send or read

Non-functional requirements

Every member sees a conversation in the same order: the server assigns gap-free sequence numbers
No message is lost while a recipient is offline
Receipts cost two numbers per member, not a row per message per reader
Thread safe: one lock per conversation, one server lock, always taken conversation first
History pages stay correct while new messages arrive

Interview questions

Why not order messages by the timestamp the phone sends?
How does this change with many chat servers?
How do you handle a group with 100,000 members?
What happens if the client sends the same message twice because it did not see the reply?
How would you add typing indicators and online presence?