skip to content

For a chat service that orders messages, why number them with a per-conversation sequence number instead of sorting by sender timestamps?

level: middleimportance: must knowfreq 68%

answer

  1. clocks disagree across devices
  2. same millisecond, no order
  3. a hole you can see
  4. last_seq + 1, atomically
  5. resume after N

basics

~20 s

A per-conversation sequence number, assigned by the server when it stores a message, gives every device the same order and makes a missing message visible as a gap. Sender timestamps suffer from clock skew and ties, and they never show that a message is missing.

solid answer

~40 s

When the server accepts a message, it stores it and gives it `seq = last_seq + 1` for that conversation, as one atomic step. This buys three things timestamps cannot. First, **one agreed order** on every device, whatever each phone's clock says. Second, **gap detection**: if a client holding 40 receives 42, it knows 41 exists and fetches it. Third, **an exact resume cursor** ("give me everything after 40"). Sender timestamps drift, can be set by hand, and collide in the same millisecond. The gap between 10:00:01 and 10:00:07 says nothing about whether a message sits between them. The counter is scoped to one conversation, so no global coordinator is needed, because unrelated conversations never need a relative order. Timestamps are still stored, but only for display.

code

pseudocode · 9 lines
pseudocode
on_message(conv, msg):
  h = highest_contiguous[conv]
  if msg.seq <= h:
    return                      # duplicate delivery
  store(conv, msg)
  if msg.seq > h + 1:
    request_range(conv, h + 1, msg.seq - 1)
  else:
    highest_contiguous[conv] = advance_over_stored(conv, h)

go deeper

for a junior

Remember the two failures of timestamps: clocks disagree between devices, and a timestamp cannot tell you that a message is missing.

for a middle

Explain how the server assigns the next number atomically per conversation, and walk through how a client uses its highest contiguous number to spot a gap and fetch the missing range.

for a senior

Talk about the write-path cost in hot groups, tombstones so deletes do not leave permanent holes, and how pending messages get their real position once the ack arrives.

for a principal

Frame the scope choice: a per-conversation counter spreads the coordination cost, whereas a global order would buy nothing a chat product needs and add a system-wide bottleneck.

## The problem ordering has to solve A chat conversation is a shared, **append-only list** of messages. Several people write to it, often from several devices each. Their messages travel over networks with very different delays. Every participant's screen must show the **same order**. A client must be able to tell that it **missed** something. After being offline, it must **resume** exactly where it stopped. The ordering key you choose decides whether these three things are cheap, expensive or impossible. ## Why timestamps are a weak ordering key - **Clock skew**: device clocks drift by seconds or minutes, and users can change them by hand. A reply can end up sorted *before* the message it answers. - **Ties**: two messages stamped in the same millisecond have no defined order unless you add a tiebreaker. - **No gap signal**: two adjacent timestamps say nothing about whether a message exists between them. - **Late arrivals**: a phone in a tunnel sends a message with an old timestamp. It gets inserted into history the reader has already scrolled past. Server receive timestamps remove skew *between devices*, but not ties or the missing gap signal. A fleet of servers also has several clocks of its own. So timestamps stay useful for **display** ("sent 10:04") but make a poor **ordering and sync key**. ## How a per-conversation sequence works When the server accepts a message, it stores it and assigns the next integer for that conversation: `seq = last_seq + 1`. The assignment must be **atomic per conversation**, so that two concurrent sends cannot receive the same number. Common ways to get that: - a **conditional update** (compare-and-set) on the conversation's `last_seq` counter, retried on conflict; - routing all writes for one conversation to a **single owner** that hands out numbers in order; - storing the message and the counter bump in **one transaction**. The counter is scoped to the **conversation**, not the whole system. A global counter would become a single write bottleneck, and nobody needs to know whether a message in one chat came before a message in an unrelated chat. | Property | Sender timestamp | Server timestamp | Per-conversation seq | |---|---|---|---| | Same order on every device | No | Mostly | Yes | | Reveals a missing message | No | No | Yes | | Exact resume cursor | No | Approximate | Yes | | Write-path coordination | None | None | Per conversation | ## Gap detection on the client The client tracks the **highest contiguous** sequence it holds for each conversation, then handles each arriving message as follows: 1. If `seq == highest + 1`, append the message and advance `highest`. 2. If `seq > highest + 1`, store the message, and request the missing range `highest + 1 .. seq - 1` from the server. 3. If `seq <= highest`, the message is a duplicate delivery, so drop it. ```pseudocode on_message(conv, msg): h = highest_contiguous[conv] if msg.seq <= h: return # duplicate, ignore store(conv, msg) if msg.seq > h + 1: request_range(conv, h + 1, msg.seq - 1) else: highest_contiguous[conv] = advance_over_stored(conv, h) ``` The same cursor serves as the **resume point** after a reconnect: "send me everything in this conversation after `highest`." ## Edge cases and trade-offs - **Acceptance order, not send order**: two users typing at the same moment are ordered by when the server accepted each message. That is acceptable because everyone sees the *same* order. - **Hot conversations**: in a very busy group, the per-conversation assignment is the contention point. Batching several messages into one counter update, or giving each conversation a single owner, keeps it cheap. - **Deletes and edits** must not renumber anything. A deleted message stays as a **tombstone** at its sequence. Otherwise a client sees a permanent hole and keeps asking for it. - **Pending sends** have no sequence until the server acknowledges them. The client shows them as "sending", then slots each one into its real position once the ack carries the assigned number. - **Scope**: this is ordering *inside the chat protocol*. How a message broker orders records between partitions is a separate concern. In short, timestamps describe *when* a message was written. The sequence number defines *where it sits* and makes a missing entry visible.

  • Why not use one global sequence number across all conversations?
    A global counter puts every message write in the system through a single coordination point, which caps throughput and creates a single point of failure. It also buys nothing, because clients only need to order and gap-check messages inside one conversation. A per-conversation counter spreads that coordination across conversations, so it scales with the number of chats.
  • What happens to gap detection when a message is deleted?
    If the deleted row simply disappears, a client that never saw it finds a permanent hole at that sequence and keeps requesting it. The fix is a tombstone: the sequence stays occupied by a "deleted" marker, so the range fetch returns something and the client's contiguous cursor can move past it.
  • How can a client show a message before the server has numbered it?
    It renders the message optimistically as "sending" and keys it by an ID the client generated. When the server's ack arrives with the assigned sequence, the client matches the ack by that ID and moves the message to its real position. If another participant's message was accepted first, the sender's copy may shift by one place.

saying these in an interview costs you the question

  • Sort by the sender's device clock; phones are synced well enough.
  • Timestamps are enough to notice a missing message.
  • Use one global auto-increment for every message in the system.
  • Delete a message by removing its row and renumbering the rest.
  • Sequence numbers reflect exactly the order users pressed send.