CRDTs: Conflict-Free Replicated Data Types

TL;DR: A CRDT is a data structure whose replicas can be updated concurrently on different nodes, without coordination, and are mathematically guaranteed to converge once all updates are delivered. This property is called Strong Eventual Consistency (SEC)^[1]. State-based CRDTs (CvRDTs) merge full states via a join-semilattice; op-based CRDTs (CmRDTs) broadcast commutative operations over causal delivery. CRDTs power Redis Enterprise Active-Active, Yjs (~4M npm downloads/week^[2]), and Automerge; Figma's multiplayer engine is CRDT-inspired but uses a centralized server-orders-events approach rather than true CRDTs^[3]. The trade-off: you pay metadata overhead and give up sequential consistency to get availability with zero coordination.

Learning Objectives#

After this module, you will be able to:

• Distinguish CvRDTs (state-based) from CmRDTs (op-based) and explain when each applies
• Implement G-Counter, PN-Counter, and OR-Set from first principles
• Choose a CRDT for a given use case (counters, sets, text, JSON documents)
• Explain why CRDTs achieve strong eventual consistency without consensus
• Recognize the costs: metadata growth, tombstones, garbage collection complexity
• Articulate why LWW-Register silently loses data and when to avoid it

Intuition#

Imagine two accountants in different cities, each keeping a ledger for the same company. Throughout the day, both record transactions independently. At closing time, they call each other and merge their books. If both use a simple rule, "for each account, take the higher balance," they will always agree on the final state without arguing about whose entry came first. No coordinator needed. No lock. No waiting.

Now imagine a collaborative whiteboard. Two designers draw strokes simultaneously. Each stroke gets a unique ID. When the strokes sync, neither erases the other because they are tagged differently. The whiteboard converges to "both strokes present" without conflict resolution logic.

That is the CRDT idea: embed the conflict resolution into the data structure itself, so replicas converge by construction. Where Raft and Paxos pay latency to get linearizability, CRDTs pay metadata and accept weaker ordering to get availability with zero coordination. This is a genuinely different regime from consensus.

Theory#

Strong Eventual Consistency (SEC)#

Plain eventual consistency promises only that replicas will "eventually" converge. It says nothing about what happens when two replicas have received the same set of updates but in different orders. Application developers must write custom conflict resolution, which is error-prone.

SEC closes that gap with a safety guarantee: any two replicas that have delivered the same set of updates are in identical states^[1:1]. No "eventually" qualifier, no application-level merge code. The data type handles it.

Shapiro, Preguica, Baquero, and Zawirski formalized SEC in their 2011 INRIA study^[1:2] and showed two sufficient conditions:

1. State-based (CvRDT): replicas exchange full state and merge using a commutative, associative, idempotent join that forms a join-semilattice. Every update moves the state monotonically upward in the lattice.
2. Op-based (CmRDT): replicas broadcast operations via reliable causal delivery, and concurrent operations commute.

Both forms achieve SEC without consensus. Replicas remain available under arbitrary network partitions, meeting AP in the CAP sense^[4].

State-based CRDTs (CvRDTs)#

A CvRDT replica holds a lattice value S. Updates move S upward. Merge takes the least upper bound (LUB) of two states. Because the merge is commutative, associative, and idempotent, replicas converge regardless of message order, duplication, or how many times they merge.

G-Counter (grow-only counter): a vector of per-replica monotonic integers. Each replica increments only its own slot. The value is the sum of all slots. Merge takes the elementwise max^[1:3].

# G-Counter: the canonical state-based CRDT
state = {}  # map<replica_id, int>, all start at 0

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

def increment(s, me):
    s[me] = s.get(me, 0) + 1

def merge(a, b):
    return {r: max(a.get(r, 0), b.get(r, 0))
            for r in set(a) | set(b)}

Three replicas increment independently; merge takes the elementwise max, and the global value is the sum of the merged vector.

PN-Counter: a pair (P, N) of G-Counters. Increments go to P, decrements go to N. Value = sum(P) - sum(N). Merge applies G-Counter merge to each half independently^[1:4].

G-Set: grow-only set. Merge = union. You can add but never remove.

2P-Set: adds plus a tombstone set for removes. Once removed, an element cannot be re-added. This limitation motivates the OR-Set.

OR-Set (Observed-Remove Set): each add tags the element with a unique identifier. A remove only removes the tags the remover has observed. A concurrent add on another replica uses a fresh tag and survives^[1:5].

Trade-offs of state-based CRDTs:

• Pro: works over any transport (gossip, TCP, UDP with retries). Duplicates and reordering are harmless.
• Con: shipping full state is expensive as replicas grow. Delta-state CRDTs (Almeida, Shoker, Baquero 2018) fix this by shipping only incremental deltas that still form a semilattice^[5].

Op-based CRDTs (CmRDTs)#

Instead of shipping state, CmRDTs broadcast operations. The middleware delivers operations in causal order, at least once, and exactly once per replica. Because concurrent operations commute, the delivery order for non-causally-ordered pairs does not matter^[1:6].

State-based ships whole states over any transport; op-based ships individual operations over a causal-broadcast channel.

Op-based OR-Set: each add(e) generates a unique tag. remove(e) broadcasts only the tags the remover observed. A concurrent add with a fresh tag is never erased.

A concurrent add uses a fresh tag, so a prior remove cannot erase it; this is why OR-Sets converge without data loss.

Trade-offs of op-based CRDTs:

• Pro: low bandwidth per update (tens of bytes vs full state). Fine-grained edit history enables undo and time travel^[6][7].
• Con: requires reliable causal broadcast. In practice that means a backplane (Redis Streams, Kafka, a custom WebSocket fanout, or a peer-to-peer protocol).

Text and rich collaboration#

Collaborative text editing is the hardest CRDT problem. Each character needs a stable identifier so concurrent inserts at the same position converge. The field evolved through multiple generations:

• WOOT (Oster et al., 2006): the first text CRDT. Characters have predecessor/successor pointers^[8].
• Logoot (Weiss, Urso, Molli, 2009): variable-length position vectors. Suffers interleaving anomalies on concurrent prepends^[9].
• RGA (Roh et al., 2011): a causal tree where each insert references an existing character ID. Automerge uses RGA^[10].
• YATA (Jahns, 2016): the algorithm behind Yjs. Similar to RGA with a different tie-break for concurrent inserts. Jahns discovered that a flat-list insertion-sort implementation is vastly faster than tree-based approaches^[10:1][6:1].
• Peritext (Litt, Lim, Kleppmann, van Hardenberg, 2022): a rich-text CRDT that anchors formatting spans (bold, italic, links) to character operation IDs rather than unstable indexes, so concurrent formatting and edits merge with intent preservation^[11].

The performance gap between implementations is staggering. On the B4 benchmark (259,778 operations, 104,852 final characters)^[12]:

Costs and pitfalls of CRDTs#

CRDTs are not free. The metadata cost is the primary engineering challenge:

Tombstones and identifiers. OR-Sets, RGA, and text CRDTs keep identifiers (and often full operations) forever so that late-arriving removes know what they target. Automerge 0.14 used ~4 KB peak RAM per keystroke on the B4 trace^[7:2]. Automerge 2.0 reduced on-disk encoding size by 1,135x through columnar compression^[7:3]. Automerge 3.0 further cut runtime memory by over 10x in general and dramatically more in some cases (pasting Moby Dick: 1.3 MB vs 700 MB in 2.0, ~538x)^[13].

Garbage collection. You can only discard metadata for operations that are "causally stable," meaning all replicas have seen them. Determining causal stability requires knowing which replicas exist and what they have received. This is non-trivial in open-membership systems.

LWW-Register: the CRDT that eats your data. LWW attaches a timestamp to every write and merge keeps the greatest. Two concurrent writes? One is silently discarded. Clock skew can reverse the "real" order. Kleppmann's local-first essay warns that LWW silently loses data under concurrent writes^[4:1].

Delta-state CRDTs (Almeida, Shoker, Baquero 2018) offer a middle ground: they transmit incremental deltas that are still in the semilattice, giving op-like bandwidth with state-like transport tolerance^[5:1]. Akka Distributed Data uses this approach in production.

Real-World Example#

Yjs: the CRDT engine behind AFFiNE, Evernote, GitBook, and Tiptap.

Yjs is a JavaScript CRDT library that exceeds 4,000,000 npm downloads per week as of May 2026^[2:1]. It powers collaborative editing in AFFiNE, Evernote, GitBook, Tiptap, Huly, Cargo, JupyterLab, Proton Docs, and dozens of other products^[2:2][14]. (Notion, by contrast, uses its own custom block-level conflict resolution system, not Yjs.)

The architecture is deceptively simple. Yjs stores the document as a flat list of items. Each item is (content, id=[clientID, clock], originLeft, originRight, deleted?). On insert, Yjs finds the origin item, scans forward using the YATA conflict rule, and splices the new item in^[10:3].

The trick that makes it fast: run-length encoding. A paste of 1,000 characters becomes one item with length 1,000, not 1,000 items. An in-memory cache of the last edit index makes the common case ("user keeps typing") O(1). Kevin Jahns "wrote and rewrote parts of Yjs 12 times" to hit these performance numbers^[10:4].

Yjs provides shared types (Y.Map, Y.Array, Y.Text, Y.XmlFragment) and is network-agnostic: connection providers (y-websocket, y-webrtc, y-redis) handle sync without a mandatory server. Delete operations are stored as a compressed bitmap, not per-item tombstones, keeping the "insert then delete same string" document size at 38 bytes^[12:1].

The result: on the B4 academic-paper editing trace, Yjs encodes 104,852 final characters in 159,929 bytes, roughly 1.52 bytes per character^[12:2]. The entire library is ~20 KB gzipped. Compare this to Automerge 0.14, whose on-disk encoding for the same document was 146,406,415 bytes (~146 MB), a ~915x size ratio that motivated Automerge's complete rewrite^[7:4].

Yjs clients sync via pluggable providers; the server holds document state for persistence and late-joining clients, but the CRDT merge happens on every replica independently.

Trade-offs#

Implementation style#

Picking a CRDT for your data#

Common Pitfalls#

Exercise#

Design the state layer for a collaborative to-do app that works offline. Users can add, remove, and re-add tasks, mark them done, and edit task text. All changes must merge cleanly when replicas reconnect. Pick CRDTs for each field (title, done flag, assignees, order) and describe the sync protocol.

Key Takeaways#

• CRDTs give strong eventual consistency without coordination. This is a genuinely different regime from consensus protocols.
• State-based CRDTs (CvRDTs) are easier to ship because they need no causal broadcast. Op-based CRDTs (CmRDTs) are bandwidth-efficient but demand more infrastructure.
• The G-Counter (vector of per-replica counters, merge = elementwise max) is the mental model for all CRDTs: find a join-semilattice.
• Do not invent your own text CRDT. Use Yjs (performance-optimized, 20 KB gzipped) or Automerge (history-preserving, Git-like branching).
• LWW-Register is the CRDT people reach for by accident. It is the one that silently loses data under concurrent writes.
• Tombstones and metadata grow without bound unless you plan for garbage collection under causal stability.
• Production CRDTs (Redis Enterprise Active-Active, Yjs, Automerge) hide CRDT semantics behind familiar APIs. The math is invisible to application developers.

Further Reading#

• A comprehensive study of Convergent and Commutative Replicated Data Types - Shapiro et al. (2011). The foundational paper; read sections 1 to 4 for SEC and the CvRDT/CmRDT duality.
• Local-first software: you own your data, in spite of the cloud - Kleppmann et al. (2019). The manifesto that positions CRDTs as the foundation for post-cloud collaboration.
• 5000x faster CRDTs: An Adventure in Optimization - Seph Gentle (2021). Performance deep dive showing why implementation beats algorithm; the B4 benchmark explained.
• How Figma's multiplayer technology works - Evan Wallace (2019). The best "we looked at CRDTs and built something simpler" writeup; clarifies when you do and do not need full CRDTs.
• Peritext: A CRDT for Rich-Text Collaboration - Litt et al. (2022). State of the art in rich-text CRDTs; explains why formatting merge is harder than plain-text merge.
• Introducing Automerge 2.0 - Ink & Switch (2023). The 275x performance improvement journey from pure JS to Rust + WASM columnar format.
• Yjs documentation and CRDT benchmarks - Kevin Jahns. The reference benchmark suite for comparing CRDT libraries head-to-head.
• Data types for Active-Active databases - Redis Enterprise docs. Production CRDT semantics for counters, sets, sorted sets, and JSON behind familiar Redis commands.

Flashcards#

References#