Ordering | IM Systems in Depth

Ana and Ben are chatting fast. Ana sends a line, and at almost the same moment Ben sends one too. A little later they notice that their chats don’t match: on Ana’s screen her line is on top, and on Ben’s screen his is.

That is odd. v1 still has one server; messages go into one table with an auto-increment id (chapter 1). The id has one order, so everyone should see the same order. That holds for the server, not necessarily for the screens: the order on a screen is made by the phone. This chapter looks at how the phone orders messages, where it goes wrong, and what the id still lacks.

1. Watch it fail

In the simulator, Ana and Ben send 7 messages in 12 seconds (A1 is Ana’s first, B1 is Ben’s first). The rules are those of the last two chapters: each leg loses 10%, a message without an ACK is resent (chapter 3), and a resend is not stored twice (chapter 4). The server numbers messages in the order it stores them, then pushes each one to the other person; pushes can be lost too. The phones do the most natural thing so far: your own message shows at the bottom at once, and others’ messages are added below it when their push arrives.

Ana and Ben each send a line at almost the same moment. There is one server, and its ids have one order. Do the two screens show the same order?

pushpush lostarrived on a resend

Pairs in the opposite order to the server: –
Missing, unnoticed: –
Fetches: –
Own messages that moved: –

The three columns are each screen at the end, with the server’s order in the middle. In this default run, three things happen once each.

Two people send at once. Ana sends A3 at 6.78 s and Ben sends B3 at 6.83 s, 50 ms apart. A3 is stored first. But Ben’s phone showed B3 at 6.83 s, and A3’s push arrives at 6.98 s and goes below it. Ben’s screen says B3, A3; the server and Ana say A3, B3.

A resend lands late. Ana sends A1 at 5.04 s; it is lost and stored only after the resend a second later. A2, sent at 5.51 s, gets through on the first try and is stored first. The server says A2, A1; Ana’s own screen says A1, A2. Chapter 3 warned about this.

A push is lost, and nobody notices. The push of A2 to Ben is lost: the server thinks the connection is alive, writes into it, and the bytes never arrive (chapter 2). Can Ben tell? The biggest id he has is B2’s, 1012, and the next to arrive is A1, id 1016. Of the three ids skipped, 1013 is A2; 1014 and 1015 belong to other conversations. The id gives an order, not a contiguous count (chapter 1); skips are normal, so the phone cannot read “skipped” as “missing”. It waits for the next pull (the phone asking the server) on its next reconnect. Until then Ben’s chat is one line short, and he doesn’t know.

When Ana next opens the chat, the app reloads it by id, and A1 and A2 suddenly swap places: the history changes by itself.

Chapter 1 also left a hole that the simulator does not draw: an id is assigned at insert but visible only after commit, and the two orders can differ. Section 3 explains it along with the fix.

2. Estimate

How often? A message crosses someone else’s when, within one round trip before it was sent, someone else sent a line: that line is stored, but its push hasn’t arrived. Say the group is busy, the others say a line every 2 seconds on average (0.5 a second), and a round trip on mobile is 0.2 s:

your line crosses another with a chance of about 0.5 × 0.2 = 0.1, one in ten. Simulating two people who each send every 2 s, 9,952 messages with no loss: 9.3 pairs per 100 messages are in the opposite order to the server on one of the screens.
On a weak signal with a 1 s round trip, the same sum gives 0.5 × 1 = 0.5 (the product overshoots at that size, but roughly every other line crosses). Resends widen the window: at the book’s 10% loss, 19.6 pairs per 100.

In a one-to-one chat people usually read the other line before replying, so crossings are much rarer.

How much goes missing? Each lost push leaves a line missing on the other screen until the next pull. At 10%, 10.0 messages per 100. Real pushes are lost far less often, but as in chapter 3, a small share of 4,000,000 messages a day is not a small number.

3. Fix it

Step 1: order by the server’s number, keep what is sending at the bottom

Crossings and late resends have one cause: the phone orders by “when I saw it”, not by the server’s order. The fix:

Order every message by the server’s number. A push carries it; for your own message, the ACK (chapter 3) brings it back; the ACK for a repeat carries the original number (chapter 4).
Messages not yet acknowledged (sending, failed) have no number. They all stay at the bottom, in the order they were sent. When the ACK arrives, the message moves to its place.

Switch the simulator to “By id”: both screens now match the server (Ben still lacks A2). On Ben’s side, B3 is sending when A3’s push arrives, so A3 goes above it; B3’s ACK brings a bigger number than A3’s, so B3 stays. On Ana’s side, A1 and A2 are both sending; A2 is acknowledged first and jumps above A1.

To be clear: this step needs only the id. With one server the id is already an order everyone agrees on; the screens just weren’t using it. The cost is that your own messages move: never with no loss in the simulator (a sending message stays at the bottom, and others’ lines only go in above it); at 10% loss, 15.8 of every 100 messages are own messages that moved.

But Ben still lacks A2 and still doesn’t know. The id cannot do that.

Step 2: one contiguous number per conversation

For the phone to know “one is missing”, the numbers must be contiguous within the conversation: 1, 2, 3… with no numbers taken by other conversations. That is the seq.

The server needs one more field: the conversations table keeps the last seq the conversation used. Writing a message takes, in one transaction (PostgreSQL, at its default READ COMMITTED isolation):

BEGIN;
UPDATE conversations SET last_seq = last_seq + 1 WHERE id = :conv RETURNING last_seq;
-- :seq is the last_seq returned above
INSERT INTO messages (conversation_id, seq, sender_id, msg_id, text) VALUES (:conv, :seq, ...);
COMMIT;

The messages table gets one more unique key, (conversation, seq). (Under REPEATABLE READ, a second writer to the same row gets a serialization error and must retry; MySQL has no RETURNING, and the usual form is last_seq = LAST_INSERT_ID(last_seq + 1), then LAST_INSERT_ID().)

The UPDATE takes a row lock on the conversation until commit: writers in the same conversation take turns for numbers, and other conversations use other rows and never wait. Now look again at chapter 1’s hole:

transaction T1 takes id 101 and is still open;
transaction T2 takes 102 and commits first;
Ben’s phone pulls after=100, sees only 102, and records after as 102;
T1 commits, and 101 is never pulled.

With the row lock, T2 in the same conversation waits for T1 to commit before it gets a number, so within a conversation, the seq order is the commit order. The reconnect pull by id keeps chapter 1’s hole until chapter 6, but a message it skipped now shows up at the next seq jump.

On the phone, each conversation remembers how far its numbers are contiguous:

it has 1 to 5 and gets 6: it fits.
it has 1 to 5 and gets 8: 6 and 7 are missing; it fetches “seq 6 to 7 of this conversation”.
the seq in the ACK for your own message counts too: Ana’s ACK brings 7 and she has 1 to 5, so 6 is missing.

Before fetching, the phone waits a moment (0.5 s in the simulator). One TCP connection keeps its order, but on the server different threads may push after their own commits, so 8, committed later, can be pushed first, with 6 and 7 right behind. The simulator never reorders pushes, so there the wait only delays a fetch by 0.5 s.

Switch to “By seq, fetch on a jump”: at 6.24 s Ben gets A1, seq #4, while he has #1 and #2. After 0.5 s #3 still hasn’t come, so he fetches at 6.74 s, and A2 is back at 6.94 s, above A1. Simulating 9,952 messages at 10% loss, “missing, unnoticed” drops from 10.0 per 100 to 0.01. What remains is a lost push of the last message: nothing comes after it, so there is no jump to see.

This conversation’s cursor (the highest contiguous seq the phone holds here) can now move with contiguous pushes too. Pulls on reconnect still use chapter 2’s after=<id> until chapter 6.

4. The cost

One conversation’s writes take turns. At about 5 ms a write when storage is healthy, one conversation takes at most 1 ÷ 0.005 = 200 messages a second; if storage slows to 500 ms a write, only 2 a second. Different conversations’ rows don’t contend. The problem at v3 is not one conversation but one server handing out seq for every conversation, 13,900 a second (chapter 27).
Your own messages move. The other way is for the outbox to send one conversation’s messages strictly in order: no next message until the previous one is acknowledged. Your own order never changes, but when one message is lost, everything behind it waits, at least one more timeout.
A lost push of the last message goes unseen until the next message or the next pull (chapter 6).
The seq must not skip. Here it is assigned inside the write’s transaction; if the transaction fails, the number rolls back with it, leaving no hole. If numbers are later assigned outside the transaction (chapter 27), a number may never get a message; when a phone asks for it, the server must answer “there is no 6”, so the phone moves on instead of asking forever.

Resource	In order of arrival	By seq
Server disk IO	one insert per message	one more row update and one more index in the same transaction; no extra flush to disk
Phone requests	a missing message waits for the next pull	one fetch per jump (13.4 per 100 messages at 10% loss; far fewer on real networks)

5. Other answers

Order by time: the clocks of two machines must agree, and two messages in the same millisecond need a rule; with the server’s own clock only, it works as well as the id on one server, and shows missing messages just as poorly.
Lamport clocks (Lamport, 1978): with no central numbering, each participant counts for itself and, on receiving someone else’s count, sets its own above it; the order never contradicts cause and effect. A chat system already has a server in the middle, so letting it number is simpler, and Lamport clocks jump, so they can’t show a gap either.
Telegram’s pts: per the docs, every event (a new message, and also an edit or a delete) carries an auto-incremented pts and a pts_count. The client checks whether local pts + pts_count equals the new pts: equal, apply it; greater, already applied, ignore it; smaller, there is a gap, and it may wait up to 0.5 s (the server may have sent the updates out of order), then call updates.getDifference to fill it. The gap check and the wait are this chapter’s idea; the unit differs: private chats and basic groups share one common sequence per user, and only channels and supergroups each have their own pts.
WeChat’s seqsvr: WeChat has described its sequence number generator in public (InfoQ, 2016, in Chinese): a 64-bit sequence per user, which, the article says, “only has to increase, not be contiguous”; the client sends the biggest sequence it has synced, and the server sends what is newer. It answers “how far have I synced” (chapter 6), not “which one is missing”.
Why no global order: nobody cares, or can even tell, which of two unrelated conversations came first; users care about the order within a conversation. On one server a global id comes for free, but it puts every message through one counter; split by conversation, each counter minds its own, and they can live on different machines (chapter 27).

6. This chapter’s decision

Chapter 5’s piece: one counter per conversation; the message layer takes the next seq in the same transaction as the insert. Pushes and ACKs carry it; phones order by seq and fetch when it jumps.

Decision card

Problem: There is one server, but each phone makes its own order: its own message goes to the bottom at once, a resent message is stored late, and Ana and Ben see different orders; a lost push goes unnoticed, because a skip in the id means nothing.
Choice: One counter per conversation; the next seq is taken in the same transaction as the insert. Pushes and ACKs carry it (a repeat's ACK carries the original seq). Phones order by seq with messages still sending at the bottom; on a jump they wait 0.5 s, then fetch what is still missing.
Cost: One conversation's writes take turns (at most 200 a second at 5 ms a write); your own messages can move; a lost push of the last message shows only with the next message or pull; the seq must not skip, and where it does, the server must say so.
Revisit when: When one server can't hand out seq for every conversation (chapter 27); syncing all of a person's conversations by cursor (chapter 6).
Other answers: Order by time (clocks disagree, and gaps don't show); Lamport clocks (for systems with no centre); Telegram's pts (the same idea, per user for private chats, per channel for channels); WeChat seqsvr (per user, increasing, not contiguous, for sync); a global order (nobody needs it, and it is a bottleneck); sending in order (your own lines never move, but one loss holds up the rest).

Now messages in a conversation are not lost, not doubled and not out of order, and a gap shows. Next: Ben’s phone was offline for 10 minutes. He is in 200 conversations. How does it catch up?