CRDTs: the catalog, real deployments, and the invariant they cannot save

What it is

A CRDT (Conflict-free Replicated Data Type) is a data structure whose merge operation is defined so that replicas which receive the same set of updates, in any order, with any duplication, end up in the same state. No coordination, no leader, no consensus round. You write locally, you gossip your state or your operations, and convergence is a mathematical property of the type rather than a protocol guarantee.

The property that makes it work is that the merge function is commutative, associative and idempotent. Those three words are the whole idea:

Commutative: merge(a, b) = merge(b, a), so message order does not matter.
Associative: merge(merge(a, b), c) = merge(a, merge(b, c)), so grouping does not matter.
Idempotent: merge(a, a) = a, so redelivery does not matter.

A function with those properties defines a join-semilattice, and repeated merging drives every replica to the least upper bound of all updates. That is convergence, proved rather than engineered.

What CRDTs are confused with: they are not a general replacement for transactions, and they are not "eventual consistency done right." They provide strong eventual consistency, which is a genuinely stronger property than plain eventual consistency (no conflict resolution is needed, ever, and there is no "last writer wins" data loss), but they achieve it by restricting what operations are expressible. The restriction is the price, and most discussions skip it.

This page is the type catalog and the deployment record. The multi-region design angle (which data type to pick for which field, and how it interacts with a regional topology) is on the conflict resolution page; the two are meant to be read together.

The problem it solves

Two users edit the same shopping cart from two devices while offline. Or two data centres accept writes to the same key during a partition. Or a mobile client makes changes on a plane and syncs on landing. In every case you have concurrent updates with no common ordering, and three unattractive options:

Refuse the write. Requires coordination, which requires availability of a quorum, which is exactly what you do not have during a partition. This is the CP corner of CAP.
Accept and pick a winner (last-writer-wins). Cheap, and silently loses data. If one user adds a book and the other adds a lamp, LWW keeps one item and discards the other, and nobody is told.
Accept and surface a conflict. This is what Dynamo did with sibling versions, and it pushes the resolution logic into every application that reads the value. It works, but every read path now needs merge logic, and it will be written inconsistently across teams.

CRDTs are the fourth option: accept, and define the type so that merging is unambiguous. Add the book and add the lamp, and the cart has both, because the type is a set and set union is the merge.

The famous demonstration of why this matters is Amazon's shopping cart in the Dynamo paper: their resolution rule was set union, which meant removed items could reappear (a known and accepted anomaly) but added items were never lost. They chose the direction of the error deliberately, and adding an unwanted item to a cart is a recoverable annoyance while losing a purchase is lost revenue.

Mechanics

The two families

State-based (CvRDT). Replicas exchange their whole state; the receiver merges. Simple, and robust to any message loss or duplication because merging is idempotent, but the messages are as large as the state. Delta-state CRDTs are the practical refinement: ship only the part of the lattice that changed, with periodic full-state anti-entropy as a safety net.

Operation-based (CmRDT). Replicas broadcast operations. Messages are tiny, but the delivery layer must guarantee exactly-once, causally-ordered delivery, which is real infrastructure you now own. In practice most systems are state-based or delta-state because the delivery requirement is heavier than it looks.

The catalog

G-Counter (grow-only counter). State is a vector, one slot per replica. Each replica increments only its own slot. Merge is element-wise max; the value is the sum.

def merge(a, b):                       # a, b: dict replica_id -> int
    return {k: max(a.get(k, 0), b.get(k, 0)) for k in a.keys() | b.keys()}

def value(c):
    return sum(c.values())

Element-wise max is commutative, associative and idempotent, so this converges. Note what makes it work: a replica never modifies another replica's slot, so there is nothing to conflict over.

PN-Counter. Two G-Counters, one for increments and one for decrements; value is sum(P) - sum(N). This is how you get a decrementable counter without a coordination point. It is also where the fundamental limitation first shows up, and we return to that below.

G-Set (grow-only set). Merge is union. Trivially a lattice.

2P-Set (two-phase set). An add-set and a tombstone-set; an element is present if it is in adds and not in removes. Once removed, an element can never be added again, which is often unacceptable.

LWW-Element-Set. Timestamps on adds and removes; the later one wins. Reintroduces the clock problem (see time and clocks) and therefore reintroduces the possibility of losing an update to clock skew. It is a CRDT by the letter of the definition and it does lose data.

OR-Set (observed-remove set). The one that actually behaves the way people expect a set to behave. Every add attaches a unique tag; a remove deletes exactly the tags the removing replica has observed. Concurrent add-and-remove resolves in favour of the add, because the remove could not have observed the concurrent add's tag.

# state: element -> set of unique tags
def add(state, e, replica_id, counter):
    state.setdefault(e, set()).add((replica_id, counter))

def remove(state, e):
    state.pop(e, None)          # removes only the tags THIS replica has seen

def merge(a, b):
    out = {}
    for e in a.keys() | b.keys():
        tags = a.get(e, set()) | b.get(e, set())
        if tags:
            out[e] = tags
    return out

The naive implementation accumulates tombstones forever; real implementations (Riak, Akka, Automerge) compress them using version vectors, which is most of the engineering effort in a production CRDT library.

MV-Register (multi-value register). Keeps all concurrent writes as siblings and hands them to the application. Honest, and pushes the decision up a layer.

RGA / Logoot / YATA / Fugue (sequence CRDTs). Ordered lists for collaborative text. Each character gets an identifier positioned between its neighbours in a dense total order, so concurrent insertions at the same cursor position get distinct stable positions. These are what a collaborative editor runs on, and they are considerably more complex than the counter and set types. YATA underpins Yjs; RGA-family algorithms underpin Automerge.

Maps. Compose the above: a map whose values are themselves CRDTs, with a recursive merge. Riak Maps and Redis Enterprise's CRDT types both work this way, and it is how you build a document.

A worked merge

Two replicas, an OR-Set representing a shared shopping cart, starting empty.

Step	Replica A	Replica B
1	`add("book")` → `{book: {(A,1)}}`
2	(gossip A → B)	`{book: {(A,1)}}`
3	`remove("book")` → `{}`	`add("lamp")` → `{book: {(A,1)}, lamp: {(B,1)}}`
4		`add("book")` → `{book: {(A,1),(B,2)}, lamp: {(B,1)}}`

Now they merge. A's state is {} (it removed the only tag it had seen, (A,1)). B's state is {book: {(A,1),(B,2)}, lamp: {(B,1)}}.

A naive union of the elements would give the wrong answer either way. The OR-Set merge works over tags, and A's removal is encoded as the absence of (A,1) from its state:

book: A has no tags for it, B has {(A,1),(B,2)}. But A's removal must suppress (A,1) specifically. A production implementation carries a version vector recording that A has seen (A,1) and removed it, so the merge drops (A,1) and keeps (B,2), because A never observed (B,2). Result: book is present, tagged {(B,2)}.
lamp: only in B, and A never observed it. Present.

Final converged state on both replicas: {book, lamp}. The concurrent add-after-remove of book wins over A's remove, which is the intended OR-Set semantic: a remove cancels only what it saw.

The naive tag-set-union implementation above (without version vectors) would resurrect book under {(A,1),(B,2)} and converge to the same elements, which is why the simple version is adequate for teaching and inadequate for production. The difference shows up as tombstone growth and as anomalies in remove-heavy workloads.

Production evidence

Riak shipped CRDTs as first-class database types in 2.0 (counters, sets, maps, flags, registers), built on the riak_dt library with Basho engineers working directly with Carlos Baquero and Marc Shapiro's group. This is the reference deployment for "CRDTs as a database feature" rather than a library.

Redis Enterprise implements active-active geo-replication using CRDTs ("conflict-free replicated databases"), mapping Redis types onto CRDT semantics so that INCR on two regions sums rather than overwrites, and set operations union. Notably, they document which Redis commands have well-defined active-active semantics and which do not, which is the honest way to ship this.

Automerge and Yjs are the two widely-used sequence-CRDT libraries for collaborative applications. Yjs's YATA algorithm underpins a large number of collaborative editors; Automerge's published benchmarks and its rewrite in Rust were driven by the memory overhead problem, which was the practical barrier to CRDT adoption in editors.

Figma is the counter-example that is worth knowing, and their engineering blog says so explicitly: they evaluated CRDTs and chose a server-authoritative Operational Transformation-like model instead, because a central server is something they have anyway, and it lets them use much simpler data structures with lower memory overhead. Their write-up is the fairest published critique of CRDTs from a team that seriously considered them.

Soundcloud's Roshi was a widely-cited LWW-element-set implementation over Redis for a time-ordered event stream, and it is a good example of choosing the simplest CRDT that fits rather than the most general.

Akka Distributed Data provides CRDT types for cluster state sharing in the JVM ecosystem, using delta-state replication with gossip, and is the most common way JVM teams meet these types in practice.

The debate

The argument for CRDTs is availability without data loss: writes succeed during a partition, and no update is silently discarded. For offline-first and multi-primary geo-replication, that is a genuinely different capability from anything coordination-based, and the alternatives (LWW, sibling resolution in application code) are worse in specific, demonstrable ways.

The arguments against are three, and all three are real.

Metadata cost. A CRDT carries per-element bookkeeping: tags, version vectors, tombstones. Automerge's early versions used far more memory than the document they represented, and tombstone accumulation in a long-lived OR-Set is a genuine operational problem requiring compaction machinery. Figma's evaluation cited exactly this.

Semantics that surprise users. The counter is the clean case; the set is mostly fine; the map with nested removes and the sequence with concurrent formatting are where converged states are legal but look wrong to a human. Two users concurrently making a paragraph bold and italic is fine; two users concurrently reordering the same list produces a legal interleaving that neither intended.

And the one that ends most discussions: CRDTs cannot maintain a global invariant. This is not an implementation limitation, it is inherent. A CRDT converges because every replica can accept every operation without asking anyone. An invariant like "the balance never goes below zero" or "at most 100 seats are sold" is a statement about the combined state, which no replica can evaluate alone. Two replicas each holding a balance of 50 will each happily accept a withdrawal of 50, and the merged state is -50. The PN-Counter converged perfectly and the business rule is violated.

The formal statement of this is in Bailis et al.'s work on invariant confluence: an invariant can be maintained without coordination if and only if it is preserved under merge of any two reachable states. Set membership is I-confluent; a lower bound on a decrementable counter is not. Coordination avoidance is possible exactly when the invariant is I-confluent, and no data structure choice changes that.

My position. Use CRDTs where the data is genuinely additive or set-like and the business has no cross-replica invariant on it: presence, tags, labels, likes, feature flags, shopping carts, view counts, collaborative documents, cluster membership. Do not use them for anything with a threshold, a balance, or a uniqueness constraint. And in a system that has a reliable central server anyway, consider whether server-side ordering solves the problem with a tenth of the complexity, because for a great many products it does. The engineering question is not "are CRDTs elegant," it is "am I actually operating without a coordination point, or am I paying CRDT complexity for a partition scenario I do not have."

An intermediate design worth knowing: escrow / reservation. Split a bounded resource into per-replica allocations (each region gets 25 of 100 seats). Within its allocation each replica operates coordination-free; only when a replica exhausts its share does it need to coordinate to borrow. This turns a coordination-per-operation cost into coordination-per-rebalance, and it is how you get most of the CRDT benefit on data that does have an invariant.

Follow-up Q&A

"Why can't a CRDT enforce a non-negative balance?"

Because enforcement requires knowing the combined state at decision time, and the whole point of a CRDT is that a replica decides locally. Replica A sees 50 and allows a withdrawal of 50; replica B concurrently sees 50 and allows the same. Both operations are valid against the state each replica could observe, and the merge is -50. The convergence guarantee is intact. The invariant is not, because it was never a property that merging preserves. Bailis's I-confluence formalises exactly which invariants survive this. The practical answers are escrow (pre-allocate budget per replica) or coordination for that specific operation.

"State-based or operation-based, and why?"

Delta-state, in almost every case. Pure state-based ships the whole structure, which is fine for a small counter and unusable for a document. Operation-based ships almost nothing but requires exactly-once causal delivery, meaning you now own a reliable causal broadcast layer, which is comparable work to what you were avoiding. Delta-state ships the changed portion of the lattice with idempotent merge, so duplicates and reordering are still harmless, and periodic full-state anti-entropy repairs anything lost. That is what Akka Distributed Data and modern Riak-style implementations do.

"How do you stop tombstones from growing forever?"

Version vectors instead of raw tag sets: a replica records "I have seen everything from A up to counter 400," which represents 400 tombstones in one entry. Then garbage collect a tombstone once every replica's version vector dominates it, which requires knowing the full membership and that every member is live, which is why tombstone GC is where CRDT implementations get operationally awkward. A replica that is offline for a month blocks GC, and the usual practical answer is to declare a maximum divergence window after which a stale replica must full-sync rather than merge.

"How is this different from Dynamo's sibling values?"

Dynamo detects concurrency with vector clocks and hands the application a set of siblings to resolve. A CRDT is the resolution, encoded in the type, so the application never sees a conflict. The difference is where the merge logic lives: scattered across every read path in every service versus once in the data type. In practice that also means the CRDT version is consistently correct and the sibling version is correct in the services whose authors thought about it carefully.

"When would you use LWW even knowing it loses writes?"

When the field is a fact about the world with a single source of truth and the latest observation is definitionally the right one: a device's last-known battery level, a user's current display name, a sensor reading. There is no meaningful merge of two display names, and keeping both is worse than keeping the later one. The requirement is that you also have trustworthy timestamps, which in practice means a hybrid logical clock or a bounded-uncertainty clock rather than System.currentTimeMillis() on machines with 200 milliseconds of skew.

"Do CRDTs violate CAP?"

No, they sit precisely where CAP says they can: AP with strong eventual consistency. They do not provide linearizability and cannot. What they add over naive AP systems is that convergence requires no application-level conflict resolution and loses no updates, which is a stronger guarantee than "eventually consistent" as normally used but strictly weaker than C in CAP terms.

Common misconceptions

"CRDTs give you consistency without consensus." They give you convergence without consensus. Convergence means all replicas agree on the final state; consistency in the transactional sense means the state satisfies your invariants, and CRDTs offer nothing there. Conflating the two is the single most common error in CRDT discussions.

"CRDTs make merge conflicts impossible." They make merge conflicts syntactically impossible. Semantically undesirable outcomes remain entirely possible: the resurrection of a removed item, an interleaving of two concurrent list reorderings, a converged document neither author wanted. Convergence says everyone sees the same thing, not that the thing is what anyone wanted.

"Last-writer-wins is not a CRDT." LWW-Register satisfies the definition: max-by-timestamp is commutative, associative and idempotent given a total order on timestamps. It is a perfectly valid CRDT that discards data. This is a useful reminder that "is a CRDT" is a much weaker claim than "preserves your updates."

"They are only for text editors." Collaborative editing is the most visible use, but counters, sets, flags and maps in geo-replicated databases and in cluster membership state (Akka, Riak, Redis Enterprise) are the higher-volume production use by a wide margin, and they are far simpler than the sequence types.

"If I use CRDTs I do not need to think about clocks." Only true for the clock-free types (G-Counter, G-Set, OR-Set). The moment you use LWW-Register or LWW-Element-Set, clock skew determines which write survives, and you are back to needing hybrid logical clocks or bounded-uncertainty clocks.

Interview delivery note

The sentence to have ready: "CRDTs give you strong eventual consistency without coordination, and the price is that they cannot enforce any invariant over the combined state, so I use them for additive and set-like data and I use escrow or coordination for anything with a threshold." That is the whole trade in one line, and it states the limitation before the interviewer has to ask for it.

The senior-versus-staff separator is naming the invariant limitation unprompted, ideally with the invariant-confluence framing. Anyone can list G-Counter, PN-Counter, OR-Set. The staff-level move is to say "this converges and still breaks the business rule," give the balance example with numbers, and then offer escrow as the design that recovers most of the benefit. The second signal is citing Figma: being able to say "a serious team evaluated these and chose not to use them, for these reasons" shows you are reasoning about a tool rather than advocating for one.

If the interviewer proposes CRDTs for a bounded resource (inventory, seats, rate limits), do not go along with it. That is a planted error in a well-designed interview, and catching it is worth more than any amount of catalog recall.

The Staff & Team Lead Interview Reference