Design a Chat App

Design a mobile-first messaging app that supports one-to-one chats and group chats of up to a few hundred people. Messages show ticks for sent, delivered and read; contacts show whether someone is online or when they were last seen; and a phone that was offline for a day must catch up on everything it missed, in the right order, when it reconnects. Users may be signed in on a phone and a laptop at the same time.

Messages are end-to-end encrypted, so the servers relay and store ciphertext they cannot read.

There are around 500 million daily users and hundreds of millions of devices connected at once on unreliable mobile networks. In 45 minutes, design the connection layer, message flow and storage, ordering and receipts, presence and offline sync, and explain at a high level how encryption changes the design.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Social & Messaging · problem 14 of 70

Ask before you design. Try answering each yourself, then compare.

1. What scale?
   Typical answer

   500 million daily users sending about 40 messages each per day, with up to 300 million devices connected at peak.

2. How big can groups be?
   Typical answer

   Up to 256 members. Broadcast channels with millions of followers are out of scope.

3. Does the server keep message history forever?
   Typical answer

   No. The server stores encrypted messages until every recipient device has acknowledged them, for at most 30 days. Long-term history lives on devices and in optional encrypted backups.

4. What ordering guarantee do we need?
   Typical answer

   Within a conversation everyone sees messages in the same order. There is no ordering requirement across different conversations.

5. Are media attachments in scope?
   Typical answer

   Briefly: they are encrypted on the device, uploaded to blob storage, and the message carries the reference and key.

6. How accurate must presence be?
   Typical answer

   Online status within about 10 to 30 seconds is fine. Users can hide last-seen.

7. What if the recipient app is closed?
   Typical answer

   Send a push notification through the mobile OS push service so the app wakes and syncs.

Requirements

Functional

• Send and receive 1:1 and group messages (up to 256 members) with text and media references.
• Show sent, delivered and read receipts per message.
• Show online status and last seen for contacts, with a privacy setting to hide them.
• Deliver messages to devices that were offline, in order, when they reconnect; support multiple devices per user.
• End-to-end encryption: the server never sees message plaintext.

Non-functional

• Message delivery p99 under 300 ms when both users are online in the same region.
• No message is lost once the server has acknowledged it; no duplicates shown to users.
• 99.99% availability for sending; 300 M concurrent connections at peak.
• Battery and data friendly: no aggressive polling.

Out of scope

• Voice and video calls.
• Large broadcast channels and bots.
• Search over message history on the server (impossible with E2EE).

Back-of-the-envelope estimates

• Messages: 500 M × 40 = 20 B/day ≈ 230,000/s on average, about 700,000/s at peak. Group messages multiply deliveries: with ~1.5 deliveries per message on average, that is roughly 1 M deliveries/s at peak.
• Connections: 300 M concurrent sockets. A tuned gateway holds around 200,000 mostly idle connections, so we need about 1,500 gateway servers plus headroom for a region failing over.
• Storage: ~200 bytes of ciphertext and headers per message ≈ 4 TB/day written. Because messages are deleted after all devices acknowledge (most within minutes, the long tail up to 30 days), the live backlog is a few tens of TB, not petabytes.
• Presence: a keepalive every 30 s from 300 M devices is 10 M pings/s, which is why presence must ride on the existing connection and only publish changes, not every ping.

The number of concurrent long-lived connections and the delivery rate drive the design; storage is modest because the server is a relay, not an archive.

API

WebSocket wss://chat.example/v1/connect?device=…   (TLS, token auth)
  client -> server: SEND {convId, clientMsgId, ciphertext[] per device}   server -> client: ACK {clientMsgId, seq}
  server -> client: MSG {convId, seq, sender, ciphertext}                 client -> server: RECEIPT {convId, seq, delivered|read}
  client -> server: SYNC {cursors: {convId: lastSeq}}                     server -> client: MSG... then SYNC_DONE
  server -> client: PRESENCE {userId, online|lastSeen}
GET  /v1/keys/{userId}          -> {devices:[{deviceId, identityKey, signedPrekey, oneTimePrekey}]}
POST /v1/media                  -> {uploadUrl, mediaId}   (bytes encrypted on device)

Every send carries a client-generated message id, and the server's ACK returns the conversation sequence number, so retries are idempotent and the client knows the final order.

Data model

messages(conv_id, seq, sender_device, payload_per_device, created_at) in a wide-column store, partitioned by conv_id and clustered by seq, so 'everything after seq N' is a single range scan. Rows carry a 30-day TTL and are deleted early once all devices acknowledge.

conversations(conv_id, members, next_seq) and user_convs(user_id, conv_id): membership is small and read on every send, so it is cached.

device_cursors(device_id, conv_id, delivered_seq, read_seq) drive receipts and offline sync.

Session registry: in-memory store mapping device_id → gateway_id with a TTL refreshed while the socket is open. Presence: user_id → {online, last_seen} in the same kind of store. Key directory: per-device public identity keys and a pool of one-time prekeys in a strongly consistent store, because handing out a prekey twice weakens security.

High-level design

Connecting. Each app opens a WebSocket through an L4 load balancer to one of many Chat Gateways. The gateway authenticates the device, records device → gateway in the Session Registry, and tells the Presence Service the user is online. Before messaging a contact for the first time, the sender fetches that contact's device public keys from the Key Directory and sets up an encrypted session.

Sending. The sender encrypts the message for every recipient device and sends it over its socket. The gateway forwards it to the Message Service shard that owns the conversation. That shard checks the client message id for duplicates, assigns the next sequence number, appends the ciphertext to the Message Store, and then acknowledges the sender (one tick). For each recipient device it looks up the current gateway in the Session Registry and publishes the message onto that gateway's topic in the Delivery Queue.

Receiving. The recipient's gateway consumes its topic and pushes the message down the socket. The device stores it, replies with a delivered receipt, and later a read receipt; both travel back to the sender the same way as messages. If a device has no live session, the Push Worker sends a content-free wake-up notification through the OS push service. When the app reconnects it sends its last sequence number per conversation and the Message Service streams everything newer from the store.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Ordering, idempotency and receipts

Give every conversation a single owner at a time: hash conv_id to a Message Service shard, which assigns gap-free sequence numbers. This gives one total order per conversation without a global clock. The client generates clientMsgId; the shard remembers recent ids per sender so a retry after a lost ACK returns the original sequence number instead of storing a duplicate. Receipts are cursors, not per-message flags: a device that reports 'delivered up to 57' covers every earlier message, which collapses thousands of receipt events in busy groups. In groups the sender sees 'delivered' only when every member's devices have reached that sequence, which the service computes from the cursors.

Offline sync and multiple devices

Treat each conversation as a log and each device as a reader with a cursor. On reconnect, the device sends its cursors and the server returns all newer entries, in order, in pages. This one mechanism covers flaky connections, phones that were off for days, and a laptop joining alongside a phone. Because the server deletes a message only after every device of every recipient has acknowledged it (or after 30 days), devices offline longer than that must restore from their encrypted backup. For a user with many conversations, keep a per-user 'conversations with new messages' index so sync does not scan every chat.

Presence at scale

Presence is derived from the connection itself: the gateway already knows when a socket opens, closes or misses keepalives, so no separate heartbeat API is needed. A disconnect starts a short grace timer (around 20 seconds) before publishing 'offline', which hides brief network drops. Changes are published only to users who are actively looking, for example someone with that chat open or the contact list on screen. Clients subscribe while the screen is visible and unsubscribe when it is not, which turns an all-to-all problem into a small, demand-driven one. Last-seen is stored as a timestamp and respects the privacy setting at read time.

End-to-end encryption, at a high level

Each device creates a long-term identity key pair and uploads public keys plus a batch of one-time prekeys to the Key Directory. To start a chat with someone who is offline, the sender takes one of their prekeys and derives a shared secret without a live handshake, then advances the key with every message so that a stolen key cannot decrypt past traffic. For multiple devices, the sender encrypts once per recipient device. For groups, each member shares a sender key with the others over the pairwise sessions, so a group message is encrypted once and stays a single payload. The server only sees metadata: who talks to whom and when. That rules out server-side search and content moderation, and makes key change warnings and backups part of the product design.

Failure modes

• If a gateway dies, its devices reconnect elsewhere (with jittered backoff), re-register in the Session Registry, and sync from their cursors, so nothing is lost.
• If the Session Registry has a stale entry, delivery to the old gateway fails; the message is already stored, so the device receives it on its next sync, and a push notification wakes it if needed.
• If a Message Service shard fails, a replica takes over ownership of its conversations after a lease expires; senders retry with the same client ids, so no duplicates appear.
• If the OS push service is slow or throttles us, messages still wait safely in the store until the app opens.

Core algorithm in code

class Conversation:
    """Server-side log for one conversation: assigns sequence numbers,
    ignores retried sends, and lets each device sync from its own cursor."""
    def __init__(self, members):
        self.members = members
        self.log = []                 # (seq, sender, ciphertext)
        self.by_client_id = {}        # (sender, client_msg_id) -> seq, for idempotent retries
        self.delivered = {}           # device -> highest seq delivered
        self.read = {}                # device -> highest seq read

    def send(self, sender, client_msg_id, ciphertext):
        key = (sender, client_msg_id)
        if key in self.by_client_id:  # the phone retried after a lost ack
            return self.by_client_id[key]
        seq = len(self.log) + 1
        self.log.append((seq, sender, ciphertext))
        self.by_client_id[key] = seq
        return seq

    def sync(self, device, after_seq):
        return [m for m in self.log if m[0] > after_seq]

    def ack(self, device, seq, kind):
        marks = self.delivered if kind == "delivered" else self.read
        marks[device] = max(marks.get(device, 0), seq)

    def status(self, seq, recipients):
        if all(self.read.get(d, 0) >= seq for d in recipients):
            return "read"
        if all(self.delivered.get(d, 0) >= seq for d in recipients):
            return "delivered"
        return "sent"


conv = Conversation(["alice", "bob"])
s1 = conv.send("alice", "a-001", b"<ciphertext 1>")
s2 = conv.send("alice", "a-002", b"<ciphertext 2>")
retry = conv.send("alice", "a-002", b"<ciphertext 2>")      # network blip: same id again
print("seqs:", s1, s2, "retry ->", retry, "| log length:", len(conv.log))

bob_phone, bob_laptop = "bob:phone", "bob:laptop"
conv.ack(bob_phone, 2, "delivered")
print("msg 2 after phone ack:", conv.status(2, [bob_phone, bob_laptop]))
print("laptop reconnects and syncs:", [m[0] for m in conv.sync(bob_laptop, after_seq=0)])
conv.ack(bob_laptop, 2, "delivered")
conv.ack(bob_phone, 2, "read")
conv.ack(bob_laptop, 2, "read")
print("msg 2 after both devices read:", conv.status(2, [bob_phone, bob_laptop]))

Trade-offs

• Persistent WebSockets give instant delivery and cheap idle cost but make gateways stateful, so deploys and failures cause reconnect storms that must be throttled.
• A single owner per conversation gives simple total ordering but costs a hot shard for very busy groups, which caps group size.
• Deleting messages after acknowledgement keeps storage tiny and limits exposure, but costs server-side history, so new devices rely on backups.
• Encrypting per recipient device is simple and secure but makes each send grow with the number of devices; sender keys cut that for groups at the cost of more complex key rotation when members leave.
• Demand-driven presence saves enormous traffic but makes status slightly stale for contacts nobody is watching.

What a strong answer shows

• Chooses persistent connections and explains how to route a message to the gateway holding the recipient's socket.
• Persists before acknowledging and gives per-conversation ordering with sequence numbers.
• Makes sends idempotent and models receipts and offline sync as per-device cursors.
• Designs presence to avoid an all-to-all broadcast.
• Explains how E2EE limits what the server can do and how it affects multi-device and groups.
• Sizes connections and gateways from the concurrency number.

Mistakes to avoid

• Using client timestamps to order messages.
• Acknowledging a message before it is durably stored.
• Broadcasting every presence change to every contact.
• Designing server-side search or moderation of message text while also claiming end-to-end encryption.
• Forgetting that one user has several devices that each need delivery and sync.

Follow-ups to expect

• How would you support groups of 100,000? (Switch to a sender-key broadcast model with fan-out on read from a channel log.)
• How do you handle a user who changes phones? (New identity key, key-change notice to contacts, history from encrypted backup.)
• How would you deliver across regions? (Home-region per conversation; gateways forward to that region; cross-region queues for remote recipients.)
• How would you rate limit spam without reading content? (Metadata signals: send rate, new-account age, reports from recipients.)

Practice next