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. Three ways to ask

To be clear first: all three ways below catch up completely, and none of them breaks at v1’s scale. They differ in cost, and in what they can express.

1. One id for the whole site (what we do now): after=1016. The phone sends one number, but the database still has to search all 200 of Ben’s conversations, and the hole above is still there.
2. 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).
3. An inboxinbox信箱A per-person index of “new messages for you”, with its own per-user sequence. Write fan-out writes it, and devices pull from it by sync cursor.See the glossary 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 cursorsync cursor同步游标One per device: how far this device has synced in its inbox. When the device comes back, it pulls everything after the cursor.See the glossary). Coming back, it asks: “give me everything in my inbox after 7,345.”

Ways 1 and 2 both look at every one of Ben’s conversations, so the real comparison is between 2 and 3. 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.

Ben comes back after 10 minutes offline, and his phone asks with 200 conversations’ cursors. The server looks at 200 conversations. How many of them have something new?

About a hundredTwenty or thirtyTwo or three

10 minutesan ordinary evening10 minutesa busy evening1 dayphone ran flat1 weeka trip1 monthan old phone, found again

A cursor per conversationthe first request carries 200 seqsOne inbox cursoreach message adds an entry to each recipient’s inbox

↑ Guess first

new messages (darker: more)the server read this conversation’s latest seq

–

	A cursor per conversation	One inbox cursor
Requests (in turn)	–	–
Phone sends	–	–
Phone receives	–	–
Server reads	–	–
Extra inbox writes	–	–
Left on server	–	–

Other messages

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-outwrite fan-out写扩散When a message is sent, write one entry into each recipient’s inbox; reading means reading your own inbox. More writes, fast reads; suits conversations with few members.See the glossary; storing one copy and letting each person fetch it when reading is read fan-outread fan-out读扩散Keep one copy in the conversation’s timeline, and each reader fetches it from there. Few writes, more reads; suits big groups.See the glossary, and way 2 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:

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. 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: in the 500-member hiking group, one message is 500 rows. 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 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 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 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): 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): 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.
• 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

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.