Design a Chat System

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 12 — rewritten and condensed for teaching.

Almost everyone uses a chat app, but "chat" means different things. One-on-one apps include Facebook Messenger, WeChat, and WhatsApp. Group-focused office chat means Slack. Game chat such as Discord adds large groups and low-latency voice. Pinning down which one the interviewer means is the first job. You don't want to design Slack when they had WhatsApp in mind.

What you'll be able to do after this lesson:

• Compare polling, long polling, and WebSocket for server-to-client delivery.
• Split a chat system into stateless, stateful, and third-party parts.
• Choose storage and message IDs for chat history, and explain why a key-value store fits.
• Trace 1:1, multi-device, and group message flows, and build presence with heartbeats and pub/sub.

---

Step 1: Understand the Problem and Establish Scope

Candidate asks	Interviewer answers
1:1 or group?	Both
Mobile, web, or both?	Both
Scale?	50 million DAU
Group size limit?	100 people
Key features? Attachments?	1:1 chat, group chat, online indicator. Text only
Message size limit?	Under 100,000 characters
End-to-end encryption?	Not required now. Discuss if time allows
How long to keep history?	Forever

We'll design something like Facebook Messenger, with:

• 1:1 chat with low delivery latency
• Small group chat (up to 100 members)
• Online presence
• Multiple devices logged in to the same account at once
• Push notifications

---

Step 2: High-Level Design

Clients never talk to each other directly. Each one connects to a chat service, which must:

• receive messages from clients,
• find the recipients of each message and relay it to them, and
• hold messages for offline recipients until they come back online.

flowchart LR
  S[Sender] -- "message" --> CS[Chat service] -- "message" --> R[Receiver]
  CS -.-> STORE[(Store if offline)]

Choosing a network protocol

The sender side is easy. The client initiates the request, so plain HTTP works. With the keep-alive header the connection stays open, which avoids repeated TCP handshakes. Facebook originally sent messages over HTTP.

The receiver side is harder. HTTP is client-initiated, so the server can't simply push a message whenever one arrives. There are three ways around this.

Polling

The client asks every few seconds whether there are new messages. Most of the time the answer is "no," so the server spends resources on useless requests.

sequenceDiagram
  participant C as Client
  participant S as Server
  C->>S: new messages?
  S-->>C: no
  C->>S: new messages?
  S-->>C: no
  C->>S: new messages?
  S-->>C: yes: here they are

Long polling

The client sends a request and the server holds it open until there's a message or a timeout. Then the client immediately reconnects.

sequenceDiagram
  participant C as Client
  participant S as Server
  C->>S: new messages? (held open)
  Note over S: wait…
  S-->>C: message arrives → respond
  C->>S: new messages? (held open again)
  Note over S: …timeout
  S-->>C: no messages

Drawbacks of long polling:

• The sender and receiver may be on different servers. HTTP servers are usually stateless, so with round-robin load balancing, the server that receives a message may not be the one holding the receiver's long-poll connection.
• The server can't easily tell when a client has disconnected.
• It's still wasteful. Users who rarely chat keep reconnecting after every timeout.

WebSocket

WebSocket is the standard answer for pushing data from server to client:

• The client initiates it as an HTTP connection, which is then upgraded with a handshake.
• It is bidirectional and persistent, so the server can push whenever it likes.
• It runs on ports 80 and 443, like HTTP and HTTPS, so it usually works through firewalls.

sequenceDiagram
  participant C as Client
  participant S as Server
  C->>S: HTTP GET + Upgrade: websocket
  S-->>C: 101 Switching Protocols
  Note over C,S: persistent, bidirectional connection
  S-->>C: message
  C->>S: message
  S-->>C: message

Because WebSocket is bidirectional, there's no strong reason to keep HTTP for sending. Use WebSocket for both directions. That simplifies both client and server. The cost is that persistent connections must be managed carefully on the server.

High-level components

Only chat needs WebSocket. Sign-up, login, profiles, and similar features can use ordinary HTTP request/response. The system splits into three groups:

• Stateless services: login, sign-up, user profiles, and so on, behind a load balancer that routes by path. They can be a monolith or microservices, and many can be bought rather than built. One matters for chat: service discovery, which gives each client the hostname of a chat server to connect to.
• Stateful service: the chat service is the only stateful part. Each client keeps a persistent connection to one chat server and normally stays on it while the server is healthy. Service discovery works with the chat service so that no server gets overloaded.
• Third-party integration: push notifications tell users about new messages while the app isn't running. See Lesson 10.

Scalability: why not one server?

Could it all fit on one machine? At 1 M concurrent users, if each connection needs about 10 KB of server memory (a rough figure that depends heavily on the language), that's only about 10 GB. A single modern server could hold every connection.

Don't propose that as the final design. A single server is a single point of failure, among other problems, and an interviewer will see it as a red flag. Starting from one server is fine, as long as you say it's a starting point.

flowchart LR
  U[Users] -- "WebSocket" --> CHAT[Chat servers]
  U -- "WebSocket" --> PRES[Presence servers]
  U -- "HTTP" --> LB[Load balancer] --> API["API servers<br/>login · signup · profile"]
  CHAT --> KV[(Key-value store<br/>chat history)]
  PRES --> KV
  CHAT --> NOTIF[Notification servers]
  API --> KV
  API --> SD[Service discovery]

• Chat servers: send and receive messages.
• Presence servers: manage online/offline status.
• API servers: everything else (login, sign-up, profile changes).
• Notification servers: push notifications.
• Key-value store: chat history, so returning users see past messages.

Check: protocols

Quiz

Polling, long polling, WebSocket

1 / 3

Why does plain HTTP make the receiver side of chat hard?

Pick an answer to see if you are right.

Storage

Two kinds of data:

1. Generic data: profiles, settings, friend lists. Store it in a reliable relational database, with replication and sharding for availability and scale.
2. Chat history, which has an unusual access pattern:
   • The volume is enormous. In 2016, Messenger and WhatsApp together handled 60 billion messages a day.
   • Mostly recent chats are read, but random access still matters for search, mentions, and jumping to a specific message.
   • Reads and writes are about 1:1 in 1:1 chat apps.

Use a key-value store for chat history:

• It scales horizontally easily.
• It gives very low latency.
• Relational databases handle the long tail of data poorly: once indexes grow large, random access gets expensive.
• It is proven at scale. Facebook Messenger uses HBase, and Discord uses Cassandra. Lesson 6's key-value store is exactly this kind of system.

Data models

1:1 messages:

Column	Type
message_id	bigint (primary key)
message_from	bigint
message_to	bigint
content	text
created_at	timestamp

The primary key message_id determines message order. created_at can't, because two messages can share a timestamp.

Group messages:

Column	Type
channel_id	bigint (partition key)
message_id	bigint
user_id	bigint
content	text
created_at	timestamp

The primary key is (channel_id, message_id), and channel_id is the partition key, because every group-chat query works within one channel (a channel is the same thing as a group here).

Message IDs

message_id must be unique and sortable by time (newer means larger). Options:

1. AUTO_INCREMENT: NoSQL stores usually don't offer it.
2. A global 64-bit generator such as Snowflake, from Lesson 7.
3. A local sequence number generator: IDs only need to be unique within a channel, since ordering only matters inside a 1:1 conversation or group. This is simpler than a global generator.

---

Step 3: Design Deep Dive

Service discovery

Service discovery recommends the best chat server for a client, based on criteria such as location and server capacity. Apache ZooKeeper is a popular choice. Chat servers register with it, and it picks one for each client.

sequenceDiagram
  participant A as User A
  participant LB as Load balancer
  participant API as API servers
  participant ZK as Service discovery (ZooKeeper)
  participant C2 as Chat server 2
  A->>LB: 1. log in
  LB->>API: 2. forward
  API->>ZK: 3. authenticate, then pick best chat server
  ZK-->>API: chat server 2
  API-->>A: connect to chat server 2
  A->>C2: 4. WebSocket connect

1:1 message flow

flowchart LR
  A[User A] -- "1" --> C1[Chat server 1]
  C1 -- "2: get ID" --> IDG[ID generator]
  C1 -- "3" --> MQ[[Message sync queue]]
  MQ -- "4: persist" --> KV[(KV store)]
  MQ -- "5a: B online" --> C2[Chat server 2]
  MQ -- "5b: B offline" --> PN[Push notification servers]
  C2 -- "6: WebSocket" --> B[User B]

1. User A sends a message to chat server 1.
2. Chat server 1 gets a message ID from the ID generator.
3. It puts the message on the message sync queue.
4. The message is stored in the key-value store.
5. If User B is online, the message is forwarded to chat server 2, where B is connected (5a). If B is offline, a push notification goes out instead (5b).
6. Chat server 2 delivers it to User B over their persistent WebSocket.

Syncing messages across devices

User A has a phone and a laptop, each with its own WebSocket connection. Each device keeps a cur_max_message_id, the newest message ID it has. A message is new to a device if:

• its recipient is the logged-in user, and
• its message_id > the device's cur_max_message_id.

Each device tracks its own cursor, so each one pulls exactly what it is missing from the key-value store.

flowchart LR
  P["Phone<br/>cur_max_message_id = 653"] --- CS1[Chat server 1]
  L["Laptop<br/>cur_max_message_id = 842"] --- CS1
  CS1 --- KV[(KV store)]

Practice: multi-device sync

Implement sync(store, user, cursor). store is a list of (message_id, recipient, text) tuples. Return (new_messages, new_cursor), where:

• new_messages holds the messages whose recipient is user and whose message_id > cursor, sorted by message_id, and
• new_cursor is the largest returned ID, or the old cursor if nothing is new.

The wrapper syncs each device listed for one user. Input: line 1 is the user, line 2 is device=cursor pairs, and each remaining line is message_id recipient text….

Small group chat flow

When User A posts in a group with B and C, the message is copied into each other member's message sync queue, one for B and one for C. Think of each queue as the recipient's inbox.

flowchart LR
  A[User A] --> CS[Chat server]
  CS --> QB[["B's inbox (sync queue)"]] --> B[User B]
  CS --> QC[["C's inbox (sync queue)"]] --> C[User C]

This suits small groups:

• Sync is simple. Each client only checks its own inbox.
• Copies are cheap when groups are small. WeChat does the same and caps groups at 500.

For very large groups, storing a copy per member costs too much.

On the receiving side, a user's single inbox collects messages from many senders and groups:

flowchart LR
  A[User A] --> CS1[Chat server 1] --> QC[["C's inbox"]]
  B[User B] --> CS2[Chat server 2] --> QC
  QC --> C[User C]

Practice: group inbox fanout with local IDs

Implement Chat.send(channel, sender, text):

• Assign the next local message ID for that channel. Each channel counts 1, 2, 3, … on its own.
• Append (channel, message_id, sender, text) to the inbox of every member except the sender.
• Return (message_id, copies_written).

Input: line 1 is the groups as channel:member,member,… pairs, and each remaining line is send <channel> <sender> <text…>. The wrapper then prints every inbox.

Notice that g1 and g2 both have a message with ID 1. That's fine, because ordering only has to hold within a channel, and the key is (channel_id, message_id).

Online presence

Presence servers manage the green "online" dot and talk to clients over WebSocket.

• Login: once the WebSocket connection is up, store the user's status as online with a last_active_at timestamp in the key-value store.
• Logout: set the status to offline.
• Disconnection is the tricky case. Marking a user offline the moment their connection drops, and online again when it returns, makes the dot flicker constantly, for example as someone's phone goes through a tunnel. That's a poor experience.

Use a heartbeat instead. An online client sends a heartbeat every few seconds. If the server hasn't received one within x seconds, the user is marked offline. In the book's example, the client sends a heartbeat every 5 seconds, sends 3, then disconnects. With x = 30 seconds, the user goes offline only after 30 seconds without a heartbeat.

sequenceDiagram
  participant C as Client
  participant P as Presence server
  C->>P: heartbeat (t=0)
  C->>P: heartbeat (t=5)
  C->>P: heartbeat (t=10)
  Note over C: disconnected
  Note over P: no heartbeat for 30 s
  P->>P: mark offline (t ≥ 40)

Practice: heartbeat presence

Implement presence(heartbeats, queries, timeout). heartbeats maps each user to a list of heartbeat times. For each (user, t) query, the user is online if they have a heartbeat at or before t and t - last_heartbeat < timeout. Otherwise they're offline.

Input: line 1 is timeout, line 2 is user:t1,t2,… pairs, and each remaining line is user t.

Online status fanout

How do friends learn that a user's status changed? Presence servers use publish-subscribe with one channel per friend pair. When User A's status changes, it's published to channels A-B, A-C, and A-D, which friends B, C, and D subscribe to. Updates reach clients over WebSocket.

flowchart LR
  A["User A<br/>status change"] --> PS[Presence servers]
  PS --> AB[[channel A-B]] --> B[User B]
  PS --> AC[[channel A-C]] --> C[User C]
  PS --> AD[[channel A-D]] --> D[User D]

This works for small groups, and WeChat uses a similar approach with its 500-member cap. For a 100,000-member group, though, each status change would create 100,000 events. For large groups, fetch presence only when a user opens the group or manually refreshes the friend list.

Check: deep dive

Quiz

Flows, sync, and presence

1 / 4

In the 1:1 flow, User B is offline when User A sends a message. What happens?

Pick an answer to see if you are right.

---

Step 4: Wrap Up

The design supports 1:1 and small group chat, using WebSocket for real time. It has chat servers (messaging), presence servers (online status), push notification servers, a key-value store (history), and API servers (everything else). Extra talking points:

• Media (photos and videos): far larger than text, so discuss compression, cloud storage, and thumbnails.
• End-to-end encryption: as in WhatsApp, only the sender and recipient can read messages.
• Client-side message caching to cut data transfer.
• Faster load times: Slack built a geographically distributed edge cache (Flannel) for users, channels, and more.
• Error handling:
  • Chat server failure: a server may hold hundreds of thousands of connections. If it dies, service discovery hands clients a new server to reconnect to.
  • Message resend: retries and queueing.

---

Key Takeaways

• Polling wastes requests, and long polling struggles with routing and detecting disconnects. WebSocket gives a persistent, bidirectional channel, so use it for both sending and receiving.
• Stateless API services sit behind a load balancer. The stateful chat service holds connections, with service discovery (ZooKeeper) choosing servers. Push notifications are a third-party integration.
• Chat history lives in a key-value store (HBase at Messenger, Cassandra at Discord), keyed by message_id for 1:1 chat or (channel_id, message_id) for groups. Local per-channel IDs are enough for ordering.
• Multi-device sync uses a per-device cursor. Small groups use per-member inboxes.
• Presence uses heartbeats with a timeout, plus pub/sub per friend pair, fetched on demand for large groups.

Previous lesson: Design a News Feed System.

Next lesson: Design a Search Autocomplete System — tries with cached top-k, offline data gathering, and prefix sharding.

---

Reference Materials

1. Erlang at Facebook
2. Messenger and WhatsApp process 60 billion messages a day — The Verge
3. Long tail — Wikipedia
4. The Underlying Technology of Messages — Facebook Engineering
5. How Discord Stores Billions of Messages
6. Announcing Snowflake — Twitter Engineering
7. Apache ZooKeeper
8. From nothing: the evolution of WeChat background system (in Chinese)
9. End-to-end encryption — WhatsApp FAQ
10. Flannel: An Application-Level Edge Cache to Make Slack Scale