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.

[josephg]

Hi! Those diagrams are great! Sorry I didn't see this - github hasn't been emailing me about opened issues here for some reason. I've tweaked the settings so fingers crossed I've fixed it now.

I've moved your question from the issue tracker to the discussion board because you are not raising an issue with the diamond types project.

As to your questions:

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

Sorry, I have no idea whats going on in that diagram.

interface Item {
    data: string
    id: [string, number]
    left: [string, number]
}

The left field here is a reference to the item's parent. In all, this forms a tree like this (from Martin Kleppman's 2020 talk):

RGA also needs a sequence number - referred to as "timestamp" in the pseudocode you screenshotted.

But remember, we're talking about 2 different ideas: How RGA thinks of the world (the semantics of the algorithm) and how we implement that algorithm in fast code. RGA conceptually forms a tree. My contribution is that we can represent that tree using a list.

My blog post intentionally didn't include a complete description of RGA, as I wanted a broader audience than just people interested enough in CRDTs.

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

Yes. Imagine I place my cursor somewhere in a document and type the "a" key. I send you information about that keystroke so that you can add my "a" to your copy of the document. Without the "parent" field, how will you know where to insert that character into your copy of the document?

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

Huh? Yjs uses a different CRDT algorithm than RGA. (It uses YATA). left in YATA is semantically equivalent to the parent field in Yjs. Yjs has no seq field. RGA has no right field.