# Chapter 6: Offline sync

> Ben’s phone was offline for 10 minutes, and he is in 200 conversations. When it reconnects, what should it ask the server?

IM Systems in Depth · https://im.liko.page/en/offline-sync/

Ben spent 10 minutes on the underground with no signal. Out of the station, his phone reconnects to the server. None
of the messages sent to him in those 10 minutes were pushed: there was no connection, and a push is only a hint
(chapter 2). One pull has to bring them back.

The question: **what does the phone ask with?**

Two words first. A **cursor** is what the phone remembers as “I have everything up to here”; a **seq** is a message’s
number within its conversation, 1, 2, 3, … (chapter 5).

Up to chapter 5, the phone reconnects with chapter 1’s `after=<id>`: “give me every message with an id bigger than
the biggest I have.” It has always worked, but it has a hole: an id is assigned at insert, while others only see the
row once it commits. Two messages are written at once, 102 commits while 101 has not yet; a phone pulling at that
moment records `after` as 102, and 101 is skipped.

Ben is in 200 conversations. This chapter decides what his phone asks with when it comes back.

## 1. Two ways to ask

First, where we are. Chapter 1’s `after=<id>` uses one id for the whole site: the phone sends one number, and on one
server with one table that is plenty. Its faults are the hole above, and that it cannot say “this conversation is
missing this message”. Chapter 5 gave each conversation a contiguous seq, so there are now two ways to ask on the way
back.

To be clear first: **both ways below catch up completely**, and neither breaks at v1’s scale. They differ in cost,
and in what they can express.

1. **A cursor per conversation**: one request carries 200 pairs of “(conversation, the last seq I have)”, 12 bytes
   each, 2.4 KB in all. The server reads each conversation’s latest seq and sends whatever the phone is missing. No
   hole: within a conversation, seq is handed out in commit order (chapter 5).
2. **An inbox per person**: when a message is stored, each recipient’s inbox gets an
   entry, “conversation X now has seq s”, numbered by the inbox’s own contiguous sequence. The phone keeps one number:
   how far it has read its inbox (its sync cursor). Coming back, it asks: “give
   me everything in my inbox after 7,345.”

In the simulator below, Ben’s 200 conversations are a grid, the most active at top left; the darker a
cell, the more new messages arrived while he was away.

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

By the book’s numbers a message reaches 10 devices on average, at 1.5 devices
per person, so 10 ÷ 1.5 ≈ **6.67 people**; with 4,000,000 messages a day and 100,000 users, Ben receives
4,000,000 × 6.67 ÷ 100,000 ≈ **267 a day**. They are not spread evenly: assume the k-th most active conversation gets a
share of 1/k.

| Away for | Messages | Conversations with news |
|---|---|---|
| 10 minutes | 1.9 | 1.8 |
| between opens | 13.3 | 10.7 |
| 1 day | 267 | 91 |

By this table, back after 10 minutes, **99.1%** of the 200 looks find nothing; between two app opens (20 a day),
still **94.6%**. In the default run, Ben is away for 10 minutes and 2 messages arrive, in 2 conversations. Asking with 200 cursors,
the server looks at 200 conversations and finds nothing in 198; switch to “One inbox cursor” and the server reads just
the 2 inbox entries. Switch to “a busy evening”: three groups got 120, 80 and 30 messages. With at most 50 messages per
reply, both ways take ⌈230 ÷ 50⌉ = **5 requests**. **Both ways download the same messages in the same number of
requests.** What differs is what the phone sends and what the server reads.

## 2. Estimate

**The server.** 100,000 people syncing 20 times a day is 2,000,000 syncs a day; at a peak of 3 × average,
2,000,000 ÷ 86,400 × 3 ≈ **69 a second**.

- A cursor per conversation: 200 conversations per sync, 69 × 200 ≈ **13,900 reads a second** at peak. Each reads one
  row by primary key, mostly from memory; one database can take it. But it grows with how many conversations Ben has,
  not with how many messages arrived: at 2,000 conversations per person it is **139,000 a second**.
- One inbox cursor: one range of the inbox per sync, **69 a second** at peak, reading exactly as many entries as
  messages arrived.

**The phone.** Each sync uploads 200 × 12 = **2,400 bytes**, 20 times a day is **48 KB**; the messages Ben receives in a
day are only 267 × 200 bytes ≈ **53 KB**. An inbox cursor is 8 bytes.

**The inbox’s bill.** Every message adds an entry for each recipient, 6.67 on average. Writing a copy for each person at
send time is called write fan-out; storing one copy and letting each person
fetch it when reading is read fan-out, and the first way (a cursor per conversation) is read fan-out. The names
are enough for now; when to use which is chapter 10’s question.

- Writes: 4,000,000 × 6.67 ≈ **26.7 million entries a day**; at peak 139 × 6.67 ≈ **927 a second**, on top of the 139
  message writes.
- Disk: 32 bytes an entry (user, inbox seq, conversation, seq), 26.7 million × 32 bytes ≈ **853 MB a day**, more than
  the messages themselves (4,000,000 × 200 bytes = 800 MB).

So it is a trade: **each sync reads only what arrived, in exchange for 6.67 extra rows written per message.** At v1’s
numbers both sides are small; either is defensible.

**What cursors cannot say.** What tips the scale is something else. While Ben was away, someone added him to a new group.
His phone asks with 200 cursors, but the group is not among the 200: the phone does not know it exists, so it never
asks. Fixing that needs one more per-person version number, “how far I have synced my conversation list”. What he read on
another device (chapter 14), being removed from a group, pinning: none of these belongs to any conversation’s seq;
they happen to Ben. By then, the per-conversation design is keeping a small inbox on the side.

## 3. The fix

### An inbox per person, with its own contiguous number

In chapter 5’s transaction that stores a message, add one entry to each recipient’s inbox:

```sql
UPDATE conversations SET last_seq = last_seq + 1 WHERE id = :conv RETURNING last_seq;
INSERT INTO messages (conversation_id, seq, sender_id, msg_id, text) VALUES (:conv, :seq, ...);
-- for each member, in ascending user id:
UPDATE users SET inbox_seq = inbox_seq + 1 WHERE id = :member RETURNING inbox_seq;
INSERT INTO inbox (user_id, inbox_seq, conversation_id, seq) VALUES (:member, :inbox_seq, :conv, :seq);
COMMIT;
```

Why does this leave no hole? Take two messages for Ben at the same moment: A, in his private chat with Ana, and C, in
the hiking group.

1. A’s transaction locks Ben’s row first and gets inbox seq 7,346;
2. C’s transaction also needs Ben’s row, and waits;
3. A commits and releases the lock; only then does C get 7,347 and commit.

7,347 cannot commit before 7,346, so **within one person’s inbox, number order is commit order**, and `after=7345`
skips nothing. Locks are taken in ascending user id because one message locks several people: if one transaction
locks Ben then Carl while another locks Carl then Ben, each waits for the other forever (a deadlock); when everyone
locks in the same order, that cannot happen.

When Ben is added to a new group, the group gets a system message, “Ben joined”, with its own seq; in his inbox it is
an ordinary entry (Y, s), so the inbox table needs no extra column. Being removed works the same way.

The phone keeps two things: **one inbox cursor**, pulling after it on reconnect and on every app open, 50 per page; and
**each conversation’s last seq**, for ordering and gaps as before (chapter 5).

Pushes carry the inbox seq too. The phone has 7,345; 7,346 arrives, and it follows on. 7,348 arrives: something is
missing, whichever conversation it belongs to, and one pull after 7,345 brings it all. Each push is sent after its own
commit, so 7,347 may arrive before 7,346; as in chapter 5, the phone waits a moment and pulls only if the gap stays,
and an extra pull does no harm. Chapter 5 noted that a lost push for the last message is noticed only with that
conversation’s next message; now Ben’s next message from any conversation is enough, on average every
1,440 ÷ 267 ≈ **5.4 minutes**.

### Offline too long

A contiguous inbox seq brings one more thing for free: “the inbox’s latest seq − the phone’s cursor” tells the server
how far behind Ben is without reading a row. When it is too far (this chapter says more than 10 pages, 500 messages),
or the cursor is older than the inbox keeps (here **7 days**: 26.7 million entries a day, about **6.0 GB**), the server
stops paging and answers “too long” with the **conversation list**: each conversation’s latest seq and newest message.
The order matters: read the inbox head first, then build the list; the other way round, an entry committed in
between is missed by both. Whatever the list picks up after the head is only a duplicate, which does no harm. The phone
moves its inbox cursor to that head; older messages load when Ben opens that chat, going back from the newest.
The phone’s history now has holes, which chapter 7 handles. This is the same move as Telegram’s `differenceTooLong` and
Matrix’s `limited` timeline. Click “1 week” in the simulator: downloading everything is 1,869 messages,
⌈1,869 ÷ 50⌉ = 38 requests and about 374 KB, oldest first, since the inbox pages forward, so the newest arrive last;
the list is ⌈200 ÷ 50⌉ = **4 requests** and 200 × (200 + 12) bytes ≈ **42 KB**.

## 4. The cost

- **Several times the writes, more for bigger groups.** Each message writes 6.67 more rows: 927 more a second at
  peak, 853 MB more a day. It grows with **the conversation’s size**: a private chat writes 2 rows per message, the
  500-member hiking group 500; an afternoon of 1,000 messages there is 500,000 rows, whether or not those people ever
  come back to read them.
  Asking per conversation is amplified too, only on the reading side: each of the 500 people checks this group when
  they come back, and every sync asks about all of their conversations, most of them for nothing. Pushing to whoever
  is online is one copy per person either way. The difference: the inbox pays for everyone **at write time**; cursors
  pay **at read time**, and only for the people who come back. What to do when a group is too big for inboxes is
  chapter 10’s question.
- **Locks.** One message locks a row for each recipient, and every message to the same person, from any conversation,
  queues on that person’s lock. At 5 ms a write, one person can receive at most 1 ÷ 0.005 = **200 messages a second**.
  Ordinary people never get near it; accounts that receive a lot, such as customer-service accounts and bots, hit it
  first.
- **Two kinds of cursor.** The phone keeps the inbox cursor and each conversation’s seq, and must handle “too long”, a
  path that rarely runs and so is the most likely to be found broken on the day it matters: test it on purpose.

| Resource | A cursor per conversation | One inbox cursor |
|---|---|---|
| Server disk IO | 200 conversation rows read per sync (about 13,900 a second at peak, mostly in memory) | one inbox range per sync (69 a second at peak); 6.67 extra rows written per message (927 more a second at peak) |
| Server disk capacity | unchanged | 853 MB more a day, about 6.0 GB for 7 days |
| Phone data | 2.4 KB uploaded per sync, 48 KB a day | 8 bytes per sync |

## 5. Other answers

- **Keep a cursor per conversation**: with few conversations and expensive writes, a reasonable choice: no extra rows,
  no inbox to expire; the price is reading every conversation at each sync, plus a per-person version for the
  conversation list.
- **Telegram**: the [docs](https://core.telegram.org/api/updates) say private chats and basic groups share one event
  sequence per user (`pts`), while each channel and supergroup has its own. On startup the client calls
  `updates.getDifference` once; `updateChannelTooLong` in the result names the channels to catch up separately; older
  than what is kept gives `differenceTooLong`, and the client re-fetches the latest state.
- **Matrix `/sync`**: in the [spec](https://spec.matrix.org/latest/client-server-api/#syncing) the client passes the last
  `next_batch` as `since`, a per-person cursor; when too much arrived, a room’s timeline is marked `limited`, with only
  the latest events and a `prev_batch` to page back. [MSC4186](https://github.com/matrix-org/matrix-spec-proposals/pull/4186)
  says it slows down with the number of rooms and the time offline; with thousands of rooms the first sync can take
  tens of minutes.
- **Facebook Messenger’s Iris**
  ([2014](https://engineering.fb.com/2014/10/09/production-engineering/building-mobile-first-infrastructure-for-messenger/)):
  a totally ordered queue of updates (new messages, read-state changes and so on); a pointer marks the last update sent
  to your phone, stays put while the phone is offline, and new updates keep queueing.
- **WeChat’s seqsvr** ([InfoQ, 2016, in Chinese](https://www.infoq.cn/article/wechat-serial-number-generator-architecture)):
  one increasing sequence number per user; the client sends the largest it has synced, and the server returns what is
  newer. The numbers need only increase, not be contiguous. That is the other side of this chapter’s choice: numbers
  can be handed out in batches by a separate service, with no lock on each person’s inbox row, and spread over many
  machines more easily; the price is that a jump no longer means a missing message, and “latest number − cursor” no
  longer says how far behind the phone is.
- **Notify, then pull**: the push only says “your inbox is at 7,346”, and the phone pulls. It costs one more round trip
  per message; this chapter’s pushes still carry the message.

## 6. This chapter’s decision

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

**Decision card**

- Problem: Ben was offline for 10 minutes and is in 200 conversations. Asking per conversation reads all 200 at every sync, mostly finding nothing, and cannot ask about a conversation the phone does not know yet (a group he was just added to).
- Choice: An inbox per person: in the transaction that stores a message, add an entry to each recipient’s inbox, locking in user-id order, numbered by that person’s contiguous inbox seq. The phone keeps one inbox cursor and pulls after it, 50 per page; pushes carry the inbox seq, and a jump means pull. More than 10 pages behind, or a cursor older than the inbox’s 7 days: the server answers with the conversation list only, and the phone moves its cursor to the head.
- Cost: 6.67 more rows written per message (927 more a second at peak, 853 MB more a day), growing with conversation size; all messages to one person queue on that person’s row lock (about 200 a second at most); two kinds of cursor on the phone; the “too long” path rarely runs and must be tested.
- Revisit when: Holes in the phone’s history, filled when scrolled to (chapter 7); what to do when a group is too big for inboxes (chapter 10); several devices per person, a cursor each (chapter 14); whether inbox writes should wait until after the ACK (chapter 28).
- Other answers: A cursor per conversation (no extra writes, but reads every conversation); Telegram (per-user pts plus per-channel pts; too old means re-fetch the latest state); Matrix /sync (a since cursor, limited timelines with prev_batch); Facebook Iris (an ordered per-user update queue); WeChat seqsvr (increasing per user); notify then pull (one more round trip).

Now Ben catches up however long he was away. But where do the messages he caught up go? Kill the app, open it again,
and it pulls everything from the start. Next chapter: the local database on the phone.