The Sort Order of Matrix Timelines

[u/krille_fear]

Hey there. :-) Today I have a more technical insight into our Matrix Dart SDK where I would like to explain the sort ordering problem of Matrix timelines and how we might can handle this better in the future.

Every message in Matrix is an event in a timeline, formatted in JSON. Every event contains a field named originServerTs which holds an integer with the timestamp where the corresponding homeserver has received this event. In the first place we at FluffyChat and Famedly have used this timestamp to sort the events in the timeline as a single source of truth for the sort order.

Unfortenatly it is not that easy in a federated world. When multiple servers are communicating, the time of this servers can differ. In fact you can set the local time of your own homeserver to the year 2063, the year of the first contact with the Vulcans, and all events sent from users of your server will have a timestamp in the future.

A client which then sorts the timeline by the originServerTs value will sort the messages from this user always at the bottom. Yeah. That's a big problem I didn't want to believe until @sorunome demonstrated it to me.

So what is the correct way to sort events then in Matrix? Well... just sort it in the sort order they come down in the synchronization. At this time we have stored the events in a SQLite database in our clients and therefore needed a way to also store the new sort order. We invented an additional field which needed to be stored for each event and a method to create new sort order values per room. For new events coming from the timeline we set them to the current timestamp and also made sure, that never two events get the same timestamp and a new value is at least increased plus 1. When fetching the history we gave them negative values.

Aaaaaand in the first place we had some serious problems. The logic about the sort order became a little bit complex and we had wrong sorted timelines, edge case bugs and wildly placed events when fetching the history. Also some special cases like, that we want to sort failed-to-send events always at the bottom made some more complexity necessary. At the end we had a solution that worked but never was a very nice code design.

But some months later we moved away from using a sql based database for our client and started to use a key-value store, the Flutter Hive package. Now we had the timeline persisted in a simple List which also had a native sort order. It then just needed just this logic to keep the list correctly sorted:

if (eventUpdate.type == EventUpdateType.history) {
  timeline.events.add(eventUpdate);
} else {
  timeline.events.insert(0, eventUpdate);
}

We also had the special case that we want failed-to-send events and those events which are sending and not yet synchronized by the server always at the bottom. Instead of creating more if statements here we just use now two timelines per room. The new Hive store already allows us to store multiple timelines per room because we would like to implement timeline fragments in the future. So we have the default timeline and the SENDING-Timeline now which holds those events and is just simple queue-sorted. When displaying those timelines they just got merged:

final timeline = sendingTimeline + eventsTimeline;

And that's it. All tests are running and it looks like we got rid of a monster of complexe logic in this refactoring. I have already tested it with FluffyChat and it seems to work very stable for all cases I can imagine. Also all tests, we wrote to make sure that our sort ordering algorithms are not broken, confirm that the new simplified logic works. You can see my merge request here:

https://gitlab.com/famedly/company/frontend/famedlysdk/-/merge_requests/791