# Chapter 1: The smallest chat

> How should a phone ask the server “anything new?”, so it misses nothing and gets nothing twice?

IM Systems in Depth · https://im.liko.page/en/smallest-chat/

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 control of their data, 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:

```sql
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, you get two things for free:

- **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 just plays out the rules: Ana sends 6 messages in 20 seconds
(sometimes two in a row), and Ben’s phone asks every 2 seconds.

*[Interactive figure: open the page to use it, https://im.liko.page/en/smallest-chat/]*

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

- **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>` grows into chapter 6’s
per-conversation catch-up, where the phone’s sync cursor becomes each conversation’s last seq.

## 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. Chapter 5’s per-conversation seq solves it:
  it is handed out one after another within each conversation, so the numbers have no gaps, and a gap means a
  message has not arrived yet; chapter 6 catches up by asking each conversation’s seq.
- **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 message
  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:

*[Interactive figure: open the page to use it, https://im.liko.page/en/smallest-chat/]*

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.

*[Interactive figure: open the page to use it, https://im.liko.page/en/smallest-chat/]*

- **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 gives it more depth.

## 6. The cost, and other answers

The cost:

- Every phone with the app open asks, new messages or not: wasted work for the server, 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.

Other answers:

- **Ask by the server’s time, with a small overlap and deduplicate by id**: use the time the server wrote as the cursor,
  re-read a little further back each time, and drop repeats by id. It works, with one more layer of dedup.
- **A “next time, start here” token from the server**: in the open Matrix protocol, for example, a client syncs
  with the `since` token the server gave it last time, and what is inside the token is up to the server. The same
  idea as asking by id: the server says where you are, not the client’s clock.
- **Long polling**: the server does not answer until it has a message. It is the first step from polling towards
  push; chapter 2 tells that whole path.

## 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

**Decision card**

- Problem: 1,000 users, chat that works soon: phones must find new messages, missing none and getting none twice.
- Choice: Poll with after=<the biggest id I have>; the server answers by id.
- Cost: Most polls are empty; about 1.2 s average wait; only while the app is open; relies on ids becoming visible in commit order (queue the writes, or re-read a little and deduplicate).
- Revisit when: When users want messages at once and polls reach thousands a second (chapter 2); when concurrent writes grow, switch to a gap-free sequence per conversation, where a gap can be noticed (chapters 5 and 6).
- Other answers: Server time with overlap and dedup; a sync token from the server (e.g. Matrix’s since); long polling.

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