Ensuring In-Order Delivery of IM Messages: Causes and Solutions

Instant‑messaging (IM) systems often face the challenge of delivering messages in the correct order. The article first examines three main causes of out‑of‑order delivery: unreliable timestamps across clients and servers, network‑level reordering, and multithreaded processing on both client and server sides.

Time‑related issues : Different machines have unsynchronized clocks, making local timestamps unsuitable for ordering messages.

Network reordering : Even a single client‑to‑gateway connection can see messages arrive out of sequence due to packet loss, retransmission, or varying network conditions.

Multithreading : Multiple send/receive threads on either side can interleave messages, further breaking order.

To address these problems, the article proposes several strategies.

Message sequence numbers : Introduce a component that generates monotonically increasing IDs independent of local time. The ID can be composed of logical server ID, channel ID, and an intra‑channel incrementing counter, ensuring a consistent ordering metric.

Group‑chat handling : Route all messages of the same chat channel to the same logical server based on the channel (or group) ID, so that ordering is preserved within that server.

Network‑level reordering mitigation : Borrow concepts from TCP, such as buffering out‑of‑order packets and using ACKs to confirm receipt of sequential messages before delivering them to the application layer.

Final solution combines the above ideas:

Clients maintain a local cache queue with sequence numbers and ACK the gateway only when a message is confirmed to be in order.

If a message with a higher sequence number arrives before missing lower numbers, the gateway replies with the last confirmed ACK, preventing the client from processing the out‑of‑order message.

When the logical server handling a channel changes (e.g., due to failure), the server ID part of the sequence changes, prompting both gateway and client to discard stale cached messages and restart the ordering process.

This design ensures that, despite time differences, network variability, and server migrations, IM messages are delivered to the application layer in the correct order.