DeltaChat almost unusable for me due to out of order message delivery

Version: 1.30.0

I’m communicating with my friends using self-hosted postfix+dovecot+deltachat. When someone comes online to receive messages, they receive them in an almost random order, and then deltachat displays them in a random order:

I don’t see any options in postfix or dovecot to make sure messages are delivered in order of timestamp.

Does anyone else have a selfhosted setup and fixed this problem?

Maybe DeltaChat should just sort by sent order, and if an unread message is above already-read messages, just indicate that in the UI and have a button to jump through these?

Hello :wave:,
does this problem still occur with version 1.32 or 1.32.1?

1 Like

Hello,

A relative of mine also has this problem when I send him several messages in a row : I just sent messages 1, 2, 3, 4, 5, 6, and he received them in the exact opposite order. He uses version 1.34.1 on iphone, I use version 1.32.1.

I saw there was a thread about this topic around 2019-2020. The debate was about whether messages should be sorted by the date they were sent or the date they were received. May I suggest another option?

But first, as far as I understand, maybe I should recall the arguments against sent vs received date:

  • received date : if you sort according to received date, the order of reception can be inconsistent with the order the messages were sent (even if there is only one sender and one receiver)

  • sent date : if you sort according to sent date, a delayed message might be placed so high in your list of messages that it is out of sight.

As far as I can tell, there could be a way to avoid inconsistencies, while reducing the risk of a delayed message being placed out of sight.

Messages exchanged by Delta Chat have the usual headers “Message-ID”, “In-Reply-To” and “References”. What about using them to sort messages?

These headers define a partial order on messages : if message y has the “Message-ID” of x in its “References”, that means x must be displayed before y. This order is only partial, since it leaves ties: when two messages y and z are replies to a same message x, it does not prescribe how to order them.

It seems that using this partial order would solve the problem of inconsistent order of messages: you would never have a reply placed before a message. In other words, with the previous example, you may display message x, then y, then z or message x, then z, then y, and none of these orders is inconsistent since neither the sender of y nor the sender of z knew the other one sent (or was about to send) a message.

Now, what about the case of a discussion where a message y replies to x but, because the author of y has no network, y is delayed for a very long time, and many messages z1, z2, …, z100 are exchanged before y really reaches its recipients? The partial order over messages just says that y replies to x and that z1, …, z100 also reply to x. So there’s a tie between y and z1, …, z100. If you break the ties according to the order of reception, y will be placed after z100, so it won’t be out of sight.

Does that make sense?

As far as I can tell, implementing such an order amounts to implement Kahn’s algorithm with a slight twist: keep the set S sorted by received date and choose the first one instead of an arbitrary one.

Your

Judicaël.

1 Like

Delta Chat downloads and processes all messages in the order they are delivered to IMAP Inbox, except for a small bug that only affects partially downloaded messages with large attachments. When the device comes online and downloads a batch of messages, they are processed in this order one-by-one, on all devices.

Delta Chat treats your Inbox as a feed. Each message is downloaded and processed exactly once, then stored in the local database and is never processed or moved around the chat again. This is the basic principle of Delta Chat design. There are control messages that should never be processed twice, such as messages that change the membership of the group, group avatar, ephemeral timer setting of the chat, securejoin messages (invisible messages exchanged when you scan someone’s QR-code to verify the key) and so on. Once message is placed in the chat, it is guaranteed that it will not move around next time you open the application. New messages will only be added below it.

For each message, sorting timestamp is calculated as follows. Sender date (Date:) header is parsed and compared with the reception time. If sender date is in the future, it is replaced with the reception date. This is to avoid someone sending you a message with year 2100 on it. Then, if message is new (not marked as \Seen by your second Delta Chat device or Thunderbird or webmail client), we check that the message will not appear above any seen messages, and move its timestamp into the future if needed, so the message appears where user will notice it. So by default Delta Chat uses sender timestamp, but then corrects it with these simple rules.

The reason messages may appear in the wrong order is when messages are delivered one-by-one in the wrong order and recipient reads them one by one. Then, each next message must be stored below the seen messages, there is no chance to correct the order. If the server has problems delivering messages, postpones delivery of failed messages and tries to deliver other messages, it may reorder messages and Delta Chat cannot do much about it.

If messages are downloaded in a large batch, Delta Chat has the freedom to sort them using topological sort before processing. But in this case all these messages are unseen and the sender timestamp will be used to sort them, so additional topological sorting will change nothing unless there are multiple senders or multiple sender devices involved which have different clocks that are not synchronized properly. So I don’t see how topological sort fixes the problem, even though it may improve things in some cases.

Do you use the same or different servers? Were these messages received in one batch after being offline or slowly delivered one-by-one? Could you check the Message Info of these messages and write down their Send, Received and Hop dates? If there are multiple Hops with significantly different dates, this could mean there were delivery problems on the path that caused reshufflish.

Thanks for this detailed answer, link2txt. I am waiting for the recipient to send me the Message Info (he receives messages in the wrong order, I don’t).

You said " If sender date is in the future, it is replaced with the reception date". Do you apply this rule strictly or do you keep the sender date if it’s only a few seconds (or minutes) in the future? (A few years ago, I noticed there could be quite a discrepancy between the pool of ntp servers used by Debian, and the ntp server of my employer’s internet provider — about a few tens of seconds)

Yes, it strictly sets the timestamp to the minimum of sender date and receiver date. Normally sender date is before the receiver date. We can probably add some allowed margin, like 30 seconds or one minute, not sure if it makes things better or worse.

when fetching a batch, it makes sense to sort it before adding it to chat, that “local sorting” would solve the issue about batch of messages fetch out of order with some seconds of difference in their timestamps

Turns out there is another bug that affects not only large attachments, discussed at Partially downloaded messages are received out of order · Issue #3688 · deltachat/deltachat-core-rust · GitHub

I now suspect that order may not be preserved when messages are moved from the Inbox to DeltaChat folder. When Delta Chat detects a batch of messages in the Inbox, it first moves them all to DeltaChat folder with a single MOVE command and then downloads them. There is no guarantee in the standard that MOVE starts moving with lowest UID.