CRDTs (Conflict-free Replicated Data Types)
CRDTs are data structures whose concurrent edits merge deterministically — commutative or lattice-based — enabling multi-leader replication without coordination and converging without conflicts.
Definition
A conflict-free replicated data type defines merge as a commutative, associative, idempotent operation, so replicas applying updates in any order and with duplicates converge to the same state. State-based (CvRDT) designs merge monotone join-semilattice values; operation-based (CmRDT) designs require commutative operations with reliable causal broadcast. Counters, sets, registers, and sequences exist as standard building blocks.
Context and scope
Applied in collaborative editors (Figma, Automerge, Yjs), offline-first mobile apps, distributed caches and config, and multi-region databases (Redis CRDB, DynamoDB-style LWW sets).
Common misconceptions
- CRDTs give eventual consistency with no conflicts — they give deterministic convergence; semantically surprising states — both deletes win and add wins simultaneously — are design decisions, not accidents
- Any data fits a CRDT — sequential text editing CRDTs carry overhead; rich structures need custom designs and expertise
- Operation-based CRDTs are simpler — they demand exactly-once causal delivery; state-based ones tolerate arbitrary duplication at bandwidth cost
Anti-patterns
- Using a grow-only set where removal is required and shipping tombstone-less deletion bugs
- Assuming CRDT convergence means users see consistent interleavings in a text sequence — interleaving anomalies are a known editor UX problem
- Replicating a CRDT across unbounded group sizes without tombstone or state compaction and growing metadata forever
Related concepts
Authoritative source
What it is
Multi-writer replication normally needs coordination: locks, leaders, quorums. A CRDT moves the resolution into the data type itself — the merge function is designed to commute — so replicas never negotiate; they just converge.
How it works
State-based CRDTs periodically exchange full states and join them via a semilattice meet — idempotent by construction. Operation-based CRDTs broadcast commutative operations, requiring causal broadcast for correctness. Registers use last-writer-wins or multi-value lattices; sets distinguish add-wins and remove-wins semantics; sequence CRDTs model concurrent text inserts as orderable identifiers.
When to use
Collaboration and offline-first products where coordination latency is unacceptable, multi-region caches merging writes, and availability-prioritized state where the merge semantics match the domain. When correctness requires transactional invariants across entities, choose consensus instead.
Pitfalls
Tombstones must persist long enough for all replicas to see deletions — garbage collection requires epoch coordination, the one bit of coordination CRDT systems reintroduce. Metadata growth in sequence CRDTs needs compaction. Semantic choices — add-wins versus remove-wins — are user-visible policy and belong in product review, not library defaults.