Skip to main content
distributed systems

CRDTs — conflict-free replicated data types

9 min read
Fully authored

G-Counter, LWW-Register, OR-Set — data structures that merge without conflict.

Three replicas of the SAME counter, operating during a network partition. Each accepts writes independently. When the partition heals, they merge. Can they converge to the correct total without conflict resolution? Yes — if you use a CRDT (Conflict-free Replicated Data Type). The magic is that the data structure itself makes merging trivially correct.

G-Counter across 3 replicas
Replica A
0
vector = [A:0, B:0, C:0]
Replica B
0
vector = [A:0, B:0, C:0]
Replica C
0
vector = [A:0, B:0, C:0]
Merges performed: 0Status: ✓ Converged

Why this works — the mathematical magic

A G-Counter stores one counter per replica, not one counter globally. Replica A tracks "how many increments happened AT A". Replica B tracks "how many happened AT B". Merge is just take the maximum of each field. There is no conflict because two replicas can never disagree about their own field — only about each other's (and max always picks the higher, correct value).

// merge two G-Counters
merge(a, b) = { A: max(a.A, b.A), B: max(a.B, b.B), C: max(a.C, b.C) }
// query total
value(c) = c.A + c.B + c.C

The CRDT family

Counter

G-Counter, PN-Counter

Increment-only (G) or increment + decrement (PN). Merge = max per field. Use for: view counts, likes, distributed metrics.

Register

LWW-Register, MV-Register

Single value; Last-Write-Wins by timestamp, or Multi-Value keeping all concurrent writes for the app to resolve. Use for: user profile fields, feature flags.

Set

G-Set, 2P-Set, OR-Set

Grow-only (G), add + remove (2P), or Observed-Remove which handles concurrent add/remove correctly. Use for: shopping carts, presence lists.

Text

RGA, LSEQ, Yjs

Collaborative text editing that merges concurrent edits without conflict. Use for: Google Docs, Figma, Linear.

The catch — when CRDTs are wrong

CRDTs give you eventual consistency without conflict resolution — that's magic. But they cannot enforce global invariants. Example: "the account balance may never go negative." A CRDT G-Counter can be decremented on multiple replicas simultaneously such that each replica sees a non-negative balance, but after merge the total is negative. For that you need coordination (linearizable writes or a leader). CRDTs handle commutative operations only.

Applied in these systems

  • URL Shortener Ch 7 — click count aggregation across regions uses a PN-Counter so async replication converges without conflict.
  • URL Shortener Ch 8 — L7 multi-region conflict resolution when a URL is edited concurrently in two regions.
  • Slack, Discord — presence lists use OR-Set style semantics.
  • Figma, Linear, Notion — collaborative editing built on CRDTs (Yjs or Automerge).
  • Redis Enterprise — active-active replication is CRDT-based.

References

  • Shapiro et al. (2011) — "A comprehensive study of Convergent and Commutative Replicated Data Types." INRIA. The founding survey.
  • Kleppmann & Beresford (2017) — "A Conflict-Free Replicated JSON Datatype." The Automerge foundation.
  • Yjs — yjs.dev. The most-used CRDT library in production.
  • Kleppmann (2020) — "Local-first software." The philosophy behind CRDT-based apps.

Practice what you just read

Every foundation concept has a companion quiz to close the loop.

Take the URL Shortener quizOpen the flagship problem

More in distributed systems

Consensus — Paxos and RaftConsistent hashingDistributed transactions — 2PC, 3PC, Saga, TCCVector clocks and hybrid logical clocksQuorum reads and writes