The smallest chat | IM Systems in Depth

The product manager: “We want chat in the app, this week.”

The app has 1,000 daily users. Ana and Ben want to message each other in it. You have one server, a database that already exists, and a week.

First, a word on why you would build it at all. There are cloud IM services you can plug in as they are, and open-source IM servers (Matrix’s Synapse, OpenIM) that give you all of this once you deploy them. Many teams still build their own, usually to keep the data in their own hands, to control the product fully, or because it costs less at scale. Whether you build or buy, it helps to understand how the design works, and that is what this series is about.

1. The simplest design

One program, one table:

messages(id, conversation_id, sender_id, text, created_at)  -- id auto-increments

Send: Ana’s app sends POST /messages. The server checks that Ana may write in this conversation, inserts the row, and replies with its id.
Receive: every 2 seconds, Ben’s app asks the server: “give me the messages with an id bigger than the biggest one I have.”

GET /messages?after=<the biggest id I have>

Why ask by id rather than by time? Ids come from one place only, the server, one after another, so the phone only has to remember the biggest id it has seen. Asking by time means worrying about two messages at the same instant and about clocks on different machines. Asking by id is simpler.

At this size, two things come with it:

Order: one database hands out the numbers, so id order is the order everyone sees.
Catching up: a phone that was off asks with its old after when it comes back, and gets everything since.

2. Run it

Below is a simulator. It talks to no real server; it plays the rules out: Ana sends 6 messages in 20 seconds (sometimes two in a row), and Ben’s phone asks every 2 seconds.

Ben asks every 2 s, and the network takes 0.1 s each way. On average, how long until Ana’s message shows on Ben’s phone?

a poll that brings messagesan empty poll how long a message waited

Poll every2 s

Ben’s phone is off from 6 s to 14 s

At 1,000 users nothing in this design breaks: every message arrives, exactly once. What you can see are its two traits:

Many polls come back empty: the grey dashed round trips asked and got nothing. Ana is busy in this run (6 messages in 20 seconds), so fewer than half are empty; real users send far less, and section 4 works out that 96% of polls are empty.
Messages wait a while: each blue bar is the time from Ana pressing Send to the message showing on Ben’s phone. One that lands just before Ben asks waits about 0.2 seconds; one that lands just after waits almost a whole interval. On average it is half the interval plus two one-way network legs (Ana’s upload and Ben’s answer, 0.1 seconds each).

Tick “Ben’s phone is off from 6 s to 14 s”: when the phone comes back, it asks with the after it had before, and the 4 messages sent while it was off all arrive at once. This after=<id> is the seed of the sync cursor in chapter 6.

3. What the design relies on

The design is enough for v0, but it relies on a few things, and later chapters meet them one by one:

Ids become visible in commit order. A new row can be read by others only once its transaction commits, but its id is handed out at insert, and transactions do not always commit in id order. Even one program handles several requests at once: if row 102 commits while 101 has not yet, and Ben asks just then, he gets 102, sets after to 102, and skips 101 for good. At 1.4 messages a second in v0 this is very rare, but not impossible. Two simple guards: queue the writes one at a time, or always re-read a little further back (longer than the longest transaction) and drop repeats by id. Chapters 5 and 6 solve it with a sequence number per conversation, handed out one after another: the numbers have no gaps, so a gap means a message has not arrived yet.
Ids give order, not continuity. Rollbacks and other conversations’ messages make ids jump, so a client must never read a gap in ids as a lost message; and id order is the order the server wrote rows, not necessarily the order two people pressed Send.
Retries by the sender make duplicates. If Ana’s request times out and the app sends it again, the same line is written to the table twice. This chapter’s “exactly once” is about the receiving side; duplicates on the sending side are solved with message IDs in chapters 3 and 4.
One answer cannot hold everything. A phone that was off for a week cannot get all its messages in one reply. The real query is “messages in my conversations with an id above the cursor, in id order, at most 100”, plus a has_more flag that tells the phone “there is more, ask again”.

4. Estimate: what asking every 2 seconds costs

The design is settled. Now its cost, with the numbers the whole series shares:

1,000 daily users, 10% online at peak: 100 phones with the app open.
Each asks every 2 seconds: 100 ÷ 2 = 50 requests a second. Easy for one server.
Messages: 40 a day per user, 40,000 a day, 0.46 a second on average, × 3 at peak = 1.4 a second.
In a 1:1 chat a message only goes to the other person’s phones (1.5 on average): about 1.4 × 1.5 ≈ 2 polls a second find something and the other 48 find nothing, so 96% of polls are empty (the sender’s own other devices receive it too, which lowers that a little). Even with the series’ assumption of 10 deliveries per message, groups included, at least 72% are empty.
A message lands at a random moment of Ben’s 2-second cycle: it waits half a cycle on average, plus the two one-way network legs (0.2 seconds in all): 1.2 seconds on average, 2.2 at worst. The default run has only 6 messages and averages 1.6 seconds; 10 minutes with 300 messages average 1.17 seconds, 2.2 at worst.

Move the sliders below to see what happens as the app grows:

Daily users1,000 Online at peak10% Poll every2 s

Phones online: 100
Requests: 50/s
Empty polls (1:1): 96%
Average wait: 1.2 sworst 2.2 s

At 100,000 daily users the requests reach 5,000 a second, and the average wait is still 1.2 seconds. That is chapter 2’s problem.

5. Open the program and its table: all five parts are there

This chapter splits nothing off, but open the program and its table and chapter 0’s four layers and the business layer beside them are all already there. “Receive” and “deliver” are meant from the server’s side: the message layer receives Ana’s message, and the dispatch layer delivers it to Ben.

The first v0 picture: chapter 0’s four layers and the business layer are all here. Three are crowded into one program, storage is the database, and the business layer is a few checks in the program.

Connection layer: answers each phone’s HTTP requests. Here every request is a new one, closed once it is answered.
Message layer (receive): checks Ana may write, inserts the row, replies with the id.
Dispatch layer (deliver): answers the polls with the messages that have a bigger id.
Storage layer: the messages table.
Business layer: “is Ana in this conversation?”

Every later version pulls one part out of this program, because it can no longer cope, and makes it deeper.

6. The cost, and other answers

The cost:

Every phone with the app open asks, new messages or not: work for the server for nothing, and data and a little battery for the phone.
Once the app is in the background, the phone’s OS will not let it ask every 2 seconds, so polling only receives messages while the app is open. Getting a message to a phone in the background takes push, later in the series.
A message waits half the poll interval on average. Halving the wait doubles the requests.

7. In practice

The first chat system the author worked on was also one machine in its first version: receiving and delivering messages in one program, the data kept in memory. Unlike this chapter, it pushed messages to clients over a WebSocket long-lived connection from day one, with no polling step.

One machine with the data in memory is a natural first version: quick to build, fast to run. The thing to watch is that a restart or a crash loses whatever is in memory. That is why even this chapter’s smallest version writes messages to a table; only what can be rebuilt if lost, such as presence and caches, belongs in memory alone.

8. This chapter’s decision

Chat works now. In the next chapter the app reaches 100,000 users, and people start saying messages are slow.