Engineering Atlas › System Design Fundamentals

Conflict-free replicated data types (CRDTs)

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

State-based CRDTs

Each replica holds a state, and a merge function computes the least upper bound of two states. Replicas periodically ship full state (or deltas) to each other. Because merge is idempotent and commutative, gossip, retries, and reordering are harmless. The classic G-Counter stores a map from replica ID to count; a replica increments only its own entry; merge takes the per-entry max; the value is the sum. A PN-Counter is two G-Counters, one for increments and one for decrements. Shapiro and colleagues' catalogue defines these and proves each one converges (Shapiro et al.).

Operation-based CRDTs

Replicas broadcast operations instead of state. Operations that may run concurrently must commute, and the delivery layer must deliver each operation exactly once and usually in causal order. Messages are small, but the transport is more demanding. Delta-state CRDTs sit in between: a delta mutator returns a small state fragment that merges like a full state, so they get small messages and keep the forgiving transport of state-based designs (Almeida, Shoker and Baquero).

Registers and sets

A LWW-Register keeps the value with the highest (timestamp, replicaId). It is simple and lossy: concurrent writes silently drop all but one. A multi-value register keeps all concurrent values, tracked with version vectors, and lets the application resolve them, as Riak's siblings did.

Sets need a policy for concurrent add and remove of the same element. An OR-Set (observed-remove) tags every add with a unique ID. A remove deletes only the tags it has observed. A concurrent add carries a tag the remove never saw, so the element survives: add wins.

Sequences for collaborative text

Text editing needs a list CRDT such as RGA, YATA (used by Yjs), or Fugue, which was designed so that two users typing at the same spot do not get their passages interleaved (Weidner and Kleppmann). Each character gets a unique, ordered identifier, for example (lamportClock, replicaId), and insertions reference the identifier of the character to their left. Deletes leave tombstones so later inserts can still find their anchor. Modern implementations compress runs of characters typed in sequence, which cuts metadata from dozens of bytes per character to a few bytes per run.

Why it converges

For state-based CRDTs, states form a join-semilattice: there is a partial order, and merge returns the smallest state at least as large as both inputs. Every update moves the state upward. Any two replicas that have received the same set of updates have the same least upper bound, regardless of path.

Down the stack

Layer 1The contract

CRDTs promise strong eventual consistency: any two replicas that have received the same set of updates are in the same state, in any delivery order, with duplicates, and without any coordination. Every replica accepts writes locally while partitioned, so local latency is a memory write. What you do not get is just as precise. There is no global invariant across replicas (two replicas can each spend the last unit of a budget), no guarantee that the merged result matches what either user intended, and no bound on staleness beyond "when the updates arrive". Operation-based CRDTs additionally require the transport to deliver every operation exactly once in causal order; state-based ones only need eventual delivery.

Layer 2The mechanism

Yjs, one of the most widely used text CRDTs, stores a document as a linked list of items. Each item has an ID (clientID, clock), the IDs of its left and right neighbours at insertion time (origin and rightOrigin), and its content. The YATA rules use those origins to place concurrent inserts deterministically. Consecutive characters typed by one client merge into a single item, so a paragraph typed in one go is one struct. A replica summarises what it has as a state vector, a map from clientID to the next expected clock. Sync is two steps: send your state vector, receive exactly the items you lack. Deletions are kept as a compact delete set of (clientID, clock, length) ranges, and deleted content can be garbage collected while the item's ID and length stay as an anchor (Yjs internals). Deletes usually come in runs, so the delete set stays tiny: for a benchmark trace with 182,000 inserts and 77,000 deleted characters it is about 4.5 KB.

Automerge takes a different shape: every change is hashed and lists the hashes of the changes it depends on, forming a DAG like a git history. Since version 2 the core is written in Rust, and documents are saved in a columnar binary format where each property of the operations (actor, counter, insert position, value) is a separate column compressed with run-length and delta encoding, and each change is identified by the SHA-256 hash of its bytes (Automerge binary format). Automerge 3.0 (July 2025) keeps that compressed form in memory too instead of expanding it on load: pasting Moby Dick into a document took about 700 MB in Automerge 2 and about 1.3 MB in Automerge 3 (Automerge 3.0).

On the server side, Redis Software's Active-Active databases (formerly called CRDB) accept writes in every participating cluster and resolve conflicts only with CRDT types, using vector clocks for strong eventual consistency (Redis docs). Riak shipped counters, sets, maps, registers and flags as built-in types; since Basho went into receivership in 2017 Riak has been maintained by its open-source community (Wikipedia), so weigh that before adopting it.

Layer 3The machine

Metadata cost is the engineering problem. A naive design that gives each character a JavaScript object with an ID, two origin pointers and a deleted flag spends well over 50 bytes of heap per character before counting the character itself, and a linked list of objects scattered across the heap misses CPU cache on nearly every step, at roughly 100 ns per miss to DRAM. Run-length merging fixes both: one item for a run of typed text, and integer fields encoded as variable-length integers that take 1 to 3 bytes for typical values. Real editing traces compress to close to the size of the text itself: a trace of about 260,000 operations whose final text is 107,121 bytes saves as 129,062 bytes in Automerge 2.0, full history included (Automerge 2.0).

On disk the usual pattern is an append-only log of small binary updates, often a few dozen bytes each, written as users type, then periodically merged into one compacted snapshot so load time stays bounded. Tombstones and per-client entries in state vectors never fully disappear, so a long-lived document with thousands of short-lived client IDs grows its version metadata even when the visible text does not.

Why it's built this way

  1. Coordination costs a round trip that offline and high-latency clients cannot pay, so every replica must accept writes alone and fix conflicts by math, not by asking.
  2. Merge must give the same result regardless of order or duplication, so it is defined as a join over a semilattice: commutative, associative and idempotent.
  3. That requires never forgetting what was seen, so IDs, tombstones and version vectors accumulate.
  4. Accumulated metadata would dwarf the data, so implementations compress runs, encode integers compactly, and garbage collect deleted content while keeping its anchors.

Diagram

flowchart LR
    A0["A: {A:0, B:0}"] --> A1["A increments: {A:2, B:0}"]
    B0["B: {A:0, B:0}"] --> B1["B increments: {A:0, B:3}"]
    A1 --> M1["A merges B: {A:2, B:3}"]
    B1 --> M1
    A1 --> M2["B merges A: {A:2, B:3}"]
    B1 --> M2
    M1 --> V["Both read 5"]
    M2 --> V

Worked example

A shopping cart service runs in 3 regions with active-active writes and 100 ms cross-region latency. Each cart is an OR-Map from product ID to a PN-Counter for quantity.

A user adds 2 mugs on a phone routed to region A. At the same moment their laptop, served by region B, removes the mug line that it saw from yesterday. After replication, A's add carries a fresh tag that B's remove did not observe, so the mug line survives with quantity 2. With last-writer-wins instead, whichever request had the later timestamp would win, and a 50 ms clock skew could decide it. The OR-Set result matches what users expect from a cart.

Metadata cost: each add tag is about 16 bytes (replica ID plus counter). A cart with 20 lines and a history of 200 adds and removes holds tags only for live adds, about 320 bytes, if removes discard observed tags. Tombstones are where costs grow, which is why systems either garbage-collect them once all replicas have acknowledged (requiring known membership) or use designs that avoid them.

For a collaborative document of 100,000 characters, a naive sequence CRDT with 32 bytes per character costs 3.2 MB of metadata. Run-length and columnar encoding in Yjs or Automerge bring the saved form close to the text size, and Automerge 3 keeps it compact in memory as well.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
State-based CRDTTolerates loss, duplication, reorderShipping large statesGossip replication between servers
Op-based CRDTSmall messagesNeeds exactly-once causal deliveryReliable ordered pipe already exists
LWW-RegisterTiny, simpleSilently loses concurrent writesValues where any recent write is fine
Multi-value registerNothing lostApp must resolve siblingsData where losing writes is unacceptable
Consensus or single leaderArbitrary invariants, exact semanticsCoordination latency, no offline writesBalances, uniqueness, inventory limits

Pitfalls in production

Leadership lens

Check yourself

  1. Why must a state-based merge be idempotent?

    Show answer

    Gossip and retries deliver the same state more than once; idempotence ensures re-merging changes nothing.

  2. In an OR-Set, why does a concurrent add survive a remove?

    Show answer

    The remove deletes only the tags it observed, and the concurrent add created a new tag the remover never saw.

  3. Why can a PN-Counter not enforce "never below zero"?

    Show answer

    Two replicas can each decrement the last unit concurrently without coordination; the invariant needs agreement before the decrement.

  4. What is the main extra requirement of operation-based CRDTs?

    Show answer

    A delivery layer that delivers every operation exactly once and in causal order.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →