Question: some question about 《5000x faster CRDTs: An Adventure in Optimization》

[DiamondYuan]

Hello, I am learning CRDT recently and trying to implement my own crdt。After reading your article, I have a few doubts.

1. Why do I think RGA in the paper looks more like yjs rather than automerge? Did I misunderstand ？

interface Item {
    data: string
    /**
     * [agentId, sequence]
     */
    id: [string, number]
    /**
     * [agentId, sequence]
     */
    left: [string, number]
}

more like a list of Item (order by id)?

2. If only need to implement plain text, is it necessary to record the parent field?

Yjs just puts all the items in a single flat list:

state = [
  { item: 'a', id: ['seph', 0], seq: 0, parent: null },
  { item: 'X', id, seq, parent: ['seph', 0] },
  { item: 'b', id, seq, parent: ['seph', 0] },
  { item: 'c', id, seq, parent: [..] }
]

Just need item and id and 'left` to implement the plain text crdt ? or parent and right are equivalent ?

const state = [
    {
        "item": "a",
        id: ['a', 0]
    },
    {
        "item": "x",
        id: ['b', 0],
        left: ['a', 0]
    },
    {
        "item": "b",
        id: ['a', 1],
        left: ['a', 0]
    },
    {
        "item": "c",
        id: ['a', 2],
        left: ['a', 1]
    }
]

[zxch3n]

For Q1

I'm confused by this one too. But I guess Joseph just skipped the concrete detail for simplicity.

As illustrated in the original RGA paper, the data structure is

which is a linked list with some optimizations already.

And Automerge's paper did not mention the recursive structure as well. So I guess it's just Automerge's implementation decision, which was not described in the paper.

For Q2

The parent in the field plays the same role as the left in your description. It's not used to construct a hierarchical structure. With item, id, and left it should be sufficient for you to build an array CRDT.