MovableTree
A replicated tree that supports concurrent move/reparent operations without ever producing a cycle.
The algorithm
Every move (and addNode, which is sugar for "move a fresh node under a parent") is recorded as a MoveOp stamped with a logical (timestamp, replicaId) pair. Merging two replicas takes the union of their op-logs, then replays them in timestamp order, smallest-first, breaking ties on ReplicaId lexicographically (larger wins so a higher replicaId move supersedes a lower one at the same instant).
Before applying each op, the replay algorithm checks whether the node being moved is an ancestor of the target parent. If it is, applying the move would create a cycle, so the op is skipped. Otherwise it is applied, updating that node's parent. Because every replica replays the same total order of the same op-log union, every replica converges to the same tree — the three semilattice laws hold.
This is the algorithm from: Kleppmann et al., "A highly-available move operation for replicated trees" (IEEE TPDS 2021).
Cycle prevention
A move move(node, newParent) is safe if and only if newParent is not a descendant of node (equivalently: node is not an ancestor of newParent). The replay procedure checks this against the tree built from ops replayed so far (the "effective" state at that point in the replay), so concurrent moves that together would form a cycle are resolved without one: the lower-priority op is skipped, and the higher-priority op alone is applied.
Move-log GC
Move-log GC is performed by compact, which removes causally-stable ops whose effect has been superseded by a later stable op on the same node. Causal stability is determined by the Quilter replicator, which gossips delivered version vectors and exposes them to MovableTreeGcCoordinator. causalDots exposes each op's (replica, seq) dot so the Quilter can compute the contiguous delivered VV. The compaction result (MoveTreeCompact) is broadcast to peers so they can trim their own logs.
Parameters
the type of node identifier — must be a stable, globally unique string (e.g. a UUID). The special ROOT_ID is reserved for the root node.
Type Parameters
the value stored at each node.
Samples
val alice = ReplicaId("alice")
val bob = ReplicaId("bob")
// Shared initial state: root → A, root → B, root → C.
val base = MovableTree.empty<String>()
val (t1, idA) = base.addNode(alice, ts = 1L, parent = MovableTree.ROOT_ID, value = "A")
val (t2, idB) = t1.addNode(alice, ts = 2L, parent = MovableTree.ROOT_ID, value = "B")
val (t3, idC) = t2.addNode(alice, ts = 3L, parent = MovableTree.ROOT_ID, value = "C")
// Alice moves A under B (ts=4); Bob moves A under C (ts=5). Both diverge from t3.
val (aliceState, alicePatch) = t3.move(alice, ts = 4L, node = idA, newParent = idB)
val (bobState, bobPatch) = t3.move(bob, ts = 5L, node = idA, newParent = idC)
// Each replica absorbs the other's delta.
val mergedByAlice = aliceState.piece(bobPatch)
val mergedByBob = bobState.piece(alicePatch)
// Convergence guaranteed: both arrive at the same tree.
check(mergedByAlice == mergedByBob)
// Bob's ts=5 wins — A ends up under C.
check(mergedByAlice.parentOf(idA) == idC)
// Cycle prevention: moving A under C while C is under A is silently skipped.
val (t4, _) = t3.addNode(alice, ts = 6L, parent = idA, value = "D")
val (_, cyclePatch) = t4.move(alice, ts = 7L, node = idA, newParent = idA)
val safe = t4.piece(cyclePatch)
check(!safe.isAncestor(ancestor = idA, descendant = idA))Functions
Apply a MoveTreeCompact received from a peer, trimming the local log to match. Idempotent — applying the same compact twice is safe.
The per-author high-water of dots this state delivered and has since compacted away without retaining their identities.
All direct children of nodeId.
Garbage-collect causally-stable ops whose effect has been superseded.
True if ancestor is a proper ancestor of descendant (i.e. ancestor appears on the path from descendant to the root, excluding descendant itself).
The join: merge the two move-logs and replay the union in timestamp order.