Case study: Chat (WhatsApp)

Chat looks simple: one person sends, another person reads. At 50 million users it is a hard problem. Phones stay connected for hours. Messages must not be lost. Replies must appear after the question. The interviewer asks: "Design a chat app. What happens between the moment I tap send and the moment my friend sees the message?"

A weak answer draws a server and a database, and says "use WebSockets". A strong answer follows one message step by step. It saves the message before it delivers it. It gives each chat its own order. It says what happens when the friend is offline. It counts the connections, the messages and the storage.

At SDE-1 level you should follow one message from sender to receiver. At SDE-2 level you should add order, offline sync and the numbers. At SDE-3 level you should also handle a server that fails, and the cost of presence ("online now").

Quick recap (lessons 49 and 59). Servers have different clocks, so sorting by timestamp can put a reply before its question. A counter for each chat, raised in one atomic step, gives an exact order inside that chat: 41, 42, 43. A missing number shows a missing message. A log keeps messages for a retention time. Each consumer keeps its own offset. A topic is split into partitions, and the partition is hash(key) mod the number of partitions. Order holds only inside one partition, so use a key such as the chat ID. A consumer group shares the partitions, one consumer for each.

Think about a post office. You give your letter to the counter. The clerk writes a number on it and puts it in a safe cabinet. Only then does the clerk say "received". Postmen carry letters to people who are at home. If the person is out, the letter waits in the cabinet. When the person comes back, they say "my last letter was number 41", and the clerk hands over 42, 43 and 44.

A chat system works the same way. The scope here: one phone for each user, and text messages. A photo is uploaded elsewhere and sent as a link. A chat is one-to-one, or a group of up to 256 members.

The parts

• Gateway servers hold the WebSocket connections of phones (lesson 75). A load balancer sends each new connection to the gateway with the fewest connections (lesson 28).
• The session map says which gateway holds each user. It is in Redis (lesson 37). The key is the user, the value is the gateway, and the key has a time to live (TTL) of 90 seconds. The phone sends a ping every 30 seconds. A ping is a tiny message that says "I am still here". Each ping makes the gateway refresh the key. A phone that goes silent disappears from the map after 90 seconds. With many users, the map is split over several Redis servers by user ID (lesson 43).
• The chat service saves messages and gives them numbers.
• The message store keeps all messages. It is split into shards by chat ID (lesson 43), with consistent hashing and virtual nodes (lesson 44).
• A log (lesson 59) carries "message saved" events to the delivery workers, which push the message to the right gateway. The topic is partitioned by chat ID.

The path of one message

1. The sender's phone sends the message over its connection. It adds a client message ID, a random value made on the phone.
2. The gateway passes it to the chat service.
3. The chat service raises the counter of the chat by 1 (lesson 49). It saves the message with that sequence number. The counter and the message are in one transaction, so a failed save gives the number back and leaves no gap. A unique constraint on the chat ID and the client message ID stops a repeat from being saved twice (lessons 22 and 61).
4. The service writes a "message saved" event to the log, and only then answers the sender: sent. So "sent" means "safely stored". If the log write fails, the sender gets an error and sends again. The repeat finds the saved row, and the service writes the event again. A phone ignores a sequence number that it already has.
5. A delivery worker reads the event. A group has at most 256 members, so one message makes at most 255 deliveries, a small fixed number. For each member of the chat (except the sender) the worker looks in the session map.
6. If the member is online, the worker sends the message to that member's gateway, and the gateway writes it to the phone. The phone answers delivered.
7. If the member is offline, nothing more happens now. The message is already in the store. A push notification is a short message sent through the phone system's own service. It can wake a closed app. The phone then asks for what it missed.
8. When the member opens the chat, the phone says read.

If any step fails before the sender sees "sent", the sender sends again. The client message ID makes that safe.

Order inside a chat

The sequence number from the chat counter gives one exact order for all members. Phones sort by it. If a phone has 41 and then receives 43, it knows that 42 is missing, and it asks for it. The order across different chats does not matter. The counter is a row on the same shard as the chat. One row takes about 500 updates per second (lesson 49). A chat of 256 members never gets near that.

Receipts as cursors

Do not store a "delivered" and a "read" row for each message and each member. Store two numbers for each member and each chat: the delivered cursor and the read cursor. "Delivered up to 57" means messages 1 to 57. A message shows "delivered to all" when the lowest delivered cursor in the group has reached its number.

Offline users

A returning phone sends its last sequence number for each chat. The server answers with the messages after it, in pages. No second copy of the message exists for the offline user. The same flow repairs a lost push and a lost connection.

Presence

Presence is "online now" or "last seen". A user is online if the session key exists. Do not push every change to all contacts. Let the phone ask when a chat screen opens, and listen to that one person while the screen stays open.

Assumptions (made up to teach with, not real data):

• 50 million daily users send 40 messages each: 2 billion messages a day.
• 80% of the messages are one-to-one. 20% go to groups, and each group message has 10 receivers.
• 10 million phones are connected at one moment. The service keeps messages for 1 year.
• A message is 300 bytes with its numbers. Peak is 3 times the average (lesson 14).
• A gateway holds 50,000 connections at 20 KB each (lesson 75). A Redis server does 100,000 commands per second, and we plan for 70% (lesson 57). A delivery worker does 2,000 deliveries per second at our 70% target. A store server holds 2.8 TB (lesson 43) and takes 5,000 writes per second.
• A day has 86,400 seconds.

Step 1: messages. 2,000,000,000 / 86,400 = 23,148 per second, and 69,444 at the peak. Deliveries: 2,000,000,000 x (0.8 x 1 + 0.2 x 10) = 5.6 billion a day = 64,815 per second, and 194,444 at the peak. That is 2.8 deliveries for each message sent.

Step 2: the connection fleet. 10,000,000 / 50,000 = 200 gateways. We add 10% for failures: 220. Each holds 50,000 x 20 KB = 1 GB. Pings: 10,000,000 / 30 = 333,333 per second. This answers the predict box: 333,333 / 23,148 = 14.4, so there are about 14 times more pings than messages. An idle connection is not free.

Step 3: the session map. Each ping refreshes a key: 333,333 per second. Each delivery also looks up a key. At the peak that is 194,444 more per second. Total = 333,333 + 194,444 = 527,777 commands per second. One Redis server takes 100,000 x 0.7 = 70,000. 527,777 / 70,000 = 7.5, so 8 Redis servers. Pings are 333,333 of the 527,777.

Step 4: the store. 2,000,000,000 x 300 bytes = 600 GB a day. For a year: 600 x 365 = 219 TB, for one copy. Then 219 / 2.8 = 78.2, so 79 shards. With 3 copies, 237 servers. By writes, 69,444 / 5,000 = 13.9, so 14 servers. Data is the limit, not writes. Adding the 80th shard moves 1 / 80 = 1.25% of the chats with consistent hashing. A plain hash mod would move 79 / 80 = 98.75%.

Step 5: the log and the workers. At the peak, 194,444 / 2,000 = 97.2, so 98 workers. A consumer group has at most one consumer for each partition, so we choose 128 partitions. The key is the chat ID, so the events of one chat stay in order.

Step 6: receipts. Per message and per member: 5.6 billion x 2 states = 11.2 billion rows a day. Assume 50 bytes for a row. Then it is 560 GB a day. With cursors, assume 20 chats for each user. Assume 40 bytes for a cursor row. Then 50,000,000 x 20 x 40 bytes = 40 GB in total, and it does not grow with the message count. The number of updates does not fall by itself. But one update such as "read up to 57" covers many messages, and the row stays the same size.

Step 7: presence. Assumption: a user's presence changes 10 times a day. Each user has 200 contacts, and 20% of them are online (10 million of 50 million). Pushing every change: 50,000,000 x 10 / 86,400 = 5,787 changes per second, x 40 online contacts = 231,481 pushes per second. That is 231,481 / 64,815 = 3.6 times the message traffic. So the phone asks only when a chat screen is open. A short break in the network must not flip a user to offline, so the 90-second TTL acts as a grace period.

Step 8: a gateway dies. It held its share of the phones: 10,000,000 / 220 = 45,455. They reconnect. All at once, that is 45,455 new connections in about 1 second. If each phone waits a random 0 to 10 seconds first, it is 45,455 / 10 = 4,545 per second. That is 4,545 / 219 = 21 per second for each of the other gateways. The old session key stays for up to 90 seconds, so deliveries to the dead gateway fail. The worker treats that as offline. Nothing is lost, because every message is stored first. Each phone sends its last sequence numbers and gets what it missed.

Step 9: ordering. A question and a reply in one chat get 41 and 42 at the chat service, whichever gateway they came through. Assumption: a busy group of 10 people sends 8 messages per second. That uses 8 / 500 = 1.6% of the counter.

• Store first, then deliver solves lost messages: "sent" means stored. It costs one write before each delivery. I would not change this at any size, because losing a message breaks the promise of the app.
• A counter for each chat solves order with no clock. It costs a hot row of about 500 updates per second, and no order between chats. I would change it for a chat with more writes than that.
• Cursors solve receipt storage (560 GB a day against 40 GB in total). They cost less detail: you cannot see exactly which message was read when. I would add detail only for the latest messages.
• Asking for presence solves a flood of pushes (3.6 times the message traffic). It costs a short delay when a screen opens.
• Consistent hashing for the store solves growth (1.25% of the chats move). It costs a ring to keep and to watch.

"Sort messages by the timestamp the server wrote." Servers differ by tens of milliseconds or more, and a reply can come first. Use the chat counter.

"If the receiver is offline, keep the message in a queue for that user." The message is already in the store with a sequence number. The returning phone asks for everything after its last number. A second copy is not needed.

"Show every contact's online status as it changes." In Step 7, that made 3.6 times more traffic than the messages themselves. Fetch it only when a chat is open.

1. In what order do these happen: deliver to the receiver, save the message, answer "sent" to the sender? Why?
2. A chat app has 20 million users, each sending 30 messages a day. A gateway holds 40,000 connections, and 6 million phones are connected. (a) How many messages per second on average? (b) How many gateways? (c) Pings every 30 seconds: how many per second?
3. A phone shows messages 11, 12, then 14. What does it do? Another phone reconnects after a day offline. What does it send and what does it get?