(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

Linkin Blocks

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

I’ve benchmarked cola against 3 other CRDTs implemented in Rust: diamond-types, automerge and yrs.