Conflict-Free Replicated Data Types

The state is a join-semilattice: a partially ordered set with a least upper bound (LUB) operation for every pair of elements. Merge is the LUB.

Semilattice requirements:
  - Commutative:  a ⊔ b = b ⊔ a
  - Associative:  (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c)
  - Idempotent:   a ⊔ a = a

Because merge is idempotent and commutative, duplicate or reordered messages are harmless. The state monotonically increases through the lattice.

Instead of shipping full state, nodes exchange operations. Operations must be commutative (but need not be idempotent — the transport layer must guarantee exactly-once delivery).

The tradeoff: CmRDTs are more bandwidth-efficient but require a reliable causal broadcast layer. CvRDTs are simpler to implement over unreliable channels.

A hybrid: nodes exchange only the delta (the difference since the last sync), not the full state. The delta is itself a join-semilattice element, so it merges the same way. This combines the bandwidth efficiency of CmRDTs with the robustness of CvRDTs.

A G-Counter is a map from node ID to count. Merge takes the max per node. The value is the sum of all entries.

;; G-Counter merge
(defn merge-gcounter [a b]
  (merge-with max a b))

;; Value
(defn gcounter-value [c]
  (reduce + (vals c)))

LWW-Register is the most common in practice (used by DynamoDB, Cassandra) but sacrifices the "conflict-free" guarantee — concurrent writes are silently dropped based on wall-clock ordering.

The OR-Set (Observed-Remove Set) is the most practical general-purpose CRDT set. Each add(e) generates a unique tag. A remove(e) removes all currently observed tags for e. A concurrent add on another node generates a fresh tag that survives the remove.

Sequence CRDTs are the backbone of collaborative text editors. The key challenge: interleaving. When two users type at the same position concurrently, their characters must not interleave arbitrarily. Fugue (Weidner et al., 2023) is the first sequence CRDT proven to be maximally non-interleaving.

Automerge is a JSON-like CRDT library. Documents are nested maps, lists, and text. The backend uses a compressed columnar format for efficient storage and sync.

Key properties:

• Full document history (immutable log of changes)
• Binary sync protocol (compact over the wire)
• Rust core with JS/WASM, Python, Swift, Go bindings
• OR-Set semantics for concurrent map key updates
• RGA-based sequence for text and lists

Yjs is an operation-based CRDT optimized for collaborative text editing.

Key properties:

• Sub-document granularity (sync parts of a document independently)
• YATA algorithm for sequences (Yet Another Transformation Approach)
• Awareness protocol (cursor positions, selections, presence)
• Provider architecture (WebSocket, WebRTC, IndexedDB, LevelDB)
• Smaller memory footprint than Automerge for text-heavy documents

Loro (2024) is a newer CRDT framework combining ideas from both:

Key properties:

• Movable tree CRDT (file system operations: move, rename)
• Peritext-inspired rich text CRDT
• Columnar encoding for history
• Rust core with WASM bindings

CRDTs are the right choice when:

• Users must work offline and sync later
• Latency to a central server is too high for interactive use
• The application is peer-to-peer with no single authority
• Conflict resolution rules are well-defined (counters, sets, text)

CRDTs add complexity that is unnecessary when:

• A single database is the source of truth and always reachable
• Conflicts require human judgment (merging spreadsheet formulas)
• The data model requires global invariants (account balance >= 0)
• Garbage collection of tombstones is impractical

Deleted elements in many CRDTs (2P-Set, OR-Set) leave metadata behind. This metadata grows without bound unless garbage collected. GC requires coordination — knowing that all replicas have observed the deletion. This is the fundamental tension: CRDTs avoid coordination for writes but often need it for cleanup.