Distributed systems
Part 1 of 6 · CRDTsCRDTs — Conflict-Free Types, Convergence & When Consensus Wins
Interview map for conflict-free replicated data types: a join that converges, the state versus op versus delta split, and the invariants that still belong on Raft or one ledger.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What makes a data type a CRDT?
Answer
A merge, or an op application, that leaves replicas in equivalent states once they have delivered the same updates. State-based types use a join-semilattice. Op-based types commute under causal delivery.
L2
What is strong eventual consistency?
Answer
If every replica has delivered the same updates, they are in equivalent states. They do not need one total order for a state-based join. They are not linearizable while delivery is still in flight.
L3
State-based versus op-based, in one sentence?
Answer
State-based ships a mergeable state and tolerates a lossy channel because merge is idempotent. Op-based ships operations and needs reliable causal delivery, plus duplicate filtering when the op is not idempotent.
L4
Why is last-writer-wins on a whole document a bad collaborative editor?
Answer
One replica's string replaces the other. Concurrent keystrokes disappear. Sequence CRDTs give each insert an identity so both edits survive.
L5
When does a linearizable store beat a CRDT?
Answer
Hard uniqueness, a balance that must not go negative, exactly-once external effects, a cross-object invariant, or an audit log that must be one total order.
L6
How do CRDTs relate to MVCC?
Answer
MVCC serves a snapshot inside one database. A CRDT merges multi-master updates that have no single snapshot authority. Storing a CRDT blob in a row does not make concurrent JSON edits merge.
L7
What do you put on the CRDT, and what do you refuse?
Answer
Likes, presence, a draft document, and a cart line can merge. Checkout stock, the username primary key, and the payment id stay on a linearizable store. A saga covers the multi-step business workflow. The CRDT does not.
Failure modes
Blind last write on a shared blob
Two devices edit the same JSON. The later timestamp replaces the other edit. Nothing in the payload says how fields merge.
A counter standing in for a ledger
Concurrent decrements commute, so the merged value can go negative. The product needed a reservation or a single commit.
A join that is not idempotent
Gossip retransmits the same payload and the value doubles, or replicas that saw the same updates still disagree.
Metadata with no compaction story
Observed-remove dots, sequence tombstones, and version vectors grow with every replica and every delete. Mobile clients fall over.
Misconceptions
CRDTs solve CAP.
They are a merge rule under partition. You still run anti-entropy. Some metadata, such as membership, may still use consensus. Availability here means concurrent updates are not dropped arbitrarily.
Eventual consistency is a strategy by itself.
You need the merge function. Without a join, replicas can exchange state forever and still diverge.
Strong eventual consistency is linearizability.
SEC says replicas that have the same updates agree. It does not say a read sees the latest committed write in real time.
Interviewer traps
Walk me through Raft leader election as the CRDT answer.
Name the join, then point at the Raft hub for total order. Do not re-teach terms, votes, or log matching.
We use Redis, so the data is eventually consistent.
Say which mode. A single primary is not an Active-Active CRDT. Cache-aside is an invalidation layer, not a merge.
Design scenario
Same prompt for every reader.
Requirements
Likes and the note converge after a partition heals. A username is unique. Stock for a SKU never goes negative. Publishing the note emits one business event.
Traffic / scale
Likes and keystrokes are the hot path. Checkout is a few hundred purchases per second in one region.
Latency
A keystroke must not wait on a cross-region quorum. Checkout may wait on one database commit.
Consistency
Strong eventual consistency for the note and the counter. Linearizability for stock and for the unique name.
Availability
A partitioned region keeps accepting likes and edits. It does not keep accepting two checkouts of one unit.
Failure assumptions
- Two regions accept writes during a partition.
- Clients edit the note offline and sync later.
- A replica will retransmit the same state.
Constraints
- Do not put the wallet balance on a counter CRDT.
- Do not re-design Raft, two-phase commit, or the saga language.
Prompt
A product has multi-region like counts, a collaborative note, and a checkout that must not sell the last unit twice. Devices edit offline.
API
Which writes are local merges, and which writes are a compare-and-set against one store?
Data
Which field is a counter, which is a sequence, and which is an ordinary row?
Architecture
Where does the publish path freeze a version and emit the business event?
What should own the concurrent write
Prefer
A typed merge when updates commute
Increments, set membership, and character inserts have a join. Replicas apply them locally and converge after gossip.
- The product accepts strong eventual consistency, not a real-time total order.
- Offline or multi-region writers are the common case.
- You can name the type: counter, register, set, map, or sequence.
Alternative
A linearizable store when one winner is the rule
Unique names, stock that must not go negative, and a payment that must happen once are not joins.
- A counter merge can go negative. That is legal for the datatype and fatal for a wallet.
- Two creates of the same username both succeed under a set merge.
- A saga or a single database commit is the business workflow, not a second CRDT.
Name the merge before you name the database
The datatype is the product rule. Dissemination comes second. Consensus is a different page.
- 1
Say what concurrent updates must become
Both increments kept, one value kept, add wins, or both characters kept. If you cannot say it, you do not have a type yet. - 2
Match a CRDT to that sentence
G-Counter or PN-Counter, LWW or MV-Register, G-Set or 2P-Set or OR-Set, OR-Map, or a sequence CRDT. The sibling pages hold the mechanics. - 3
Ask whether a join can express the invariant
Exactly one username, a balance that stays non-negative, or one shipment is not a join. Those go to a linearizable store. - 4
Only then pick state, op, or delta
Lossy gossip wants an idempotent join. A large document wants deltas or an op log plus a snapshot. Compaction is part of the design, not a later cleanup.
Overview
Conflict-free replicated data types let replicas update independently and still converge. There is no leader on the write path. Replicas exchange state, operations, or deltas, and a merge function combines them. Collaborative editors (Yjs, Automerge), multi-master stores (Riak data types, Redis Active-Active), and offline clients are the usual homes.
Convergence is not linearizability. Strong eventual consistency says that replicas which have delivered the same updates are in equivalent states. It does not say that a read in another region sees the latest write before the sync arrives. Interviews that stop at "eventual consistency" without a merge function have not answered the question.
This cluster is the taxonomy, the classic types, how they travel, and when a consensus log or a single ledger should win. It does not rewrite those neighboring tutorials.
Why a shared integer or a shared blob fails
Without a conflict strategy, multi-writer replicas do one of five things:
- Last writer replaces the whole value. Concurrent edits vanish.
- Every keystroke waits on a leader. That is a legal design for a config key and a poor one for text.
- Offline clients cannot mutate, because the protocol wanted a quorum first.
- Someone hand-merges JSON with a function that is not associative or idempotent, and replicas diverge forever.
- The design doc says "eventual consistency" and never names the merge.
A state-based CRDT fixes the last one by making merge the least upper bound of a join-semilattice. That function is commutative, associative, and idempotent, so gossip can reorder and repeat messages. An op-based CRDT instead ships operations that commute when they are concurrent, and it asks the channel for reliable causal delivery.
Flow
- 1
1 Both replicas update
- next2 Ship state, ops, or deltas
- 2
2 Ship state, ops, or deltas
- next3 Merge is the join
- 3
3 Merge is the join
- next4 Same updates, same state
- 4
4 Same updates, same state
Lesson map
CRDTs — Conflict-Free Types, Convergence & When Consensus Wins
Interview map for conflict-free replicated data types: a join that converges, the state versus op versus delta split, and the invariants that still belong on Raft or one ledger.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Both replicas update"] b["2 Ship state, ops, or deltas"] c["3 Merge is the join"] d["4 Same updates, same state"] a -->|1 Both replicas update| b b -->|2 Ship state, ops, or deltas| c c -->|3 Merge is the join| d
Read the diagram as a delivery story, not a leader. Replica A and replica B both write. What travels is a payload the receiver can join or apply. After both sides have the same updates, the states match. A retransmit of the same state must not change the result again. That is the idempotent half of the join.
Where a CRDT sits next to stronger tools
| Dimension | CRDT multi-master | Raft or Paxos | Two-phase commit | Sagas | A distributed lock |
|---|---|---|---|---|---|
| Coordination per write | None on the write. Sync is async | Quorum or a leader | Coordinator and participants | Async messages | The lock holder |
| What you get | Strong eventual consistency | Linearizability when the log is applied correctly | Atomic commit, with a blocking window | Business-level eventual, via compensation | Mutual exclusion only |
| Offline writes | Natural | Hard | Hard | A local queue, then the rest of the workflow | Usually blocks |
| Conflict story | Typed merge, or ops that commute | One total order | Abort or block | A compensating transaction | Serialize a short critical section |
| Best fit | Text, counters, presence, carts that recheck at checkout | Config, leadership, a ledger that needs one order | Rare, tightly coupled resource managers | Long-running cross-service workflows | Short critical sections |
| Refuse when | The rule is exactly one of X | The workload is a fan-in of local edits | The path is wide-area and fails over often | One database already has the commit | The lock would be held across RPCs |
The rule of thumb: use a CRDT when concurrent updates are expected and the datatype's merge is the product rule. Use a linearizable store when the business rule is "exactly one of X" or "the balance never goes negative under concurrent spend." Use a saga for a multi-step workflow. Use a lock for a short critical section. The protocol pages already exist: Raft, two-phase commit, sagas, and Redis cache-aside.
Decisions
- 1
1 Concurrent writes?
- No2 One writer or a lock
- Yes3 Does the merge fit?
- 2
2 One writer or a lock
- ?
3 Does the merge fit?
- Yes4 Use a CRDT
- No5 Use Raft or a ledger
- 4
4 Use a CRDT
- 5
5 Use Raft or a ledger
"No" on the first question means a single writer, a row version, or a short lock. "Yes" only continues if you can point at a type on the next pages. If the merge would silently drop a debit or accept two usernames, take the ledger branch.
Taxonomy in one page
- State-based (CvRDT). Ship the state, or a stand-in for it. The receiver merges. The state forms a join-semilattice. A lossy, reordering channel is acceptable because merge is idempotent.
- Op-based (CmRDT). Ship operations. Concurrent operations must commute. Delivery is typically reliable causal broadcast. A fresh replica needs a snapshot plus the ops it missed, or a full state transfer.
- Delta-CRDTs. Ship the join-fragment since the last sync. The receiver still joins, so the channel assumptions stay close to state-based, and the bytes stay closer to the op log.
- Pure-op and buffer tricks. Buffer, acknowledge, and prune. These are still the op-based family. They do not remove the need for a delivery rule.
The dissemination page owns the bandwidth and compaction detail. The type pages own the payloads.
CAP, said carefully
CRDT stores are often labeled AP. They prefer availability and partition tolerance and give up linearizability. That sentence is incomplete.
- Anti-entropy still has to run: gossip, Merkle trees, hinted handoff, or a provider that syncs a document. Otherwise the system is not eventually anything. It is stuck.
- Cluster membership and bucket configuration may still sit on a consensus log. The data plane can be a CRDT while the control plane is not.
- Version vectors and causal delivery wrap the payload when the client must see happens-before, not only the final join.
Do not claim CRDTs "solve CAP." They give you a principled merge so a partition does not drop concurrent updates by accident.
When consensus or linearizability wins
Put the write on Raft, or on one database transaction, when:
- Uniqueness is a rejection. Only one account may own the username. Two concurrent creates must not both succeed.
- The balance must not go negative and you are not using reservations. Concurrent debits that both merge will both subtract.
- An external effect happens once, tied to a total order. One payment id, one shipment.
- The invariant crosses objects and cannot be written as a composition of joins without freezing the set inside a real transaction.
- An auditor wants one total order, not merely a converged value.
CRDTs stay a good fit for like and view counts, presence, collaborative documents, cart lines that checkout will recheck, and feature-flag sets whose policy is add-wins or observed-remove. Checkout itself often flips to a linearizable inventory service. Hybrid designs are the normal senior answer, not a compromise you apologize for. The production page is that decision in detail.
What this cluster covers
- Counters and registers - G-Counter, PN-Counter, last-writer-wins, and the multi-value register.
- Sets and maps - G-Set, 2P-Set, observed-remove, and maps of nested types.
- Sequences - RGA, LSEQ, Yjs, and Automerge.
- State, op, and delta - channels, anti-entropy, and compaction.
- Production and when not - Riak, Redis Active-Active, collab apps, and the line against Raft.
The ring returns here after the last page.
A production baseline
- Pick the type for the invariant. The wrong register drops a concurrent value and the metrics stay green.
- Bound metadata. Observed-remove tombstones, sequence tombstones, and version vectors need a compaction plan before launch.
- Watch merge lag. Anti-entropy delay, delta buffer size, and replica skew are the SLOs that matter. A green process is not a converged one.
- Do not put secrets in a payload that fans out to every replica.
- Hybridize. CRDT fields for collaboration, a linearizable store for money and uniqueness, a saga for a multi-step checkout.
- Test schedules, not just examples. Commutativity, associativity, and idempotence under drops and reorders beat a single happy-path unit test.
MVCC is the snapshot story inside one database. It is not this merge. A row that stores a CRDT blob can still be versioned by the database. Concurrent writers across replicas still need the CRDT rule, or one of them overwrites the other.
Interview Q&A
What makes a data type a CRDT?
Answer
A merge, or an operation application, that guarantees replicas converge once they have seen the same updates. For state-based types that merge is a join-semilattice: commutative, associative, and idempotent. For op-based types the concurrent operations commute, and delivery is usually causal. If you cannot point at that function, the type is only "we hope sync sorts it out."
Is eventual consistency enough for a bank ledger?
State-based versus op-based, in one sentence?
Answer
State-based ships a value you can merge, and resending it is safe. Op-based ships an operation that must arrive reliably, in causal order when the op is not commutative with everything, and must not apply twice unless it is idempotent.
Why do collaborative editors avoid a last-writer-wins string?
Answer
Last-writer-wins on the whole document keeps one string and throws the other away. Sequence CRDTs assign an identity to each insert, so concurrent edits both remain. RGA, LSEQ, Yjs, and Automerge are that idea with different identifier schemes. The sequence page is the detail.
How do CRDTs relate to MVCC?
Answer
MVCC lets one database serve a snapshot without blocking a writer. A CRDT merges updates from replicas that do not share that snapshot. You can store the CRDT in a row that MVCC versions for local durability. Snapshot isolation will not merge two concurrent JSON edits into both users' fields. That confusion is why MVCC stays its own page.
Name a production CRDT system, precisely.
Answer
Redis Enterprise Active-Active types, Riak data types, Automerge, and Yjs. SoundCloud's Roshi was an early observed-remove timeline. Cosmos DB conflict policies include last-writer-wins and a custom procedure. That is a register policy, not a full observed-remove suite. Say which one you mean.
What does a delta buy you that full state does not?
Answer
Full-state gossip costs bytes proportional to the object on every round, even when one element changed. A delta is the join-fragment since the last acknowledgement. The receiver still joins, so a duplicate delta is safe. The dissemination page is the buffer and compaction story.
When do you refuse a CRDT in a design review?
Answer
When losing a concurrent update is unacceptable and the datatype would drop or double it: unique primary keys, non-negative money without reservations, exactly-once side effects, or a regulator's total order. Offer a linearizable store for that field and keep the CRDT on the fields whose merge you can defend.
Pitfalls
- Calling a replicated blob a CRDT because it syncs.
- Using last-writer-wins on collaborative text.
- Treating a PN-Counter as a bank balance.
- Shipping an observed-remove set with no tombstone bound.
- Answering a merge question with a Raft election or a two-phase commit log walk.
- Saying "Redis" without saying cache-aside, single primary, or Active-Active.
Take a like count, a display name, a shopping-cart SKU, a collaborative paragraph, and a username. For each, say CRDT or linearizable store, name the type if it is a CRDT, and say what a concurrent update becomes. If every answer is "CRDT," start again at the username.
Go Deeper
- Shapiro, Preguiça, Baquero, and Zawirski, Conflict-free Replicated Data Types (INRIA RR-7687). The taxonomy this cluster uses.
- Ink & Switch, Local-first software. The product argument for offline merge.
- Martin Kleppmann, CRDTs: The Hard Parts (video). Interleaving, tombstones, and the gaps in textbook types.
- Redis Active-Active and Yjs for two production shapes.
Next: Counters and registers.