Sign inStart practicing
Start practicing Sign in

CRDTs: Conflict-Free Replicated Data Types

CRDTs explained: counters, sets and sequences that merge without conflicts, state vs operation based CRDTs, and how collaborative editors use them.

Advanced 3 min read · Updated

A CRDT (conflict-free replicated data type) is a data structure that can be updated independently on many replicas, without coordination, and always merges to the same result. Counters, sets, maps, registers and even text sequences can be built as CRDTs. They're how collaborative editors, offline-first apps and some geo-replicated databases let everyone keep working through network partitions and still converge, without a central server deciding order.

statestateReplica Aadds milkReplica Badds eggsMergeorder doesn't matterReplica Amilk, eggsReplica Bmilk, eggs
Two replicas edit the same list while apart. Because the merge is commutative and idempotent, both reach the same state whatever order the updates arrive in.

The problem they solve

Two users edit the same document offline, or two data centres accept writes during a partition. When they reconnect, the replicas hold different states. Last-write-wins discards someone's work; asking the user to resolve every conflict is painful. A CRDT defines updates and a merge so that, whatever order replicas receive each other's updates, they reach the same state. This property is called strong eventual consistency.

Why merges converge

A state-based CRDT's merge function must be:

  • Commutative: merge(A, B) = merge(B, A), so order doesn't matter.
  • Associative: merge(merge(A, B), C) = merge(A, merge(B, C)), so grouping doesn't matter.
  • Idempotent: merge(A, A) = A, so receiving the same update twice is harmless.

With those properties, replicas can gossip states in any order, with duplicates and delays, and still converge. Operation-based CRDTs instead send operations that are designed to commute, and rely on a delivery layer that delivers each operation exactly once to every replica.

Common CRDTs

CRDTHow it worksUse
G-Counter (grow-only)Each replica keeps its own count; the value is the sum; merge takes the per-replica maximumViews, likes
PN-CounterTwo G-Counters: increments and decrementsInventory deltas, votes
LWW-RegisterA value with a timestamp; merge keeps the latestSimple fields where losing a concurrent write is acceptable
MV-RegisterKeeps all concurrent values for the application to resolveFields where conflicts must be visible
OR-Set (observed-remove)Adds are tagged uniquely; a remove deletes only the tags it has seen, so a concurrent add survivesShopping carts, tags, membership
Sequence CRDTs (e.g. RGA, Logoot-style)Each character gets a unique, ordered position ID, so concurrent inserts interleave deterministicallyCollaborative text editing
// G-Counter: one slot per replica
state A = { A: 3, B: 1 }     // A saw its own 3 increments and 1 from B
state B = { A: 2, B: 4 }
merge   = { A: max(3,2), B: max(1,4) } = { A: 3, B: 4 }   // value = 7

CRDTs vs operational transformation

Operational transformation (OT)CRDTs
How concurrency is handledA server transforms concurrent operations against each otherOperations or states commute by construction
ServerUsually needs a central server to order operationsPeer-to-peer or server-assisted; a server is optional
Offline editingHarder; long offline periods are painfulNatural: merge whenever reconnected
Metadata overheadLowCan be high (IDs per character, tombstones), though modern libraries compress it well
ExamplesClassic Google Docs-style editorsLibraries such as Automerge and Yjs; offline-first apps

Costs and limits

  • Metadata growth: tombstones for deleted elements and per-replica state can grow, requiring garbage collection when all replicas have seen a deletion.
  • Not every invariant fits: "balance must never go below zero" or "username must be unique" needs coordination; a CRDT can't prevent two replicas from both spending the last ₹100.
  • Merges can be surprising: an OR-Set keeps an item one user removed while another re-added it, which may or may not match user intent.
  • Design up front: choosing the right CRDT per field is part of the data model.

A pragmatic pattern is a hybrid: CRDTs for collaborative content and counters, and a coordinated path (a single leader or a transaction) for operations with hard invariants such as payments.

Where it’s used

Collaborative editors and whiteboards

Sequence and map CRDTs let many users edit at once, including offline, and converge.

Offline-first mobile apps

Local changes merge with server state without losing edits.

Geo-replicated databases

Counters and sets accept writes in every region and merge across regions.

In an interview

  • Define strong eventual consistency and the commutative, associative, idempotent merge.
  • Give a G-Counter or OR-Set example and walk through a merge.
  • Compare CRDTs with operational transformation for collaborative editing.
  • Say which invariants need coordination instead of CRDTs.

Further reading