Crate crdt_tree

Implements Tree Conflict-Free Replicated Data Type (CRDT).

For usage/examples, see: examples/demo.rs tests/tree.rs

This code aims to be an accurate implementation of the tree crdt described in:

“A highly-available move operation for replicated trees and distributed filesystems” [1] by Martin Klepmann, et al.

[1] https://martin.kleppmann.com/papers/move-op.pdf

For clarity, data structures in this implementation are named the same as in the paper (State, Tree) or close to (OpMove –> Move, LogOpMove –> LogOp). Some are not explicitly named in the paper, such as TreeId, TreeMeta, TreeNode, Clock.

Structs

Clock

Implements a Lamport Clock consisting of an Actor and an integer counter.

LogOpMove

Implements LogOpMove, a log entry used by State

OpMove

Implements OpMove, the only way to manipulate tree data.

State

Holds Tree CRDT state and implements the core algorithm.

Tree

Implements Tree, a set of triples representing current tree structure.

TreeNode

TreeNode is a node that is stored in a Tree.

TreeReplica

TreeReplica holds tree State plus lamport timestamp (actor + counter)

Traits

TreeId

TreeId trait. TreeId are unique identifiers for each node in a tree.

TreeMeta

TreeMeta represent the app-defined data that an application stores in each node of the tree.