5 ms·

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

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.
    - adastra22 2y ago
      Only if you're not ok with eventual consistency and renumbering in the case of discovered conflicts or net splits.
  - toast0 2y ago
    I'm pretty sure this is actually impossible in a distributed system with independent operation, and if it were possible, it would be terrible UI anyway. Problem one is if you want to order events chronologically, you need to precisely decide what the time of the event means. Probably not the time the client hit send, because you can only measure that on the client and client clocks are at best approximately accurate. You could consider the time the server received it, and assume your server times are accurate, but that's still problematic because even in a well functioning system, if a user sends message A to server.wdc around the same time as a user sends message B to server.lax, users connected to server.wdc will get A then B, and users connected to server.lax will get B then A, and this leads to problem two: Problem two is messages generally display in order of receipt. If you get a message that slots in earlier in the thread, you may need to scroll up to see it. In a busy theead, it's going to be hard to read all the messages because of the back and forth. If you send a message, it may need to be reordered too. If you go back to the thread later, new messages may be in different places. This is more disorienting IMHO than different message orders for different viewers. Problem two gets even worse when you don't just have distance between servers, but also some network or other operational issues. If a server accepts a message, but is unable to forward it immediately, you probably want it to forward it whenever it can... if there's a significant delay, now the message is again going to be displayed in a place where it's difficult to see. You can kind solve this by forcing messages to a group to go through a single queue which forces an ordering, but that makes accepting messages for a group a lot more difficult.
    - j16sdiz 2y ago
- thomastay 2y ago
  yeah, having eventual consistency for messages across homeservers makes the work on the client harder. I guess they just have to accept that messages will "appear in the past" as you said. But at least for messages sent within the same homeserver, I would think that those two apis should return the same data
  - fiddlerwoaroof 2y ago
    I think you basically want a partial order for federated chat: messages should arrive after the messages that cause them but not necessarily after messages that didn’t cause them. In the case of a network partition, this allows people on either side of the partition to continue communicating at the cost of non-determinism when the partition is resolved.
    - duskwuff 2y ago
      I'd maintain that an important property is for the system to be eventually consistent with regards to history. You don't want a transient network event to potentially result in two users permanently seeing messages in a different order.
      - fiddlerwoaroof 2y ago
        I don’t think you can prevent that without centralizing on a single server
        lmm 2y ago
        You can, but it results in the situation the article is complaining about. During a netsplit, people chatting on opposite sides of the netsplit continue to be able to chat (by design), but will (obviously) see a different history from each other. So when the netsplit heals, you have a dilemma: either you splice the history from the other side in, giving eventual consistency at the cost of changing the history that people have already read, or you keep permanently different histories on servers that were on one side or the other.
- mycall 2y ago
  Split-brain scenarios can be resolved using an odd number of nodes (or voters) to achieve a majority consensus to agree on the state of the system, stopping the services on the minority side to prevent conflicting operations. Once communication is restored, the stopped nodes can rejoin the cluster and synchronize their data. Vector clocks are a great abstraction for ensuring correct ordering as well.
- wolrah 2y ago
  Perhaps I'm wrong about how Matrix works, but my understanding was that at least public rooms still had a "primary" homeserver, like for example I can connect to #debian:matrix.org from any number of federated servers but matrix.org is still where that room "lives". If that understanding is correct, then IMO the answer is simply that the canonical timeline is what that server says it is. Poorly connected users or those on other servers experiencing issues or delays with federation may temporarily see a different sequence of events but once everyone's had a chance to sync back up the state should generally be what the primary server for the room saw it as. Perhaps there should be some sort of flag for "this message has been reordered during a resync" that clients which initially had a different state due to whatever reason could store to make it clear what happened, and likewise if the central homeserver receives messages with a timestamp significantly off real time it could flag those messages as possibly having been received out of order while still displaying them in the order they were received.
  - moritzruth 2y ago
    AFAIK there is no primary homeserver. The human-readable name of a channel has a homeserver part, but this is only for discovery purposes and maps to an alphanumeric random ID.
nine_k 2y ago
What's mysterious here? One ordering is dictated (arrival time), another left for the consideration of the server (likely allowing for stuff like pinned messages, etc, that break the strict ordering). If a Matrix server allows to delete messages (by the poster or by a moderator), then increasing IDs with no gaps become impossible. If the server allows editing of existing messages, then a sequence with no gaps is not sufficient to reflect all changes. Ideally a server does not do either, but uses more messages to augment existing messages, or mark some as deleted; with that, a sequence with no gaps would suffice.

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.
  - adastra22 2y ago
    Only if you're not ok with eventual consistency and renumbering in the case of discovered conflicts or net splits.
- toast0 2y ago
  I'm pretty sure this is actually impossible in a distributed system with independent operation, and if it were possible, it would be terrible UI anyway. Problem one is if you want to order events chronologically, you need to precisely decide what the time of the event means. Probably not the time the client hit send, because you can only measure that on the client and client clocks are at best approximately accurate. You could consider the time the server received it, and assume your server times are accurate, but that's still problematic because even in a well functioning system, if a user sends message A to server.wdc around the same time as a user sends message B to server.lax, users connected to server.wdc will get A then B, and users connected to server.lax will get B then A, and this leads to problem two: Problem two is messages generally display in order of receipt. If you get a message that slots in earlier in the thread, you may need to scroll up to see it. In a busy theead, it's going to be hard to read all the messages because of the back and forth. If you send a message, it may need to be reordered too. If you go back to the thread later, new messages may be in different places. This is more disorienting IMHO than different message orders for different viewers. Problem two gets even worse when you don't just have distance between servers, but also some network or other operational issues. If a server accepts a message, but is unable to forward it immediately, you probably want it to forward it whenever it can... if there's a significant delay, now the message is again going to be displayed in a place where it's difficult to see. You can kind solve this by forcing messages to a group to go through a single queue which forces an ordering, but that makes accepting messages for a group a lot more difficult.
  - j16sdiz 2y ago
thomastay 2y ago
yeah, having eventual consistency for messages across homeservers makes the work on the client harder. I guess they just have to accept that messages will "appear in the past" as you said. But at least for messages sent within the same homeserver, I would think that those two apis should return the same data
- fiddlerwoaroof 2y ago
  I think you basically want a partial order for federated chat: messages should arrive after the messages that cause them but not necessarily after messages that didn’t cause them. In the case of a network partition, this allows people on either side of the partition to continue communicating at the cost of non-determinism when the partition is resolved.
  - duskwuff 2y ago
    I'd maintain that an important property is for the system to be eventually consistent with regards to history. You don't want a transient network event to potentially result in two users permanently seeing messages in a different order.
    - fiddlerwoaroof 2y ago
      I don’t think you can prevent that without centralizing on a single server
      - lmm 2y ago
        You can, but it results in the situation the article is complaining about. During a netsplit, people chatting on opposite sides of the netsplit continue to be able to chat (by design), but will (obviously) see a different history from each other. So when the netsplit heals, you have a dilemma: either you splice the history from the other side in, giving eventual consistency at the cost of changing the history that people have already read, or you keep permanently different histories on servers that were on one side or the other.
mycall 2y ago
Split-brain scenarios can be resolved using an odd number of nodes (or voters) to achieve a majority consensus to agree on the state of the system, stopping the services on the minority side to prevent conflicting operations. Once communication is restored, the stopped nodes can rejoin the cluster and synchronize their data. Vector clocks are a great abstraction for ensuring correct ordering as well.
wolrah 2y ago
Perhaps I'm wrong about how Matrix works, but my understanding was that at least public rooms still had a "primary" homeserver, like for example I can connect to #debian:matrix.org from any number of federated servers but matrix.org is still where that room "lives". If that understanding is correct, then IMO the answer is simply that the canonical timeline is what that server says it is. Poorly connected users or those on other servers experiencing issues or delays with federation may temporarily see a different sequence of events but once everyone's had a chance to sync back up the state should generally be what the primary server for the room saw it as. Perhaps there should be some sort of flag for "this message has been reordered during a resync" that clients which initially had a different state due to whatever reason could store to make it clear what happened, and likewise if the central homeserver receives messages with a timestamp significantly off real time it could flag those messages as possibly having been received out of order while still displaying them in the order they were received.
- moritzruth 2y ago
  AFAIK there is no primary homeserver. The human-readable name of a channel has a homeserver part, but this is only for discovery purposes and maps to an alphanumeric random ID.

nine_k 2y ago

What's mysterious here? One ordering is dictated (arrival time), another left for the consideration of the server (likely allowing for stuff like pinned messages, etc, that break the strict ordering). If a Matrix server allows to delete messages (by the poster or by a moderator), then increasing IDs with no gaps become impossible. If the server allows editing of existing messages, then a sequence with no gaps is not sufficient to reflect all changes. Ideally a server does not do either, but uses more messages to augment existing messages, or mark some as deleted; with that, a sequence with no gaps would suffice.