Chat message ordering

Users expect the messages in one conversation to show up in the same order on every device. Wall-clock timestamps can't guarantee that, because machines disagree about time. Chat uses a sequence number per conversation instead. Each message gets the next number in its channel. Devices apply messages in sequence and fill any gaps.

The big idea

Think of page numbers in one book. You only need the numbers to be right within that book, not across a whole library. Global order across every conversation is expensive, and users don't need it.

The rule is simple. Keep total order inside each conversation, and drop any idea of order between conversations.

Walking through it

There are two common ways to assign the position.

• Snowflake-style IDs combine time, a shard and a sequence in one number. They sort roughly in time order.
• A per-channel pair, (channelId, channelSeq), where channelSeq comes from a sequencer or the partition leader for that channel.

Either way, one owner issues the next number for each conversation. That keeps the order consistent.

A device applies a live message only if its sequence is the next one it expects. Otherwise it backfills. Here is a device that has message 10 and receives message 13.

Device has:      ... 10
Live message:    13   → not next (expected 11), so hold it
Fetch history:   11, 12
Apply in order:  11, 12, 13

Reconnect. After a reconnect, the client sends the last sequence it saw for each channel. The server returns the missed messages. If the gap is huge, because the user was offline for a week, the server says so, and the client pages through HTTP history instead. Don't push millions of messages through one socket.

Common mistakes

• Ordering by device or server clock. Two servers 2 ms apart can't be ordered reliably by their timestamps.
• Applying live messages without a gap check. A device then shows messages out of order, and the gap never fills.
• Replaying huge gaps over the socket. Send the client to paginated history instead.

Check yourself

1. A device has message 10 and receives message 13. What should it do? Fetch 11 and 12 from history, then apply 11, 12 and 13 in order.
2. Who should issue the per-channel sequence number? One owner per channel, such as a sequencer or the partition leader, so every position is assigned once.

Key takeaways

• Order messages per conversation with a sequence issued per channel.
• Apply live messages only when the sequence is next, and backfill gaps from history.
• Don't rely on wall-clock time to order messages across machines.
• Use paginated history for large gaps, not the socket.

Further learning

The message ordering page covers ordering in queues, which uses similar ideas.

Next, read about chat storage, which explains how the history behind these sequences is stored.