CRDTs in Production, in depth: choosing data types, syncing with state vectors, storing and compacting history, evolving schemas and securing merges

The production architecture

Nearly every deployed CRDT system has the same shape. Each client holds a full replica of the documents it works on, persisted locally so it survives restarts and works offline. A sync service authenticates clients, relays updates between replicas of the same document, and persists them. Storage holds an append-only log of updates per document plus periodic snapshots that fold the log into a compact state. Read models, such as a search index or a relational projection for reporting, are derived from the snapshots, because querying the internal CRDT structure directly is rarely practical.

The server is not an authority in the consensus sense; it does not order operations or reject conflicts. It is a durable, always-online replica with extra responsibilities: access control, validation, fan-out and compaction. That framing matters because it tells you which failures are safe. If the server loses its in-memory state, any connected replica can resend what it has. If it loses its disk, clients can often repopulate it. If it accepts a hostile update, every replica merges it faithfully, and there is no conflict to notice.

Choose the data type by its surprises

Each CRDT resolves concurrency in one fixed way, and that resolution is a product decision disguised as a data structure. Before choosing, write down what the user should see when two people change the same thing at the same time.

Two rules follow. First, invariants that span the whole system, such as a unique username, a balance that never goes negative, or a seat sold once, cannot be guaranteed by a CRDT alone; route those through a coordinated path and keep CRDTs for the collaborative state around them. Second, LWW is almost never the right default for user content. If you use it, record the losing value somewhere visible, or use hybrid logical clocks, explained in hybrid logical clocks, so wall-clock skew does not decide the winner.

Libraries: do not write your own sequence CRDT

Counters, registers and sets are short enough to implement and test yourself. Sequence CRDTs for text and lists are not: correct, fast implementations took years of research and engineering, and the naive ones have quadratic memory or subtle interleaving bugs. Two open-source libraries dominate application use. Yjs is a JavaScript library with ports and bindings to other languages, a compact binary update format, and editor bindings for common rich-text editors. Automerge has a Rust core with JavaScript and other bindings, keeps the full change history of a document with a compressed storage format, and has a companion repository layer for networking and storage. Both expose maps, lists and text as shared types.

Choose on history semantics first and performance second. Automerge's model treats full history as a feature, which suits audit trails and version browsing. Yjs can garbage-collect the content of deleted items while keeping the structural metadata needed for merging, which keeps documents smaller when history is not needed. Benchmark with your own document shapes and edit traces, not published figures, because results depend heavily on document size and edit patterns. With a central server and little offline use, also consider operational transformation, which is simpler to secure because the server orders every operation.

Syncing with state vectors

Replicas do not ship full documents on every connection. Each replica summarises what it has seen as a state vector: for every client identifier, the highest operation clock it has integrated. This is the same idea as a version vector, covered in vector clocks. On connect, each side sends its state vector, and the other replies with only the updates the first side is missing. After that, both sides stream new updates as they happen. In Yjs the exchange uses real library functions:

import * as Y from 'yjs'

// Replica A wants to catch up with replica B.
const svA = Y.encodeStateVector(docA)           // what A already has
const diff = Y.encodeStateAsUpdate(docB, svA)   // on B: only what A is missing
Y.applyUpdate(docA, diff)                       // on A: idempotent, order-free

// Live updates after the handshake.
docA.on('update', (update, origin) => {
  if (origin !== 'remote') transport.send(update)
})
transport.onMessage(update => Y.applyUpdate(docA, update, 'remote'))

Because applying an update is idempotent and commutative, the transport can be at-least-once and unordered. Updates that arrive before their causal dependencies are held as pending by the library until the missing pieces arrive, which is why a replica that only ever receives relayed live updates can stall: a lost message is never re-requested unless the handshake runs again. Run the state-vector handshake on every reconnect and periodically on long-lived connections, as a cheap form of the anti-entropy described in anti-entropy.

Storing documents on the server

The simplest durable design appends every received update to a per-document log and, when the log grows past a threshold, merges it into a snapshot. Merging updates is itself a CRDT operation, so compaction never needs to understand document content. The write path must be idempotent, since clients resend; content-hash each update or rely on the library's own deduplication.

# Pseudocode for a per-document store. Y_merge stands for Y.mergeUpdates,
# called through a sidecar or a language port of the library.
def on_update(doc_id, update_bytes, principal):
    authorize(principal, doc_id, "write")
    validate(doc_id, update_bytes)                    # size limits, decodable, allowed paths
    log.append(doc_id, update_bytes)                  # durable before acknowledging
    broadcast(doc_id, update_bytes, exclude=principal)
    if log.length(doc_id) > 500 or log.bytes(doc_id) > 2_000_000:
        compact(doc_id)

def compact(doc_id):
    with doc_lock(doc_id):                            # one compactor per document
        snap, upto = snapshots.latest(doc_id)
        tail = log.read_after(doc_id, upto)
        merged = Y_merge([snap] + [u.bytes for u in tail])
        snapshots.write(doc_id, merged, upto=tail[-1].seq)
        log.truncate_through(doc_id, tail[-1].seq)    # only after the snapshot is durable

def load(doc_id):
    snap, upto = snapshots.latest(doc_id)
    return Y_merge([snap] + [u.bytes for u in log.read_after(doc_id, upto)])

Keep old snapshots for a retention window; they are your backup and debugging tool. Store derived read models separately and rebuild them from snapshots, never the other way round.

Tombstones and metadata growth

A deleted element in a sequence CRDT cannot simply vanish. A concurrent insert elsewhere may reference it as its position, so the structure keeps an identifier for it, a tombstone, even after the text is gone. Every element also carries identity metadata such as client identifier and clock. In a document that is edited heavily for years, metadata can outgrow content.

An illustrative example, not a benchmark: a shared runbook of 20,000 visible characters that has seen 2 million characters typed and deleted over its life still carries structural records for those deletions. Libraries encode runs of consecutive operations compactly, so the real cost depends on edit patterns, but the direction is fixed: size tracks history, not visible content. Measure it for your own documents by recording snapshot bytes against visible length over time.

Removing tombstones safely requires causal stability: knowing that every replica that might ever send an update has already seen the deletion. In an open system with offline phones, you never know that for certain. The practical escape hatch is an epoch reset. The server creates a fresh document from the current visible state, marks the old document as closed at a recorded state vector, and clients switch at their next sync. A client that returns with edits against the old epoch has them replayed as a best-effort merge into the new one, or saved as a conflict copy for the user to review. Plan epochs from the start.

Schema evolution on replicas you do not control

Documents live on devices that may run an old app version for months. A CRDT merges structure, not meaning, so a field renamed on new clients and still written under the old name by old clients produces two fields that both merge happily. Three rules keep this sane. Make changes additive: add new keys, never repurpose old ones. Put a schema version in the document and have old clients open documents with a newer major version read-only. When a migration must transform data, make it deterministic and idempotent, keyed by a migration identifier stored in the document, so two clients that migrate concurrently produce the same operations rather than duplicate content.

Authorization: every merge is trusted

A CRDT has no concept of a forbidden write. Whatever reaches a replica is merged. Security therefore lives entirely in what the sync service accepts. At minimum, enforce per-document read and write permissions at connection time and on every update, cap update sizes, and reject updates for read-only users rather than relaying them. Finer rules, such as only editing your own comments, require decoding each update and checking which parts of the document it touches, which the library's binary format makes possible but not trivial. A malicious client can also forge another client's identifier or reuse clocks, corrupting causality for everyone; bind client identifiers to authenticated sessions on the server. If different users need provably different views of the same data, split it into separate documents with separate permissions instead of filtering one.

Test convergence with random delivery orders

Unit tests with hand-picked interleavings miss the bugs that matter. A property-based test generates random operations on several replicas, delivers them in random orders with duplicates, and asserts that all replicas end in the same state. The self-contained example below tests an observed-remove set; the same harness wraps a library document by replacing the three methods.

import itertools, random, uuid

class ORSet:
    def __init__(self):
        self.adds, self.removes = set(), set()          # (element, tag) pairs
    def add(self, e):
        op = ("add", e, uuid.uuid4().hex)
        self.apply(op); return op
    def remove(self, e):
        tags = {t for (x, t) in self.adds if x == e}
        op = ("rem", e, frozenset(tags))
        self.apply(op); return op
    def apply(self, op):                                  # idempotent
        kind, e, tag = op
        if kind == "add": self.adds.add((e, tag))
        else: self.removes |= {(e, t) for t in tag}
    def value(self):
        return {e for (e, t) in self.adds - self.removes}

def trial(n_replicas=3, n_ops=40, seed=None):
    rng = random.Random(seed)
    reps = [ORSet() for _ in range(n_replicas)]
    ops = []
    for _ in range(n_ops):
        r = rng.choice(reps)
        e = rng.choice("abcde")
        ops.append(r.add(e) if rng.random() < 0.6 else r.remove(e))
    for r in reps:                                        # shuffled, duplicated delivery
        delivery = ops + rng.sample(ops, len(ops) // 4)
        rng.shuffle(delivery)
        for op in delivery:
            r.apply(op)
    values = [frozenset(r.value()) for r in reps]
    assert len(set(values)) == 1, (seed, values)

for seed in range(5000):
    trial(seed=seed)
print("converged in all trials")

Shuffling is safe for this set because removes carry the exact tags they observed. A sequence CRDT needs causal delivery or the library's pending buffer, and the harness should also kill and restore replicas from persisted bytes mid-run, which catches encoding bugs that in-memory tests never see. Run these tests in continuous integration on every library upgrade.

Failure modes

Operationally, track per document: update rate, log length since the last snapshot, snapshot bytes against visible content size, and the age of the oldest connected client's state vector. Those four metrics surface nearly every problem in the table before users report it. Causal consistency explains why delivery order matters for the operation-based variants.

What to do next

1. For each piece of shared state, write the behaviour users should see under concurrent edits, then pick the type that delivers it.
2. Move global invariants such as uniqueness and non-negative balances out of the CRDT into a coordinated path.
3. Adopt a maintained library for text and lists; benchmark it on your own recorded edit traces.
4. Implement the state-vector handshake on every reconnect and on a timer.
5. Build the append-log plus snapshot store with idempotent writes and a single compactor per document.
6. Authorise and size-limit every update on the server; bind client identifiers to sessions.
7. Add a schema version, additive-only changes and deterministic migrations before the first release.
8. Design epoch resets now and measure metadata growth monthly.
9. Run randomised convergence tests with persistence round-trips in CI.