Live data from Hacker News

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

artificialworlds.net

111–119 of 119 posts

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

#111
post #105
post #89

Earlier quoted context omitted.

Give up on the idea of "the timestamp" of an event. There is no such thing. Clocks are unreliable, and even if every clock in a system is perfectly in-sync (via atomic transponders or whatever) they're still subject to speed-of-light discrepancies that make it impossible to define "the time" of any event. Two nodes separated by 10000km require ~33ms to send information in one direction, and ~66ms to do a roundtrip. S…

> Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them). Vector clocks don't solve this problem, as they only provide a partial ordering. When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events. Vector clo…

> When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events.

That's right! Vector clocks only provide partial order. But partial order is the only actual truth in any distributed system. Total order is a fiction, which only exists in the context of a specific node, based on that specific node's experience of reality (message receipt).

In any non-trivial distributed system, there is no consistent (total) order of events, at least not without a consensus protocol. There are lots of ways to hack a (fake) total order, and many of those approaches are enormously successful nearly all of the time. But, still, you know.

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

#112
post #111
post #105

Earlier quoted context omitted.

> Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them). Vector clocks don't solve this problem, as they only provide a partial ordering. When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events. Vector clo…

> When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events. That's right! Vector clocks only provide partial order. But partial order is the only actual truth in any distributed system. Total order is a fiction, which only exists in the context of a specific node, based on that…

I don't understand why you seem to agree with me but also said

> Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them).

A partial order solves the problem when messages are not simultaneous and so the partial order provides a total order. That there is in fact no total ordering of simultaneous messages doesn't solve the problem that users would like to have messages arrive in a consistent order without delay. This is unsolved, because it's unsolvable, therefore vector clocks aren't the solution.

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

#113
post #95
post #83

Earlier quoted context omitted.

I don't think IRC is a good analogy here because there's no "message resync" that happens when the netsplit is resolved. If there are two people on opposite sides of a split, and they both send messages to a channel while things are still split, they will not see the other's messages when the split is over. In the Matrix case, if a homeserver disappears for a while, it will sync any missed messages when it comes back…

Which is a design deficiency when those messages are 6 months old, and are spam, from people who got banned 5 months ago.

I think so, but I'm not sure that OP would agree, given that they apparently want to see the exact same scrollback on all their devices.

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

#114
post #112
post #111

Earlier quoted context omitted.

> When multiple messages are in flight in the same 'simultaneity window', different observers may receive them in different orders and vector clocks can't determine a consistent order of those events. That's right! Vector clocks only provide partial order. But partial order is the only actual truth in any distributed system. Total order is a fiction, which only exists in the context of a specific node, based on that…

I don't understand why you seem to agree with me but also said > Logical ordering of events in a distributed system is a solved problem. The solution is vector clocks (or something like them). A partial order solves the problem when messages are not simultaneous and so the partial order provides a total order. That there is in fact no total ordering of simultaneous messages doesn't solve the problem that users would…

Vector clocks provide a deterministic partial order, but partial order doesn't provide any kind of total order. That's true, yes.

But (as I'm sure you're aware) there is no single deterministic total order of events in a distributed system. The system can assert some specific total order, based on some specific criteria -- say, LWW based on node identity -- but that's system-specific and arbitrary.

That "users would like to have messages arrive in a consistent order without delay" is a nice and valid expectation, but is literally impossible, in the general case. Vector clocks solve a lower-level problem; nothing can solve the higher-level problem.

(Again, as I'm sure you're aware.)

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

#115
post #98
post #87

Earlier quoted context omitted.

> How far back should you be able to amend history? If user U1 sends a message M1 at time T1, then U1 must be able to modify/delete that message M1, in some reasonable sense, at any conceivable time from T1 forwards. Any protocol that doesn't support some reasonable form of message modification/deletion in this sense, is a toy protocol, and will never be widely adopted.

I'm not talking about message editing but rather posting new messages with a backdated time.

I suppose every message has a few timestamps, including

- The timestamp that the user specified as part of the message

- The timestamp of the server that the user submitted the message to, directly

- The timestamp of the server that first received that message

- Any additional timestamp(s) of additional server(s) that received that message

The user can I guess backdate a time, but that would apply only to the first thing, and none of the others?

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

#116
post #115
post #98

Earlier quoted context omitted.

I'm not talking about message editing but rather posting new messages with a backdated time.

I suppose every message has a few timestamps, including - The timestamp that the user specified as part of the message - The timestamp of the server that the user submitted the message to, directly - The timestamp of the server that first received that message - Any additional timestamp(s) of additional server(s) that received that message The user can I guess backdate a time, but that would apply only to the first t…

The first one is the only one that can accurately describe where the user intended for the message to land in the conversation. All the others are subject to network delays, so if you order messages by anything other than the first one, you are going to get a bad experience if you try to participate in a busy conversation with a poor connection.

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

#117
post #116
post #115

Earlier quoted context omitted.

I suppose every message has a few timestamps, including - The timestamp that the user specified as part of the message - The timestamp of the server that the user submitted the message to, directly - The timestamp of the server that first received that message - Any additional timestamp(s) of additional server(s) that received that message The user can I guess backdate a time, but that would apply only to the first t…

The first one is the only one that can accurately describe where the user intended for the message to land in the conversation. All the others are subject to network delays, so if you order messages by anything other than the first one, you are going to get a bad experience if you try to participate in a busy conversation with a poor connection.

The first one is entirely un-trustable, because the user-submitted timestamp can be at any arbitrary point in time, from t=0 to t=infinity. So the receiving system can use that timestamp as an important bit of signal, but it can't really treat it as strictly authoritative, at least not if it expects to maintain a coherent set of events overall.

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

#118
post #117
post #116

Earlier quoted context omitted.

The first one is the only one that can accurately describe where the user intended for the message to land in the conversation. All the others are subject to network delays, so if you order messages by anything other than the first one, you are going to get a bad experience if you try to participate in a busy conversation with a poor connection.

The first one is entirely un-trustable, because the user-submitted timestamp can be at any arbitrary point in time, from t=0 to t=infinity. So the receiving system can use that timestamp as an important bit of signal, but it can't really treat it as strictly authoritative, at least not if it expects to maintain a coherent set of events overall.

Exactly, that's why I'm saying it's a more challenging problem than it appears and there's no one solution that always gives the best experience in every case. I personally think a hybrid approach of allowing some limited discrepancy between user and server timestamps is probably the best you can do.

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

#119

I'm the author of the spec issue this blog post is based on: 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 co…

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.

One idea of mine was to continue when Matrix 2.0 would be stable. Might still have some time.
Post reply on HN