System Design Cases
CRDTs — Conflict-Free Replicated Data Types
CRDTs (Conflict-Free Replicated Data Types) concept page. Three replicas R1/R2/R3 with three clients hitting nearest replica (no central coordinator, AP system). Anti-entropy gossip mesh between all replicas. Four scenarios: G-Counter element-wise max merge, OR-Set add-wins with tagged elements, RGA concurrent text insert with deterministic tie-break, and LWW pitfall showing how naive last-write-wins loses updates under clock skew. ADR on CRDTs vs Operational Transform.
CRDTs: convergence requires algebra and delivery assumptions
A state-based CRDT uses a join-semilattice, inflationary local updates, and least-upper-bound merge. Associative, commutative, idempotent join tolerates state reordering and duplication. A delta-state CRDT sends joinable deltas but keeps the same algebra and anti-entropy obligations.
An operation-based CRDT has a different contract: concurrent effectors commute and non-commuting dependencies receive causal delivery. Unique dots and duplicate handling remain explicit. Replica convergence does not prove application invariants such as unique names or nonnegative stock.
Prerequisites and model
- The payload, causal metadata, merge/effect function, and delivery assumptions are one protocol.
- Replica and element identities remain unique across restart and garbage collection.
- Application invariants are analyzed separately from convergence.
Correctness claims and invariants
- CRDT-C1. State-based convergence requires a join-semilattice, inflationary updates, and repeated LUB merge.
- CRDT-C2. Associative, commutative, idempotent join tolerates reordered and duplicate state delivery.
- CRDT-C3. Operation-based convergence requires concurrent effectors to commute and stated causal/reliability delivery.
- CRDT-C4. Observed-remove sets need unique add tags and an explicit add-wins or remove-wins rule.
- CRDT-C5. Tombstones or dots are compacted only after causal stability excludes relevant old operations.
- CRDT-C6. Delta CRDTs retain the lattice contract while reducing transfer granularity.
- CRDT-C7. Some invariants are not coordination-free even when all replicas converge.
What the scenarios prove
- State grow-only counter (
state-gcounter): Replica components grow and join by componentwise maximum.
- Duplicate state (
duplicate-state): Idempotent join makes repeated state harmless.
- PN-counter invariant boundary (
pn-counter): Counter convergence does not preserve nonnegative inventory.
- Observed-remove add-wins set (
or-set-add-wins): A remove deletes observed tags; an unseen concurrent add survives.
- Operation causal delivery (
operation-causal-delivery): A dependent non-commuting operation waits for its predecessor.
- Duplicate operation dot (
duplicate-operation): At-least-once delivery cannot apply one dot twice.
- Causally stable tombstone GC (
tombstone-gc): Compaction waits until old operations cannot reappear.
- Global invariant coordination (
invariant-coordination): Two locally valid reservations can jointly oversell.
Failure, concurrency, and retry traps
- An ad-hoc JSON merge is not a CRDT without the required algebra.
- A PN-counter may converge to negative inventory.
- Operation redelivery needs a unique dot and idempotent effect or dedupe.
- Deleting tombstones by age can resurrect removed elements when an old replica reconnects.
Boundaries and non-guarantees
- Convergence is not consensus, linearizability, or application correctness.
- Add-wins and remove-wins are product semantics, not universal answers.
- State growth, causal metadata, and anti-entropy bandwidth are design costs.