Question about CRDTs and Reorderable Lists Implementation

[serhii-k]

Hello Daniel,

I'm new to CRDTs and need a solution for reorderable lists. I've come across several complex algorithms like RGA and its modifications. However, when I reviewed your solution, it appeared to be relatively simple. That said, I noticed an issue with how positions are implemented, and I wanted to ask if it's a critical problem or not a major concern.

Let's start with two instances, both online.

Step 1. Create a new list with 3 tasks:
Task 1
Task 2
Task 3
Ensure that these tasks are synced across both devices.

Step 2. Set the second device to Offline.

Step 3. On the first device, move Task 1 to the bottom of the list:
Task 2
Task 3
Task 1

Step 4. On the second (offline) device, move Task 2 to the bottom of the list:
Task 1
Task 3
Task 2

Step 5. Bring the second device back online.

Both devices converge to this order:
Task 3
Task 1
Task 2

However, if we inspect the Postgres todos table, we see the following:
Task 1 position=2
Task 2 position=2
Task 3 position=1

I'm concerned about what might happen if we had more elements in the list, and the devices stayed offline for longer periods. What's your take on this? Do you think this implementation of reorderable lists is reliable for production use, or is it just for demo purposes?

[cachapa]

This is rather a discussion about the design decisions made for the tudo app rather than CRDTs in general, but it's interesting to debate here anyway.

This is the code that updates the list order - it is run every time the user reorders any item:

  Future<void> setItemOrder(List<ToDo> items) async {
    await _crdt.transaction((txn) async {
      for (int i = 0; i < items.length; i++) {
        final item = items[i];
        if (item.position != i) {
          await txn.execute('''
            UPDATE todos SET position = ?1
            WHERE id = ?2
          ''', [i, item.id]);
        }
      }
    });

Essentially it checks for each item whether its internal position matches the to-do list's order, and updates it accordingly skipping unchanged items.

This can lead to edge cases like the one you identified where the order is no longer valid. Another such case is when you modify the order after deleting or marking an item as done. Done and deleted items are not reordered, which also leads to duplicated order positions when restored to the to-do list.

There are complex ordering algorithms that try to avoid such cases, or try to minimize the number of database changes. I deemed all of those too complex for a small to-do app, but if you might want to look into them if your requirements are different.

[cachapa]

There's another edge case which is caused by the fact that the item's position is stored in the item itself: updating the position will trigger a complete record update which can "reset" changes made by other users. For example:

1. User 1 creates entry "A"
2. User 1 goes offline
3. User 2 edits entry "A" -> "B"
4. User 1 changes entry position
5. User 1 comes back online

Because the latest update is from User 1, its position change will cause the name to be reset to "A".

To fix this you could just create a new table for the positions, something like (list_id, item_id, position), but again I didn't think it was worth the extra complexity for tudo.

[serhii-k]

Hello Daniel,

Thank you very much for your clarifications, and especially for the warning regarding the case where changing the position might overwrite changes made by other users. The positions should definitely be stored in a separate table.

I've decided to stick with the solution you implemented for tudo, mainly because of its absolute simplicity. In the event that some positions become duplicated (until a subsequent move is initiated by a user), I believe it would be sufficient to simply ORDER BY position and id (or hlc). This way, we can still maintain consistent ordering on the clients.