Save all received messages to DB even if duplicate ID is used

[jubalh]

This is to track a discussion that we had in the MUC and via PM.

Most of the things were already mentioned in

• Improve logging of DB message insertion #1893 (comment)
• Improve logging of DB message insertion #1893 (comment)

So I believe what needs to be done is:

• Save all messages even with duplicate IDs in DB (don't require to be unique)
• If the server generated stanza-id from XEP-0359: Unique and Stable Stanza IDs is not unique then we use log_warn and print it to console
• With things like Last Message Correction we just use the newest/latest message with that ID

It still would be valuable to find out what other clients do in this case and write it here on the issue.

Issue will most likely be worked on by @H3rnand3zzz (only can assign you after commented on this thread).

[H3rnand3zzz]

The Short Stanza-ID Problem (Unreliable History in DB)

Abstract

Reports of unreliable message history in the database led to a diagnostic commit (#1893), which helped users to provide additional data on the issue. The data proved that the problem is in fact in the short stanza-ids produced by some non-compliant clients and have a form of short letter-number combination, such as "ab20a", "a13baa". Most of the related things were discussed and described at #1893, so I won't provide repetitive details here. Here I provide a potential solution as well as a discussion on the topic.

DB Structure

Table: ChatLogs

Note ID, stanza_id (stanza-id), replace_id (replace-id)

• id (INTEGER PRIMARY KEY AUTOINCREMENT): The unique ID of the DB entry.
• stanza_id (TEXT): The ID in the <message> stanza.
• replace_id (TEXT): The ID from XEP-0308: Last Message Correction.
• from_jid (TEXT NOT NULL): The sender's JID (Jabber Identifier).
• to_jid (TEXT NOT NULL): The receiver's JID.
• from_resource (TEXT): The sender's resource (if available).
• to_resource (TEXT): The receiver's resource (if available).
• message (TEXT): The message text.
• timestamp (TEXT): The timestamp of the message, formatted as "2020/03/24 11:12:14".
• type (TEXT): Used to distinguish the type of message, such as "message" (chat), "MUC message" (muc), or "muc pm" (mucpm).
• archive_id (TEXT): The stanza-id from XEP-0359, used for XEP-0313: Message Archive Management.
• encryption (TEXT): Used to distinguish the encryption type, such as "none," "omemo," "otr," or "pgp".
• marked_read (INTEGER): A flag (0 or 1) indicating whether a message has been marked as read via XEP-0333: Chat Markers.

Visualization

```c
// src/database.c:260
auto_sqlite gchar* query = sqlite3_mprintf("SELECT * FROM ("
                                           "SELECT COALESCE(B.`message`, A.`message`) AS message, "
                                           "A.`timestamp`, A.`from_jid`, A.`type`, A.`encryption` FROM `ChatLogs` AS A "
                                           "LEFT JOIN `ChatLogs` AS B ON (A.`stanza_id` = B.`replace_id` AND A.`from_jid` = B.`from_jid`) "
                                           "WHERE A.`replace_id` = '' "
                                           "AND ((A.`from_jid` = '%q' AND A.`to_jid` = '%q') OR (A.`from_jid` = '%q' AND A.`to_jid` = '%q')) "
                                           "AND A.`timestamp` < '%q' "
                                           "AND (%Q IS NULL OR A.`timestamp` > %Q) "
                                           "ORDER BY A.`timestamp` %s LIMIT %d) "
                                           "ORDER BY `timestamp` %s;",
                                           contact_barejid, myjid->barejid, myjid->barejid, contact_barejid, end_date_fmt, start_time, start_time, sort1, MESSAGES_TO_RETRIEVE, sort2);
```
To display messages for user (by retrieving history), we are getting all the messages within the time frame and limited by some value, by at the same time replacing by joining original message with messages which `replace_id` = original message's `stanza_id` (also we check the sender since #1898).

The Case

We have 2 messages from the same (or different) senders at different points in time. Both of them are replaced, but both of them have the same stanza-ID. It might be a tough edge case, but that's the point of a good design: to withstand harsh conditions.

ID	stanza_id	replace_id	message
0	aa	NULL	Hlo
1	xx	aa	Hello
2	aa	NULL	Hw re you
3	yy	aa	How are you?

the end result of the visualization should be

Hello
How are you?

Wrong Approaches

1. Naive
   We can just let usage of non-unique stanza IDs, what can go wrong?
   With the current implementation of visualization, we will get this result:

   How are you?
   How are you?
   

   Because we are replacing messages if we can find that they have "replace_id" counterparts in the DB.

2. Naive-2 (just replace the last one)
   Through some heavy manipulation on the SQL query we can achieve replacement of the last message only with the last corrected code. It's going to fail the case:

   Hlo
   How are you?
   

   Which is not a desired output. And to achieve the desired output, we have no way of learning to which message correction messages are assigned to. It can be 2 correction messages for the last message or 2 correction messages for the first one, just in the case above. Not to mention other cases. 2 or more correction for the message are allowed by the standard A single message may be corrected multiple times by subsequent edits.. So we have no way of learning in the case of non-unique stanza ids which message and how should we correct.

Proposed solution

To address unreliable message history caused by non-unique stanza-ids, I propose introducation of a new column: replaces_db_id. This column points to the original message in the database that particular message replaces and uses (UNIQUE) DB ID instead of (NOT UNIQUE ANYMORE) stanza-id for it.

So, for short,
replace_id -> (NON UNIQUE) stanza_id
replaces_db_id -> (UNIQUE) ID

This way unnecessary complexity of other potential (and sometimes even working) solutions might be avoided, as we can preserve unique identifier to which we can rely upon. The replace_id column might be kept for compatibility, debug and other purposes, but it will lose initial value as an unique identifier.

ID	stanza_id	replace_id	replaces_db_id	message
0	aa	NULL	NULL	Hlo
1	xx	aa	0	Hello
2	aa	NULL	NULL	Hw re you
3	yy	aa	2	How are you?

As you can see here, we can handle variety of cases with multiple replacements, non-unique stanza-ids, but maintain all the functionality (LMC).

Conclusion

The problem provides a challenge, but with a minor DB redesign, it's possible to solve it in a sustainable and well-suited manner.

[jubalh]

Detailed report :)

It might be that one of us is misunderstanding something.

I don't see the value of replaces_db_id.
When we get an LMC message from the server it contains the ID that it should replace. It does not contain your self created replaces_db_id. So I don't see how you want to associate the LMC message with the correct previously received message. Basically the problem will stay the same. Because you will have several messages in the database with the same ID. And some of them will have an internal replaces_db_id. But then you still don't know WHICH of those to replace because the sender couldn't inform you about that.

Even if that would work then you wouldn't need replaces_db_id to have an unique idientifier you could just use the DB ID field, right?

The abstract of XEP-0308 sais: This specification defines a method for indicating that a message is a correction of the last sent message..

So what I believe is the correct behaviour is to replace the newest message with the specified ID as mentioned in #1893 (comment) a week ago :)

And as mentioned above (and in the 1893 PR) it would be interesting to check what Dino, Conversations, Gajim are doing. My guess is that they will do exactly that.

[H3rnand3zzz]

I don't see the value of replaces_db_id. When we get an LMC message from the server it contains the ID that it should replace. It does not contain your self created replaces_db_id. So I don't see how you want to associate the LMC message with the correct previously received message. Basically the problem will stay the same. Because you will have several messages in the database with the same ID. And some of them will have an internal replaces_db_id. But then you still don't know WHICH of those to replace because the sender couldn't inform you about that.

The server should find the last record with that particular stanza-id and user in the DB, in the absence of which replacement considered incorrect (no message to replace) -- that's the association part. "Because you will have several messages in the database with the same ID", that would be different, because if I to correct the second part again, it would correct the second part only and vice versa, as we choose only the last correction message.

ID	stanza_id	replace_id	replaces_db_id	message
0	aa	NULL	NULL	Hlo
1	xx	aa	0	Hello
2	aa	NULL	NULL	Hw re you
3	yy	aa	2	How are you
4	zz	aa	2	How are you?

1st replacement: "Hlo" -> "Hello" (impossible to do by relying purely on stanza_id)
2nd replacement: "Hw re you" -> "How are you?" (since we use only the latest replacement with the same DB ID)
Result is unachievable with purse usage of the replace_id

Even if that would work then you wouldn't need replaces_db_id to have an unique idientifier you could just use the DB ID field, right?

It does not work in the aforementioned case since we can't track which change affects which message.

The abstract of XEP-0308 sais: This specification defines a method for indicating that a message is a correction of the last sent message..

So what I believe is the correct behaviour is to replace the newest message with the specified ID as mentioned in #1893 (comment) a week ago :)

See naive-2. The problem with that would be that old messages are going to stay uncorrected and also that correction might apply to a new messages (though today I get an idea of workaround for preventing replacement of new messages by checking that replacement message's db id > db id of original, but it won't prevent replacing of older message and would require even worse SQL request than we have now). So to check that the replacement is historically inbound, we have to select next message with the same id and make sure that the replacement is applied to the Nth "original message", which is too complicated for one SQL query, hard to debug, bad for performance.

And as mentioned above (and in the 1893 PR) it would be interesting to check what Dino, Conversations, Gajim are doing. My guess is that they will do exactly that.

Ok, I can check them and add it do my report, though I guess that no one has a little sophisticated, but powerful system that was proposed.

[jubalh]

1st replacement: "Hlo" -> "Hello" (impossible to do by relying purely on stanza_id)

But that is how XEP-0308 works. Last message correction.

And I still didn't see how your replaces_db_id works. This ID will only be in our local database. How does it have any relation to the message we get/correct?

I hope somebody else can comment here since we seem to don't understand each other on this topic.

[H3rnand3zzz]

Additional overview (with code examples) of the potential solutions

Requirements for the solution

1. Solution MUST be performant. The current implementation searches an unindexed column in the query, causing excessive load. Conditions in SELECT and JOIN clauses MUST use indexed columns or be avoided altogether.
2. stanza_id MUST NOT be trusted as an unique identifier.
3. All correction MUST be applied in the order that they were introduced or not applied at all and instead displayed as a plain messages (in accordance with the XEP).
4. In case of subsequent edits, solution MUST adhere to the standard

If the same message is to be corrected several times, the id of the original message is used in each case (e.g. If a message of id 1 is corrected by a message of id 2, a subsequent correction should correct 1, not 2).

5. All correction messages SHOULD be saved.

replace_db_id concept

As we can have many messages with the same stanza ID sent at different times, we can have correction messages to them applied at different times as well. There is barely any good way to track the changes accordingly with just the stanza_id and replace_id columns, since none of them are unique.

ID	stanza_id	replace_id	message
0	aa	NULL	Hlo
1	xx	aa	Hello
2	aa	NULL	Hw re you
3	yy	aa	How are you
4	zz	aa	How are you?

In this example if rely only upon those 2 we can either replace both messages, replace the last message with the last edit (though it's going to be hard to even make this SQL query not to mention performance of it will violate the first condition).

If we additionally would use ID for this purpose, we can potentially track some bounds in which correction can be applied (but we should priorly find all the "neighbouring" stanzas (rows with the same stanza_id) and then set them as boundaries).

What I offer is to add an additional column replaces_db_id which would track to which exact message's (by DB ID) the change should be applied.

ID	stanza_id	replace_id	replaces_db_id	message
0	aa	NULL	NULL	Hlo
1	xx	aa	0	Hello
2	aa	NULL	NULL	Hw re you
3	yy	aa	2	How are you
4	zz	aa	2	How are you?

On insert we already do the following:

    if (message->replace_id) {
        auto_sqlite char* replace_check_query = sqlite3_mprintf("SELECT `from_jid` FROM `ChatLogs` WHERE `stanza_id` = '%q'",
                                                                message->replace_id ? message->replace_id : "");

to ensure integrity of the message's sender.

But what we can do instead is this:

    if (message->replace_id) {
        auto_sqlite char* original_message_query = sqlite3_mprintf("SELECT `id` FROM `ChatLogs` WHERE `stanza_id` = '%q' AND `from_jid` = '%q' AND `replace_db_id` = NULL ORDER BY `id` DESC",
                                                                message->replace_id ? message->replace_id : "",
                                                                from_jid->barejid ? from_jid->barejid : "");

This way we can always find the original message and at the same time check integrity of the message's sender.
I offer to do a mental exercise and go one by one in the example table above so you can see how the ID of the exactly previous (at the point of insertion) "original" message is selected (don't forget the condition in C before the query). You can skip the from_jid condition as it's out of scope of the problem and is needed only for integrity check. As you can see, it will be kept exactly at the appropriate message at the time.

Visualization for the selection would be about the same, but we would use instead of replace_id, replace_db_id. Dixi.

Gajim's way

Gajim offers us a different view and approach on the problem. It's much more performant than other solutions and rely on different mechanisms.

It replaces the message in the DB, but leaves original message in the additional_data column stored in JSON, hence it's possible to restore the original message, though it would require us to lose correction metadata (time, stanza_id) or include it in the JSON, which can grow to the questionable sizes, especially in the case of big messages (though it's not often the case). Anyway, on the most important part (data visualization) it's the most performant solution as it does not require any JOINs. The solution for me looks the most appealing due to its performance.

[ike08]

Off topic: The third correction's replace-id will be the second correction's message-id, not the first message-id.

ID	stanza_id	replace_id	replaces_db_id	message
2	aa	NULL	NULL	Hw re you
3	yy	aa	2	How are you
4	zz	aa <-- should be yy	2	How are you?

On topic: You shouldn't need replace_db_id. You can select the right message by querying for the most recent message-id and sender-jid match.

Reasoning: Querying for sender-jid will solve the case where there are two messages with the same message-id sent from different jids. As for the case where there are two messages with the same message-id sent from the same jid, replace the most recent one.

my two cents.

[H3rnand3zzz]

Off topic: The third correction's replace-id will be the second correction's message-id, not the first message-id.
ID stanza_id replace_id replaces_db_id message
2 aa NULL NULL Hw re you
3 yy aa 2 How are you
4 zz aa <-- should be yy 2 How are you?

If the same message is to be corrected several times, the id of the original message is used in each case (e.g. If a message of id 1 is corrected by a message of id 2, a subsequent correction should correct 1, not 2). According to XEP.

On topic: You shouldn't need replace_db_id. You can select the right message by querying for the most recent message-id and sender-jid match.

Reasoning: Querying for sender-jid will solve the case where there are two messages with the same message-id sent from different jids. As for the case where there are two messages with the same message-id sent from the same jid, replace the most recent one.

The problem arises from the fact that some senders send non-unique stanza-ids, which was described at the PR and here as well. The sender's integrity check is already present.

Replacing the most recent one represents a challenge as well, since we need to find which one is the most recent one and for older ones, we should show them "as is", hence the SQL query gets less performant, not to mention that it will be less than perfect solution, especially in case if correction was important (e.g. there was a typo in IBAN), as we can't (and don't have to) enforce users not to use corrections for important changes and in the end it would violate corrected message storage integrity.

[jubalh]

If the same message is to be corrected several times, the id of the original message is used in each case (e.g. If a message of id 1 is corrected by a message of id 2, a subsequent correction should correct 1, not 2).

Ah! So:

<message to='[email protected]/balcony' id='bad1'>
  <body>Helo</body>
</message>

We display the message and save it to DB.

<message to='[email protected]/balcony' id='good1'>
  <body>Hell</body>
  <replace id='bad1' xmlns='urn:xmpp:message-correct:0'/>
</message>

We save the message to DB. We look for the message with the id bad1 in the UI and replace it.

<message to='[email protected]/balcony' id='good2'>
  <body>Hello!</body>
  <replace id='bad1' xmlns='urn:xmpp:message-correct:0'/>
</message>

We save the message to DB. We look for message with id bad1 and can't find it because it got replaced by our first correction which has the ID good1.

So that's why you want to save replaces_db_id. To always save the ID of the original ID that we want to replace!
Why didn't you say so ;)

So that would mean that we need a new field in the db and in the ProfMessage struct?

Will need to think a bit more about it and and consider Gajim solution. Did you also check other clients btw?

[jubalh]

@Ppjet6 do you remember what approach you are taking?

[H3rnand3zzz]

If the same message is to be corrected several times, the id of the original message is used in each case (e.g. If a message of id 1 is corrected by a message of id 2, a subsequent correction should correct 1, not 2).

Ah! So:

<message to='[email protected]/balcony' id='bad1'>
  <body>Helo</body>
</message>

We display the message and save it to DB.

<message to='[email protected]/balcony' id='good1'>
  <body>Hell</body>
  <replace id='bad1' xmlns='urn:xmpp:message-correct:0'/>
</message>

We save the message to DB. We look for the message with the id bad1 in the UI and replace it.

<message to='[email protected]/balcony' id='good2'>
  <body>Hello!</body>
  <replace id='bad1' xmlns='urn:xmpp:message-correct:0'/>
</message>

We save the message to DB. We look for message with id bad1 and can't find it because it got replaced by our first correction which has the ID good1.

So that's why you want to save replaces_db_id. To always save the ID of the original ID that we want to replace! Why didn't you say so ;)

So that would mean that we need a new field in the db and in the ProfMessage struct?

Will need to think a bit more about it and and consider Gajim solution. Did you also check other clients btw?

It's rather to keep the message history coherent. We don't touch the original message, but the original message is different at different point in time. It's hard to calculate it dynamically. E.g. today I write to you my IBAN (stanza-id=aa) "122345", I make a mistake there, so I replace it with "12345", tomorrow I write you "Hell" (stanza-id=aa), I fix it with "Hello". But when we are visualizing data, how do we know that we should replace 122345 with "12345" and not "Hello" and that we should replace "Hell" with "Hello" and not "12345" if the message ID is the same? Especially it's problematic when we have multiple edits over the stanza that we meet multiple times. And I've shown that all the originals are getting replace either by last replacement or first replacement, which is wrong. Each message should have its own replacement, but to do that in SQL we either have to calculate every time which replacement applying to which message (it would require additional selects and let's directly forget about it) or use something reliable and unique to know which exact message should be replaced with what. Also we will use replacement dynamically and internally, to initially assign the replacement, we check the latest "original" message (yesterday - IBAN, today - Hell, tomorrow - anything else or maybe still Hell).

But let's focus on the Gajim approach as I like it the most (due to performance gain). In the next few hours I am going to explain their approach, why is it good and how can we implement it (a few ways).

[H3rnand3zzz]

Lol, we forgot to close it @jubalh