This is a pretty good description of RGA (Replicated Growable Array). Which is a list & text CRDT that works pretty well in practice. Automerge used to use this algorithm for text editing, before moving across to FugueMax.
This algorithm has another obscure downside: It has interleaving problems if you insert items backwards. If two users do a series of inserts in reverse order, their inserts will get interleaved in a weird, unpredictable way. Eg, if I type "aaaaa" (as a series of prepended inserts) and you type "bbbb" in the same way, we can end up with "ababababa" or "aabbabbaa" some combination like that. We generally want CRDTs to be non-interleaving - so, "aaaaabbbb" or "bbbbaaaaa" should be the only possible results.
This problem is fixed by FugueMax, described in "The Art of the Fugue" paper[1]. If you're thinking of implementing a text CRDT, I recommend starting there. Fuguemax is a tiny change from RGA. We swap out the sequence numbers for a "right parent" pointer and the problem goes away. Coincidentally, the algorithm is also a 1 line change away from Yjs's CRDT algorithm.
And its really not that complicated. Most of the complexity in the fuguemax paper comes about because - like with RGA - they describe the algorithm in terms of inserts into a tree. If you ask me, this is a mistake. The algorithm is simpler if you primarily think of it as inserts into a list. (Thanks Kevin Jahns for this insight!) I programmed Fuguemax up live on camera a few months ago like this. You can fit a simple reference implementation of fuguemax in ~200 lines of code[2]. (The video is linked from the readme in that repository. In the video I explain the algorithm and all the code along the way).
The big benefit of eg-walker is that you don't need to load any history from disk to be able to do collaborative editing. There's no need to keep around and load the whole history of a document to be able to merge changes and send edits to other peers. Its also much faster in most editing situations - though modern optimizations mean text based CRDTs are crazy fast now anyway.
The downside is that eg-walker is more complex to implement. Compare - this "from scratch" traditional CRDT implementation of FugueMax:
Eg-walker takes about twice as much code. In this case, ~600 lines instead of 300. Its more complex, but its not crazy. It also embeds a traditional CRDT inside the algorithm. If you want to understand eg-walker, you should start with fuguemax anyway.
Wow. Didnt know there were these CRDT examples for mere mortals. I supppose once you put Rust in the mix the heads start to explode, mine included. Cool!
This is a pretty good description of RGA (Replicated Growable Array). Which is a list & text CRDT that works pretty well in practice. Automerge used to use this algorithm for text editing, before moving across to FugueMax.
This algorithm has another obscure downside: It has interleaving problems if you insert items backwards. If two users do a series of inserts in reverse order, their inserts will get interleaved in a weird, unpredictable way. Eg, if I type "aaaaa" (as a series of prepended inserts) and you type "bbbb" in the same way, we can end up with "ababababa" or "aabbabbaa" some combination like that. We generally want CRDTs to be non-interleaving - so, "aaaaabbbb" or "bbbbaaaaa" should be the only possible results.
This problem is fixed by FugueMax, described in "The Art of the Fugue" paper[1]. If you're thinking of implementing a text CRDT, I recommend starting there. Fuguemax is a tiny change from RGA. We swap out the sequence numbers for a "right parent" pointer and the problem goes away. Coincidentally, the algorithm is also a 1 line change away from Yjs's CRDT algorithm.
And its really not that complicated. Most of the complexity in the fuguemax paper comes about because - like with RGA - they describe the algorithm in terms of inserts into a tree. If you ask me, this is a mistake. The algorithm is simpler if you primarily think of it as inserts into a list. (Thanks Kevin Jahns for this insight!) I programmed Fuguemax up live on camera a few months ago like this. You can fit a simple reference implementation of fuguemax in ~200 lines of code[2]. (The video is linked from the readme in that repository. In the video I explain the algorithm and all the code along the way).
[1] https://arxiv.org/abs/2305.00583
[2] https://github.com/josephg/crdt-from-scratch/blob/master/crd...
Big fan of Automerge and other CRDTs. What are your thoughts on Eg-Walker?
https://loro.dev/docs/concepts/event_graph_walker
I invented it, so personally I like it very much.
The big benefit of eg-walker is that you don't need to load any history from disk to be able to do collaborative editing. There's no need to keep around and load the whole history of a document to be able to merge changes and send edits to other peers. Its also much faster in most editing situations - though modern optimizations mean text based CRDTs are crazy fast now anyway.
The downside is that eg-walker is more complex to implement. Compare - this "from scratch" traditional CRDT implementation of FugueMax:
https://github.com/josephg/crdt-from-scratch/blob/master/crd...
With the same ordering algorithm implemented on top of egwalker:
https://github.com/josephg/egwalker-from-scratch/blob/master...
Eg-walker takes about twice as much code. In this case, ~600 lines instead of 300. Its more complex, but its not crazy. It also embeds a traditional CRDT inside the algorithm. If you want to understand eg-walker, you should start with fuguemax anyway.
Haha if the author note had been at the bottom, I think this would have been even funnier!
Wow. Didnt know there were these CRDT examples for mere mortals. I supppose once you put Rust in the mix the heads start to explode, mine included. Cool!
(2024)