Conflict-free Replicated Data Types (CRDTs) are data structures that converge to the same value across replicas, regardless of update order, without requiring coordination.
For systems with multiple writers and high availability requirements, CRDTs offer strong eventual consistency without the complexity of consensus.
In a distributed system with multiple replicas:
Without coordination, concurrent updates conflict. How do replicas reconverge?
Options:
CRDTs trade some flexibility for automatic correctness.
Eventual consistency: replicas eventually converge if updates stop.
Strong eventual consistency: replicas with the same set of updates have the same state — regardless of order.
CRDTs guarantee SEC by design.
Each replica has state. Replicas exchange full state. Merge function:
These properties define a join-semilattice.
Replicas exchange operations. Operations must commute.
Requires reliable, exactly-once delivery (or operations must be idempotent).
State-based vs op-based: different constraints; choose based on network reliability and bandwidth.
State: vector of counts per replica.
Increment: replica i increments its slot.
Merge: max per slot.
Value: sum of slots.
Used for: counters that only increase (page views, likes).
Two G-counters: one for increments, one for decrements.
Value: positive sum - negative sum.
Used for: counters that can increase or decrease.
Add-only set.
Add: insert element.
Merge: union.
Used for: append-only collections.
Add and remove. Two G-Sets: added and removed.
Once removed, can't re-add.
Last-write-wins set. Each element has add timestamp and remove timestamp.
Element is present if add timestamp > remove timestamp.
Used for: sets with eventual additions and removals.
More sophisticated. Each add gets a unique tag. Remove removes specific tags.
Removes only what was observed; concurrent adds are preserved.
Hard to do well. Various designs:
Used for collaborative text editing.
Replicated map structures, often using OR-Set semantics for keys + CRDTs for values.
Bounded counters, monotonic-only counters — for specific domain semantics.
For correct merge, often need to track causality:
These track which updates each replica has seen.
JavaScript CRDT library. Used for real-time collaboration (Y.js, Tiptap, Liveblocks).
JSON-like CRDT. Used in collaborative apps.
Distributed database with CRDT support (counters, sets, maps).
CRDB feature in Redis Enterprise.
Distributed database designed around CRDTs.
Alternative to CRDT for collaborative editing. Used historically (Google Docs).
CRDTs increasingly preferred for distributed scenarios.
Multiple users editing same document. CRDTs for text, spreadsheets, drawings.
Distributed shopping cart. Add items concurrently; merge cleanly.
Distributed counters across regions.
Distributed config that multiple admins update.
Mobile apps that work offline; sync when online. CRDT structures merge cleanly.
Devices update locally; sync to cloud. CRDTs handle concurrent changes.
CRDTs often store metadata per element (vector clocks, tombstones).
OR-Set: tombstones grow with deletions.
State-based: send full state. Large for big structures.
Op-based: send ops. Often smaller.
Delta-based CRDTs send only changes.
Tombstones, version vectors accumulate. Need cleanup mechanism.
Often requires occasional coordination (which defeats the purpose somewhat).
Subtle bugs are common. Use libraries; don't roll your own for non-trivial structures.
Some operations don't fit CRDT model:
CRDTs guarantee write convergence; reads can return any state up to date.
For "I just wrote X, so I should read X" semantics: same-replica reads or session guarantees.
Can't have a CRDT counter with strict upper bound (without coordination).
Tombstones live forever in basic OR-Set. Real implementations need GC strategies.
CRDT fits when:
CRDT doesn't fit when:
If you have a single writer (master-replica), CRDTs are unnecessary.
If you need strong consistency (banking transactions, inventory), use consensus-based systems.
If your domain has natural conflicts that need user resolution: surface conflicts; don't auto-merge.
OR-Set when you wanted last-write-wins. Subtle differences matter.
Forgetting that tombstones / version vectors grow. Production OOM eventually.
Mixing CRDT with non-CRDT operations. Break SEC.
Designing your own CRDT is hard. Composition of standard CRDTs is safer.
CRDT is a tool, not a complete solution. Many distributed systems still need coordination.
CRDTs rely on:
The math is well-developed. The engineering is the hard part.