CRDT: Mutable Tree Hierarchy

← Back to the algorithm list Published on November 18th, 2022

Collaborative peer-to-peer applications may need to arrange data in a mutable tree structure that allows reparenting. For example, a peer-to-peer document storage system might need to sync an arbitrarily-nested directory structure. The algorithm presented here is one way to do this. It comes from a family of algorithms called CRDTs, which I will not describe here. Unlike my original article about this technique, the algorithm presented here does not require a central server, and works in true peer-to-peer scenarios.

The algorithm:

You can use any conflict-resolution strategy for syncing the entries of the per-node parent pointer maps to other peers, as long as editing two different entries for the same map on the same node are not considered a conflict. The demo below assigns a timestamp to each write of an entry in a map and uses last-writer-wins to resolve conflicts, with the identifier of the peer that originally did the write as a tie-breaker.

Below is a demo of what this looks like in practice. Each quadrant represents a peer, and peers send messages to each other with a simulated network delay. Drag a child node to another parent node to reparent it. Click Undo or Redo for a given peer to rewind or playback that peer's local edits. Temporarily disable the simulated network with the pause button to construct simultaneous editing scenarios. You can use your browser's "view source" feature to view the source code for this demo:

Note that this algorithm does not affect the order of children within a parent. This order may not matter for some applications. If this order is important, then this CRDT can be combined with another CRDT for ordered sequences such as fractional indexing or tree-based indexing. It's likely best to store the information for this second CRDT in the value for the edge map for this CRDT along with the counter so that the information about which parent the node has and where in that parent's children the node lives is always updated together atomically.

This technique has the following benefits and drawbacks: