CONCEPT Cited by 1 source

CRDT (conflict-free replicated data type)

What it is

A Conflict-free Replicated Data Type is a data structure whose replicas can be updated concurrently and without coordination and will still converge to the same value deterministically once all updates propagate. Formally: the merge operation is associative, commutative, and idempotent.

Two flavours:

• State-based (CvRDT) — each replica periodically sends its full state; merge is a join.
• Operation-based (CmRDT) — each replica broadcasts the operations; delivery order need not be causal for all operations, but equivalent state requires the broadcast channel to respect causality where needed.

Why CRDTs matter for state distribution

CRDTs let you build eventually-consistent distributed systems without needing distributed consensus for every write. You trade strong linearizability for uncoordinated write throughput and simple failure semantics: a replica that hasn't heard an update yet still returns a valid (just slightly stale) answer.

Critical in high-write-rate, globally-distributed shapes where consensus is either too slow (WAN RTT) or overkill (writes rarely conflict in practice because each node owns a disjoint slice of the keyspace).

Canonical wiki instance — cr-sqlite in Fly.io Corrosion

Fly.io's Corrosion uses cr-sqlite — a SQLite extension from vlcn-io — to make any marked SQLite table CRDT-managed. Row-level changes are logged to a crsql_changes table, gossiped across the cluster, and applied last-write-wins using logical timestamps (causal ordering, not wall-clock).

The design leans on an orchestration invariant: "workers own their own state, so updates from different workers almost never conflict." CRDTs handle the rare actual conflict deterministically; the common case is conflict-free by construction.

CRDT-family mechanics produce their own operational hazards though:

• Nullable-column backfill — adding a nullable column to a large CRDT table makes cr-sqlite backfill every row at once; see concepts/nullable-column-backfill-amplification.
• Whole-object republish is safer than delta republish — CRDTs filter no-op changes at the merge layer, so broadcasting the whole object hides deltas without hurting convergence. See patterns/eliminate-partial-updates.

Trade-offs

• ✅ Uncoordinated writes; WAN-scale-friendly; simple local reads.
• ❌ No unique constraints, no referential integrity, no global transactions, no linearizability.
• ❌ Ordering-sensitive operations (monotonically-increasing counters, uniqueness) need extra machinery.
• ❌ Schema changes on CRDT tables need careful staging (the nullable-column lesson).

Seen in

• sources/2025-10-22-flyio-corrosion — canonical primary source. CRDT-SQLite is one of the three shape-defining axes of Corrosion (alongside SWIM membership + QUIC reconciliation transport).

Related

• systems/cr-sqlite — the CRDT extension Corrosion uses.
• systems/corrosion-swim — canonical production deployment.
• concepts/last-write-wins — the conflict-resolution rule.
• concepts/gossip-protocol — the propagation mechanism.
• concepts/no-distributed-consensus — the design choice CRDTs enable.
• concepts/conflict-free-replicated-data-type — existing wiki companion page.