Syncing the conversation list | IM Systems in Depth

Chapter 10 settled it: the conversations live on the server and the phone copies them. But syncing still works as in chapter 6: on every return the phone asks for the latest seq of every conversation (the seq of its newest message) and compares; a bigger one means new messages.

Ana is in 2,000 conversations, so each sync downloads 2,000 seqs, 12 bytes each with the conversation ID: 24 KB. Twenty opens a day make 480 KB, 9 times the text she receives in a day (267 messages, about 53 KB). Yet between two opens only a dozen or so conversations change. The server wastes work too, reading 2,000 seqs every time.

The server sends everything because it does not know what this phone got last time. This chapter makes the phone get only what changed.

1. The idea: stamp each conversation row with a version

There are two numbers in this chapter. Keep them apart:

seq: a conversation’s own message number. The hiking group’s 4,823rd message has seq 4,823, the same for everyone in the group.
version: each person’s own counter (chapter 6’s record version). Whenever one of Ana’s conversations changes, her version goes up by one.

Server: Ana’s chats, a row each

Phone

On the server, each of Ana’s conversations is a row (a conversation record), which now also holds the latest seq.
Every message updates each member’s row for that conversation: the new seq, stamped with that member’s next version.
The phone keeps the largest version it has received, and on return asks only for “the rows above it”.

In the figure, Ana’s phone last synced up to version 9,000. The hiking group (9,013) and the work chat (9,004) are above it and come back; the book club (8,571) has not changed and is not sent.

Here is Ana’s day, one cell per conversation:

Replies can be lost (10%, the series’ loss rate) The app is reinstalled before open 11 (version starts over)

One day, 20 opens: what each downloads (tap a bar to see that open)

Open 1: the server replied with 24 KB, all 2,000 chats.

changed, sentunchanged, sent anywayphone lacks the newest message

The day: 480 KB downloaded in all; after the last open the phone knows every chat’s newest message.

Send everything: 24 KB every time, all 2,000 cells lit, when only a dozen or so changed.
Only rows above my version: three or four hundred bytes each time. When a reply is lost (the opens marked “lost”), the phone’s version does not move, so the next sync asks the same question and those conversations come again (the cells outlined in orange). Nothing is missed.

2. Fan-out comes back a little

Chapter 10 said that, with the list built on the server, a message writes nothing for its members. This chapter writes again: every message updates one row per member. Chapter 6 listed this variant among its other answers; with few conversations it was not worth it then.

Against an inbox, for the 500-member hiking group:

The same number of writes. An inbox appends 500 entries, this updates 500 rows, and each update costs a little more: it locks the person and bumps the version.
The rows do not grow. An inbox gains 500,000 entries a day and keeps piling up; here it is the same 500 rows, over and over. In a busy group, several updates to one row can be merged into one.
Reads shrink. The phone gets only the dozen or so changed rows, and the server reads only those.

3. Two things to get right

Never take a version first and write later. Hand out the version first and write the row afterwards, and a change can be missed:

Message A takes version 101 for Ana but has not written yet;
Message B takes 102 and writes first;
The phone syncs now, gets 102, and notes “up to 102”;
Only then does A write, with 101, below what the phone noted, and it is never sent.

The fix: take the version and write the row in the same transaction, locking the person as you take it (UPDATE users SET record_version = record_version + 1, the same as chapter 6). The next version cannot be taken until the previous write is done, so a smaller version is always written first. The server returns rows in version order, and the phone keeps the largest version in the reply; it never asks the server separately “what version are we at”.

The sender does not wait. A message in the hiking group updates 500 rows, and the sender cannot wait for that. The message’s transaction only adds one to-do row: “hiking group 4,823: update every member’s conversation”; the ACK and the push go out as usual. Dispatch then works through the to-do, one small transaction per member, and picks up where it left off after a crash. Doing a row twice is harmless: the seq only moves up, and an extra version bump only sends that conversation once more.

Leaving a group or deleting a conversation works the same way: update the row (marked deleted, not removed) and bump the version, and the phone hears about it.

4. The numbers

The phone: 28 bytes per changed conversation (the 24-byte record plus a 4-byte latest seq), about 360 bytes for a dozen or so per sync, about 7 KB a day.
The server: at v2’s peak, 139 messages a second with 6.67 recipients each on average (the series’ numbers), about 927 row updates a second, roughly a tenth of what one storage server can write.

5. The cost

Writes grow with group size. A 500-member group sending 10 messages a second means 5,000 row updates a second, half a storage server.
The row lags the message a little. A sync that comes before the to-do is done misses the newest message; the push usually gets there first; if not, the next sync does.
Each person’s version row is a hot spot. Someone in several busy groups has that row locked several times a second, and a long transaction on it holds up all of that person’s updates.

6. Other answers

Use the update time as the version. Each conversation row keeps an updated_at; the phone takes the largest one it has and pages forward until there is nothing left. No extra counter and no lock on the person. Two things to watch: several rows can share one moment, so pages must be ordered by time and conversation ID together; and the time is taken when the row is written, not when it commits, so a row that took its time early and committed late lands where the phone has already paged past, the same hole as in section 3. The usual patch is to look back a few seconds on every sync; a transaction or clock skew longer than that still slips through, so a full reconcile is needed as a backstop.
The server remembers each connection. Matrix’s simplified sync (MSC4186) does this: it remembers what it last sent each connection and sends only what changed. A message updates no member rows; the cost is state per connection (about 360 MB at v2), and the server must know the last reply arrived.
Skip the rows for big groups; sweep them on return. Small groups work as in this chapter, big groups as in chapter 6, by asking for the latest seq. There are two paths to maintain.
Send everything. Chapter 6’s way. For someone with an average 200 conversations (2.4 KB) it does not really hurt.

7. This chapter’s decision

Chapter 11: the conversation records follow the messages. A message’s transaction adds a to-do row; dispatch then updates each member’s record with the latest seq and the next record version, taken by locking that member’s row in users. The phone keeps one version number and on return gets only the records above it, instead of every conversation’s latest seq.

Decision card

Problem: Someone in many conversations downloads every conversation’s latest seq at each sync: Ana is in 2,000, 24 KB each time, nearly all unchanged.
Choice: Every message writes the latest seq into each member’s conversation row, stamped with that member’s next version (taken and written in one transaction, locking the person); the sender only adds a to-do, and the rows are updated afterwards. The phone keeps its largest version and gets only the rows above it.
Cost: One more write per member per message (about 927 a second at v2’s peak); the row lags the message a little; each person’s version row is a hot spot.
Revisit when: Whose member list the to-do uses (chapter 12); read positions on the same version (chapter 14); the to-do becomes the message log (chapter 28); groups of tens of thousands off this path (chapter 39).
Other answers: The update time as the version; the server remembers each connection (Matrix MSC4186); big groups swept on return; send everything.

The chat list syncs only what changed. But who is in a group is still a list looked up on the fly: Ben leaves the group and still gets its next message; someone new sees messages from before they joined. Next: joining and leaving a group.