CRDTs

The last lesson ended with a weight in your hands: the convergence contract — deterministic, order-blind, counted once — to be hand-written, correctly, for every field of every feature, forever. Then it made a promise: a counter that can't miscount, a set that unions itself, data types where the merge is built in and mathematically incapable of the trap.

This lesson delivers those objects. They're called CRDTs, conflict-free replicated data types, and the name undersells the move. You don't write a smarter merge policy and bolt it onto your data. You pick data whose shape makes bad merges impossible, the way a round peg makes square holes irrelevant. Once you see the trick, you'll recognize it running inside systems you already use: your Redis clusters spread across regions, the presence list in a chat app, the notes app on your phone syncing after a flight.

Recall what the contract demands of any resolver, then ask an odd question: what if the value itself were the resolver? A replica holds a state; another state arrives; the value merges the two. For that to satisfy the contract no matter what the network does, the merge function needs exactly three properties.

Any order. merge(a, b) must equal merge(b, a), because you can't control which direction of the exchange lands first.

Any grouping. merge(a, merge(b, c)) must equal merge(merge(a, b), c), because with three replicas gossiping, states arrive pre-combined in whatever pairings the network happened to produce.

Any repeats. merge(a, a) must equal a, because sync loops love to re-deliver, and the second delivery must count for nothing.

Now notice which functions pass. Taking the maximum of two numbers: passes all three. Union of two sets: passes all three. Elementwise max of two vectors, OR of two booleans: pass. And notice which fail: addition double-counts on repeats; average depends on grouping; overwrite depends on order. The passing family shares one character: each merge can only move forward, absorbing information and never un-knowing it. Mathematicians call the structure a join semilattice; you can call it the max family and lose nothing. Every CRDT in this lesson is a value dressed up so that its merge is some flavor of max-or-union, which is why none of them can build the divergence trap, even by accident.

Try to build a replicated like-counter and the naive designs fall exactly the way The Conflict Problem taught. Keep one integer and overwrite on sync: two concurrent +1s, one survives: a like silently gone. Add the incoming total to yours instead: now a re-delivered state counts twice. One design fails intent, the other fails the counted-once law.

The fix is a shape you already own. In Vector Clocks the rule was: one counter per machine: tick your own slot, send the whole vector, take the elementwise max on receive. That exact object, read as data instead of as a detector, is the G-Counter. Each device increments only its own slot, so slots never race. The displayed value is the sum of all slots. The merge is per-slot max: order-blind, grouping-blind, repeat-proof, straight from the max family. Two +1s on two devices land in two different slots; nothing can overwrite anything; the count is exact, always. The same shape that once detected concurrency now absorbs it.

Decrements need one honest trick. You can't subtract inside a max-only world; a smaller number just loses the merge. So run two grow-only counters: P for increments, N for decrements, value = P minus N. That's the PN-Counter, and it's the whole design: unlikes, inventory drains, seat counts, anything that counts down rides a second counter that only counts up.

Sets look easier and are secretly the hard case. A grow-only set (merge is union, done) is a perfect CRDT right until someone wants to remove something, and someone always does.

You already know union's flaw by name: the union has no losers, and no memory of losses. Delete the umbrella on your phone, merge with the laptop that still has it, and the umbrella climbs back out of the grave: the exact resurrection the famous shopping cart accepted as a business decision. First patch: remember deletions in a second grow-only set of tombstones; an element is present if it's in the adds and not in the deletes. Convergent, yes. And now removal is forever: re-adding the umbrella next winter is impossible, because the tombstone always wins. One wrong turn (resurrection) traded for another (permanent death).

The honest fix is the OR-Set, the observed-remove set. Every add gets a unique tag, invisible to users. A remove doesn't kill the element; it kills the specific tags it has observed. A concurrent re-add carries a fresh tag the remove never saw, so it survives: add wins, deliberately, and deletion works whenever the remover actually saw what it was deleting. If that behavior feels familiar, it should: the honest-merge mode you drove in the divergence trap, where a raced delete lost loudly to a newer add, was this exact move. The price is metadata: tags to carry, tombstone bookkeeping to eventually collect. A CRDT doesn't forget; it remembers deletions so it can defend them.

Below are two devices sharing a likes counter and a tag set, with the machinery visible. Start in naive sync: cut the link, click +1 on both sides a few times, heal, sync. The ground-truth strip counted your actual clicks, so read exactly how many likes the overwrite just spent. Then flip to CRDT sync and run the same abuse: the counter shows its per-device slots merging by max, the tags show their add-wins fights, and EXACT stays green no matter what you do.

Then prove the laws to yourself, because buttons beat belief: flip delivery order re-runs the exchange in the opposite direction: nothing changes. Deliver again re-ships the last state: nothing changes. Order-blind, counted once, live under your finger.

Everything above moved states: send your whole value, merge on arrival. The 2011 paper that named this field (Shapiro, Preguiça, Baquero, and Zawirski) calls these state-based CRDTs, and their whole appeal is indifference: states can arrive late, duplicated, out of order, over any transport, and the max family absorbs it all. The cost is size: shipping a whole counter vector to move one like. The refinement, delta CRDTs, ships only the recently-changed fragment and merges it the same way.

The alternative is operation-based: broadcast the operations themselves, increment, add sunscreen, and require every replica to apply each one exactly once, in causal order. Smaller messages, heavier demands on the messenger: the counted-once law stops being free and becomes the delivery layer's problem.

Either way, the guarantee earned has a name worth knowing: strong eventual consistency. Eventual consistency promises replicas eventually agree on something; SEC promises that any two replicas that have seen the same updates are in the same state right now, no reconciliation pending. It is the convergence contract from last lesson, upgraded from a design goal to a theorem you inherit by picking the shape.

And the bill, plainly: per-device slots that outlive devices, tags on every add, tombstones awaiting garbage collection. CRDT metadata is the mortgage on never having to write a merge policy again: usually worth it, never free.

Here is the sentence that keeps CRDTs honest: they guarantee that replicas agree, not that what they agree on satisfies your business rules.

Watch it break. A PN-Counter tracks stock for the last concert ticket: one left. Two regions each sell it (each decrement is perfectly legal locally) and the merged counter reads minus one, exactly, on every replica, forever. Converged, consistent, and wrong in the only way your CFO cares about. The same wall stands behind every contradiction from last lesson: seat 14A can't compose, a unique username can't union, a balance floor can't max. No tag scheme makes two incompatible truths compatible.

So the map stays split the way The Conflict Problem drew it. Compose-shaped data — counts, memberships, presence, flags — crosses into CRDT country and never conflicts again. Contradiction-shaped data still needs one answer, which means an owner, a majority, or an application that refuses: the door this course already built, one section ago. CRDTs abolish the trap. They do not abolish the dilemma.

This is production machinery, not a research toy.

Redis Enterprise sells the whole lesson as a product: in active-active geo-replication, INCR rides a counter CRDT, SADD rides observed-remove set semantics, and plain SET strings fall back to last-write-wins: the three stars of this lesson and its confession, in one command table. Riak ships counters, sets, flags, registers, and nestable maps as data types, citing the 2011 authors by name; the same store that taught this course siblings now hands you types that never produce one. Phoenix Presence keeps who's-online-in-this-room as a CRDT replicated over a gossip protocol: presence is news, the mail rides the heartbeats, and no server owns the room. Apple Notes syncs your offline edits across devices with state-based CRDTs under the hood. And libraries like Automerge and Yjs package entire JSON documents as CRDTs for local-first, collaborative apps.

Notice what the whole roll call is made of: counts, sets, presence, registers, maps of the same. Compose-shaped, all of it. That's not an accident; that's the border, holding.

• The trick: don't write a merge policy — pick a value whose merge is a law. Any order, any grouping, any repeats: the max family (max, union, elementwise max) passes all three, so the divergence trap can't be built.
• A counter that can't miscount: one slot per device, tick only your own, merge by per-slot max, value is the sum. The vector clock's shape, promoted from detector to data. Decrements ride a second grow-only counter: P minus N.
• A set that unions itself, deletion included: union resurrects, tombstones kill forever, and the observed-remove set threads the needle: removes kill only the tags they saw, so a concurrent re-add wins, loudly and by design.
• State-based or op-based, the prize is strong eventual consistency: same updates, same state, as a theorem. The mortgage is metadata: slots, tags, tombstones. A CRDT remembers deletions so it can defend them.
• Converged is not correct. Two regions can sell the last ticket and agree perfectly on minus one. Compose-shaped data crosses the border; contradictions still need the one-answer door.

One data type sat this lesson out, and it's the one you're staring at right now: text. A document is a sequence — position is meaning, and "insert after the third word" collides with a concurrent edit that moved the third word. Union has no answer; order is the whole point. Making two cursors share one sentence took a different weapon (transform the operations against each other) and it carried Google Docs for two decades. That machine is next: Operational Transformation.