CRDTs

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 4 — Data

Layer 4 · Post 15 of 17

← Previous: Dual Writes → Next: Logical Clocks

Layer 4 — Data · Post 109 of 119

Data structures designed so replicas can update independently and always merge to the same result.

What you'll learn

What "conflict-free" actually guarantees
G-Counter, LWW-Register, OR-Set — enough intuition to not hand-wave
When CRDTs are the right merge, and when you still want a leader

The idea in one minute

CRDT (conflict-free replicated data type): a value you can update on disconnected replicas, then merge, and every replica ends at the same state (strong eventual consistency) without a central lock and without "pick one write, drop the other" unless that is the type's spec.

Merge is associative, commutative, idempotent (a join on a semilattice). Order of arriving updates should not matter.

Replica A: increment  (offline)
Replica B: increment  (offline)
Merge:     2          — not "A wins" or "B wins"

Last-write-wins registers are a CRDT family member — they do drop a concurrent write by timestamp. "Conflict-free" means merge is defined, not "we never lose an intent." Counters and sets can preserve concurrent adds.

Why it matters

Multi-region AP, collaborative editors, shopping carts on flaky mobile, and some caches need a merge math better than "whoever hit Redis last." Interviews: CRDTs are the named answer next to "eventual consistency" when they ask how you converge.

They are not a free replacement for Postgres. Metadata (tombstones, version vectors) grows. Some types cannot express "transfer $10" without a ledger.

How it works

Two flavors (jargon).

State-based (CvRDT): send your full state; merge = join(local, remote). Easy, can be fat.
Op-based (CmRDT): send operations; they must be delivered exactly once and often in causal order. Thinner, pickier about the channel.

G-Counter (grow-only). Each replica increments its own slot; merge takes max per slot, then sum. Concurrent +1 and +1 become +2. You cannot decrement (that's a PN-Counter: two G-Counters).

LWW-Register. Value + timestamp (or unique id). Merge = higher timestamp. Concurrent writes: one is discarded. Simple; brutal for text.

OR-Set / observed-remove. Add and remove with unique tags so concurrent add-wins or remove-wins is well-defined. Tombstones are the cost.

Text. Automerge, Yjs, Share: CRDTs or OT (operational transform) for cursors and characters. Different beast than a Redis counter.

Idempotent merge is how you survive at-least-once gossip (Post 119).

A simple example

Three POS terminals, flaky WAN, "units sold today."

LWW integer: two shops each sell one widget offline. Merge: 1 if timestamps fight. You lost a sale.

G-Counter: each terminal has an id; merge sums. 2. That is the CRDT win.

Money transfer from account A to B: two increments/decrements without a single serializable history can create or destroy money unless you model it as a log of intents (or a PN-Counter with care, still not a bank). Use a leader or a ledger for that.

Common mistakes

"We'll CRDT the user profile JSON." Concurrent name and address edits need field-level types, not one LWW blob.

Ignoring tombstone GC. Sets that delete a lot grow until you compact with extra protocol.

CRDT as AP magic for unique constraints. "Username unique" is still a coordination problem. CRDTs do not give you a global unique index for free.

Implementing from a blog in prod. Use Riak-style types, Redis CRDTs (enterprise / some modules), Automerge, or a store that already merged (Azure Cosmos conflict policies, etc.) — and still read the merge spec.