Local-first data

How do CRDTs merge changes without conflicts?

CRDTs merge changes without conflicts by building the merge rule into the data type itself. In a state-based CRDT, merging two states is commutative, associative and idempotent, so copies can merge in any order and any number of times. In an operation-based CRDT, concurrent operations commute, so every replica that applies the same operations reaches the same state.

TL;DR

Copies edited apart converge because the data type fixes the merge rule in advance, so delayed, reordered or duplicated messages do no harm. State-based CRDTs send whole states, while operation-based ones send small operations that must arrive exactly once, in causal order. A merge cannot guarantee what people intended or protect an invariant like one booking for the last seat.

Learning objectives

After reading this article you will be able to:

  • Explain why commutative, associative and idempotent merges let copies converge in any order
  • Compare state-based and operation-based CRDTs on data sent and network demands
  • Identify outcomes a CRDT merge cannot decide, such as broken invariants

Conflict-free guarantee in CRDTs

In a CRDT, “conflict-free” does not mean two people never edit the same thing. It means the data type has already decided what the merged result will be, so no conflict is left for anyone to resolve.

Two copies of the same data, called replicas, are edited while they cannot reach each other. The edits are concurrent: each was made without knowledge of the other. When the replicas meet again, something has to decide what the combined data looks like.

Some replicated systems apply an update, discover later that it clashes with another, and roll it back. A CRDT avoids that step. Shapiro, Preguiça, Baquero and Zawirski define the goal as strong eventual consistency: any two replicas that have received the same set of updates are in the same state, with no rollback and no vote. There are two ways to build that guarantee.

State-based CRDT merging

A state-based CRDT merges whole states: each replica changes its own state and from time to time sends that state to another replica, and the receiver combines the incoming state with its own using a merge function.

The paper gives the conditions that make this converge. The possible states must be ordered so that any two of them have a least upper bound, the smallest state that contains both. The merge must compute that least upper bound, and every local update must move the state upward, never back. A merge built this way is automatically:

  • Commutative: merging A with B gives the same result as merging B with A.
  • Associative: merging A with B and then with C gives the same result as merging A with the result of B and C.
  • Idempotent: merging A with itself gives A.

A grow-only counter shows how this works in practice. Each replica keeps a count for every replica and only increments its own entry. Merging takes the larger value for each entry, and the counter’s value is the sum. If phone A has counted three items and phone B two, any merge of their states reads five, however many times the states are exchanged. Adding the entries together on merge would be wrong, because receiving the same state twice would count it twice. The older name for this family is convergent replicated data type (CvRDT).

Operation-based CRDT merging

In an operation-based CRDT, each change is turned into an operation, such as “increment” or “insert this character after that one”, and the operation is sent to every replica. The rule here is that any two concurrent operations must commute: applying them in either order leaves the replica in the same state. Addition commutes, so an operation-based counter just adds each increment it receives.

This style moves less data but asks more of the network. The papers assume reliable causal delivery: every operation reaches every replica exactly once, and an operation is never applied before the operations it depended on. The CRDT glossary puts the practical side plainly: the system must resend operations that are lost and ignore duplicates. The older name is commutative replicated data type (CmRDT).

The comprehensive study weighs the two. State-based CRDTs are simpler to reason about and work over weak channels, but sending whole states can be expensive for large objects. Operation-based CRDTs have simpler payloads but need reliable broadcast, which in general means tracking who is in the group. Delta CRDTs sit between them: they are state-based, but replicas send only the part of the state that changed. The 2011 paper also proves that each style can emulate the other.

CRDTs on unreliable networks

Message order, duplicates and delays do not matter to a CRDT, because the three merge properties map onto what goes wrong on unreliable links. Kleppmann and Beresford design their JSON CRDT for a network that “may arbitrarily delay, reorder and duplicate messages”.

  • Because merges commute, it does not matter which device’s changes arrive first.
  • Because they are associative, a device can merge changes it collected from several others and pass the combined state on, and the result is the same as merging each one separately.
  • Because they are idempotent, a change that arrives twice through two routes does no harm.

Yjs states the same thing about its own document updates: they are commutative, associative and idempotent, so they can be applied in any order and more than once. This is why CRDTs pair well with store-and-forward delivery and peer-to-peer links. Shapiro and colleagues note that any group of replicas that can talk to each other converges, even while cut off from the rest, and no consensus protocol is needed.

CRDT merge limits

A CRDT merge cannot decide what people intended, and it cannot stop changes that are each valid from breaking a rule together. Convergence means every device agrees, not that everyone gets what they intended. The data type picks the outcome in advance:

  • A set has to choose whether a concurrent add or remove of the same item wins. The comprehensive study shows that a replicated set cannot behave exactly like a sequential one, so every CRDT set is an approximation with a stated rule.
  • A last-writer-wins register keeps one of two concurrent values and drops the other.
  • Two people can each book the last seat, and both bookings merge cleanly into a state that breaks the rule. Shapiro’s paper defines a conflict as concurrent updates that are each correct but together violate an invariant, and a merge alone cannot prevent that.

Metadata has a cost too. In some CRDTs a deleted item leaves a tombstone so that a late concurrent edit still has something to refer to, and the comprehensive study reports that CRDTs tend to become inefficient as tombstones accumulate. For choosing between merging, keeping both versions and asking an authority, see how sync conflicts are resolved. The kinds of CRDT article covers which rule each common type uses.

Frequently asked questions

Do CRDTs need a server to merge changes?

No. The merge runs on each replica, so two devices can merge directly with each other. A server can still be useful to relay or store changes, but it is one more replica rather than the place where conflicts are decided.

Is a state-based CRDT better than an operation-based one?

Neither is better in general. State-based CRDTs ask little of the network but can send a lot of data; operation-based CRDTs send small operations but need every operation delivered once, in causal order. Each style can emulate the other.

What is the difference between a CvRDT and a CmRDT?

CvRDT, convergent replicated data type, is the older name for a state-based CRDT, which sends whole states and merges them. CmRDT, commutative replicated data type, is the older name for an operation-based CRDT, which sends operations that must commute.

Why does a grow-only counter take the larger value instead of adding on merge?

Adding the entries together would be wrong, because receiving the same state twice would count it twice. Taking the larger value for each replica's entry keeps the merge idempotent, and the counter's value is the sum of the entries.

What is a delta CRDT?

A delta CRDT is state-based, but replicas send only the part of the state that changed. It sits between state-based CRDTs, which send whole states, and operation-based ones.

Can a CRDT stop two people booking the same last seat?

No. Both bookings merge cleanly into a state that breaks the rule. Shapiro's paper defines a conflict as concurrent updates that are each correct but together violate an invariant, and a merge alone cannot prevent that.

Sources

Build it with Offline Protocol

The shared state guide shows how replicated documents in the Offline Protocol Mesh SDK merge when peers reconnect, lists the merge behaviour of each collection type, and gives steps for testing edits made on both sides of a partition.

Read the shared state guide