Archivedistributed-systems
CRDTs: Convergence Without Coordination
If every replica applies operations commutatively, order stops mattering. The cost is metadata and semantics.
- Published
- Reading time
- 1 min read
A conflict-free replicated data type guarantees that replicas which have seen the same updates converge, regardless of order or duplication. That removes coordination from the write path.
Two families
- State-based (CvRDT): replicas merge states with a join that is commutative, associative, and idempotent. Example: grow-only set, LWW register, OR-Set.
- Operation-based (CmRDT): replicas broadcast operations that commute. Example: counters, sequence CRDTs.
The metadata bill
Removing conflicts requires tracking causality: version vectors, dotted version vectors, or tombstones. An OR-Set that adds and removes elements forever accumulates metadata unless compacted.
The semantic bill
Convergence is guaranteed; meaning is not. Last-writer-wins silently discards concurrent edits. Text CRDTs preserve intent better but are heavier.
Takeaway: CRDTs are excellent when operations genuinely commute (counters, sets, presence). For business rules with invariants, you still need a coordinator or a compensating transaction.