CRDTs

Overview

Conflict-free replicated data types are structures whose merge function guarantees convergence. Each replica applies updates locally and exchanges state or operations later, in any order. Redis Enterprise, Riak and collaborative editors such as Automerge and Yjs rely on them.

How it works

A G-Counter keeps one slot per replica. Increments touch only your slot; merge takes the maximum per slot; value is the sum.

A: {A:3, B:0}      B: {A:2, B:4}
merge = max per slot -> {A:3, B:4}
value = 7
merge(x, x) = x ; merge(x, y) = merge(y, x)

An OR-Set tags each added element with a unique id; a remove deletes only the tags it observed, so a concurrent add wins. Delta CRDTs send only the changed fragment, reducing bandwidth. Convergence holds because the merge is a least upper bound on a lattice.

Pitfalls

• Removal usually leaves tombstones; without causal-stability garbage collection, state grows without bound.
• CRDTs cannot guarantee invariants like stock never negative; use reservations or coordination for those.
• A PN-Counter can go negative across replicas even if each local check passed.
• LWW-Register hides conflicts and depends on clock quality.
• Operation-based types need exactly-once or causal delivery, which transport must provide.

Key takeaways

• Commutative, associative, idempotent merge gives convergence with no coordination.
• Choose the type whose merge matches user intent, such as add-wins sets.
• Budget for metadata growth and compaction.
• Use coordination, not CRDTs, for hard invariants.
• Test with duplicated, reordered and delayed messages in staging, since convergence under those conditions is the whole point of the design.