9 ms·

Message order in Matrix: right now, we are deliberately inconsistent

136 points by whereistimbo 2y ago

lmm 2y ago
In general we certainly want to be able to change things "in the past". When there is unpleasant spam in a groupchat, you want a moderator to be able to remove or at least hide it, in a way that means people scrolling up won't be exposed to it unless they explicitly want to. (You could argue for having the client deal with all of that, but I don't think there's much benefit). And if, as in the example at the end, clients on different homeservers will inevitably see different views, then I don't think always showing the same history to the same client, or clients on the same server, solves the "gaslighting" problem - if anything it could make it worse. Maybe clients should make it obvious when messages have been "retconned" into the scrollback, and maybe servers should have certain features to support that. But the idea of having a consistent linear timeline is one of those answers that's clear, simple, and wrong.
danpalmer 2y ago
This is something that many chat apps get wrong and I'm not sure this article is moving in the right direction. The UX is fairly clear in my mind: 1. All up-to-date clients should be displaying the same message order. 2. A single client should not send messages in the wrong order. Yes a client may be out of date and therefore show something different, but once it becomes up to date it should be showing the same state even if that means amending history. Why? Because the humans reading it will be confused otherwise! An app getting more data is something we intuitively understand, but if my client shows something and yours shows something else, we will conclude different meanings from it. Additionally there are some clients that treat each message input by the user as a retriable thing in isolation, which is also clearly incorrect. If I send two messages and the first fails to go through, I almost certainly don't want to retry the second until the first has gone through, otherwise my client has literally sent out of order messages! I use Beeper for chat and this is one of the most frustrating things it does.
- lmm 2y ago
  > Additionally there are some clients that treat each message input by the user as a retriable thing in isolation, which is also clearly incorrect. If I send two messages and the first fails to go through, I almost certainly don't want to retry the second until the first has gone through, otherwise my client has literally sent out of order messages! I don't think that's clearly incorrect. If you sent two messages you presumably want them to be two messages and they should be retried as such. If what you wanted to send was a single, multi-line message, surely you would have just done that?
  - winwang 2y ago
    I break up my messages, as do many people.
    - adastra22 2y ago
      Do you do so with the expectation that they might arrive out of order, or one fails?
      - Spivak 2y ago
        Out of order no, failing and having to manually re-send which makes it out of order is acceptable.
        kelnos 2y ago
        I find that unacceptable and frustrating, personally. If a message fails to send, I want the client to hold back any later messages until the failed message is resolved somehow. It should auto-retry and (hopefully) eventually succeed, or I can manually delete it and "release" the following messages.
      - agos 2y ago
        I do so with the expectation that they should arrive in order if no one fails, but apparently it is "debatable" if this is a reasonable expectation
thomastay 2y ago
Having dealt with this problem at work for several years now, I feel the pain of keeping different clients in sync - it's extremely difficult. Not sure if it's possible in Matrix, but consider having a message ID that increments by one on every message in a room. That lets the client know pretty quickly if there's a gap or a misordering. Not really getting this point though: The /sync API returns events in an order "according to the arrival time of the event on the homeserver". The spec for /messages says it returns events "in chronological order. (The exact definition of chronological is dependent on the server implementation.)". Why would those two return different results? When does the chronological order of two messages differ from the arrival time of the event on the homeserver?
- AlotOfReading 2y ago
  Non-monotonic clocks?
- wkrp 2y ago
  /messages might be a legacy endpoint compared to a newer /sync. I know Matrix has been working hard on their sliding sync api.
- duskwuff 2y ago
  What I think you're missing is that Matrix runs as a distributed system. There's no central authority to assign IDs to messages, and it's possible for a single group chat to run in a split-brain configuration if two homeservers lose connectivity to each other. When those homeservers reconnect, users connected to each one will see messages appear "in the past" which were sent by users on the other side of the split.
  - adastra22 2y ago
    That makes the problem harder, but not impossible.
    - lmm 2y ago
      It makes an incrementing message ID impossible.
throwaway14356 2y ago
i had a hilarious argument with the significant other when my messages appeared a very lame response to messages i didn't receive. i think the mental model should be what is most useful in court. if a netsplit occurs the state of the room doesn't exist anymore, conversation can continue but it should be a different room populated with working available clients. The main room can be restored and the missed convo can be a 3rd room
- agos 2y ago
  I remember when iMessage/Apple Messages did this, back in its first days. Everybody hated it.
Vanit 2y ago
I'm throwing some shade here, but this reeks of backend engineers not caring about UX.
- fsckboy 2y ago
  this reeks of backend engineers not caring about UX designers who don't understand the problem while the UI designers who do understand are barred from attending meetings for bad behavior. I'm not throwing shade.
  - kelnos 2y ago
    I don't agree. There's no technical reason why the different API endpoints can't return the same ordering. The current top comment here[0] is from someone who has implemented this (IMO) correctly in a different homeserver implementation. [0] https://news.ycombinator.com/item?id=42325737 https://news.ycombinator.com/item?id=42325737
shepherdjerred 2y ago
This sounds like a pretty good use case for a consensus algorithm like Paxos or Raft
- evilotto 2y ago
  I think the most important property to preserve is causality; that is, if a user sends a message B after they have read (i.e., received) a message A, then B should come after A for everyone, because B depends on A. Basically use a Lamport clock.
- purpleidea 2y ago
  Those are CP which is impossible in a distributed messaging system where it has to obviously be AP. Otherwise you'd have to guarantee that everyone involved is always online (no partition) to make progress on sending messages! I think I have this right anyways. (CAP theorem for anyone curious.)
timokoesters 2y ago
I'm the author of the spec issue this blog post is based on: https://github.com/matrix-org/matrix-spec/issues/852 https://github.com/matrix-org/matrix-spec/issues/852 In my implementation for the Conduit Matrix server, the /sync order is used for everything. The timeline is just one list that grows on one end for incoming events and on the other end for backfilled events. I think it's important that the message order does not change, because that's very difficult to communicate to the user.
- moritzruth 2y ago
  A few years ago, I started writing a Matrix client library for Kotlin. At one point, I had to make an API decision based on how messages are ordered. When I found this issue, I subscribed to it and planned on continuing with my library when the spec was clarified. Given how foundational this spec unclarity is, I thought it wouldn't take too long. Well.
  - solarkraft 2y ago
    One idea of mine was to continue when Matrix 2.0 would be stable. Might still have some time.
- Fizzadar 2y ago
  Oh that’s neat (TIL), am also working on a HS that also does this [1]. Not only does it feel like the most correct (I don’t think there is a perfect) behaviour for the user but also makes implementation much simpler. Synapse has a LOT of ordering foo and magic in the code I still don’t fully understand and I’ve gone fairly deep into synapse at times for work. [1] https://github.com/Beeper/babbleserv https://github.com/Beeper/babbleserv
Saris 2y ago
That's something that Telegram always seems to get right, I've never seen messages out of order in different clients, and if I do something like upload a video then immediately send more text messages before it's done, it will shove the video in between the messages where it should be when the upload is done. I know it's a much harder problem without a central server managing things. But consistency is very important for messages, out of order they could have a very different meaning and be very confusing.
- dspillett 2y ago
  > I know it's a much harder problem without a central server managing things. In got example it is easy if the structures relating to the video and text contain some what to identify the source node, or just that they belong to the same lineage (you could have a per-thread-per-source-node value, produced from a salted hash of the real information, if source host Id is considered sensitive) and a timestamp taken at that node. (Caveat: I know little of the specific protocols that are relevant here, so don't know if they do contain any such datum) Where message ordering gets difficult to the point of impracticality (if not impossibility) is where you are ordering messages from many different sources that may not have fully synchronised clocks. You can make it easier with "in reply to" and "sent after" priorities (in each case, the value being a message identifier) so any given message can be sorted by its context, but the order of sibling messages may still not have a single possible ordering. And you have to decide, if using a "sent after" value, if you have the last message received at the time of sending, the last message received before this message was stated, the latest opened messages, etc, all of which could give different results. To a certain extent you have to get to a point where ordering is good enough and you give up on it being exact & unambiguously consistent, or you'll spend so much time working out the ordering and have no time to send you own messages :)
Terr_ 2y ago
My preference would be to avoid even attempting to force all into a single chronology. Instead, imagine something like the output of `git log --graph`, where the network split/rejoin moments are also displayed by lines. It would allow people to tell that two independent conversations were going on, and that certain messages were written while another was not known.
amstan 2y ago
It's infuriating how the client must be stateful and have local storage, for both the access_token and the last message recieved. That's right you must remember as the client where the last events [1] you've seen (even if you already told the server to mark it as read) was or else the server will happily send you the same messages over and over again across restarts of your client. I kind of miss making IRC bots where things were much simpler and ... quicker honestly (latency wise). [1] https://uhoreg.gitlab.io/matrix-tutorial/sync.html#:~:text=w https://uhoreg.gitlab.io/matrix-tutorial/sync.html#:~:text=w...
rkangel 2y ago
This article makes a logical step that I think is incorrect - that message order from the server is the order that a client then displays them in. Surely that's a presentation issue - you should display messages chronologically, regardless of what order you got them from the server? The author does touch on this a little bit, I don't see how that isn't the "obviously" correct approach?: > An alternative is to continue providing events in any order, but add some kind of order number that allows clients to sort events into /sync order. MSC4033 proposes this.
- dzaima 2y ago
  That "presentation issue" is quite an issue though; how do you sanely present to a user the fact that there are new messages to read, but they're scattered throughout the history of the message log arbitrarily far back? Granted, tacking them all at the end isn't necessarily good, but at least the user will see them, and timestamp indicators can help make sense of it. And I don't even see how placing them chronologically would be particularly useful - given a netsplit there's not gonna be any relation between the previously-present and delayed-received messages at that time interval anyway, you're just interleaving two entirely different discussions for no reason. (ok maybe there can be some unidirectional delay where it could maybe be useful, idk)
  - snackbroken 2y ago
    > how do you sanely present to a user the fact that there are new messages to read, but they're scattered throughout the history of the message log arbitrarily far back? Like this[1]. It's how Element does it, and it's perfectly fine. Show the unread messages with a different background color until the user dismisses them if you must distinguish them from previously read messages. Alternatively, add a "jump to last unread message" button (and change the "jump to first" icon into a double up-arrow) that marks said message as read after jumping to it so you can just keep clicking it to hop to each one. If there's anything I'd change about this UI element, it's to display the number of unread messages in the green dot. [1](https://imgur.com/UMboT1o https://imgur.com/UMboT1o)
    - 2y ago

136 points by whereistimbo 2y ago

lmm 2y ago

In general we certainly want to be able to change things "in the past". When there is unpleasant spam in a groupchat, you want a moderator to be able to remove or at least hide it, in a way that means people scrolling up won't be exposed to it unless they explicitly want to. (You could argue for having the client deal with all of that, but I don't think there's much benefit). And if, as in the example at the end, clients on different homeservers will inevitably see different views, then I don't think always showing the same history to the same client, or clients on the same server, solves the "gaslighting" problem - if anything it could make it worse. Maybe clients should make it obvious when messages have been "retconned" into the scrollback, and maybe servers should have certain features to support that. But the idea of having a consistent linear timeline is one of those answers that's clear, simple, and wrong.

danpalmer 2y ago

This is something that many chat apps get wrong and I'm not sure this article is moving in the right direction. The UX is fairly clear in my mind: 1. All up-to-date clients should be displaying the same message order. 2. A single client should not send messages in the wrong order. Yes a client may be out of date and therefore show something different, but once it becomes up to date it should be showing the same state even if that means amending history. Why? Because the humans reading it will be confused otherwise! An app getting more data is something we intuitively understand, but if my client shows something and yours shows something else, we will conclude different meanings from it. Additionally there are some clients that treat each message input by the user as a retriable thing in isolation, which is also clearly incorrect. If I send two messages and the first fails to go through, I almost certainly don't want to retry the second until the first has gone through, otherwise my client has literally sent out of order messages! I use Beeper for chat and this is one of the most frustrating things it does.

lmm 2y ago
> Additionally there are some clients that treat each message input by the user as a retriable thing in isolation, which is also clearly incorrect. If I send two messages and the first fails to go through, I almost certainly don't want to retry the second until the first has gone through, otherwise my client has literally sent out of order messages! I don't think that's clearly incorrect. If you sent two messages you presumably want them to be two messages and they should be retried as such. If what you wanted to send was a single, multi-line message, surely you would have just done that?
- winwang 2y ago
  I break up my messages, as do many people.
  - adastra22 2y ago
    Do you do so with the expectation that they might arrive out of order, or one fails?
    - Spivak 2y ago
      Out of order no, failing and having to manually re-send which makes it out of order is acceptable.
      - kelnos 2y ago
        I find that unacceptable and frustrating, personally. If a message fails to send, I want the client to hold back any later messages until the failed message is resolved somehow. It should auto-retry and (hopefully) eventually succeed, or I can manually delete it and "release" the following messages.
    - agos 2y ago
      I do so with the expectation that they should arrive in order if no one fails, but apparently it is "debatable" if this is a reasonable expectation

thomastay 2y ago

Having dealt with this problem at work for several years now, I feel the pain of keeping different clients in sync - it's extremely difficult. Not sure if it's possible in Matrix, but consider having a message ID that increments by one on every message in a room. That lets the client know pretty quickly if there's a gap or a misordering. Not really getting this point though: The /sync API returns events in an order "according to the arrival time of the event on the homeserver". The spec for /messages says it returns events "in chronological order. (The exact definition of chronological is dependent on the server implementation.)". Why would those two return different results? When does the chronological order of two messages differ from the arrival time of the event on the homeserver?

AlotOfReading 2y ago
Non-monotonic clocks?
wkrp 2y ago
/messages might be a legacy endpoint compared to a newer /sync. I know Matrix has been working hard on their sliding sync api.
duskwuff 2y ago
What I think you're missing is that Matrix runs as a distributed system. There's no central authority to assign IDs to messages, and it's possible for a single group chat to run in a split-brain configuration if two homeservers lose connectivity to each other. When those homeservers reconnect, users connected to each one will see messages appear "in the past" which were sent by users on the other side of the split.
- adastra22 2y ago
  That makes the problem harder, but not impossible.
  - lmm 2y ago
    It makes an incrementing message ID impossible.

throwaway14356 2y ago

i had a hilarious argument with the significant other when my messages appeared a very lame response to messages i didn't receive. i think the mental model should be what is most useful in court. if a netsplit occurs the state of the room doesn't exist anymore, conversation can continue but it should be a different room populated with working available clients. The main room can be restored and the missed convo can be a 3rd room

agos 2y ago
I remember when iMessage/Apple Messages did this, back in its first days. Everybody hated it.

Vanit 2y ago

I'm throwing some shade here, but this reeks of backend engineers not caring about UX.

fsckboy 2y ago
this reeks of backend engineers not caring about UX designers who don't understand the problem while the UI designers who do understand are barred from attending meetings for bad behavior. I'm not throwing shade.
- kelnos 2y ago
  I don't agree. There's no technical reason why the different API endpoints can't return the same ordering. The current top comment here[0] is from someone who has implemented this (IMO) correctly in a different homeserver implementation. [0] https://news.ycombinator.com/item?id=42325737 https://news.ycombinator.com/item?id=42325737

shepherdjerred 2y ago

This sounds like a pretty good use case for a consensus algorithm like Paxos or Raft

evilotto 2y ago
I think the most important property to preserve is causality; that is, if a user sends a message B after they have read (i.e., received) a message A, then B should come after A for everyone, because B depends on A. Basically use a Lamport clock.
purpleidea 2y ago
Those are CP which is impossible in a distributed messaging system where it has to obviously be AP. Otherwise you'd have to guarantee that everyone involved is always online (no partition) to make progress on sending messages! I think I have this right anyways. (CAP theorem for anyone curious.)

timokoesters 2y ago

I'm the author of the spec issue this blog post is based on: https://github.com/matrix-org/matrix-spec/issues/852 https://github.com/matrix-org/matrix-spec/issues/852 In my implementation for the Conduit Matrix server, the /sync order is used for everything. The timeline is just one list that grows on one end for incoming events and on the other end for backfilled events. I think it's important that the message order does not change, because that's very difficult to communicate to the user.

moritzruth 2y ago
A few years ago, I started writing a Matrix client library for Kotlin. At one point, I had to make an API decision based on how messages are ordered. When I found this issue, I subscribed to it and planned on continuing with my library when the spec was clarified. Given how foundational this spec unclarity is, I thought it wouldn't take too long. Well.
- solarkraft 2y ago
  One idea of mine was to continue when Matrix 2.0 would be stable. Might still have some time.
Fizzadar 2y ago
Oh that’s neat (TIL), am also working on a HS that also does this [1]. Not only does it feel like the most correct (I don’t think there is a perfect) behaviour for the user but also makes implementation much simpler. Synapse has a LOT of ordering foo and magic in the code I still don’t fully understand and I’ve gone fairly deep into synapse at times for work. [1] https://github.com/Beeper/babbleserv https://github.com/Beeper/babbleserv

Saris 2y ago

That's something that Telegram always seems to get right, I've never seen messages out of order in different clients, and if I do something like upload a video then immediately send more text messages before it's done, it will shove the video in between the messages where it should be when the upload is done. I know it's a much harder problem without a central server managing things. But consistency is very important for messages, out of order they could have a very different meaning and be very confusing.

dspillett 2y ago
> I know it's a much harder problem without a central server managing things. In got example it is easy if the structures relating to the video and text contain some what to identify the source node, or just that they belong to the same lineage (you could have a per-thread-per-source-node value, produced from a salted hash of the real information, if source host Id is considered sensitive) and a timestamp taken at that node. (Caveat: I know little of the specific protocols that are relevant here, so don't know if they do contain any such datum) Where message ordering gets difficult to the point of impracticality (if not impossibility) is where you are ordering messages from many different sources that may not have fully synchronised clocks. You can make it easier with "in reply to" and "sent after" priorities (in each case, the value being a message identifier) so any given message can be sorted by its context, but the order of sibling messages may still not have a single possible ordering. And you have to decide, if using a "sent after" value, if you have the last message received at the time of sending, the last message received before this message was stated, the latest opened messages, etc, all of which could give different results. To a certain extent you have to get to a point where ordering is good enough and you give up on it being exact & unambiguously consistent, or you'll spend so much time working out the ordering and have no time to send you own messages :)

Terr_ 2y ago

My preference would be to avoid even attempting to force all into a single chronology. Instead, imagine something like the output of `git log --graph`, where the network split/rejoin moments are also displayed by lines. It would allow people to tell that two independent conversations were going on, and that certain messages were written while another was not known.

amstan 2y ago

It's infuriating how the client must be stateful and have local storage, for both the access_token and the last message recieved. That's right you must remember as the client where the last events [1] you've seen (even if you already told the server to mark it as read) was or else the server will happily send you the same messages over and over again across restarts of your client. I kind of miss making IRC bots where things were much simpler and ... quicker honestly (latency wise). [1] https://uhoreg.gitlab.io/matrix-tutorial/sync.html#:~:text=w https://uhoreg.gitlab.io/matrix-tutorial/sync.html#:~:text=w...

rkangel 2y ago

This article makes a logical step that I think is incorrect - that message order from the server is the order that a client then displays them in. Surely that's a presentation issue - you should display messages chronologically, regardless of what order you got them from the server? The author does touch on this a little bit, I don't see how that isn't the "obviously" correct approach?: > An alternative is to continue providing events in any order, but add some kind of order number that allows clients to sort events into /sync order. MSC4033 proposes this.

dzaima 2y ago
That "presentation issue" is quite an issue though; how do you sanely present to a user the fact that there are new messages to read, but they're scattered throughout the history of the message log arbitrarily far back? Granted, tacking them all at the end isn't necessarily good, but at least the user will see them, and timestamp indicators can help make sense of it. And I don't even see how placing them chronologically would be particularly useful - given a netsplit there's not gonna be any relation between the previously-present and delayed-received messages at that time interval anyway, you're just interleaving two entirely different discussions for no reason. (ok maybe there can be some unidirectional delay where it could maybe be useful, idk)
- snackbroken 2y ago
  > how do you sanely present to a user the fact that there are new messages to read, but they're scattered throughout the history of the message log arbitrarily far back? Like this[1]. It's how Element does it, and it's perfectly fine. Show the unread messages with a different background color until the user dismisses them if you must distinguish them from previously read messages. Alternatively, add a "jump to last unread message" button (and change the "jump to first" icon into a double up-arrow) that marks said message as read after jumping to it so you can just keep clicking it to hop to each one. If there's anything I'd change about this UI element, it's to display the number of unread messages in the green dot. [1](https://imgur.com/UMboT1o https://imgur.com/UMboT1o)
  - 2y ago