CRDTs

A family keeps one shopping list on two phones. One person is in the metro with no signal and ticks off milk, because they just bought some. At home, the other notices the milk has run out again and adds it. Twenty minutes later both phones are online. What should the list say?

No server was there to decide, and no clock can be trusted to settle it. The two edits happened without either phone seeing the other's. Most systems would quietly pick one and lose the other. A CRDT is a way of designing the data so that the two phones merge on their own, always to the same answer, without losing either edit.

Replicas that merge on their own#

The chapters so far gave you two ways to keep copies of data in step. Consensus makes every write wait for a majority, so it is correct and stops working on the minority side of a split. Last write wins accepts every write everywhere and silently drops one of two concurrent ones.

CRDTs (conflict-free replicated data types, named in a 2011 paper by Marc Shapiro and colleagues) take a third path. Every replica accepts writes locally, with no coordination, and the data type comes with a merge that is guaranteed to bring replicas to the same state once they have seen the same updates, in any order. That guarantee is called strong eventual consistency: no conflicts to resolve by hand, no write thrown away, no waiting.

The catch is that you cannot do this with any data type. The merge must have three properties:

Commutative: merging A into B gives the same result as merging B into A. So the order updates arrive in does not matter, and you do not need clocks to order them.

Associative: merging A with B and then C is the same as A with the result of B and C. So it does not matter which replica gossips with which first.

Idempotent: merging the same state twice changes nothing. So duplicate delivery, the whole problem of the exactly-once chapter, simply stops mattering.

Those three properties make the two hardest problems of this path (ordering and duplicates) irrelevant. The rest of this chapter is about which data can be shaped to have them.

Counters#

Start with the like counter from the question above. Switch between the two merge rules, add likes on both sides, and sync. Then press Sync again.

A single number cannot be merged correctly. Mumbai says 140 and Singapore says 125. Is the answer 140, 125, or 265? From two numbers alone you cannot tell what each side added.

A G-counter (grow-only counter) keeps one slot per replica, and each replica only ever increases its own slot. To merge, take the larger value of each slot. The total is the sum of the slots. Taking the larger of two numbers is commutative, associative and idempotent, so the whole counter is too.

// replica id -> how many increments that replica has made
type GCounter = Record<string, number>
 
const increment = (c: GCounter, me: string): GCounter => ({ ...c, [me]: (c[me] ?? 0) + 1 })
 
const value = (c: GCounter): number => Object.values(c).reduce((sum, n) => sum + n, 0)
 
// For every replica, keep the larger count. Order, grouping and repeats make no difference.
function merge(a: GCounter, b: GCounter): GCounter {
  const out: GCounter = { ...a }
  for (const [id, n] of Object.entries(b)) out[id] = Math.max(out[id] ?? 0, n)
  return out
}

Need to count down too, for unlikes? A PN-counter is two G-counters, one for increments and one for decrements, and the value is the first total minus the second. Each half only grows, so each half merges safely.

This is the pattern behind every CRDT: keep enough history in the state that merging can never go backwards.

Registers: a single value#

A register holds one value, like a profile photo or a delivery address. There are two honest options.

LWW register: keep the value with the highest timestamp. It is a real CRDT (taking the maximum is commutative, associative and idempotent) and every replica will agree. They will agree on a value chosen by clocks, so one of two concurrent writes is still lost, with all the skew problems from the clocks chapter.

Multi-value register: track versions with a vector clock, and when two writes are concurrent, keep both and show both. This is what Amazon's Dynamo did for its shopping cart. Nothing is lost, and someone (the app or the user) has to choose.

Sets: the shopping list#

Back to the milk. Try the second tab of the widget: remove milk on one phone, add it on the other, sync, and compare the two rules. Then do the same two actions in the other order.

With last write wins, the answer depends on which edit has the later timestamp, which is an accident of timing (or of clock skew). The person at the shop might find milk missing from the list though they added it.

An OR-Set (observed-remove set) fixes this. Each add creates a unique tag, like A0 or B1. A remove does not delete "milk"; it deletes the specific tags the removing phone has seen. Merging takes the union of all tags and the union of all removed tags. Milk is on the list if any of its tags has not been removed.

When one phone removes milk while the other adds it, the remove only covers the old tag. The new add's tag survives. A concurrent add and remove always ends with the item present, in either order, on every replica. That rule is called add wins, and for a shopping list it is the right one: it is better to buy milk twice than to forget it.

The cost is visible in the widget's small print: removed tags have to be remembered (tombstones) so that an old add arriving late is recognised as already removed.

Text and documents#

Collaborative editors are the most famous use. The hard part is position: "insert 'x' at index 5" means something different once someone else has inserted text before index 5. Text CRDTs give every character a unique, permanent id and describe each insert relative to its neighbours' ids instead of by index, so concurrent inserts always land in the same place on every replica. Yjs and Automerge are the two libraries you will hear about. Design a collaborative editor compares this, step by step, with the server based alternative, operational transformation.

What CRDTs cannot do#

CRDTs work because no replica ever has to ask another one before acting. Any rule that does need asking is out of reach.

Invariants across replicas. "The wallet balance never goes below zero." Mumbai and Singapore both see ₹600 and both approve a ₹500 payment. Each decision was locally correct, and the merged balance is −₹400. Nothing in a merge can undo a payment that already left. The same goes for "only one person gets seat 42" and "usernames are unique". These need coordination: consensus, a single owner per key, or splitting the budget up front (each region may spend up to ₹300 without asking).

Unbounded history, for free. Tombstones and per-replica slots grow. Throwing old tombstones away is safe only once every replica has seen the delete, and if a replica can stay offline for a month, you cannot know that. CRDT documents grow over time for this reason, and libraries spend a lot of effort compacting them.

Your intent. Add wins is a choice. So is remove wins. A CRDT guarantees replicas agree, not that they agree on what the user wanted. Pick the rule per field, deliberately.

Checkpoint#