1

Let's say we have a group chat in a chat app build with websockets. And 3 users (A, B and C) chatting in that group. All 3 users send their message one after another with an interval of 1 second (it looks like the time is in h:mm format but it doesn't matter in our case):

enter image description here

The server recieves those messages in the same exact order as they were sent. And after some time server broadcasts those messages to all users in the same exact order (and same time, of course). But messages from each user are broadcasted with 1s interval:

enter image description here

enter image description here

And "I'm Carol (from C)" has been broadcasted at 2:37.

Now let's say some kind of network issue took place so Bob received Alice's message with a 10 second delay. But his own message and Carol's message were delivered on time and in the same order the server broadcasted them. And now users have the following message order in their chat clients:

For Alice:

  1. Me: I'm Alice
  2. B: I'm Bob
  3. C: I'm Carol

For Carol:

  1. A: I'm Alice
  2. B: I'm Bob
  3. Me: I'm Carol

But for Bob the order is broken:

  1. Me: I'm Bob
  2. B: I'm Carol
  3. A: I'm Alice

It could be ever stranger if each user sent several messages and then each user received those messages in different orders due to newtwork issues.

My question is does websocket protocol have any mechanisms to prevent such behavior? If it does not then how can I as a developer preserve the same order of messages for all users?

My idea was to add a timestamp to each message on the server side when it broadcasts them. The timestamp could tell the client app in which order each message should be displayed. But what if some message was delivered with a 10 second delay and a few other messages were delivered in the meanwhile? To insert the delayed message before new ones on delivery seems like a bad idea. Because: 1) a user can miss this message because it was inserted in between the old messages: 2) it would seems like we shuffle chat messages so it would be difficult to reason about the chat history - you don't have some message in chat history, but the next time you check, it's there.

Is it really a problem for chat apps? And what are some solutions to it?

2
  • 1
    WebSocket uses a TCP connection or HTTP/3, both of which guarantee order of packets. As long as you're using one connection, all messages in that connection will be delivered in order, or the connection will time out. So this is a non-issue. Even if out of order delivery were possible, this could be fixed if the server assigns a logical timestamp (a counter like message 1), so clients could see when messages are missing and could sort messages into the correct order. This is exactly what TCP does, though TCP also buffers data until the next packet is there, and makes the server re-send data.
    – amon
    Jan 14 at 7:30
  • 2

3 Answers 3

3

This is a (mostly) solved problem that has two parts:

  • Synchronization of chat log between clients
  • Consistent representation of out-of-order messages

Synchronization

Most chat applications do not do synchronization at all, however others do. Suppose that your applications deems order of messages important. Then:

Consider, that chat application deals with state of chat log instead of separate chat messages. Synchronization of a state where multiple parties contribute changes is a solved problem and multiple protocols exists for the task with different tradeoffs. A trivial example would be for client to send "commands" instead of "messages". Each command could be "insert a message2 after message1" where messages are uniquely identified. This way ordering of messages is preserved to some extent (conflict resolution is still required, but can be trivially done for chat applications). It is important to ensure that parties apply commands in an idempotent manner.

Note that additional functions such as message removal and in-place editing require more effort. For complex applications like these read about consensus and consistency.

Representation

There are multiple ways to approach the problem of reduced visibility for out-of-order messages. They have different tradeoffs and may be combined.

Reply tracking

Enhance messages with additional meta-information, that indicates which message is being replied to. Even in absence of full-blown synchronization, this would help visualize and understand the chat history.

Cons

  • user has to specify the message to reply to
  • hard to trace concurrent discussions

Example: Telegram chats.

Threads

Threads are built on reply tracking and organize all messages in discussion trees, where timing of the messages is largely ignored.

Cons

  • user has to specify the message to reply to
  • hard to get overall "feel" of the chat
  • hard to find a specific message of interest as the structure of chat is non-linear and not all messages are visible

Example: Reddit.

Typing notifications

When a user starts authoring the message, show a placeholder or notification on other clients, to ensure they see a work is being done on the message and to help them recognize when they miss one. In the old days, a message draft was included in the notification, but that was eliminated for security concerns. This only works to an extent, as during prolonged network outages notifications fail to reach destination.

Cons

  • expects user to keep track of other parties and their activity

Example: Slack.

Address (@)

User can explicitly mention another in a message, imitating normal address in the in-person offline conversation.

Cons

  • only works well for conversation tracking in a small party

Example: StackOverflow

2

You mentioned "the server", which simplifies matters since there's just one.

Server puts unique monotonic timestamps on the JSON payload of incoming messages, and we preserve those timestamps as messages get sent around. Each client is free to display messages in timestamp sorted order.

This scheme essentially says that a send event "happened" when it arrived at the server.


Alternatively, we could make adventurous assumptions about all clients being NTP synchronized, and that being "good enough", and we could tag messages with client timestamps instead.

This sacrifices the notion of causality. Messages racing against one another can still show ordering consistency issues similar to that depicted in the OP example.

The usual way to wiggle out of such trouble is with vector clocks, which resolve some causality ambiguities. We can only impose a partial order over the resulting observed messages, since some relationships truly are acausal and unordered due to races. But it is an improvement, and at least the assertions made by such a distributed system will be true facts.

If "the server" expands to a redundant cluster of servers, it will be hard to avoid this issue, so we're likely to add vector clocks at that point.

Let each message be tagged by the client with GUID and origin timestamp, using ULID or UUIDv7. Then the simplest vector clock implementation is to add a single "References: guid1" field to each outgoing message. Choose guid1 as the most recent message displayed in the channel at the time a user strikes the RETURN key. (For extra credit, list the K most recent guids, so we go from a 1-vector to a vector of length K.) This induces a partial order over messages. Distant clients will attempt to display a given message after the referenced message. Use timestamps to break ties.


Client timestamps will inevitably drift and not correspond to causal relationships. So it doesn't really matter if such timestamps appear down at the WebSocket framing level or up at the app level.

To solve the problem properly you're still going to need vector clocks or some similar fancy high-level approach, perhaps Birman's Virtual Synchrony or a competing Atomic Multicast protocol.

1

Assuming this actually is about a chat applications for humans to interact with each other and not a placeholder for some other kind of system, I would be more concerned with (the appearance of) responsiveness than with ensuring a globally consistent ordering of messages.

If I were a user of your chat application, I would be more concerned that it takes several seconds before my own message appears in my own chat window. It would be perfectly fine to see

I'm Bob
I'm Alice
I'm Carol

on Bob's device and

I'm Carol
I'm Alice
I'm Bob

on Carol's device.

Sometimes it might take a few seconds to figure out what someone is responding to, but we humans are usually quite capable of doing that.

2
  • There would be no delays if messages are inserted and not appended. Which implementation do you address?
    – Basilevs
    Jan 14 at 11:24
  • @Basilevs, I am addressing the example implementation where the server-side processing takes 5 seconds and apparently you only see the messages sent by the server. Jan 14 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.