Roadmap for Array

[cloneot]

What would you like to be added:

• Presenting a roadmap focused on SetByIndex Operations for Yorkie Array data structure.

Why is this needed:

• Present current issues and direction of changes needed.
• Provide a roadmap for futre contributors to understand the context and continue the work.

The table of contents is as follows:

• Current Issues
• Roadmap for Resolving Issues

Current Issues

1. Support other types in json array

Currently, Json array support only integer type for Insert and SetByIndex operation (InsertIntegerAfter, SetInteger).
It have to support other types. Particularly, SetObject will be useful to tldraw. tldraw uses Object with string id.

2. SetByIndex operation is incomplete

Currently, GC logic has not been implemented in the SetByIndex operation. GC methods such as root.RegisterRemovedElementPair are implemented based on createdAt, so the old element and the new element cannot be distinguished.

3. Array operation does not converge in some cases (#985)

Currently, array operations does not ensure convergence. We have to ensure convergence between array operations.
You can test in local by running go test -tags integration -race -run ^TestArrayConcurrencyTable$ ./test/integration -v.
Let we think convergence without move operation at first, because convergence of move operation is hard (#987).

a. Convergence without Move operation (Insert, Set, Remove)

• i) Insert.Prev.Next == Set.Target
  • initial: [1, 2, 3, 4]
  • client A: insert 5 after 1 [1, 5, 2, 3, 4]
  • client B: set 2 to 6 [1, 6, 3, 4]
  • result: [1, 5, 6, 3, 4] or [1, 6, 5, 3, 4]
• ii) Remove.Target == Set.Target
  • initial: [1, 2, 3, 4]
  • client A: remove 2 [1, 3, 4]
  • client B: set 2 to 6 [1, 6, 3, 4]
  • result: [1, 6, 3, 4] or [1, 3, 4]

b. Convergence with Move operation (Insert, Set, Remove, Move)

• iii) Move.Target == Set.Target
  • initial: [1, 2, 3, 4]
  • client A: move 2 after 3 [1, 3, 2, 4]
  • client B: set 2 to 6 [1, 6, 3, 4]
  • result: [1, 3, 6, 4] or [1, 6, 3, 4]
• iv) Move.Prev.Next == Set.Target (note: different crdt metadata from (iii))
  • initial: [1, 2, 3, 4]
  • client A: move 3 after 1 [1, 3, 2, 4]
  • client B: set 2 to 6 [1, 6, 3, 4]
  • result: [1, 3, 6, 4] or [1, 6, 3, 4]
• v) Move.Target == Insert.Prev
  • initial: [1, 2, 3, 4]
  • client A: move 2 after 3 [1, 3, 2, 4]
  • client B: insert 6 after 2 [1, 2, 6, 3, 4]
  • result: [1, 3, 2, 6, 4] or [1, 6, 3, 2, 4]
• vi) Move.Target == Move.Prev
  • initial: [1, 2, 3, 4]
  • client A: move 2 after 3 [1, 3, 2, 4]
  • client B: move 4 after 2 [1, 2, 4, 3]
  • result: [1, 3, 2, 4] or [1, 4, 3, 2]

4. Array concurrency tests are not sufficient

Array concurrent tests are added in #985. But it compares only content of document, not crdt metadata like movedAt, removedAt. Disagreement of metadata will be potentially result in divergence. It has to be checked as well.

I cannot be sure if #985 cover all scenario. Bruteforce testing might be needed for all possible cases.

Roadmap for Resolving Issues

• 1. Support other types in json array Insert and SetByIndex operations
  • Insert
  • SetByIndex
• 2. SetByIndex operation is incomplete
  • add GC logic
  • add GC tests
• 4. Array concurrency tests are not sufficient
  • metadata comparison
  • bruteforce tests

Introduce UpdatedAt() and SetUpdatedAt() method in Element interface (3-a-i, 3-b-iii, 3-b-iv)

Currently, SetByIndex operation uses movedAt as updatedAt. But, movedAt is used in PositionedAt(), it results in divergence between SetByIndex and positional operations (insert, move). We have to distinguish movedAt with updatedAt.

Introduce RemovedAt() and SetRemovedAt() method in Element interface (3-a-ii)

Currently, SetByIndex operation does not copy removedAt, it results in divergence.
For copying removedAt from old element to new element, SetRemovedAt() method is needed.

• 3-a. Convergence between array operations without move.

Introduce OPSet or REG structure for re-execution to achieve convergence (3-b-v, 3-b-vi) (#987)

Move operations do not satisfy commutativity, so we have to store operations for re-execution scenario.

• 3-b. Convergence between array operations with move.

additional notes:

• If converge of move is dropped, we can use movedAt as updatedAt in set by index operation. In this scenario, we can resolve 3-a-i by updating PositionedAt() to CreatedAt() in findNextBeforeExecutedAt method without structural changes.