CRDTs: data types that always merge

Mei and Tomas share a grocery list app. Each phone keeps a full copy of the list and edits it locally, because the supermarket basement has no signal. When a phone reconnects, it syncs its copy with the server and through it with the other phone. Both may have changed the list in the meantime, and there is no moment when the two could have agreed first.

Multi-region replication shows the usual shortcut, last writer wins, and how it silently drops one side's change. A conflict-free replicated data type (CRDT) instead defines a merge that combines both sides. Such a merge needs three properties: it must be commutative (order doesn't matter), associative (grouping doesn't matter) and idempotent (merging the same thing twice changes nothing).

With those three properties, replicas that have received the same updates are in the same state, whatever order the updates came in and however often they were repeated. This is called strong eventual consistency (Consistency models). The rest of this page is about designing merges with those properties for real data types.

The list says 6 eggs. Offline, Mei adds 2 and Tomas adds 1, so the right answer is 9. The obvious merges both fail. Keeping the larger total gives max(8, 7) = 8, losing Tomas's egg. Adding up increments as they arrive works until one sync is delivered twice, which networks do.

That last design is the G-Counter, a grow-only counter. Each replica increments only its own entry. Merging takes the maximum of each entry, which is commutative, associative and idempotent; the value is the sum of all entries. A repeated sync changes nothing, because max(2, 2) is still 2. A PN-Counter supports decrements with two G-Counters, one for increments and one for decrements, and reports the difference.

It resembles a vector clock: one entry per node (Time, clocks & ordering). It also shows the cost: the state grows with the number of replicas, not with the value.

Adding is easy: merging two copies of a set takes their union, which already has all three properties. Removing is where meaning comes in. In the store, Mei buys milk and removes it from the list. At home, at the same moment, Tomas opens the fridge, sees the milk is low and adds it again. Neither saw the other's change. Should milk be on the list?

This is the OR-Set, or observed-remove set: a remove applies only to the adds it has seen, so a concurrent add wins. Redis's active-active databases and Akka's ORSet both use this add-wins rule. The simpler 2P-Set keeps a second set of removed elements, nicknamed the tombstone set. Remove wins, and an element can never be added again: once milk is removed, it's gone for good, which is wrong for a grocery list.

Some fields hold one value, such as the list's name. If Mei renames it "Saturday" and Tomas renames it "Weekend shop" while both are offline, there is no merge that respects both. A register CRDT must pick a rule.

The two common rules:

• Last-writer-wins register: keep the value with the higher timestamp. Simple and convergent, but it discards one write, and clocks drift. Redis stores a wall-clock timestamp with every string for this purpose, which is safe only where it doesn't matter which of two updates made within the clock skew wins.
• Multi-value register: keep every concurrent value, tracked with version vectors, and let the app or the user choose, the way Riak returns concurrent versions of plain values as siblings.

Real documents are maps of these types nested together. Automerge, which models JSON-like documents as CRDTs, merges concurrent changes to different fields automatically. In practice, conflicts are rarer than expected: they arise only when two people change the same property of the same object, and then the CRDT keeps both values for the app to resolve.

There are two ways to keep replicas in step:

• State-based CRDTs send their whole state, and the receiver merges it. Because merging is idempotent and order-free, the network may drop, repeat and reorder messages freely.
• Operation-based CRDTs send each operation, "add milk with tag b7". Messages are small, but the network must deliver each one exactly once and in causal order, so retries and ordering become the transport's job.

Delta-state CRDTs sit between them. A replica sends only the part of its state that changed, which is merged like a full state. Akka's example: adding c and d to the set {a, b} sends the delta {c, d}. Some types tolerate deltas in any order; others, such as Akka's maps, need deltas delivered causally.

Size still matters. Akka replicates a whole map on each update, so one map of 1,000 elements is better split into 10 entries of 100. The trade-off is that separate entries replicate at different times and can't be updated together atomically.

A merge sees two copies, never the whole system, so a CRDT can't enforce a rule that depends on everyone. The classic example is a counter that must never go below zero. Each replica can refuse to decrement at 0, but two replicas at 1 can each decrement once, and the merged value is -1. The same goes for keeping a tree free of cycles, or not selling the last ticket twice (Inventory & booking contention).

Such operations need coordination. The common design: updates that commute run without coordination, and the rare operation that needs agreement, such as checkout in a shopping cart, synchronizes. For the grocery list, nothing needs it; for a shared bank balance, the withdrawal does.

The other cost is metadata. Counters keep an entry per replica, OR-Sets keep tags for elements, and removed elements can leave tombstones. Some designs grow without bound, and collecting the garbage needs some synchronization, kept off the critical path. Shared text needs sequence CRDTs of its own (Collaborative editing).

CRDTs are in production in several forms: as data types inside databases (Redis active-active, Riak), as a replicated-data library for a cluster (Akka Distributed Data), and as document libraries for collaborative and offline apps (Automerge, Yjs). In each case the developer chooses the type per field, and the type decides how conflicts end.