Low-level design: chat application

In a low-level design (LLD) round, “design a chat application” means the classes that store each message once, show every conversation in the same order on every phone, tell the sender whether a message arrived and was read, and run group rooms by their own rules. Four decisions carry this design. The server gives each message the next sequence number of its conversation, and phones order by that number, never by a clock. The sender’s phone picks a client message id, so a send retried after a lost reply stores nothing new. Receipts are records of their own: two marks per member that only move forward. And a group room is the Mediator between its members, so who may post, who receives a message and who is alerted are its rules alone.

The prompt, the requirements and the first design

The prompt, “design a chat application”, hides its hard parts, so the first minutes go on questions. Groups too, and how large? Do senders see delivered and read marks, and in a group, read by how many? What happens to messages sent while a phone is offline, and to a send repeated when the network drops? The answers assumed here:

• C1 A conversation is a direct chat between two people or a group room of up to 256 members.
• C2 Each message gets the next sequence number of its conversation, and every phone shows that order.
• C3 The sender’s phone gives each message a client id; a retried send stores nothing and returns the first number.
• C4 The sender sees whether a message reached each member’s phone and whether the member read it; neither moves back.
• C5 Admins add and remove members; a muted member receives without an alert; a new member sees messages from the moment they joined; an admin may let only admins post.
• C6 A phone that was offline or missed a push asks for everything after the last message it has.
• N1 The model reads no real clock and opens no socket: the time and the transport are given to it.

Out of scope, said aloud: encryption, attachments, typing indicators, alerts to offline phones, and several phones per person.

C2 deserves the first test, because the obvious designs fail it. Three friends plan dinner. Ben’s phone clock runs 90 seconds slow, Asha’s third message is sent twice because its reply was lost, and the network brings message 4 to Chen’s phone before message 3:

"""Three friends plan dinner in a group chat, and Chen's phone shows the conversation three ways.

Ben's phone clock runs 90 seconds slow. Asha's third request reaches the server, but its reply is lost on her weak
connection, so her phone sends it again five seconds later. The network then delivers message 4 to Chen's phone
before message 3. Times are milliseconds on the server's clock; nothing here reads a real clock.
"""

SENDS = [  # (server time, sender, the sender's own message number, text)
    (0, "Asha", "a1", "Are we still on for seven?"),
    (4_000, "Ben", "b1", "Yes. I booked a table for four."),
    (9_000, "Asha", "a2", "Running ten minutes late."),
    (11_000, "Ben", "b2", "No problem, we will order starters."),
    (14_000, "Asha", "a2", "Running ten minutes late."),  # the retry: same message, same number
]
PHONE_CLOCK_ERROR = {"Asha": 0, "Ben": -90_000}  # Ben's phone is 90 s slow
DELAY_TO_CHEN = [300, 200, 3_500, 300, 300]  # one slow path for the third request


def store(dedupe: bool) -> list[dict]:
    """The server's log. Each stored message gets the next number of the conversation."""
    log, seen = [], set()
    for request, (at, sender, client_id, text) in enumerate(SENDS):
        if dedupe and (sender, client_id) in seen:
            continue  # a retry: the message is already stored, under its number
        seen.add((sender, client_id))
        log.append({"seq": len(log) + 1, "sender": sender, "text": text, "request": request, "at": at,
                    "phone_time": at + PHONE_CLOCK_ERROR[sender]})
    return log


def deliveries(log: list[dict]) -> list[dict]:
    """The pushes to Chen's phone, in the order they arrive."""
    return sorted(log, key=lambda m: m["at"] + DELAY_TO_CHEN[m["request"]])


def show(title: str, messages: list[dict]) -> None:
    print(title)
    for m in messages:
        print(f"   {m['sender']:<5} {m['text']}")


every_request = store(dedupe=False)
show("1. Every request stored, shown in the order the pushes arrive", deliveries(every_request))
show("2. Every request stored, sorted by the time on each sender's phone", sorted(every_request, key=lambda m: m["phone_time"]))

numbered = store(dedupe=True)
shown, early = [], {}
for m in deliveries(numbered):
    early[m["seq"]] = m
    while len(shown) + 1 in early:  # show a message only when every earlier number is here
        shown.append(early.pop(len(shown) + 1))
show("3. One message per (sender, number), shown in the conversation's own order", shown)
print(f"The server stored {len(every_request)} messages without the senders' numbers, {len(numbered)} with them.")

1. Every request stored, shown in the order the pushes arrive
   Asha  Are we still on for seven?
   Ben   Yes. I booked a table for four.
   Ben   No problem, we will order starters.
   Asha  Running ten minutes late.
   Asha  Running ten minutes late.
2. Every request stored, sorted by the time on each sender's phone
   Ben   Yes. I booked a table for four.
   Ben   No problem, we will order starters.
   Asha  Are we still on for seven?
   Asha  Running ten minutes late.
   Asha  Running ten minutes late.
3. One message per (sender, number), shown in the conversation's own order
   Asha  Are we still on for seven?
   Ben   Yes. I booked a table for four.
   Asha  Running ten minutes late.
   Ben   No problem, we will order starters.
The server stored 5 messages without the senders' numbers, 4 with them.

Showing pushes as they arrive puts Ben’s answer before Asha’s apology. Sorting by each sender’s phone clock puts both of Ben’s messages before the question they answer. Both views show the apology twice. Only the third view is the same on every phone, because one counter per conversation sets the order and the retry carried the same client id.

The service owns the conversations and hands each new message to a transport port. Six choices shape the design:

• Sequence numbers per conversation: the conversation counts its own messages, so no clock decides the order.
• Client message ids: a sender and a client id name one message, so a retry finds it.
• Cumulative receipts: a phone reports “everything up to 41 arrived”, and read marks only grow.
• The room as Mediator: members never reach each other; the room decides who receives and who is alerted.
• Transport behind a port: a WebSocket server and a fake network implement one interface.
• Jittered reconnects: after a restart, phones wait a random time before reconnecting, so they arrive spread out.

The deep dives that decide whether this design holds:

1. Why one counter per conversation, and who keeps it when there are several servers?
2. Why look up the client id before any other rule?
3. How do receipts for a group of 200 stay small, and how is “read by 37 of 199” counted?
4. Where do mute, join and posting rules live, and how does a new rule arrive?
5. What does a phone do with copies, late pushes and gaps, and when does it ask the server?
6. What happens when a server restarts and 10,000 phones reconnect at once?

An answer is judged on the requirements, ordering and retries, receipts, the room’s rules, and failure handling.

Sending once: one counter per conversation, one message per client id Pro: opens with a Pro, Premium or Ultimate pass