Quilted

A delta-state CRDT: a value living in a join-semilattice.

piece is the join — the least-upper-bound of two states. It MUST satisfy the three lattice laws:

• idempotent a.piece(a) == a

• commutative a.piece(b) == b.piece(a)

• associative a.piece(b).piece(c) == a.piece(b.piece(c))

These laws are exactly what make convergence robust to kuilt's frame delivery semantics: a fabric may drop, duplicate, and reorder frames, but any two replicas that have absorbed the same set of states — in any order, with any repeats — compute the same value.

Operations are modeled as delta-mutators that return a Patch (a small fragment of the same lattice), which any replica absorbs with piece. The name nods to kuilt's quilting metaphor: a whole pieced from independent patches.

Two mutator shapes, one absorption path. A mutator may return either a Patch (the minimal lattice fragment for the change — BoundedCounter.trySpend, ORSet.add, ORMap.put, LWWMap.set) or a full new state S (LWWRegister.set, Gauge.observe). Both are absorbed by the identical piece join: a Patch is applied with piece(patch), and a returned full state is itself a valid join argument (a.piece(newState)).

Return a full state only when the whole state genuinely is the minimal delta. That is true of a single-cell type — an LWWRegister holds one tagged value, so there is nothing smaller to send. It is not true of a collection, however single-celled its per-key merge looks: an ORSet add touches one element, an ORMap put one key, an LWWMap set one cell, a JsonCrdt set one document key, and returning the container would put every other element on the wire too. Those four return a Patch for exactly that reason, and their deltas are pinned byte-for-byte by the delta-mutator law X.piece(mᵟ(X)) == m(X) (#2044, #2111) — unconditionally for ORSet, ORMap and JsonCrdt, and for LWWMap exactly while the write's (timestamp, replica) tag dominates the key's current one, which is what its own tag-uniqueness rule already requires. Outside that domain no delta exists, because a delta is joined and a join can only move up the lattice (#2087).

The law is necessary and nowhere near sufficient, so do not stop at it. A whole state dominates itself, so X.piece(whole(X)) == whole(X) holds for any lattice at all: a mutator returning Patch(wholeNewState) satisfies the law perfectly while saving nothing. No property of piece can tell the two apart — only measuring the encoded frame across two instance sizes can. Every type above therefore carries a flat-frame test beside its law test, and a delta shape that is merely correct is not the thing being claimed here.

A pair of traps that both caught this codebase, worth reading before adding a type. An earlier version of this paragraph offered registers and maps together as the family whose whole state is already minimal; the maps were never in it, and that sentence is a large part of why every write shipped O(state) bytes for six months without anyone looking. And a law test is only as good as its reference: JsonCrdt's first one compared the delta path against root.piece { it.put(…) }, which is root.piece(root.put(…).delta) — the same expression — so it asserted x == x and pinned nothing (#2111). Point the reference at a second implementation and prove it by mutating the delta path and watching the law go red. When adding a type here, ask what one write costs on a large instance — not what the merge function looks like.

Type Parameters

Inheritors