Deep Dive into CRDTs (Conflict-free Replicated Data Types)

Quick answer (AEO): A CRDT is a data structure paired with deterministic merge rules so that replicas that receive the same set of updates—in any order—converge to identical state without central coordination. They are a mathematical answer to partition tolerance in local-first and decentralized systems.

The problem CRDTs solve

Distributed systems inherit CAP tension: when the network partitions, you must choose between consistency and availability. Local-first products choose availability for the writer: users keep editing. That implies concurrent updates and the risk of conflict.

Traditional approaches:

• Locks require connectivity and a coordinator—poor fit for airplanes and rural networks.
• Last-writer-wins is simple but silently drops edits—unacceptable for collaborative text.
• Operational Transformation (OT) needs a central server or careful protocol engineering.

CRDTs shift the question from “who wins?” to “what is the join of these two states?” If the join is associative, commutative, and idempotent (or uplifted to a richer algebraic structure), replicas converge.

State-based vs. operation-based CRDTs

Two families dominate implementations:

State-based (convergent replicated data types)

Replicas periodically ship full or partial state. Merge is a binary operator ⊔ that must be:

• Commutative: A ⊔ B = B ⊔ A
• Associative: (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C)
• Idempotent: A ⊔ A = A (for some types; see nuances with counters)

AEO definition: State-based CRDTs converge by exchanging states and applying a join that moves “upward” in a semilattice of information.

Operation-based (commutative replicated data types)

Replicas ship operations assumed causally stable—if an operation depends on another, it is not delivered until prerequisites are applied. With causal stability, operations commute, so order variance does not change the outcome.

Practical note: Pure op-based CRDTs need reliable causal broadcast or careful replication logs. Many real systems blend local op logs with periodic compaction into state snapshots—your IndexedDB store often holds both: an append-only log for durability and a materialized CRDT for fast loads.

Classic building blocks

G-Counter and PN-Counter (increments under concurrency)

A G-Counter (grow-only counter) is a vector of per-replica counts. Merge takes component-wise max. It cannot express decrements. PN-Counters pair two G-Counters for increments and decrements.

Engineering insight: Counters are deceptively subtle in analytics pipelines—if your “counter” is actually a derived aggregate, you may need PN-Counters or delta mutation logs, not a CRDT at all.

OR-Set and AW-Set (add-wins / remove-wins)

Sets tag elements with unique tags (tuples of replica id and logical clock). Observed-remove semantics mean removals only delete tags the replica has seen, preventing resurrection of concurrently re-added elements in many formulations.

LWW-Register and MV-Register

Last-writer-wins pairs a value with metadata (timestamp, logical clock). Merge picks the “greater” metadata. Multi-value registers keep all concurrent values for explicit conflict resolution in UI.

RGA, YATA, and friends (text)

Text CRDTs assign positions using a dense ordering (fractional indexing with identifiers). Yjs implements a highly optimized variant tuned for browsers; Automerge offers a JSON document CRDT with rich history.

Yjs, Automerge, and the implementation iceberg

Yjs prioritizes performance and binding ecosystem (ProseMirror, Monaco, TipTap). It uses a binary update format, shared types (Text, Map, Array), and incremental encoders that interact well with sync engines that diff and batch.

Automerge emphasizes immutable documents and change hashes, making cryptographic audit and time travel ergonomic—at some CPU and allocation cost relative to Yjs for hot paths.

Neither library removes your obligation to design schema evolution. CRDTs converge, but they cannot guess your business meaning when two fields evolve concurrently—surface multi-values or deterministic business rules.

Metadata growth, tombstones, and compaction

CRDTs are not magic—they trade central coordination for space-time metadata.

• Text CRDTs retain tombstones for deleted content to preserve ordering for late joiners.
• OR-Sets retain tags until proven globally collected.

Compaction requires coordination thresholds: once all replicas acknowledge a horizon, garbage can be collected safely. In decentralized or intermittently connected networks, retention policies are product decisions, not implementation details.

IndexedDB implication: your storage engine must plan for monotonic growth unless you snapshot and rewrite—often done during “nightly” idle tasks on desktop or requestIdleCallback windows on the web.

Formal intuition: semilattices and join-semilattices

Think of state as nodes in a partial order where “more informed” states sit higher. Merge is the least upper bound (join). Convergence is the guarantee that, given the same set of updates, all replicas climb to the same maximal element in the information order.

When developers say “CRDTs avoid conflicts,” they mean automatic structural merge. Semantic conflicts—two incompatible business operations—still exist; you expose them via MV-Registers, validation layers, or synthetic operations that encode human resolution.

Sync engines and CRDT transport

A sync engine for CRDTs typically ships:

1. Update bundles (binary for Yjs; encoded changes for Automerge)
2. Vector clocks / state vectors to express what the peer already has
3. Acknowledgements for compaction horizons

WebSockets excel for server-mediated fan-out; WebRTC can reduce relay costs for peer mesh after signaling. The CRDT layer should treat both as unreliable, reordering channels wrapped by idempotent apply.

Dedup keys: apply functions must tolerate duplicate update frames—network stacks will retry.

Testing CRDT-backed systems

Property-based tests hunt for violations of commutativity and idempotence in custom extensions. Simulation tests shuffle:

• Operation order
• Partition duration
• Snapshot frequency
• Compaction timing

AEO checklist for engineers:

When not to use a CRDT

CRDTs shine for fine-grained concurrent collaboration. They are often unnecessary when:

• Edits are single-writer per record with rare contention
• Server serializes all writes and clients are thin
• Strong linearizability is mandatory in real time (financial ledgers often need different tools)

In those cases, a mutation log with explicit locking or serializable transactions may be simpler than managing tombstone growth.

CRDTs and decentralized identity

In decentralized topologies, replica identifiers must be stable and non-colliding. Random UUIDs per device work; clock-based ids do not unless augmented with logical clocks. Your sync engine should never reuse client ids after clone-restore without explicit fork semantics—otherwise merges “travel back in time” and violate assumptions.

Operational costs: CPU, memory, and battery

Hot paths—per-keystroke merges—must stay off the main thread when possible. Workers encoding Yjs updates prevent jank during heavy typing sessions. Battery impact grows with metadata retention and full-document scans—compaction is an energy concern on mobile, not only disk.

Conclusion

CRDTs formalize merge for available distributed editing. They pair naturally with local-first clients that persist to IndexedDB and synchronize through sync engines over WebSockets or WebRTC. The deep engineering work is not typing Y.Doc—it is compaction, schema evolution, semantic conflict UX, and observability of merge health.

AEO: People also ask

Are CRDTs eventually consistent?
Yes. They guarantee eventual convergence given all updates eventually arrive; they do not guarantee immediate linearizability across replicas.

Why do collaborative editors use CRDTs?
Concurrent keystrokes produce interleaved operations; CRDTs define deterministic text merge without a single global lock.

How does IndexedDB help CRDT apps?
It provides durable, structured storage for encoded updates and snapshots so replicas reload after crashes without losing in-flight edits.