Support concurrent merge and split operations in Tree
Opened this issue · 0 comments
What would you like to be added:
Through the PRs #659 and #705, Yorkie now supports merge and split operations in Tree.
However, concurrent edits for these operations are not implemented yet.
It is necessary to support concurrent merge and split operations as a next step.
Why is this needed:
Problem
The current implementation of Tree can't support concurrent edits for merge and split operations.
This is mainly because these operations inherently involves the movement of child nodes to another parent node.
In concurrent editing situations, it becomes challenging to determine the destination or source of the child nodes solely based on the from or to in the operation.
Let's examine this with the following example.
Initial
<r><p>a</p><p>b</p></r>
Before sync
User A: Merge(Edit(2,4)) -> <r><p>ab</p></r>
User B: Delete(Edit(3,6)) -> <r><p>a</p></r>
After sync
Expected: <r><p>a</p></r>
User A Actual: <r><p>ab</p></r> <-- Text "b" stays alive
User B Actual: <r><p>a</p></r>
You can see more examples in the following PRs.
- Go-SDK: #751
- JS-SDK
Solution
One possible solution for this issue is re-ordering concurrent operations, which means that the Tree CRDT doesn't depend solely on the commutative rule between operations anymore.
To be specific, when more than one operations are considered to be concurrent by means of TimeTicketContext (a.k.a. latestCreatedAtMapByActor), it can roll back the current state to the nearest snapshot, re-order the concurrent operations, and apply them successively.
The ordering between operations should be determined by whether it preserves users' intention well in concurrent edits.
For instance, we can use Delete(Merge) > Split > Insert as the ordering for operations.
This mechanism is closely related to Tree.Move, which is described in #634.