(2023-09-02) Cola A Text Crdt For Realtime Collaborative Editing
Riccardo Mazzarini's GitHub profile Riccardo Mazzarini on cola: a text CRDT for real-time collaborative editing. In this blog post I’ll talk about the theoretical background and the technical implementation of cola, a text CRDT for real-time collaborative editing written in Rust. Reading this is not at all necessary to be able to use cola, so if that’s all you’re interested in you can safely skip this post and go straight to the documentation
First part: Intro to text CRDTs
The only assumption we make on the network layer is that every edit is received by all the peers in the network. Edits can be sent multiple times and in any order, but they must eventually reach all the peers.
Anchors in a sea of text
offsets depend on the state of the document at the time an edit was made. We can’t just exchange offsets without also exchanging the context they depend on.
With insertions out of the way let’s now focus on deletions.
Second part: cola’s implementation
RLE all the things
A better alternative: B-trees
An even better alternative: G-trees
I couldn’t find any established name for this kind of tree-in-a-vector data structure, so I’ve been calling it a G-tree, short for grow-only tree.
Anchors to Leaves
Third part: Benchmarks