Get ready to be blown away by an elegant CRDT design that is a game-changer for text collaboration applications. In this article, we’ll take a deep dive into Causal Trees and get a refresher on some important distributed systems concepts.
CRDTs are a family of algorithms and datastructures that guarantee eventual consistency by following simple mathematical properties. These have become increasingly popular and are commonly found in collaborative applications, local network, and peer-to-peer environments. What’s really exciting is that CRDTs don’t require a central authority to reconcile inconsistencies, making them a revolutionary alternative to complicated processes like consensus. Just check out how widely used CRDTs are by big names like Figma, Soundcloud, and many others.
The star of the show today is the Causal Tree, as discovered by Victor Grishchenko. We’ll examine this CRDT in the context of a simple text collaboration application. But before we get into the nitty-gritty, take a moment to play around with the example below. Watch out for the unique ids associated with each node and see how the algorithm responds when characters are deleted.
Example 1
In the example above, each client has their own local causal tree, and the compiled value is displayed in their respective text inputs. The implementation we’ll be discussing is a state-based CRDT, or CvRDT, which means that the entire tree is sent to clients instead of individual operations as they occur. As a client types, new nodes are added to their tree and sent to interested peers. When a client receives another client’s tree, they merge it with their own tree to guarantee a consistent result. Think of the merge operation like a set join – the order doesn’t matter, the result will always be the same.
Tree structure
In our example, each node represents an individual character, with the parent being the letter directly preceding it. This is one way we can position nodes consistently, unlike other structures where characters have an array index position.
