CRDT (Conflict-free Replicated Data Type)

CRDTs are classified into two operational models: state-based (CvRDTs) and operation-based (CmRDTs). CvRDTs propagate the entire local state to peers, requiring the merge function to be a commutative, associative, and idempotent join over a semilattice — meaning replicas can receive updates in any order, any number of times, and duplicates any number of times, and still converge. CmRDTs instead propagate the operation itself (a delta), which is cheaper on the wire but demands a reliable, causally-ordered broadcast channel — if an operation is delivered out of causal order or dropped, convergence breaks. This distinction directly dictates your transport layer requirements: CvRDT gossip can ride on unreliable UDP-style anti-entropy, while CmRDT dissemination usually needs something closer to a causal broadcast primitive layered over vector clocks or version vectors.

The canonical failure mode engineers underestimate is metadata bloat. A naive OR-Set (Observed-Remove Set) or a PN-Counter accumulates tombstones or per-replica counters that never shrink, because the merge lattice must retain enough history to resolve add/remove races correctly. In long-running systems with high replica churn (ephemeral pods, autoscaled nodes), this metadata can dwarf the actual payload. Production-grade implementations mitigate this with delta-state CRDTs, which only ship the incremental lattice growth since the last acknowledged sync, and with periodic causal stability pruning — garbage collecting tombstones only once you can prove, via the version vector, that no replica in the cluster can still generate a conflicting concurrent operation against the removed element.

CRDTs do not eliminate the CAP tradeoff; they relocate it. You trade linearizability for availability under partition, and you push the semantic burden onto the data type designer. This is why generic CRDT libraries only cover primitives cleanly: counters, sets, sequences (for collaborative text, e.g., RGA/Logoot), maps, and registers (LWW-Register, MV-Register). Composing them into application-level invariants — e.g., ‘account balance must never go negative’ — is provably impossible to express as a pure CRDT merge, because that invariant is not monotonic on the lattice. Systems that need CRDTs for availability but also need such invariants typically layer a reconciliation pass (compensating transactions, escrow-based reservation) on top rather than trying to force the invariant into the merge function itself.

Architecturally, adopting CRDTs shifts complexity from the coordination layer to the replica and the client. You no longer pay consensus latency per write, but you inherit a permanent obligation to run anti-entropy (gossip, Merkle-tree diffing, or push-pull sync) and to reason about convergence bugs that only manifest under specific interleavings — which are notoriously hard to catch in testing and usually require model checking (e.g., with TLA+) or property-based testing with simulated network partitions to surface.